# Sharing a GPU cluster

Lecture 21 · Sharing the cluster · Distributed Systems I
Paper: Philly (ATC 2019), Tiresias (NSDI 2019)
The page also has slides and an interactive simulator: https://alfonsocampodonico.com/classes/distributed-systems/repartir-un-cluster-de-gpus?lang=en
Code: https://github.com/AlfonsoCampodonico/ta050-sistemas-distribuidos/tree/main/repos/planificar-gpus (`gh repo clone AlfonsoCampodonico/ta050-sistemas-distribuidos`)

> Who runs, when and on which GPUs: all or nothing, locality, fragmentation and scheduling without knowing durations, with the Philly trace and Tiresias.

## 1. From a job with every GPU to a cluster that shares them

In Lectures 16 and 17, training already had its GPUs: Llama 3 on 16,384, all of them its own. In reality, a GPU cluster is shared by hundreds of users and dozens of teams, with one-GPU jobs and jobs of hundreds, and someone has to decide **who runs, when and on which GPUs**.

Today's paper is the analysis of **Philly**, Microsoft's training cluster (Jeon et al., USENIX ATC 2019): the first large trace of a deep learning cluster, the one nearly every scheduler that came after it uses. It comes with **Tiresias** (Gu et al., NSDI 2019), which schedules without knowing how long jobs take, **Gandiva** (Xiao et al., OSDI 2018), which shares GPUs over time, and the analysis of Alibaba's cluster, **MLaaS in the Wild** (Weng et al., NSDI 2022).

This is a scheduling lecture, with classic problems and two new twists: jobs ask for many GPUs at once, and where they run changes how long they take.

| Part | The question | The classic version |
| --- | --- | --- |
| The workload | who asks for GPUs, how many, for how long? | cluster traces |
| All or nothing | what happens if a job gets only part of its GPUs? | deadlock, head-of-line blocking |
| Locality | wait for the good spot or start in a worse one? | fragmentation |
| No durations | who goes first if nobody knows how long anything takes? | SRTF, LAS, preemption |
| Sharing | and across teams, or one GPU among several jobs? | time-sharing, quotas |

## 2. The workload

**Philly** (Jeon et al., §2): 75 days of logs, from October to December 2017, with **96,260 jobs** from **14 virtual clusters**. A virtual cluster is one team's slice, with its GPU quota. The paper doesn't give the exact GPU count: hundreds of servers and thousands of GPUs of the same model, in two server types, with 2 and 8 GPUs. The scheduler is YARN extended for GPUs, with gang scheduling and locality.

The surprising number: almost every GPU is allocated, but **allocated GPUs are only 52% utilized on average**. The two reasons the paper finds are the subject of this lecture: jobs spread over many servers, which wait on the network, and interference between jobs that share a server.

**The shape.** A huge number of small jobs and a few enormous ones:

- More than 82% of Philly's jobs ran on a single GPU (as summarized by Weng et al., §2).
- The median duration was **26 minutes**, and the p90 was **25 hours** (Weng et al., §3.2).
- **0.5%** of jobs took more than a week, and jobs that ask for more GPUs tend to run longer (Jeon et al., §2.4).

This is a **heavy-tailed** distribution: the median tells you little. In big data, by contrast, tasks last from milliseconds to a few hours.

The repository's synthetic workload has that shape (the percentages are illustrative, not Philly's):

| GPUs | Jobs | GPU·time |
| --- | --- | --- |
| 1 | 70% | 10% |
| 2 to 8 | 24% | 46% |
| more than 8 | 6% | 45% |

The 1% of jobs that ask for the most takes half the GPU·time (GPUs times duration: what a job costs the cluster). Optimize for average wait per job and you favor the small ones, which are nearly all the jobs; optimize for utilization and you favor the big ones, which are nearly all the GPU·time.

**Nobody knows how long their job will run, or whether it will finish** (Jeon et al., §4, table 6):

