All code, data pipelines, and results: github.com/santhosh-svg-kum/gpudefrag

For years I worked on fulfillment optimization: deciding which warehouse ships which order, how to pack limited capacity without stranding space, and when a slower but globally better plan beats a fast greedy one. GPU infrastructure turns out to be the same problem in a different costume.

A GPU cluster is a warehouse whose shelves are GPUs and whose orders are jobs. It has the same failure mode: capacity that exists but can’t be used, because it’s in the wrong shape.

TL;DR

• Reproduced a strong published baseline (FGD, USENIX ATC ’23) within 1 pp before comparing anything.
• Solver-based batch placement beats FGD by +0.28 pp, but only at the right batch size.
• Demand-driven defragmentation recovers up to +2.6 pp GPU allocation under heavy load; plain bin-packing still wins placement for multi-node gang jobs.

Two 8-GPU nodes, each half busy. Eight GPUs are free, but a job that needs a whole node can’t start. Moving four small jobs once fixes it.

This is GPU fragmentation, and on hardware that can cost well over a thousand dollars per GPU per month, every stranded GPU is money you’re paying to keep idle. So I built gpudefrag, an open-source scheduler and defragmenter that uses a constraint solver instead of greedy heuristics. Then I spent most of the effort on the part I think matters more than the algorithm: benchmarking it honestly, including the cases where it loses.

This post covers how it works, what it showed, and what surprised me.

The supply-chain parallel: heuristics vs. solvers

Most Kubernetes-style schedulers place one pod at a time with a scoring heuristic: filter feasible nodes, score them, pick the best. That’s fast and usually good. But it’s greedy: each decision is made without regard to the next ones.

In supply chain, we rarely accept greedy for capacity decisions. We formulate them as mixed-integer programs and let a solver search the joint space, because “best for this order” and “best for today” diverge.

The usual objection is latency: solvers are slow and schedulers must be fast. That holds less often than you’d think on a GPU fleet. When placement is followed by minutes of node provisioning, driver initialization and model loading, spending a few hundred milliseconds to decide a batch of placements jointly is a good trade, if the result is actually better and the solver can never make a decision worse than the heuristic it replaces.

That “if” is the whole project.

Step 0: reproduce a published baseline before claiming to beat it

My baseline is FGD (Fragmentation Gradient Descent, USENIX ATC ’23), a strong published scheduler for exactly this problem, and a reproducible one. It defines fragmentation as the expected amount of a node’s free GPU that a typical incoming task couldn’t use, and places each pod where fragmentation grows least. The authors released their simulator and the Alibaba production GPU trace it was evaluated on.

It’s easy to “beat” a baseline you implemented badly, so before writing any solver code I reimplemented six published schedulers (FGD, BestFit, GpuPacking, GpuClustering, DotProd, Random) and built a calibration gate: every baseline must reproduce FGD’s published curves within ±1 percentage point, or no comparison gets reported at all.

All six pass; FGD itself is within 0.1 pp. Getting there taught me things you only learn by matching someone else’s numbers:

• The integer truncation of scores matters. FGD’s score is int(sigmoid(Δ/1000) × 100). That truncation creates frequent ties.
• The tie-breaker is “lowest node name”: deterministic, but accidentally a packing rule. Hold that thought; it comes back.
• Exact per-seed reproduction is impossible, so the gate compares seed-means across 10 seeds. It’s statistical, not anecdotal.

How gpudefrag places pods

Each scheduling session takes a batch of pending pods and:

1. Warm-starts from FGD’s own answer. The FGD placement becomes the solver’s starting point (a “hint”), so the solver begins from a strong published heuristic and only searches for improvements.
2. Optimizes FGD’s own objective, jointly over the batch: first maximize placed GPU work, then minimize total fragmentation.
3. Validates every answer in Go against the real cluster state (device capacity, GPU counts, gang wholeness, topology) and keeps whichever of {solver, FGD} is better by the exact objective. The result is never worse than FGD on that batch’s objective. That’s a guarantee about each decision, not about the cluster over time; Result 2 shows the difference. On timeouts, errors or invalid output, it falls back and counts the reason.

