GPU Allocation Queues, in depth: quota, provider capacity and cluster admission as one pipeline, why large gangs wait longest, and how to shape requests

Three queues between a job and a GPU

Quota is a number, such as 64 GPUs of a given type in a region or a namespace. It does not reserve anything. A raised quota means you may ask for more, not that the machines exist. Planning that treats quota as supply will miss deadlines.

Provider capacity is the physical supply in a zone. Cloud providers expose three shapes of queue here. On-demand launches are a queue of length zero: if capacity is missing the call fails (on EC2, with an InsufficientInstanceCapacity error) and the caller must retry. Queued provisioning parks the request until the whole shape can be granted; Google Cloud's flex-start mode, part of Dynamic Workload Scheduler, works this way and limits the resulting VMs to seven days of run time. Future reservations, such as EC2 Capacity Blocks for ML, which can be booked up to eight weeks ahead, replace the line with a calendar. The reserved capacity article compares the commercial terms.

Cluster admission is the queue you control. Kueue on Kubernetes or a Slurm partition holds jobs until the GPUs your organisation already owns or has reserved are free within the job's share. Kueue can also connect the layers. Its ProvisioningRequest admission check asks the cluster autoscaler for queued provisioning and admits the workload only when the nodes arrive, so one Kubernetes queue fronts a provider queue. The Kueue article explains that object model.

Why big requests wait longest: Erlang C

Start with the simplest model that captures size. Suppose a pool has N GPUs and every job asks for exactly g of them as a gang, all at once. The pool then behaves like c = N/g servers. If jobs arrive at random with rate lambda and hold their GPUs for a mean time S, the offered load is a = lambda times S and the utilisation is rho = a/c. The Erlang C formula gives the probability that an arriving job must wait, and from it the mean wait. These M/M/c results assume random arrivals and exponential run times, which real clusters violate, but the shape of the answer survives.

import math

def erlang_c(c, a):
    """Probability an arrival waits, for c servers and offered load a = lambda * S."""
    top = a ** c / math.factorial(c) * c / (c - a)
    bottom = sum(a ** k / math.factorial(k) for k in range(c)) + top
    return top / bottom

def mmc_wait(c, lam, mean_service):
    a = lam * mean_service
    pw = erlang_c(c, a)
    return pw, pw * mean_service / (c - a)        # P(wait), mean wait

Now hold the pool at 64 GPUs and utilisation at 80 percent, and change only the gang size. Mean wait scales linearly with S for a fixed c and rho, so it is reported below as a multiple of the job's own run time. That separates the effect of size from the effect of duration.

Same pool, same load, and the 32-GPU job waits on average almost twice its own run time, while the single-GPU job barely waits at all. The reason is pooling: with 64 servers the chance that every one is busy at once is small, but with two servers it happens most of the time.

Load has the second effect. For the 8-GPU case with 6-hour jobs the same code gives a mean wait of 1.1 hours at 75 percent utilisation, 3.8 hours at 87.5 percent and 9.7 hours at 93.75 percent. Waits grow like 1/(1 - rho), so the last few points of utilisation are the most expensive, and this curve is the honest place to negotiate utilisation targets. The QPS math article applies the same tail behaviour to serving traffic.

Provider capacity: fail fast, wait in line, or book a slot

Each provider-side shape changes who absorbs the uncertainty.

Fail fast. On-demand answers in seconds, but a refusal says nothing about when capacity returns, and tight retry loops become retry storms. Back off with jitter, cap attempts, and record each refusal as supply data.

Wait in line. Queued provisioning suits batch training with a flexible start. The run is bounded (seven days for flex-start VMs) and all-or-nothing grants favour smaller shapes, as Erlang C predicts, so checkpoint often.

Book a slot. A future reservation moves waiting from start time to planning time. It ends at a fixed time, so the job must save state before the machines are reclaimed.

A useful policy tries these in order of cost and certainty, with explicit timeouts at each step:

def acquire(shape, deadline):
    # shape = (gpu_type, count); every step is bounded so the ladder always ends
    if reservation_has_room(shape):
        return claim_from_reservation(shape)
    req = submit_queued_request(shape, max_run_hours=shape.run_hours)
    if wait_for_grant(req, timeout=min(deadline, hours(12))):
        return req.grant
    cancel(req)                                   # never leave a stale request behind
    for smaller in elastic_shapes(shape):         # e.g. 64 -> 48 -> 32 GPUs
        grant = try_on_demand(smaller, retries=5, backoff="exp+jitter")
        if grant:
            return grant
    raise CapacityUnavailable(shape)              # page a human, do not loop forever

The function names are placeholders, not real APIs. What matters is that every stage has a timeout, abandoned requests are cancelled, and the fallback lowers the shape.

Inside the cluster: head-of-line blocking and backfill

Inside the cluster the dominant problem is head-of-line blocking. Under strict first-in first-out order, a 32-GPU job at the head waits for 32 free GPUs, and every smaller job behind it waits too, even when it would fit. Backfill fixes this by reserving a start time for the head job and letting later jobs run now if they will finish before that reservation or use only GPUs the head job will not need. The Slurm scheduling article covers how Slurm configures it; the simulation below shows why it matters.

import heapq, math, random, statistics