| How it ended | Jobs | GPU·time |
| --- | --- | --- |
| Succeeded | 69.3% | 44.5% |
| Killed by the user | 13.5% | 37.7% |
| Failed | 17.2% | 17.8% |

30.7% of jobs didn't finish successfully, and they took about 55% of the GPU·time. Killing isn't always bad: many people train until they see the curve stop improving, or discard configurations in a hyperparameter search. Failures are mostly user errors (the most common is running out of CPU memory; then incorrect inputs and bugs in the code); two infrastructure failures (checkpoint-write errors and MPI runtime failures) are only 6.2% of attempts, but they show up late and account for 36% of the time-to-failure. Jobs with more than 4 GPUs retry more and fail more.

The paper's three recommendations, which run through this lecture: (1) since jobs run for a long time, the scheduler should **trade waiting for locality**; (2) isolate jobs on dedicated servers, with migration to defragment; (3) **catch failures early**, before asking for a large cluster.

## 3. All or nothing

**Gang scheduling.** As we saw in Lecture 16, all-reduce is a barrier: with 500 of 512 GPUs, the job doesn't take a single step. If an orchestrator places each pod on its own, two 8-GPU jobs on an 8-GPU cluster can end up with 4 each, waiting forever for the other's. All four Coffman conditions are there: mutual exclusion, **hold and wait**, no preemption and circular wait.

Gang scheduling breaks hold and wait: the job is admitted whole or stays in the queue without taking anything, like acquiring all of a transaction's locks at once. Philly says it outright: frameworks need all their GPUs at once, so the scheduler does gang scheduling and also tries to respect locality (§2.3).

**Head-of-line blocking.** With gang and strict FIFO, a 32-GPU job at the front of the queue, with 20 free, waits; and so do the 1, 2 or 4-GPU jobs behind it, even though they fit. The free GPUs sit idle.

**Backfill.** If the first one doesn't fit, the ones that do fit go ahead. Philly does this: 38.1% of decisions were out of order, and every job with more than 4 GPUs was overtaken at some point; in 85% of those cases, without lengthening its wait (§3.1.1). The Alibaba analysis finds the same problem: about 9% of short instances spent more than half their time waiting.

**The price: starvation.** With greedy backfill, every time a GPU frees up a small job takes it, and the big one never gathers its GPUs. The classic HPC fix is **EASY backfilling** (Lifka, 1995): the first job reserves the time it will fit, and only jobs that finish before then go ahead. It needs every job to declare its duration, which nobody knows in deep learning. Philly, on top of that, reclaims a team's quota with preemption only when the cluster is above 90% utilization.

**The demo** (`go run ./cmd/sim gang`): 2,000 jobs on 256 GPUs (4 racks of 8 servers with 8 each), at 90% load.

| Scheduler | Avg. JCT | Wait 1 GPU | Wait 2–8 | Wait >8 | Utilization |
| --- | --- | --- | --- | --- | --- |
| One pod at a time, no gang | 29.7 h | 24.5 h | 26.2 h | 27.2 h | 72% |
| FIFO, gang | 10.0 h | 6.4 h | 6.4 h | 6.6 h | 68% |
| FIFO + backfill, gang | 3.8 h | 14 s | 8 min | 3.2 h | 74% |

JCT is job completion time, from when a job arrives until it finishes. Without gang it never gets fully stuck (some small job always finishes), but the GPUs held by jobs waiting for the ones they're missing add up to about 6,000 GPU·hours. With strict FIFO, everyone waits more than 6 hours with 32% of the cluster unallocated. With backfill, small jobs wait seconds and jobs with more than 8 GPUs wait more than 3 hours. `go run ./cmd/sim traba` shows the minimal deadlock: 8 GPUs and two 8-GPU jobs.

## 4. Locality and fragmentation