The first version modeled fragmentation directly in OR-Tools CP-SAT, with reified constraints per GPU and per task class. It was correct (it matched brute force on small cases) but too weak to beat its own warm start in a two-second budget.

The fix came straight from operations research: a pattern-based formulation, the idea behind classic cutting-stock models. For each node, Go enumerates the small subsets of batch pods that could land there, with their exact post-placement fragmentation. CP-SAT then solves a small set-packing problem: pick one pattern per node, use each pod at most once. Batches are small, so the patterns are enumerated up front rather than generated on demand (no column generation needed), and it made the solver fast enough to matter.

Go: candidates → patterns (exact fragmentation per node subset) → gRPC
Python: CP-SAT picks one pattern per node; gangs all-or-nothing; domains respected
Go: validate → keep the better of {solver, FGD} → bind

Result 1: it beats FGD on FGD’s own benchmark, at the right batch size

With batches of 16 pods and a 500 ms budget, gpudefrag allocates 95.58% of GPUs at 130% offered load vs. FGD’s 95.30%: +0.28 pp, with a paired 95% confidence interval of ±0.12 pp, and it wins on all 10 of 10 seeds. That sounds small until you notice the ceiling: FGD already leaves under 5% on the table.

The two losing configurations taught me more than the winning one:

• Batch size 64 doesn’t win. The solver often runs out of time and falls back to FGD. A solver that misses its budget is just an expensive heuristic.
• Batch size 1 loses to FGD. Optimizing FGD’s exact metric one pod at a time is worse than FGD itself. Remember the tie-breaker: FGD’s truncated scores plus “lowest node name” quietly pack pods onto the same nodes. Removing that accident and optimizing the metric precisely gave up a hidden packing effect the metric doesn’t capture.

Lesson: the benefit of a solver here comes from deciding a batch jointly, not from computing a heuristic’s metric more precisely.

Defragmentation: fix the layout once you know what’s waiting

Placement is a bet on the future: you don’t know what arrives next. Defragmentation is different. When a job is actually blocked by fragmentation, it computes the cheapest set of migrations that frees room for it.

The design choices that make it safe:

• Demand-driven. It runs only when a pending job is blocked even though enough GPUs are free in total. No continuous reshuffling.
• Checkpoint-aware cost. Moving a job costs restart time plus the work lost since its last checkpoint. A job that checkpointed five minutes ago is cheap to move; one that checkpointed ninety minutes ago is expensive. The solver minimizes total lost work.
• Budgets and hysteresis. At most K moves per tick, the plan must clearly beat its cost, gang members are never moved, and freed capacity is reserved for the blocked job so nothing else grabs it.

Result 2: under a time-driven workload, the effect depends on load

FGD’s protocol is arrival-only (pods never finish). To test departures, latency and defragmentation, I added a time-driven simulator. It’s an event-driven engine with a single “busy server” scheduler whose decision time counts as virtual time, so a slow solver shows up as queueing delay instead of being hidden.

The Alibaba trace’s timestamps turned out to be snapshot-like (peak concurrency about 1% of capacity), so this suite uses a clearly labeled synthetic workload: real (pod, duration) pairs resampled under Poisson arrivals at a chosen offered load.

The first runs exposed a real weakness: with spare capacity, gpudefrag stranded 2–4× more 8-GPU jobs than FGD. The fragmentation metric weights task types by how often they appear, and 8-GPU jobs are rare by count but huge by capacity. I fixed it with a capacity-weighted objective and a penalty for opening idle nodes. Because seeds 42–46 informed that diagnosis and tuning, the results below come from held-out seeds 47–51 that were never used for tuning.

