writing 한국어로 읽기
훈련이 끝난 뒤 part 10 of 13

Filling the empty slot made the cache longer

guide / / 8 sections

Part nine sorted requests by length and took padding waste from 47.4% to 0.7%. Its closing paragraph noted that sorting is a one-shot arrangement: when requests finish at different times, the seat a short one vacates stays empty. Filling that seat immediately is continuous batching.

Two things went unmeasured there. What continuous batching actually buys, and how request lengths are distributed in the first place. Part nine used lengths uniform from 1 to 128, which I chose rather than measured.

Measure the lengths first

Ask the model. Draw a prompt of 8 to 64 characters from the validation split, let it continue, stop at a newline. Each request gets its own random seed so its length is the same whichever batch it lands in - otherwise changing the schedule would change what is being scheduled.

256 requests, stop at newline, cap 64
  mean 37.6   median 37   min 1   max 64   sd 21.3
  10th pct     8
  25th pct    19
  50th pct    37
  75th pct    64
  hit the cap    69

Not uniform. Half are under 37 characters and 27% run all the way to the cap - the bunched-at-the-short-end shape with a long tail that part nine guessed at.

Part nine’s handle does not turn here

Prompt length is known the moment a request arrives. Generation length is known only when it is over. The correlation between them is -0.076.

So sorting by prompt length removes none of the seat waste.

                        steps  row-steps   row occ   cache occ   mean cache
static, arrival           512     16,384     58.8%       61.7%         93.3
static, by prompt         512     16,384     58.8%       82.3%         70.0
static, by gen len        332     10,624     90.6%       67.7%         87.9
continuous, arrival       336      9,630    100.0%       56.2%        104.1
continuous, by prompt     339      9,630    100.0%       70.8%         87.2

The first two rows have identical row-steps. 512 = 8 x 64: the maximum in all eight groups was exactly 64. With 69 of 256 requests hitting the cap, any 32 you grab almost certainly contains one, and reordering does not change that.

Handing the sort to an oracle that knows the generation length gets 90.6%. What part nine had was not an algorithm but information - prompt length is in your hand on arrival and generation length is not.

Not leaving the seat empty

If you cannot sort, go the other way. Instead of waiting for the whole group, admit the next queued request the instant one finishes.

Static - a finished slot stays empty until the group ends Continuous - the next request takes the slot at once 32 slots 32 slots done at 336 Cache length attention has to read on that step 0 64 128 staticcontinuous 128 256 336 512 step
The real trace of 256 requests at batch 32. Above, static batching leaves a ragged idle edge at the end of every group and takes 512 steps. In the middle, continuous batching has no gaps and finishes at 336. Below, the cache length attention has to read on that step - static drops back at each group boundary, continuous goes up and stays.

Row-steps fall from 16,384 to 9,630, steps from 512 to 336.

The 100.0% occupancy is a definition, not a discovery: a schedule that drops a finished row from the tensor immediately cannot waste rows. The numbers beside it are the ones worth reading.

The seat is paid for out of the cache

In the mean-cache column, continuous batching is the longest at 104.1 - longer than static in arrival order at 93.3.

Of course it is. Continuous batching deliberately parks a freshly admitted short request next to a long-running one, and if the cache is one dense tensor its length is set by the longest occupant. That is where the seat is paid for.

Row-steps fell 41%, but what attention actually reads - the sum of rows x cache - only fell 34%, from 1,528,896 to 1,009,601. Seven points leaked into the cache.

Converting to time

Measuring one step across a grid of row counts and cache lengths and fitting t = a + b·R + d·R·C:

a = 569 us         fixed, per step
b = 7.68 us        per row
d = 0.1015 us      per row x cache slot

Worst residual over the 3 x 3 grid is 2.6%. At 32 rows and cache 104 that is 49% fixed, 21% on rows, 29% attention.

Pricing five schedules with that, against 41 rounds of paired measurement:

                        predicted   measured   25th ~ 75th
static, arrival              1.00       1.00
static, by prompt            1.07       1.06   0.94 ~ 1.13
static, by gen len           1.57       1.57   1.49 ~ 1.66
continuous, arrival          1.56       1.58   1.50 ~ 1.69
continuous, by prompt        1.64       1.65   1.54 ~ 1.78

The sorting row straddles 1.0, buried by going through a common baseline. So the two configurations were divided against each other directly instead, in the same round, alternating which ran first, 61 times:

static,     by prompt / arrival   1.077   quartiles 1.036 ~ 1.127   won 54 of 61
continuous, by prompt / arrival   1.057   quartiles 0.992 ~ 1.102   won 44 of 61

Three things fall out.

One. Sorting by prompt length is 1.08. It lifted cache occupancy a full 20 points, 61.7% to 82.3%, and bought 8% of the time - because attention is only 29% of a step. Part nine’s “removing the waste does not halve the time” is not close to a half here.

Two. Continuous batching alone is 1.58, effectively the oracle’s 1.57. It delivers what knowing the unknowable would have delivered, while knowing nothing.

Three. Together they are 1.65. Laying the sort on top of continuous batching adds 1.06 - small, 44 rounds of 61, but one-sided. They do not overlap: sorting fixes padding in the cache dimension, continuous batching fixes it in the row dimension. Continuous plus prompt sort has the smallest rows x cache total of the five, 801,245.

One place this disagrees with part nine

Part nine measured the cache going from 1 to 128 at batch 32 as 675 us of added time and reported 48.3% of a step as length-dependent. This grid fit puts the same span at 412 us and 33.8%.

Same laptop, same model, fifteen points apart. Part nine was a single sweep over cache length (its table even dips going from 16 to 32), while this is a plane fit to a 3 x 3 grid measured round-robin 50 times. I trust the second more, but the honest conclusion is that this machine cannot say whether the fraction is in the thirties or the forties. That is why the speedup table above reports measured paired ratios rather than the prediction.

What is left

27% of requests hit the cap at 64. The real tail is cut off, and had it not been, static batching would have looked worse - the cut favours continuous batching, so the numbers above are the conservative ones.

Holding the cache as one dense tensor is also a choice. Split it into fixed-size blocks and each row can hold only what it needs, and the price continuous batching pays here disappears. This part did not go there.

The priced absolute times land 24~29% below the measured ones. All five miss in the same direction by about the same amount, so the ratios get used and the absolute times do not.

The day this table was first measured, the same trace came out at 1,581 ms. Today it is 461 ms. Same code, same data, a factor of 3.4 - the laptop was busy with other things that day. The speedup ratio that day was also 1.58. Only the numbers divided within a round survived; had the absolute times been the result, every one of them would have been wrong.

So

  • Generation length is not predictable from prompt length. Correlation -0.076
  • So sorting by prompt length does not move row occupancy off 58.8% at all. The maximum in all eight groups was 64
  • An oracle sorting by generation length reaches 90.6%. What part nine held was information
  • Continuous batching makes row occupancy 100%, which is a definition. The step count, 512 -> 336, is the real number
  • The seat is paid for out of the cache: mean cache 93.3 -> 104.1, the longest of the five
  • Row-steps fall 41% while rows x cache falls only 34%
  • Measured 1.08 (sorting) / 1.58 (continuous) / 1.65 (both). They fix different waste, so they add

Comments