**Why where matters.** Inside a server, all-reduce goes over NVLink; between servers, over the network, and the ring runs at the speed of the slowest link (Lecture 16). Philly measures it (§3.2.1): 16-GPU jobs use their GPUs 43.7% on average if they're on 2 servers, 40.9% on 4 and **28.6% on 8** (table 5). 8-GPU jobs on one server, 56.9%; 16-GPU ones, 34.3%. On top of that, jobs that share a server with other people's jobs interfere with each other: CPU, host memory, PCIe, network.

**The dilemma.** In Philly's virtual cluster 2, 25% of jobs with more than 4 GPUs waited 10 minutes or more to start, against 10% of 1-GPU jobs. The paper separates two causes of waiting (table 2):

| GPUs | Quota | Fragmentation |
| --- | --- | --- |
| 2 to 4 | 40.6% | 59.4% |
| 5 to 8 | 25.8% | 74.2% |
| more than 8 | 2.1% | 97.9% |

**Fragmentation**: there are plenty of free GPUs, but not in one server or one rack, which is what locality asks for. Measured in time, about 80% of all jobs' waiting is due to fragmentation. With the cluster at two-thirds utilization, fewer than 4.5% of servers are completely empty. It's external memory fragmentation, with servers instead of pages, and it has the same fixes: place with best-fit (the small job goes to the fullest server it fits in) and compact, which here means migrating.

**What Philly does.** If there's no spot with good locality, the job waits a few minutes (2 to 3), retries, and after a fixed number of retries accepts scattered servers. Jobs with more than 8 GPUs spread over 16 servers start much sooner than those that waited for 2 or 4 (figure 4), but run worse.

**What Tiresias proposes: consolidate only when it matters** (§2.2). Sensitivity to locality depends on how the parameters are split into tensors, because each tensor travels as one message in gradient aggregation. In VGG19 the largest tensor is 71.5% of the model; in AlexNet, 61.0%; in ResNet-50, 9.2% (table 6). Models with one giant tensor suffer when spread out; the rest, not much. Tiresias profiles the model without asking the user and consolidates only the sensitive ones; compared with random placement, the improvement in training time reaches 1.67×.

**The demo** (`go run ./cmd/sim localidad`), with FIFO + backfill. Half of the multi-GPU jobs are sensitive and, when spread out, run at 60% (an illustrative number, in the range Tiresias measures).

| Placement | Avg. JCT | Wait >8 | … due to fragmentation | Slowdown | Useful utilization |
| --- | --- | --- | --- | --- | --- |
| Always consolidated | 3.82 h | 3.6 h | 39% | 1.00× | 73% |
| Wherever there's room | 4.00 h | 2.3 h | 0% | 1.11× | 71% |
| Relax after 10 min (Philly) | 4.15 h | 3.3 h | 0% | 1.12× | 71% |
| Consolidate if it matters (Tiresias) | 3.82 h | 3.2 h | 15% | 1.01× | 73% |

Spreading out shortens the wait but lengthens the run, and since jobs run for hours, it loses: that's Jeon et al.'s first recommendation. Consolidating only the sensitive jobs gives the JCT of always consolidating with less waiting for the big ones. To be honest: the numbers depend on the speed model and the workload; with other samples, always consolidated and consolidate-if-it-matters sometimes swap places. What doesn't change is that spreading everyone out loses.

## 5. Without knowing durations

**SRTF and LAS.** Serving first the job with the least time left (SRTF, *shortest remaining time first*) minimizes average response time, but it needs to know how much each job has left. **LAS** (*least attained service*) serves first the job that **has received the least service**, a number the scheduler does have. It works because of the heavy tail: a job that has been running for 5 minutes is probably one of the many short ones; one that has been running for 3 days, one of the few that last weeks. It's the classic foreground-background scheduler from time-sharing systems.

**2D-LAS (Tiresias, §3.2.2).** Service has two dimensions: a 32-GPU job that ran for an hour cost the cluster the same as a 1-GPU job that ran for 32 hours.

> priority = − GPUs × time running