def simulate(policy, gpus=64, hours=20000, seed=7):
    rng = random.Random(seed)
    mix = [(1, 2.0, 0.60), (8, 6.0, 0.35), (32, 12.0, 0.05)]  # (GPUs, mean h, share)
    demand = sum(g * h * s for g, h, s in mix)
    lam = 0.80 * gpus / demand                                # 80% offered load
    t, jobs = 0.0, []
    while t < hours:
        t += rng.expovariate(lam)
        g, h, _ = rng.choices(mix, weights=[m[2] for m in mix])[0]
        jobs.append((t, g, rng.expovariate(1 / h), h))        # true run, estimate
    free, now, queue, running, waits = gpus, 0.0, [], [], {1: [], 8: [], 32: []}
    i = 0
    def start(job):
        nonlocal free
        arr, g, run, est = job
        free -= g
        heapq.heappush(running, (now + run, g, now + est))
        waits[g].append(now - arr)
    def schedule():
        while queue and queue[0][1] <= free:
            start(queue.pop(0))
        if policy == "fifo" or not queue:
            return
        need, avail, shadow, extra = queue[0][1], free, None, 0
        for end, g, est_end in sorted(running, key=lambda r: r[2]):
            avail += g
            if avail >= need:
                shadow, extra = est_end, avail - need
                break
        for job in list(queue[1:]):                           # EASY backfill
            arr, g, run, est = job
            if g <= free and (now + est <= shadow or g <= extra):
                if now + est > shadow:
                    extra -= g
                queue.remove(job); start(job)
    while i < len(jobs) or running:
        next_arr = jobs[i][0] if i < len(jobs) else math.inf
        next_end = running[0][0] if running else math.inf
        if next_arr <= next_end:
            now = next_arr; queue.append(jobs[i]); i += 1
        else:
            now, g, _ = heapq.heappop(running); free += g
        schedule()
    return {g: (statistics.mean(w), sorted(w)[int(0.95 * len(w))]) for g, w in waits.items()}

One run with seed 7, run-time estimates equal to the class mean and true run times drawn from an exponential distribution gives these waits in hours (mean, then 95th percentile):

Under FIFO every class waits about as long as the biggest, because the big jobs block the line. Backfill cuts the mean wait for small jobs by about three quarters and still improves the 32-GPU class, because the GPUs it would have idled are now doing work. The estimates matter: when jobs overrun their estimate the head job's reservation slips, so backfill quality depends on users giving honest time limits.

Worked example: a 256-GPU fine-tune

A worked example ties the layers together. A team needs 256 H100-class GPUs for a three-day fine-tune and owns a 512-GPU cluster that runs at about 85 percent. Treating the cluster as 512/256 = 2 servers of the job's shape, the Erlang table already says the job will usually wait, likely for longer than it runs. Three options exist.

1. Submit the gang and wait. Expected admission wait is a multiple of three days; with backfill reservations it will eventually start, but the date is unpredictable.
2. Book capacity. A three-day future reservation for 256 GPUs fixes the start date. The price is paid whether or not the run is ready, so this only makes sense once the data and code are frozen.
3. Make the job elastic. If the training code can start at 128 GPUs and grow to 256, it asks for a shape that the queue grants far more often (four servers instead of two), and it runs at reduced throughput instead of waiting. This needs checkpoint and resharding support but turns a lumpy queue into a smooth one.

The cheapest way to cut allocation wait is usually to change the shape of the request, not to buy more GPUs.

What to measure

A queue you do not measure will be described by anecdote. Record a timestamp at every transition and report these per stage and per size class:

• Wait time: p50 and p95 from submit to provider grant, to admission and to first training step.
• Age of the oldest request in each queue. A rising oldest age with a flat median is starvation of large jobs.
• Provider refusals and queued-request timeouts per GPU type and zone, as the only signal of supply you will get.
• Granted but idle GPUs: capacity that arrived before the job could use it. This is the stranded cost of hedging and slow start-up.
• Utilisation versus wait on one chart, so the trade on the 1/(1 - rho) curve is visible to the people who set the targets. The capacity planning article shows how to turn this demand data into a buy decision.

Failure modes

• Hoarding partial gangs. A scheduler that grants GPUs one node at a time lets two big jobs each hold half the pool while waiting for the rest. Neither starts. Use all-or-nothing admission for gangs.
• Duplicate grants from hedging. Submitting the same request to several regions and forgetting to cancel the losers bills you for idle machines. Cancel on first grant, and alert on granted-idle capacity.
• Starvation under backfill. Without a reservation for the head job, a steady stream of small jobs can delay a large job indefinitely. Make sure the reservation exists and add aging so priority grows with wait.
• Lying time limits. Users who pad limits make backfill useless; users who undershoot get killed. Publish the actual run-time distribution so limits can be set from data.
• Time-bounded grants without checkpoints. Queued and booked capacity both end. A job that cannot checkpoint and resume loses everything since its last save when the grant ends.

Trade-offs

What to do next

1. Instrument submit, quota, grant, admission and first-step timestamps, and publish p50 and p95 wait per stage and per GPU count this week.
2. Run the Erlang C function on your pool size, target utilisation and common gang sizes; share the table with whoever sets utilisation targets.
3. Check that gang jobs use all-or-nothing admission and that backfill keeps a reservation for the head job.
4. Write your acquisition ladder down: reservation, queued request with a timeout, smaller elastic shape, then escalate. Make every step cancel what it abandons.
5. Make the largest training jobs checkpoint at an interval well inside any time-bounded grant, and test resume from a checkpoint before you rely on queued capacity.
6. Add an alert on granted but idle GPUs and on the age of the oldest queued request.