granted07@kolkata:~/DES_GPUQueueingModel$ build/DES_GPUQueingModel
des-gpu-queue
A simulator, written in C, of requests waiting for a GPU. The dots behind this text are a copy of it, running live in your browser. Each dot is one request.
scroll
A simulator does not tick. It jumps.
Between two things happening, nothing happens, so there is no reason to look. It skips straight to the next thing.
Here there are only ever two things that can happen next. A new request arrives, or the GPU finishes a batch.
next = min(next_arrival, batch_done) clock = next
That is the whole engine. Step through it.
t = 0.0 ms
the whole future, sorted
The top one happens next. The clock jumps straight to it.
queue (buffer holds 5)
on the GPU
turned away so far: 0
what just happened
Press next event. Nothing has happened yet, and the first thing on the list is an arrival.
Where do the two times come from? Random numbers, shaped on purpose.
Gaps between arrivals are exponential. Batch run times are gamma. The only dial on the second is how much they spread.
arrivals exp(λ) service gamma(mean, cov)
arrival gaps
Mean gap 4.90 ms. The strip is the first 50 arrivals on a timeline. Gaps pile up near zero, so requests arrive in clumps with long quiet stretches. That is what no pattern looks like.
batch run times
Measured from 4,000 draws: mean 12.12 ms, CoV 0.50. CoV is spread divided by mean. At 0 every batch takes exactly the mean. At 1.4 some batches take several times longer than others.
Why batch at all?
A GPU pays a fixed cost to start a batch, then a small cost per request. The mean batch time is a straight line in the batch size.
mean = slope * b + intercept; departure = start + gamma(mean, cov);
In the repo, the slope and intercept are fitted to timings of a real network on a real GPU.
one batch of 8 7.3 ms per request 0.91 ms GPU can sustain 1096 requests/s
Time per request as the batch grows. Alone, a request pays the whole fixed cost. In a batch of 64 it pays a sixty-fourth of it. Sustainable load goes from 323/s at batch 1 to 1565/s at batch 64. Send more than that and the queue only grows. These numbers are placeholders until your GoogLeNet fit goes into lib/des/sim.ts.
now break it
Everything above, running together. Push the load past what the GPU can sustain and watch the buffer fill and requests get turned away. Then ask it to wait for 8 requests while only a few arrive.
warming up: 0/200 requests thrown away
Each dot is one finished request. Red ones are the warm-up, which the simulator throws away because the system started empty. Green ones are kept. The yellow line is their running average settling down.
Little's Law check
waiting for numbers
How do you know it is right?
Two independent ways of measuring the same wait have to agree. Add up the wait of every finished request, or take the average number of requests inside and divide by how fast they get in. That is Little's Law, and the simulator computes both.
It also throws away the first requests. The system starts empty, so those waits are unusually short, and they would drag the average. The red dots in the chart are that stretch.
And one more trick. With the same seed you get the same run, every time. Try it in the lab.
The C program does not run one setting. It sweeps all of them, many seeds each, and writes one row per combination to a CSV. This is that, live.
28 settings × 3 seeds × 3,000 requests, using the sliders from the lab above (except batch limit and cache chance, which this sweeps). Along one edge the batch limit goes 1 → 64. Along the other the cache hit chance goes 0 → 0.75. Height is mean latency. Green to red is the share of requests turned away. Click a bar.
where the real numbers come from
- Download GoogLeNet and time it on a real GPU, for batch sizes 1, 2, 4, 8, 16, 32 and 64.
- Check that the GPU is really doing the work, not the CPU.
- Turn those timings into the mean batch time the simulator uses.
- Run the simulator with three amounts of run-time spread: 0, 0.5 and 1.4.
- Plot the distributions, the latency and the blocking.
scripts/run_googlenet_experiment.sh
While it simulates, the C program allocates no memory. Everything lives in fixed-size storage set up beforehand.
what it does not claim
!The timings come from a Kaggle GPU. They are not the hardware in the BatOpt paper, so absolute numbers are not directly comparable.
!The CUDA benchmark times a stand-in workload. The GoogLeNet run uses the real model.
!Random numbers come from the C standard library generator, and every repetition has an explicit seed.
!The numbers in this page's sliders are placeholders, not your measurements.