**Discretizing (§3.2.3).** Pure LAS changes priority all the time and would force constant preemption. Tiresias uses K queues with GPU·time thresholds: a job starts in queue 1 and moves down when it passes the threshold. Between queues, strict priority with preemption; inside each queue, **FIFO by the time it first started** (by arrival, a job that hasn't started yet would preempt one that's already running, for no gain). **K = 2** is enough: with 3 or 4 queues average JCT improves by only 1% (§5.4.2). In their testbed, the threshold is 3,200 GPU·seconds. Against starvation, PROMOTEKNOB: if a job has waited PROMOTEKNOB times as long as it ran, it goes back to queue 1 (the *aging* of process schedulers). Tiresias calls the framework 2DAS; when the duration distribution is known it uses the Gittins index instead of LAS (Tiresias-G), with nearly the same results.

**Preemption costs a checkpoint.** Taking a job's GPUs away means saving its state and loading it back, like the checkpoints in Lectures 16 and 17. In the Tiresias testbed, 221 preemptions cost 13,724 seconds: **about 62 s each** (§5.2.4). Gandiva makes it much cheaper by suspending at a mini-batch boundary, when GPU memory is at its minimum (it measured a 77× difference between maximum and minimum): under 100 ms for image classification, up to 1 s for translation; with one-minute turns, 2% or less.

**Tiresias results** (60 P100 GPUs, 15 machines with 4 each): against YARN-CS, a capacity scheduler like the one Microsoft used, average JCT improves **5.5×** and median 27×; average wait drops from more than 8,000 seconds to about 1,000, and half of the jobs wait 13 seconds or less; makespan drops 1.21×. In simulation with the Philly trace (table 5): 2.4× better than YARN-CS, 1.5× against best-effort and 2× against Gandiva, and **the same average JCT as SRTF**, which knows the durations.

**The demo** (`go run ./cmd/sim duraciones`), same workload, all consolidating only when it matters:

| Scheduler | Avg. JCT | Wait 1 | Wait >8 | Preemptions |
| --- | --- | --- | --- | --- |
| FIFO | 10.03 h | 6.4 h | 6.6 h | 0 |
| FIFO + backfill | 3.82 h | 14 s | 3.2 h | 0 |
| 2D-LAS, threshold 3,200 GPU·s | 4.12 h | 29 min | 24 s | 2,642 |
| 2D-LAS, threshold 300,000 GPU·s | 3.70 h | 2 s | 23 min | 569 |
| SRTF (knows the durations) | 3.67 h | 0 s | 47 min | 1,386 |

With a threshold suited to the workload (300,000 GPU·s, about 80 GPU·hours), 2D-LAS beats backfill and lands within 1% of SRTF. With the Tiresias testbed's threshold, on this workload of hours-long jobs, almost everything drops a queue right away (a 32-GPU job after 100 seconds) and there are more than four times as many preemptions: worse than backfill. You pick the threshold by looking at the workload. 2D-LAS also fixes backfill's starvation: a new big job has high priority while it has received little, and waits 23 minutes instead of 3.2 hours.

The cost of each preemption, with the good threshold: free 3.70 h; 1 min 3.70 h; 10 min 3.76 h; 30 min 3.91 h. To be honest: against backfill the improvement is small (3%); the big one is against strict FIFO. The paper's simulation shows the same thing: 2.4× against YARN-CS, which has head-of-line blocking, and only 1.5× against best-effort, which already backfills.

## 6. Sharing

**Over time: Gandiva (OSDI 2018).** Training is predictable: each mini-batch looks like the one before. Gandiva uses that for three things: **time-slicing** (jobs take turns on the GPUs a minute at a time, suspending between steps, and a new job gives its first signal in minutes instead of waiting hours), **packing** (two small jobs on one GPU if they don't get in each other's way) and **migration** (moving a job in seconds, to defragment or improve locality). On a 180-GPU cluster, average utilization goes from 50.1% to 62.8%, 26% more; in hyperparameter search it explores almost 10× as many configurations. It aims for fairness and utilization more than JCT: in the Tiresias simulation it comes out 2× worse on JCT.

