Lab 01 — GPU Cluster Scheduler Simulator (Python)

Phase: 06 — GPU Scheduling | Difficulty: ⭐⭐⭐⭐☆ | Time: 5–8 hours Language: Python (stdlib) | Hardware: none

Concept primer: ../WARMUP.md Ch. 6–7, 9.

Run

python solution.py

0. The mission

Simulate a GPU cluster and run a job trace through four placement policies, measuring what platform leaders actually argue about: utilization, queue wait, stranded GPUs, and gang-deadlock avoidance.

The simulator is event-driven: jobs arrive, request k GPUs for a duration, get placed (or queued), run, and release. Policies differ only in where they place.

Expected output:

== Placement-policy comparison (mixed trace + whole-node jobs) ==
policy            util%  p50_wait  p99_wait  stranded  deadlocks
spread             60.9       0.0     228.0        24         0
first_fit          67.0       0.0      36.0          2         0
best_fit           67.0       0.0      36.0          2         0

== Gang vs naive: the partial-allocation deadlock ==
  naive_no_gang : 0/3 jobs completed, 3 deadlocked (held GPUs, never able to finish)
  best_fit_gang : 3/3 jobs completed, 0 deadlocked

1. What each policy proves

  • spread vs best_fit: this is the headline. The cluster runs at the same moderate load, but spread scatters 2-GPU jobs across all four nodes, leaving 2 free GPUs per node and no whole node free — so the whole-node NVLink-8 jobs strand (p99 wait jumps to 228, and 24 GPUs sit free while jobs wait). best_fit consolidates the small jobs onto fewer nodes, keeping whole nodes available → the NVLink jobs run almost immediately. Same hardware, same jobs; only the placement shape differs. This is Phase 05's fragmentation at cluster scale, and the reason topology/consolidation-aware placement exists (WARMUP Ch. 6–7).
  • The gang-vs-naive deadlock: three 6-GPU jobs on a 12-GPU cluster. Naive round-robin placement gives each job one 4-GPU node; all 12 GPUs are held, every job is stuck at 4/6, none can finish or release — permanent partial-allocation deadlock. Gang scheduling refuses partial commits and runs them one at a time: all three complete (WARMUP Ch. 7).

2. Reading order (solution.py)

  1. Cluster / Node — the resource model and free_gpus, stranded_gpus.
  2. place_* policy functions — each takes (cluster, job) → placement or None.
  3. The gang logic: naive reserves GPUs as it finds them (can deadlock); gang only commits if the whole job fits atomically.
  4. The event loop and metrics.

3. Extensions

  1. Preemption: high-priority jobs evict low-priority ones; model the checkpoint cost (a fixed penalty added to the preempted job's remaining time). Show priority-inversion avoidance.
  2. DRF fairness: jobs request GPUs and CPU; schedule by dominant share; prevent one tenant monopolizing.
  3. Topology depth: model 2 nodes × 4-GPU NVLink islands; add an inter-island bandwidth penalty to job duration when a gang spans islands — then watch topology_aware pay off in throughput, not just placement.
  4. Backfill: let small jobs run while a big gang waits for its reservation; measure the utilization recovery.

4. Common pitfalls

  1. Counting "free GPUs" as "usable GPUs" — the whole stranded-GPU lesson is that they differ once jobs have co-location constraints.
  2. Releasing GPUs in the wrong event order (release before the job's end event) — corrupts utilization accounting.
  3. Modeling gang scheduling as "retry until it fits" without a reservation — that's just busy-waiting and can still starve big jobs; the lab uses reservation-style atomic commit.

5. What this lab proves about you

You can reason about cluster scheduling with numbers — stranding, gang-deadlock, topology — which is the difference between "we use Kubernetes" and "here's our placement policy, here's the fragmentation it controls, here's why big jobs don't starve." That's the platform-leadership altitude this JD hires for.