Gang Scheduling and Fragmentation
Why a distributed training job cannot start until every worker starts, how that requirement produces both deadlock and stranded capacity, and the placement constraints that make a cluster's usable size smaller than its size.
A cluster reports 40 percent of its GPUs idle and a job requesting 64 of them will not start. Both facts are true simultaneously, and the reason is that distributed training needs all its workers at once, in the right places, and a scheduler designed for independent tasks cannot provide that.
All or nothing
A data-parallel training job synchronises gradients at every step. If 63 of 64 workers are running, they all block on the all-reduce waiting for the 64th, consuming 63 GPUs and making no progress. Partial allocation is not partial progress; it is a complete stall that also holds the resources hostage.
Gang scheduling, sometimes called co-scheduling, is the scheduler policy that allocates all of a job's workers atomically or none of them. Kubernetes has no native concept of this, which is why batch schedulers layer it on and why running large training jobs on a stock orchestrator is a well-known way to deadlock a cluster: two jobs each acquire half the GPUs, each waits for the rest, and neither releases.
Fragmentation
Even with gang scheduling, free GPUs are not interchangeable. Sixty-four free GPUs scattered as one or two per node cannot host a job that needs eight-GPU nodes with high-bandwidth interconnect, because the job's communication pattern depends on placement.
Topology matters concretely. Within a node, GPUs are connected by NVLink at hundreds of gigabytes per second; between nodes, by InfiniBand or Ethernet at a fraction of that. A tensor-parallel group placed across nodes runs at the speed of the slower link and can be several times slower than the same group placed within one node. So the scheduler must satisfy not "64 GPUs" but "8 nodes of 8, ideally in one network rail".
The consequence is that a fleet's usable capacity is well below its nominal capacity, and the gap grows with the diversity of job shapes. A cluster running only 8-GPU jobs packs perfectly; one running a mix of 1, 3, 16 and 64-GPU jobs strands capacity continuously.
Mitigations
Defragmentation by preemption. Checkpoint and evict low-priority jobs to consolidate free capacity. Effective, and it costs the preempted job's progress since its last checkpoint, which makes checkpoint frequency a cluster-level rather than a job-level decision.
Shape standardisation. Requiring jobs to request power-of-two node counts packs far better than allowing arbitrary sizes, at the cost of some jobs over-requesting.
Backfill. Small short jobs fill gaps while a large job's reservation accumulates, which raises utilisation without delaying the large job, provided their runtime estimates are honest.
Elastic training. Jobs that can add and remove workers dynamically sidestep the atomicity requirement entirely. The framework support exists and the cost is real: changing world size changes the effective batch size, which changes the optimal learning rate, so elasticity has to be accounted for in the training recipe rather than bolted on.
When it breaks
Utilisation is measured wrongly. "GPU allocated" is not "GPU busy". A fleet at 90 percent allocation can be at 40 percent actual utilisation because jobs are waiting on data loading, on checkpoint writes, or on stragglers. Allocation is a scheduling metric; SM occupancy and achieved FLOPs are the ones that say whether the hardware is doing work.
One slow worker sets the pace. A single node with a degraded link, thermal throttling, or a noisy neighbour slows an entire synchronous job to its speed. Straggler detection belongs in the training loop, reporting per-rank step times, because the cluster scheduler cannot see it.
Queueing policy is a political artefact. Fair-share, priority and reservation policies encode organisational decisions about whose work matters, and they are usually inherited rather than designed. The observable symptom is teams gaming the policy by over-requesting, which is a rational response.
Failures are not rare at scale. With thousands of GPUs and multi-week jobs, hardware failure during a run is expected rather than exceptional. Capacity planning must include spare nodes for replacement, and a fleet running at 100 percent allocation has no ability to recover a failed job without evicting something else.
16 flashcards for this concept
Click a card to reveal the answer.