**One GPU among several: MLaaS in the Wild (Alibaba PAI, NSDI 2022).** Two months of 2020 on **6,742 GPUs** (1,295 machines with 2 GPUs and 519 with 8), more than 1.2 million tasks and 7.5 million instances. Much more heterogeneous than Philly: training, inference, notebooks. The median instance uses **0.042 GPUs** and the median request is 0.5. With GPU sharing, on average **50%** of the GPUs is enough, and at peak hour up to 73% is saved; interference is rare. And the other way round: reserving the good machines for big jobs and packing the small ones onto the rest cut the big jobs' wait by 68% and everyone's by 45%. Today GPUs can be split into isolated instances (MIG) or shared over time.

**Across teams: quotas.** Philly has one quota per virtual cluster; what a team doesn't use is lent out, and reclaimed with preemption only when the cluster is above 90%. Waiting on quota is the other column of table 2: for 2 to 4-GPU jobs, 40.6% of the waiting.

In Kubernetes:

- **Kueue** does quota-based admission: one ClusterQueue per team, and queues in the same cohort lend each other what they don't use. For all or nothing, **waitForPodsReady**: if not all of a job's pods are ready within a configured time, the job is evicted and goes back to the queue. The documentation calls it a simple all-or-nothing implementation: it doesn't prevent hold and wait, it cuts it off with a timeout, like deadlock recovery.
- **Volcano** is an alternative scheduler with gang scheduling: the group of pods is placed whole or not at all.

**Today, at scale: MAST (Meta, OSDI 2024).** Dozens of regions, millions of machines, tens of thousands of GPUs. Before, each user picked by hand the region to store their data and run in (the two have to be together), and those isolated decisions overloaded some regions while others had spare capacity. With MAST the job goes to a global scheduler that decides where the data and the job go; its principles are temporal decoupling, scope decoupling and exhaustive search. In the most loaded region, high-priority GPU demand went from **2.63× the supply to 0.98×**.

**Training and serving on the same fleet.** Serving follows the users, with daytime peaks and nighttime troughs; the GPUs left over at night can train, if the scheduler can give them back in time, with preemption and checkpoints. DeepSeek scales down its inference nodes at night and uses those GPUs for research and training (it says so in the inference-system overview we saw in Lecture 19). Lecture 22 brings the two workloads together in a different way: a single loop that both serves and trains.

## 7. Demo, questions and reading

**The repository.** `planificar-gpus` is a discrete-event simulator of a 256-GPU cluster, in Go with no dependencies. Packages: `cluster` (topology, best-fit placement, fragmentation and speed depending on where the job landed), `trace` (the synthetic workload) and `sched` (the simulator and the schedulers). A 2,000-job run takes milliseconds.

| Command | What it shows |
| --- | --- |
| `go run ./cmd/sim carga` | the shape of the workload |
| `go run ./cmd/sim traba` | two jobs without gang, stuck |
| `go run ./cmd/sim gang` | no gang, FIFO and backfill |
| `go run ./cmd/sim localidad` | consolidate, spread or relax |
| `go run ./cmd/sim duraciones` | FIFO, 2D-LAS and SRTF, with preemption cost |
| `go test ./...` | the tests for what the lecture claims |

The tests check, with three different workloads, that without gang two jobs get stuck; that backfill removes head-of-line blocking and makes the big jobs wait; that consolidating beats spreading; that always consolidating causes waiting from fragmentation; that consolidating only when it matters matches the JCT with less waiting; that 2D-LAS beats FIFO and backfill and lands within 5% of SRTF; that a low threshold preempts too much; and that an expensive preemption makes JCT worse.

The *GPU scheduler* simulator is the same model in the browser: the 256-GPU grid fills up live, the queue says why the first job is waiting (for GPUs or for fragmentation), and you can change the ordering, the placement, the workload and the preemption cost. The Compare button runs every scheduler on the same workload.

