# Distributed model training

Lecture 16 · Training models · Distributed Systems I
Paper: Megatron-LM (SC 2021)
The page also has slides: https://alfonsocampodonico.com/classes/distributed-systems/entrenamiento-distribuido?lang=en
Code: https://github.com/AlfonsoCampodonico/ta050-sistemas-distribuidos/tree/main/repos/entrenamiento-distribuido (`gh repo clone AlfonsoCampodonico/ta050-sistemas-distribuidos`)

> Data, tensors and pipeline: how model training gets split up, and what each split costs.

Training a large language model is a distributed systems problem before it is a machine learning problem: the model doesn't fit on one GPU, and the computation wouldn't finish within a human lifetime. This lecture shows how that work is split along three dimensions —data, tensors and pipeline— and what each one costs in communication, memory and idle time.

**Paper:** D. Narayanan et al., [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://arxiv.org/abs/2104.04473), SC 2021.

**Further reading:** S. Rajbhandari et al., [ZeRO: Memory Optimizations Toward Training Trillion Parameter Models](https://arxiv.org/abs/1910.02054), SC 2020; P. Patarasuk and X. Yuan, [Bandwidth Optimal All-reduce Algorithms for Clusters of Workstations](https://www.cs.fsu.edu/~xyuan/paper/09jpdc.pdf), JPDC 2009.

**Repository:** `entrenamiento-distribuido` (Go, no dependencies), with three demos we run in class.

Almost nothing we'll see is new for this course. Data parallelism is input sharding, like in MapReduce. ZeRO is state sharding, like in Lecture 3. All-reduce is a barrier, and a barrier drags in the straggler problem we already saw with backup tasks. What's new is the scale, and the fact that the state is huge, mutable and coupled: every step depends on everyone having finished the previous one.

## 1. Why training is a distributed problem

There are two walls, and each one forces you to distribute for a different reason: **memory** and **compute**.

Training is a very simple loop repeated millions of times. You take a batch of examples and run the **forward** pass (push the input through every layer until you get a prediction and an error), then the **backward** pass (walk the layers in reverse, computing the gradient of every parameter), and finally the **optimizer step**, which nudges each parameter a little against its gradient. For us, the model is a function with billions of numbers inside it, and training is a loop that updates them.

The compute wall shows up in one number from the paper: training GPT-3, with 175 billion parameters, would take about **288 years** on a single V100 GPU. Nobody can wait that long, so the compute has to be spread over thousands of GPUs.

The memory wall is subtler. You'd think a 175-billion-parameter model in 16 bits takes 350 GB. But training isn't just storing the weights: you also have to store the gradients and the optimizer state, and that multiplies the total by eight (we'll see this in section 4). The biggest GPU in the paper has 80 GB. The model simply doesn't fit.

> The paper sums up both walls on its first page: a GPU's memory capacity is limited, so a large model doesn't fit even on a multi-GPU server; and the number of operations leads to unrealistic training times. The two reasons call for different things: the compute one is solved with more copies working in parallel, the memory one by splitting the model.

## 2. Data parallelism

The simplest idea is MapReduce's: if the input is huge, split it. Each worker has a **full copy of the model** and processes a different slice of the batch. It runs its forward and backward passes locally and gets a gradient that only reflects *its* examples.

The problem shows up at the optimizer step. If each worker applied its own gradient, the model copies would diverge on the very first step, and we'd have d different models instead of one. Everyone has to apply **exactly the same update**, and for that they have to agree on the gradient: add up everyone's gradients and divide by d. That operation —everyone contributes a vector and everyone gets back the sum— is called **all-reduce**.

With all-reduce, data parallelism has a very strong property: with the same global batch, d workers produce **the same model** as a single one. The paper calls it *strict optimizer semantics*. It's the same kind of guarantee MapReduce gave with deterministic mappers: the distributed run is indistinguishable from a sequential one. You can see it directly in the demo: the difference between the weights trained with 1 worker and with 4 is on the order of 10⁻¹⁶, pure rounding because the sum is done in a different order.

That guarantee has a price: all-reduce is a **barrier**. No worker can take the next step until everyone's gradients have arrived, so each step takes as long as the slowest worker. With thousands of GPUs, there's always a slower one: a straggler. In MapReduce we solved this with backup tasks, but here you can't launch a copy of the slow worker without also duplicating its share of memory and its state.

> The paper points out two limits of data parallelism (§1). First, past a certain point the per-GPU batch gets so small that the GPU is poorly used and communication dominates. Second, the maximum number of GPUs is the batch size: GPT-3 was trained with a batch of 1536, so data parallelism only allows 1536 GPUs, when finishing in a reasonable time needed about 10,000. And there's a third limit that adding replicas doesn't fix: **each replica has to fit on one GPU**. Data parallelism attacks the compute wall, but not the memory wall.

## 3. Ring all-reduce

The naive all-reduce is a **parameter server**: a coordinator receives everyone's gradients, adds them up and sends the result back to each one. It works, but the coordinator receives and sends (n−1)·S data, where S is the gradient size. It's the same bottleneck the MapReduce master had, now on the network: its link carries everything, and the cost grows linearly with the number of GPUs.

**Ring all-reduce** gets rid of the coordinator. The n GPUs form a ring, each one only sends to its right-hand neighbor, and the gradient is split into n chunks. The operation has two phases of n−1 steps each:

1. **Reduce-scatter.** At each step, every GPU passes a chunk to its neighbor, which adds it to its own. After n−1 steps, each GPU holds *one* chunk with the sum from everyone.
2. **All-gather.** Each GPU circulates its finished chunk. After another n−1 steps, everyone has every chunk.

> *Diagram: ring all-reduce with 4 GPUs · the gradient split into 4 chunks (A–D). It is in the slides.*

After the reduce-scatter, each GPU holds a single chunk with the full sum (GPU r holds chunk r+1); the all-gather hands them out to everyone.

At each step, every GPU sends S/n data, and there are 2(n−1) steps. In total, each GPU sends:

```latex
\text{sent per GPU} = 2 \cdot \frac{n-1}{n} \cdot S
```

That approaches 2·S **no matter how many GPUs there are**, and every link works at the same time. Patarasuk and Yuan proved in 2009 that this is the minimum possible: there is no all-reduce in which each process sends less. The demo measures it by counting floats per channel:

| GPUs | Central: rank 0 sends | Ring: each rank sends |
| --- | --- | --- |
| 2 | 1.00·S | 1.00·S |
| 4 | 3.00·S | 1.50·S |
| 8 | 7.00·S | 1.75·S |
| 16 | 15.00·S | 1.88·S |
| 32 | 31.00·S | 1.94·S |

The ring isn't free: it optimizes bandwidth, not latency. It has 2(n−1) sequential steps, and each one pays the latency of a message. For small gradients or very long rings, a tree algorithm with 2·log n steps is better; NCCL picks between the two based on size. For the gradients of a large model, which are gigabytes, bandwidth rules and the ring wins.

> The paper uses this property to analyze data parallelism (§3.3.1): since the cost of ring all-reduce scales with (d−1)/d = 1 − 1/d, adding replicas barely increases per-GPU communication. That's why data parallelism scales so well as long as the model fits in memory.

## 4. Where the memory goes: ZeRO

Each parameter costs **16 bytes** of memory during training, not 2. This is the breakdown the ZeRO paper gives for mixed-precision training with the Adam optimizer:

| What's stored | Precision | Bytes per parameter |
| --- | --- | --- |
| Weights (the ones the forward uses) | 16 bits | 2 |
| Gradients | 16 bits | 2 |
| Master copy of the weights | 32 bits | 4 |
| Adam momentum | 32 bits | 4 |
| Adam variance | 32 bits | 4 |
| **Total** |  | **16** |

By that count, a trillion-parameter model needs about 16 TB just for its state, not counting the forward activations. And data parallelism doesn't help: each replica stores the full 16 bytes per parameter. The ZeRO paper reports that plain data parallelism runs out of memory with models above 1.4 billion parameters on 32 GB GPUs.

ZeRO's observation is that this memory is **redundant**: the d replicas store exactly the same thing. It's the same diagnosis that led to sharding in Lecture 3. If there are d identical copies of a huge state, you can split it into d pieces and make each worker own one. ZeRO does this in three stages, each splitting a bit more:

| Stage | What's split across the d replicas | Memory per GPU (7.5 billion parameters, d = 64) |
| --- | --- | --- |
| Data parallelism | Nothing | 120 GB |
| ZeRO-1 | Optimizer state | 31.4 GB |
| ZeRO-2 | + gradients | 16.6 GB |
| ZeRO-3 | + weights | 1.9 GB |

With ZeRO-3, memory per GPU drops linearly with d. In exchange, no worker holds the full weights: before computing each layer it has to ask the others for their piece and throw it away when it's done. Stages 1 and 2 add no communication compared to data parallelism; stage 3 does.

> Narayanan et al. compare their approach with ZeRO-3 (§5.2) and find that, when doubling the number of GPUs with the same batch, theirs delivers 70% more for 175- and 530-billion-parameter models. The reason is inter-node communication: ZeRO-3 pulls the weights over the network at every layer. The two ideas don't compete, they combine: PyTorch implements ZeRO-3 as FSDP, and it's used together with the techniques that follow.

## 5. Tensor parallelism

If the model doesn't fit on one GPU, the alternative to ZeRO is to split **the computation of each layer**. A transformer is almost entirely matrix multiplications, and a matrix multiplication can be spread across GPUs by splitting one of the matrices. This is the Megatron technique (Shoeybi et al., 2019), and section 2.3 of the paper sums it up with the MLP block of each layer:

```latex
Y = \mathrm{GeLU}(XA) \qquad Z = \mathrm{Dropout}(YB)
```

The trick is *how* each matrix is split. A is split by columns, A = \[A₁, A₂\]: each GPU computes its half of XA and applies GeLU on its own, because GeLU works element by element and doesn't need the other half. B is split by rows, and each GPU multiplies its half of Y by its half of B. Only at the very end do the two partial results have to be added: an all-reduce. Attention works the same way, split by heads. The result is **two all-reduces in the forward pass and two in the backward pass for every layer**.

That's a lot of communication, and it sits on the critical path: no GPU can move on until the layer's all-reduce finishes. The paper works out that each GPU communicates 8·b·s·h·(t−1)/t data per layer and per microbatch, with b the microbatch size, s the sequence length, h the hidden dimension and t the degree of tensor parallelism.

That's why tensor parallelism only works over very fast links. Inside a DGX A100 server, the 8 GPUs are connected by **NVLink and NVSwitch**; between servers, each node has 8 InfiniBand cards at 200 Gb/s, which are quite a bit slower. A transformer with t = 8 inside a node works well; with t = 16, each of those all-reduces has to cross the inter-node network and performance drops.

> The paper adds a second problem (§3.3.2): with a large t, each GPU multiplies smaller and smaller matrices, and modern GPUs don't reach their peak on small matrices. Splitting too much wastes the hardware even if the network were infinite. That's where *Takeaway #1* comes from: use tensor parallelism up to the number of GPUs in a server, and scale beyond that with something else.

## 6. Pipeline parallelism

The other way to split the model is by **layers**: GPU 0 has the first layers, GPU 1 the next ones, and so on. Between stages, only the activation of one layer travels to the next, over point-to-point communication: b·s·h data per microbatch, much less than the all-reduce of tensor parallelism. That's why the pipeline can cross the network between servers.

The problem is obvious as soon as you draw it. With a whole batch, GPU 1 can't start until GPU 0 is done, and while one works the others wait. The fix is the one from any assembly line: split the batch into **m microbatches** and let them flow one after another. Even so, at the start of each batch the pipeline is filling up and at the end it's draining. That idle time is called the **bubble**.

This is the demo's output with p = 4 stages and m = 8 microbatches. Numbers are forwards, letters are backwards (which take twice as long) and dots are time when the GPU does nothing:

```text
GPipe — p=4, m=8, tf=1, tb=2
GPU 0 │12345678.........aabbccddeeffgghh│
GPU 1 │.12345678......aabbccddeeffgghh..│
GPU 2 │..12345678...aabbccddeeffgghh....│
GPU 3 │...12345678aabbccddeeffgghh......│
tiempo=33  ideal=24  burbuja=37.5%  (fórmula (p-1)/m = 37.5%)
activaciones en memoria (pico por GPU): [8 8 8 8]

1F1B (PipeDream-Flush) — p=4, m=8, tf=1, tb=2
GPU 0 │1234......aa5bb6cc7dd8ee.ff.gg.hh│
GPU 1 │.123....aa4bb5cc6dd7ee8ff.gg.hh..│
GPU 2 │..12..aa3bb4cc5dd6ee7ff8gg.hh....│
GPU 3 │...1aa2bb3cc4dd5ee6ff7gg8hh......│
tiempo=33  ideal=24  burbuja=37.5%  (fórmula (p-1)/m = 37.5%)
activaciones en memoria (pico por GPU): [4 3 2 1]
```

The paper computes the bubble (§2.2.1). Filling the pipeline costs p−1 forwards and draining it p−1 backwards, while the useful work is m forwards and m backwards. The time lost, measured relative to the ideal time with no bubble, is:

```latex
\text{bubble} = \frac{p-1}{m}
```

With p = 4 and m = 8 that's 3/8 = 37.5%, exactly what the simulator measures: (33 − 24) / 24. As a fraction of total time it is (p−1)/(m+p−1): in the diagram, 9 of 33 slots per GPU. To keep the bubble small you need **m ≫ p**: many microbatches per stage.

Both schedules have the same bubble, but not the same memory. **GPipe** runs all the forwards and then all the backwards, so each GPU keeps the activations of all m microbatches until the backward. **1F1B** (PipeDream-Flush) starts with a few forwards and then alternates one and one, so a stage never has more than p microbatches in flight. With m ≫ p, which is exactly what we want to shrink the bubble, 1F1B uses much less memory.

The bubble exists because of a design decision: at the end of each batch there's a **flush**, you wait for all the microbatches to finish and only then apply the optimizer. That's what preserves strict semantics, because each microbatch sees the same weights in the backward that it saw in the forward.

> The paper proposes an **interleaved** schedule (§2.2.2): instead of one contiguous block of layers, each GPU has v small chunks (GPU 1 has layers 1, 2, 9 and 10; GPU 2 has 3, 4, 11 and 12). Each chunk takes v times less, and the bubble drops to (p−1)/(v·m). The cost is that point-to-point communication also multiplies by v. With the scatter/gather optimization from §4.1, which takes advantage of the 8 InfiniBand cards in each node, the interleaved schedule improves throughput by 10% or more.

## 7. PTD-P: composing the three dimensions

None of the three techniques is enough on its own, and the paper's contribution is showing how to combine them. The n GPUs are arranged as a grid of **p × t × d = n**: each model replica is split into p pipeline stages, each stage is split across t GPUs with tensor parallelism, and there are d replicas with data parallelism.

| Dimension | What's split | Communication | When | Where it lives |
| --- | --- | --- | --- | --- |
| Tensors (t) | The matrices of each layer | 4 all-reduces per layer | Every microbatch | Inside the node, over NVLink |
| Pipeline (p) | The layers | Point to point, b·s·h | Every microbatch | Between nodes, over InfiniBand |
| Data (d) | The batch | 1 all-reduce of the gradients | Once per batch | Between replicas |

Read the table as a cost hierarchy. Whatever communicates the most goes over the fastest link, and whatever communicates the least goes over the slowest. The rule comes from the hardware, not from the model.

> *Diagram: PTD-P on the cluster · tensors inside the node, pipeline between nodes, data between replicas. It is in the slides.*

Each row is a full replica of the model; each column, a pipeline stage. The dotted lines connect the GPUs that hold the same layers in different replicas: those are the ones that do the gradient all-reduce.

The paper sums it up in three practical rules (§3):

1. **Takeaway #1.** Use tensor parallelism up to the number of GPUs in a server (8 in a DGX A100), and scale across servers with pipeline.
2. **Takeaway #2.** Pick the smallest model-parallel size t·p that makes the model fit in memory, and use data parallelism for everything else. Data parallelism is the one that communicates the least per unit of compute.
3. **Takeaway #3.** The optimal microbatch size depends on the model: a bigger one uses the GPU better, but leaves fewer microbatches per batch and grows the bubble.

With those rules, the paper trains a **trillion-parameter model on 3,072 A100 GPUs** at an aggregate throughput of 502 petaFLOP/s. That's 163 teraFLOP/s per GPU, 52% of the theoretical peak of 312, and it includes communication, data loading and the optimizer. They estimate that the full training run, over 450 billion tokens, would take about 84 days.

> The number that says the most about distributed systems is in §5.9: with the trillion-parameter model, pipeline communication used an effective bisection bandwidth of 892 GB/s, and data parallelism 12.9 TB/s. The paper is explicit that its result comes from optimizing software and hardware together: with a slower inter-node network, or with a partitioning that communicates more, scaling falls apart. Suboptimal combinations of tensors and pipeline get as low as half the throughput, even with fast links.

## 8. Failures and checkpoints

In MapReduce a failure was cheap: you retried the failed task and everything else kept going. In synchronous training, **one failure stops everyone**. Every step needs the gradients from all replicas, every pipeline stage needs the previous one, and every split layer needs its t GPUs. If a single one of the 3,072 GPUs goes down, no step can finish.

Recovery is the mitigation the MapReduce paper described for the coordinator and chose not to implement: **periodic checkpoints**. Every so often you save the full state, and on a failure everyone goes back to the last checkpoint and redoes the lost steps. With thousands of GPUs, failures stop being unlikely and become part of normal operation, so here checkpointing isn't optional.

For going back to be correct, you need the same condition as in MapReduce: **determinism**. If the batch for each step depends only on the step number, redoing steps 100 to 120 gives exactly the same weights as the first time. In the demo, a training run with a failure at step 120 and checkpoints every 50 steps ends with the same weights, bit for bit, as one with no failures; it only ran 21 extra steps.

Choosing how often to save is a trade-off. Saving often costs time at every checkpoint; saving rarely costs a lot of redone steps on every failure. With a checkpoint cost C and a mean time between failures F, Young's classic approximation gives the optimal interval:

```latex
T_{\text{optimal}} \approx \sqrt{2 \cdot C \cdot F}
```

> The paper gives the numbers for the problem (§5.10): the checkpoint of the trillion-parameter model is **13.8 TB**. The initial load from the 384 nodes reaches 1 TB/s, the maximum of the parallel file system, and saving reaches 273 GB/s, 40% of peak write bandwidth. At that speed, each checkpoint takes about a minute with all 3,072 GPUs waiting. Storage shows up again as part of the compute system, just like GFS in MapReduce.

The same "all or nothing" logic shows up when **scheduling** the job. An orchestrator like Kubernetes places pods one at a time by default. If a training job needs 512 pods and only 500 fit, those 500 sit holding GPUs without being able to take a single step. That's why training clusters use *gang scheduling*: the whole job gets its resources, or it gets nothing.

## 9. Demo, questions and references

The repository simulates all of the above in Go: each GPU is a goroutine, each link a channel, and it counts the data that goes through each one. The three demos we run in class are:

```text
go run ./cmd/demo allreduce                 # central vs ring
go run ./cmd/demo train -straggler 2ms      # the barrier waits for the slowest
go run ./cmd/demo train -fail-at 120        # one failure sends everyone back to the checkpoint
go run ./cmd/demo pipeline -p 4 -m 8        # the GPipe and 1F1B bubble
```

**Review questions**

1. Why doesn't data parallelism let you train a model that doesn't fit on one GPU, no matter how many replicas you add?
2. With 8 GPUs, how much does the busiest rank send in a central all-reduce, and how much in a ring one? What happens to each number when you go to 64 GPUs?
3. How is ZeRO like the sharding from Lecture 3? What communication does stage 3 add that stages 1 and 2 didn't have?
4. Why does tensor parallelism go inside the node and pipeline parallelism between nodes? Justify it with the amount of communication each one needs.
5. With p = 8 stages, how many microbatches do you need for the bubble to be under 10%? And with the interleaved schedule and v = 2?
6. GPipe and 1F1B have the same bubble. Why is 1F1B preferred?
7. In MapReduce, a slow worker was handled with backup tasks. Why doesn't that technique apply directly to synchronous training?
8. What condition does training have to meet for going back to a checkpoint to give the same result? Which MapReduce condition does it correspond to?

**References**

- D. Narayanan et al. [Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM](https://arxiv.org/abs/2104.04473). SC 2021.
- S. Rajbhandari et al. [ZeRO: Memory Optimizations Toward Training Trillion Parameter Models](https://arxiv.org/abs/1910.02054). SC 2020.
- P. Patarasuk and X. Yuan. [Bandwidth Optimal All-reduce Algorithms for Clusters of Workstations](https://www.cs.fsu.edu/~xyuan/paper/09jpdc.pdf). JPDC 69(2), 2009.
- M. Shoeybi et al. [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://arxiv.org/abs/1909.08053). 2019.
- J. Dean and S. Ghemawat. [MapReduce: Simplified Data Processing on Large Clusters](https://static.googleusercontent.com/media/research.google.com/es//archive/mapreduce-osdi04.pdf). OSDI 2004 (Lecture 2).

## Run the examples

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

```sh
cd repos/entrenamiento-distribuido
go test ./...
go run ./cmd/demo allreduce
go run ./cmd/demo pipeline
```
