Gang Scheduling

Some workloads cannot start until all their parts start. A distributed training job across 64 accelerators performs synchronous collective operations at every step; 63 accelerators produce no progress, they produce 63 idle accelerators. Gang scheduling makes the allocation atomic: the job either receives its full set or waits.

Why it matters

Without it, a scheduler that grants resources as they free up produces partial-allocation deadlock. Job A holds 40 accelerators waiting for 24 more. Job B holds 30 waiting for 34. Neither can proceed and both are consuming the scarcest resource in the organisation while producing nothing.

The failure is silent in the worst possible way: utilisation metrics look excellent. The dashboard shows the cluster fully allocated while no valuable work is being completed.

Implementation patterns

• Atomic admission. The scheduler evaluates the whole request against available capacity and admits or defers; it never partially grants.
• Topology awareness as part of the allocation. For accelerator workloads, which devices matters as much as how many — devices spread across the fleet may be nominally allocated and functionally useless, because collective communication becomes the bottleneck. Placement is part of the allocation.
• Reservations with backfill. Reserve a future window for the large job, and allow small jobs into the gap only if they will complete before the reservation begins. This is the classic high-performance computing answer, and it recovers most of the utilisation gang scheduling would otherwise cost.
• Preemption with checkpointing. Lower-priority long jobs are suspended to assemble a gang and resume from a checkpoint. Without checkpointing, preemption destroys work and becomes politically unusable.
• Defragmentation. Periodically migrate small jobs to consolidate free capacity — the same problem as memory compaction, with the same solution.

Industry example

Large-scale model training is where this is most acute. Jobs range from minutes to weeks, the largest need hundreds of co-located accelerators on high-bandwidth interconnect, and demand permanently exceeds supply.

A naive first-come-first-served scheduler with best-fit packing produces exactly the pathology above: small jobs continuously arrive and fill gaps, so a third of the fleet is free as scattered pairs and never coalesces into a contiguous block. The most valuable job in the queue has not started in three days while the cluster reports 95% utilisation.

The same shape appears in CI systems where large parallel test suites need many workers at once, in batch analytics where a query needs a minimum degree of parallelism to fit in memory, and in any system where the unit of value is a completed job rather than an occupied resource.

Failure scenarios

• Starvation of large jobs, where small ones perpetually win because they always fit.
• Utilisation optimised as the goal, which actively rewards the behaviour causing starvation.
• Gang scheduling without backfill, leaving large blocks idle while waiting and destroying throughput.
• Preemption without checkpointing, so making room discards days of work.
• Ignoring topology, granting the right count on the wrong hardware.

Trade-offs

Gang scheduling reduces raw utilisation — deliberately. A reservation leaves capacity idle; refusing a partial allocation declines to use free hardware; defragmentation spends capacity on migration.

This trade needs stating explicitly, because utilisation is the number leadership watches. A cluster at 95% utilisation where large jobs never start is worth less than one at 80% where they do. The right metric is queue time relative to job size, not occupancy.

Interview question

"Your GPU cluster reports 95% utilisation and the research team says their large training runs have not started in three days. Diagnose it, and tell me which of your fixes makes the utilisation number worse."