Exercises in the README: EASY backfilling, Tiresias's PROMOTEKNOB, per-team quotas with lending, failing early with a test queue, migrating to defragment and sharing a GPU between small jobs.

**Review questions.**

1. Which Coffman condition does gang scheduling break? And Kueue's timeout? *Gang breaks hold and wait: all the GPUs together or none. Kueue lets jobs hold, and if the job doesn't complete in time it evicts it: it breaks "no preemption", like deadlock recovery.*
2. Why can a big job never start with greedy backfill? *Every time room frees up, a small job that fits takes it; the big one needs many free GPUs at once and never gathers them. You fix it by reserving (EASY, which needs durations) or with priorities like LAS.*
3. In Philly, why do mostly the big jobs wait, if there are free GPUs? *Because of fragmentation: they ask for locality and the free GPUs are scattered across half-used servers. For jobs with more than 8 GPUs, 97.9% of the waiting.*
4. Why does LAS look like SRTF when durations are heavy-tailed? *Because having run for a long time predicts a long time left: serving first the job that has received the least is serving first, on average, the job with the least left.*
5. What happens with 2D-LAS if the threshold between queues is very low? And if preemption is expensive? *With a low threshold, almost everything drops right away to the second queue, which is FIFO, and there's far more preemption. If preemption is expensive, each one adds that time to the job and JCT goes up.*
6. Why does Gandiva suspend jobs at a mini-batch boundary? *Because that's when GPU memory is at its minimum (the activations have already been freed): there's very little to copy, and suspending takes less than a second.*
7. A team has a 64-GPU quota and uses 10. What does Philly do with the other 54, and what happens when the team asks for them? *It lends them to other teams with jobs waiting; when the owner asks for them, they're reclaimed with preemption, only if the cluster is above 90% utilization.*
8. At Alibaba, the median instance uses 0.042 GPUs. What changes if you allocate fractions of a GPU? What's the risk? *On average half the GPUs are enough. The risk is interference between instances sharing a GPU, which turned out to be rare in the trace.*

**Reading.**

- Jeon et al., [Analysis of Large-Scale Multi-Tenant GPU Clusters for DNN Training Workloads](https://www.usenix.org/conference/atc19/presentation/jeon), USENIX ATC 2019. This is the lecture's paper.
- Gu et al., [Tiresias: A GPU Cluster Manager for Distributed Deep Learning](https://www.usenix.org/conference/nsdi19/presentation/gu), NSDI 2019.
- Xiao et al., [Gandiva: Introspective Cluster Scheduling for Deep Learning](https://www.usenix.org/conference/osdi18/presentation/xiao), OSDI 2018.
- Weng et al., [MLaaS in the Wild: Workload Analysis and Scheduling in Large-Scale Heterogeneous GPU Clusters](https://www.usenix.org/conference/nsdi22/presentation/weng), NSDI 2022.
- Choudhury et al., [MAST: Global Scheduling of ML Training across Geo-Distributed Datacenters at Hyperscale](https://www.usenix.org/conference/osdi24/presentation/choudhury), OSDI 2024.
- Kueue, [Setup All-or-nothing with ready Pods](https://kueue.sigs.k8s.io/docs/tasks/manage/setup_wait_for_pods_ready/).

**Wrap-up.** In Lectures 16 and 17 the job had all the GPUs; today we saw why getting them isn't trivial. A GPU scheduler decides three things without knowing how long anything takes: **all or nothing** (gang, backfill and starvation of the big jobs), **where** (locality against waiting, with fragmentation in between) and **in what order** (2D-LAS, with preemptions that cost a checkpoint). They're the classic problems of deadlock, fragmentation and SRTF, with jobs that ask for many GPUs at once and run differently depending on where they land.

## Run the examples

With Go installed and no dependencies, from the repository root:

```sh
cd repos/planificar-gpus
go test ./...
go run ./cmd/sim carga
go run ./cmd/sim traba
go run ./cmd/sim gang
go run ./cmd/sim localidad
go run ./cmd/sim duraciones
```