• When overloaded (load 1.1), placement wins: +0.31 pp allocation, statistically clear.
• With slack (load 0.9), placement loses: −0.56 pp. FGD’s simple packing is hard to beat when capacity isn’t scarce.
• Defragmentation trends positive (+0.7 to +1.0 pp at loads 0.9–1.0), but the intervals are wide with five seeds. At load 0.9 its p95 wait cost is negligible; at load 1.0 p95 wait rises by roughly 35–55 s.

Result 3: a real gang-training backtest, where defrag shines and placement doesn’t

The last suite replays real submit times and durations from SenseTime’s Helios traces (the Venus cluster: 1,080 GPUs; multi-node “gang” jobs are 58% of GPU-time). It uses the four busiest weeks, synthetic topology domains, and all-or-nothing gangs. The baseline is Volcano-style bin-packing, the usual choice for gang workloads.

• At normal load, nothing differs. The cluster is demand-limited.
• As load rises, defragmentation pays off. Adding gpudefrag’s defragmenter on top of ordinary bin-packing gives +2.64 ± 2.12 pp GPU allocation at 1.5× load (paired by week; the CI clears zero). The strongest result wasn’t solver placement at all; it was the defragmenter. On a 1,000-GPU fleet that’s about 26 GPUs’ worth of extra average allocation, without buying hardware.
• gpudefrag’s placement does not beat bin-packing on gangs. It’s slightly worse (not statistically significant) at every load. The solver isn’t failing: fallbacks were rare. It’s optimizing a metric designed for GPU-sharing workloads, while gangs need whole nodes kept free, which aggressive bin-packing does naturally.

What I’d tell someone building this

1. Calibrate your baselines against published numbers first. It caught real bugs, and it’s the only reason anyone should believe the comparisons.
2. Hold out seeds after you tune. My most flattering results came from the seeds I tuned on.
3. Report the negative results. “Placement doesn’t beat bin-packing on gangs” is as useful to a reader as the wins, and it points to the next experiment.
4. Never trust the solver blindly. Warm-start from the best heuristic, validate every answer, and fall back. “Never worse than the baseline, per decision” is a property you can test, not a hope. Just don’t confuse it with “better over time”; my timed results show those differ.
5. In these experiments, defragmentation mattered more than cleverer placement. Placement guesses the future; defragmentation corrects the past once you know what’s actually waiting.

From simulator to control loop

The simulator is deliberately not a Kubernetes scheduler. The production version of these ideas is a control loop: observe cluster state and pending demand, detect fragmentation that is actually blocking work, propose a bounded set of migrations, execute them through a reconciler, and verify that observed state converges to desired state. There, idempotency, disruption budgets, topology constraints, rollback and degraded-node handling matter as much as the optimization objective.

Limitations

These are simulation results. They rank configurations; they don’t predict production numbers exactly. The timed suite is synthetic, the gang suite’s topology is synthetic (Helios doesn’t publish rack layout), and the defragmenter’s restart model is simplified: a fixed restart time, and no eviction grace period.

What’s next

• Warm-starting from the better of FGD and bin-packing, plus a gang-aware objective, to address the gang result.
• A sweep over migration restart cost, to find where defragmentation stops paying off.
• Running it as a real Kubernetes scheduler plugin and defrag controller on a KWOK cluster, next to Karpenter, KEDA and Volcano.
• An elastic mode, where adding and removing nodes is part of the same optimization.

Try it

git clone https://github.com/santhosh-svg-kum/gpudefrag && cd gpudefrag
make data     # fetch checksum-pinned public traces
make test     # Go + Python tests
make calib    # the calibration gate (~10 s)
make suite1a  # FGD protocol benchmark

Code, benchmarks, and the full results with paired statistics: github.com/santhosh-svg-kum/gpudefrag. I’d love feedback from anyone working on GPU scheduling, Kubernetes, or capacity planning.

Thanks to the authors of FGD (Weng et al., USENIX ATC ’23) for releasing their simulator and data, to Alibaba for the openb trace, and to SenseTime for HeliosData. gpudefrag is Apache-2.0.