LLM & VLM courseBlog
49Track 3: Pretraining and scale · session 19 of 22

Pipeline, context and expert parallelism; 3D and 4D parallel

Data parallelism and tensor parallelism are not enough for the largest runs: the model is too deep, the sequences are too long, and mixture-of-experts layers have too many experts. This session adds the three remaining ways to cut a training step: pipeline parallelism splits the layers, context parallelism splits the sequence, and expert parallelism splits the experts. Then it shows how real runs such as Llama 3 405B and DeepSeek-V3 combine them into 3D and 4D parallelism.

Time: 3 to 4 hours (reading 2 hours, exercises 1 to 2 hours)Level: IntermediateBefore this: Sessions 43 to 48 (collective communication, DDP, ZeRO, FSDP, tensor parallelism); session 29 (mixture of experts) helps for the expert part

What you will learn

  • How pipeline parallelism cuts the layers into stages, why it needs micro-batches, and how to compute the pipeline bubble (p − 1)/m
  • Why 1F1B has the same bubble as GPipe but stores only p micro-batches of activations, and how the interleaved schedule divides the bubble by v
  • How ring attention splits a long sequence over GPUs with an online softmax, when its communication hides behind compute, and why a zig-zag split balances causal attention
  • How DeepSpeed-Ulysses uses two all-to-alls to switch from a sequence split to a head split, and when it sends fewer bytes than ring attention
  • How expert parallelism places experts on different GPUs, the dispatch and combine all-to-alls, capacity factors and dropped tokens
  • How to combine DP × TP × PP × CP (and EP): the rank order, which dimension goes on which link, and the real layouts of Llama 3 405B and DeepSeek-V3

Why this matters

Llama 3 405B was trained on up to 16,384 H100 GPUs. Its model states do not fit on one GPU, one sequence of 128K tokens does not fit on one GPU, and even one 8-GPU node is far too small. Meta cut every training step in four ways at the same time: tensor parallelism 8, context parallelism 16, pipeline parallelism 16 and data parallelism 8. [Certain] This session explains the three cuts you have not seen yet, and how they fit together.

So far in this track you have met two cuts. Session 44, session 45 and session 46 split the batch: every GPU runs the whole model on different examples. Session 48 splits the weight matrices inside each layer, which needs two all-reduces per layer and therefore fast NVLink inside one node. Three things are still missing:

  • The model may be too deep: with tensor parallelism capped at one node of 8 GPUs, a 405B model still has 50 billion parameters per GPU. Pipeline parallelism (PP) gives each GPU group only some of the layers.
  • The sequence may be too long: the activations of one 128K-token sequence do not fit on one GPU group. Context parallelism (CP) gives each GPU only part of the sequence.
  • A mixture-of-experts model may have too many experts: DeepSeek-V3 has 256 routed experts in each MoE layer. [Certain] Expert parallelism (EP) puts different experts on different GPUs.

Each cut has its own communication pattern and its own cost: idle time in the pipeline, key-value passing in the ring, all-to-all traffic for experts. The engineering question of a big run is how to multiply them so that each kind of traffic runs on a link that is fast enough for it.

Four ways to cut a training step

A training step multiplies a batch of sequences by a stack of layers. You can cut this work along any of its axes. Each cut leaves some tensor complete on every GPU and splits another one, and that decides which collective you need (session 43):

CutWhat each GPU holdsMain communicationHow oftenNeeds
Data (DP, FSDP)all layers, part of the batchall-reduce (or reduce-scatter + all-gather) of gradients and weightsonce per step (FSDP: per layer, but easy to overlap)can cross nodes
Tensor (TP)part of every weight matrixall-reduce of activations2 per layer in forward, 2 in backwardNVLink, one node
Pipeline (PP)some layerspoint-to-point send of activations to the next stageper micro-batch, per stage boundarylittle bandwidth; crosses nodes well
Context (CP)part of every sequencekeys and values passed in a ring, or all-to-allper attention layerfast links, or long enough chunks
Expert (EP)some experts of every MoE layerall-to-all of token vectors2 per MoE layer in forward, 2 in backwardhigh all-to-all bandwidth

The world size is the product of all degrees, and the rest of the session takes them one at a time:

\[ N_{\text{GPU}} = \text{TP} \times \text{CP} \times \text{PP} \times \text{DP} \tag{49.1} \]
Read the symbols
TP, CP, PP, DP
the degree of each kind of parallelism: how many GPUs share one piece of that axis. For example PP = 16 means the layers are cut into 16 stages.
\(N_{\text{GPU}}\)
the total number of GPUs. Expert parallelism is usually not an extra factor: the EP group reuses GPUs of the DP (and CP) groups, as explained later.

Pipeline parallelism: cut the layers into stages

Take a model with \(L\) layers and \(p\) GPUs. Give GPU 0 the first \(L/p\) layers, GPU 1 the next \(L/p\), and so on. Each group of layers is a stage. In the forward pass, stage \(s\) computes its layers and sends the output activations (a tensor of shape batch × sequence × hidden) to stage \(s+1\). In the backward pass, the gradient with respect to those activations flows back from stage \(s+1\) to stage \(s\). That is all the communication there is: one point-to-point send per stage boundary, no collective. Each GPU stores only \(1/p\) of the weights, gradients and optimizer states.

The problem is obvious once you draw it. If the whole batch goes through as one piece, stage 1 waits while stage 0 computes, stage 2 waits for stage 1, and in the backward pass the order reverses. At any moment only one of the \(p\) GPUs works. A pipeline of 4 stages runs at 25% use.

Micro-batches and the bubble (GPipe)

GPipe (Huang et al., 2019) fixes this the way a factory does: split the batch into \(m\) micro-batches and push them through one after another. While stage 1 works on micro-batch 1, stage 0 already works on micro-batch 2. GPipe runs all \(m\) forwards, then all \(m\) backwards, and then one optimizer step with the gradients summed over the micro-batches, so the result is exactly the same as one big batch. [Certain] (This is gradient accumulation, from session 39, spread over GPUs.)

Some idle time remains at the start (the pipeline fills) and at the end (it drains). This idle time is the pipeline bubble. Let one micro-batch need \(t_f\) for the forward and \(t_b\) for the backward of one stage. The last micro-batch can only start on stage \(p-1\) after it passed \(p-1\) earlier stages, so one step takes

\[ T_{\text{step}} = (m + p - 1)\,(t_f + t_b), \qquad T_{\text{ideal}} = m\,(t_f + t_b) \tag{49.2} \]
\[ \frac{T_{\text{bubble}}}{T_{\text{ideal}}} = \frac{p - 1}{m}, \qquad \frac{T_{\text{bubble}}}{T_{\text{step}}} = \frac{p - 1}{m + p - 1} \tag{49.3} \]
Read the symbols
\(p\)
number of pipeline stages (the PP degree)
\(m\)
number of micro-batches per training step and per pipeline
\(t_f, t_b\)
time of one forward and one backward of one micro-batch on one stage (often \(t_b \approx 2 t_f\))
\(T_{\text{bubble}}\)
\(T_{\text{step}} - T_{\text{ideal}}\): the time each GPU is idle in one step

Megatron-LM (Narayanan et al., 2021) reports the first form, bubble over ideal time. [Certain] It is the extra cost you pay. The only ways to shrink it: more micro-batches \(m\), or fewer stages \(p\). GPipe observed close to linear speedup once \(m \ge 4p\). [Likely] With \(p = 4\) and \(m = 16\), the bubble is \(3/16 = 19\%\) of the ideal time, or \(3/19 = 16\%\) of the step.

Algorithm 1: GPipe, one training step, seen from stage \(s\) of \(p\)
  1. input: this stage’s layers; \(m\) micro-batches (stage 0 has the tokens, the last stage has the labels)
  2. for \(i = 1, \dots, m\): // forward phase
  3.   \(x_i \leftarrow\) receive from stage \(s-1\) (stage 0: embed micro-batch \(i\))
  4.   \(y_i \leftarrow \text{layers}_s(x_i)\); keep the activations of micro-batch \(i\); send \(y_i\) to stage \(s+1\) (last stage: compute loss \(\ell_i\))
  5. for \(i = 1, \dots, m\): // backward phase
  6.   \(g_i \leftarrow\) receive \(\partial \ell / \partial y_i\) from stage \(s+1\) (last stage: start from \(\ell_i / m\))
  7.   backward through \(\text{layers}_s\); add the weight gradients; free the activations of \(i\); send \(\partial \ell / \partial x_i\) to stage \(s-1\)
  8. flush: wait until all stages are done, then every stage runs its optimizer step // same result as one big batch

Activation memory: why 1F1B

GPipe has a memory problem. Every stage finishes all \(m\) forwards before the first backward, so it must keep the activations of all \(m\) micro-batches at once. And we just said \(m\) should be large. GPipe answered with activation recomputation (re-running each stage’s forward during the backward). [Certain]

The 1F1B schedule (“one forward, one backward”), from PipeDream (Harlap, Narayanan et al., 2018) and used in its synchronous form (PipeDream-Flush) by Megatron-LM, changes only the order. [Certain] Stage \(s\) does \(p - s - 1\) “warm-up” forwards, then alternates one forward and one backward, and finishes with the remaining backwards. A backward runs as soon as its gradient arrives, and frees that micro-batch’s activations. So stage \(s\) never holds more than \(p - s\) micro-batches:

\[ M_{\text{act}}^{\text{GPipe}} = m \cdot A_{\text{stage}}, \qquad M_{\text{act}}^{\text{1F1B}}(s) = \min(p - s,\ m) \cdot A_{\text{stage}} \le p \cdot A_{\text{stage}} \tag{49.4} \]
Read the symbols
\(A_{\text{stage}}\)
activation memory that one micro-batch leaves on one stage after its forward pass
\(s\)
stage index, 0 for the first stage. Stage 0 is the worst: it holds \(p\) micro-batches.

The bubble is the same: 1F1B still fills and drains the pipe once per step, so (49.3) still holds. What changes is that memory no longer grows with \(m\), so you can raise \(m\) to shrink the bubble without running out of memory. That is why 1F1B, not GPipe, is the default in Megatron-LM and in most large runs. [Likely]

Algorithm 2: 1F1B (PipeDream-Flush), the order of work on stage \(s\) of \(p\)
  1. \(w \leftarrow \min(p - s - 1,\ m)\) // warm-up forwards: the last stage has none
  2. for \(i = 1, \dots, w\): forward of micro-batch \(i\)
  3. for \(i = w + 1, \dots, m\): forward of micro-batch \(i\); then backward of micro-batch \(i - w\) // steady state
  4. for \(i = m - w + 1, \dots, m\): backward of micro-batch \(i\) // cool-down
  5. each operation waits for its input from the neighbor stage (forward: from \(s-1\); backward: from \(s+1\))
  6. optimizer step after the flush // at most \(p - s\) micro-batches of activations alive

Interleaved 1F1B: smaller bubble, more messages

Megatron-LM’s second trick attacks the bubble itself. Instead of one block of \(L/p\) consecutive layers, each GPU gets \(v\) smaller model chunks spread over the depth. With \(p = 4\) GPUs, \(v = 2\) and 16 layers, GPU 0 holds layers 1–2 and 9–10, GPU 1 holds 3–4 and 11–12, and so on. A micro-batch now visits every GPU \(v\) times, and each visit is \(v\) times shorter. The fill and drain take \(v\) times less time: [Certain]

\[ \frac{T_{\text{bubble}}}{T_{\text{ideal}}} = \frac{p - 1}{v \cdot m} \tag{49.5} \]

The price: \(v\) times more point-to-point messages, and somewhat more activation memory on the first stages. Megatron-LM reports more than 10% higher throughput from this schedule. [Certain] It needs \(m\) to be a multiple of \(p\) in its original form. [Certain] Llama 3 uses an interleaved schedule too, with a bubble of \((\text{PP}-1)/(V \cdot M)\) in its own notation. [Certain] Figure 1 simulates all three schedules.

Stages \(p\):
Watch stage:
forward (chunk 1)backward (chunk 1)forward (chunk 2)backward (chunk 2)idle so far (bubble)activations kept
    Figure 1. Pipeline schedules, simulated and animated. Each row is one GPU (stage); numbers are micro-batches. A forward of a whole stage takes 1 time unit and a backward 2; with interleaving each chunk takes half of that. Communication time is ignored. The page really runs the schedule: every operation starts when its stage is free and its input has arrived from the neighbor stage. Red is time a stage has spent idle so far. The green bars on the right count the micro-batches whose activations each stage keeps at the cursor time (the tick marks the peak so far). Under the timeline, the code of the watched stage with its current line, and the bubble formulas with the live numbers.
    How to read Figure 1

    The figure opens on the finished step. Press Play to run it from time 0, or Step and Back to jump from one event (an operation starting or ending) to the next. Start with GPipe, \(p = 4\), \(m = 8\), watching stage 0. Stage 0 starts at once, but stage 3 waits 3 units for the first micro-batch: that red block is the fill. At time 11 stage 3 has finished all 8 forwards and starts the backward of micro-batch 1. Stage 0 sits idle from 8 to 17: it waits for that gradient to travel back through stages 3, 2 and 1, and its green bar stays at 8 micro-batches. The step takes 33 units instead of 24: \((m + p - 1)(t_f + t_b) = 11 \times 3\). The idle share is \(3/11 = 27.3\%\) of the step, and the bubble over the ideal time is \(9/24 = 0.375 = 3/8\). Switch to 1F1B and play again: the step still takes 33, but the code of stage 0 goes warm-up (3 forwards), steady state, cool-down. It runs 4 forwards, waits from 4 to 10 for the first gradient, then alternates, and its green bar never passes 4 (the last stage: 1). Switch to interleaved: 28.5 units, bubble 0.1875 = 3/16, half of 1F1B, with 5.5 micro-batches’ worth of activations on stage 0. Now move \(m\) to 24 with 1F1B: the bubble falls to 0.125 while memory stays at 4. Set \(m = 1\): one GPU works at a time, and the step takes \(4 \times 3 = 12\) for 3 units of useful work.

    Zero-bubble and DualPipe schedules

    A newer idea splits the backward pass in two: B, the gradient with respect to the layer’s input (needed at once by the previous stage), and W, the gradient with respect to the weights (needed only by the optimizer). W can be moved later, into the holes of the bubble. Qi et al. (2024) use this to build schedules with (nearly) zero bubble, and report up to 23% more throughput than 1F1B at a similar memory limit, and up to 31% with a looser one. [Certain] DeepSeek-V3’s DualPipe feeds micro-batches from both ends of the pipeline and overlaps the forward of one micro-batch with the backward of another, so that their communication hides behind each other’s computation. Its paper compares the bubbles like this, with \(F\), \(B\), \(W\) the times of forward, input-backward and weight-backward chunks: [Certain]

    ScheduleBubbleWeights per GPUActivations
    1F1B\((PP-1)(F+B)\)1×\(PP\)
    ZB1P (zero bubble)\((PP-1)(F+B-2W)\)1×\(PP\)
    DualPipe\((PP/2-1)(F\&B+B-3W)\)2×\(PP+1\)

    DualPipe keeps two copies of the weights (one per direction), which is affordable for DeepSeek-V3 because expert parallelism already spreads most of the weights. [Certain]

    What a stage boundary costs

    Per micro-batch, each boundary sends the activations forward and their gradients backward:

    \[ V_{\text{PP}} = 2 \cdot b\,s\,h \cdot \text{bytes} \quad \text{per micro-batch and boundary (forward + backward)} \tag{49.6} \]
    Read the symbols
    \(b, s, h\)
    micro-batch size (sequences), sequence length, hidden size
    bytes
    2 for BF16

    This is small compared with tensor parallelism, which all-reduces a tensor of the same size 4 times per layer. A stage has many layers and only one boundary. That is why pipeline parallelism is the cut that goes across nodes, over the slower network, while TP stays inside a node. Megatron-LM even sends only \(1/\text{TP}\) of the tensor per GPU across the boundary and all-gathers it on the other side over NVLink (its “scatter/gather” optimization). [Certain]

    Worked example: the pipeline of Llama 3 405B

    Llama 3 405B has 126 layers and \(h = 16{,}384\), and was trained with PP = 16, sequences of 8,192 tokens and 16 sequences per data-parallel replica (Table 4 of the paper). [Certain] 126 is not a multiple of 16: Meta removed one layer from the first and from the last stage, because those stages also hold the embedding and the output layer with the loss. [Certain] That gives \(7 + 14 \times 8 + 7 = 126\).

    If one micro-batch is one sequence, \(m = 16\). Plain 1F1B would give a bubble of \(15/16 = 94\%\) of the ideal time: almost half the step idle. An interleaved schedule with \(v = 4\) gives \(15/64 = 23\%\), with \(v = 8\) it gives \(15/128 = 12\%\). (The paper does not say which \(v\) it used; these are only examples.) One boundary crossing of one micro-batch is \(1 \times 8{,}192 \times 16{,}384 \times 2\) bytes \(= 268\) MB, and with TP = 8 each GPU sends only 33.5 MB of it.

    Context parallelism: cut the sequence

    Most activation memory grows linearly with the sequence length \(N\) (the attention scores do not need to be stored with FlashAttention). For long-context training, one sequence alone can fill a GPU. Megatron’s sequence parallelism from session 48 only splits the sequence in the LayerNorm and dropout regions; inside attention, every TP rank still sees all \(N\) tokens. Context parallelism splits the sequence everywhere: CP rank \(i\) holds \(N/\text{CP}\) tokens of every sequence, in every layer.

    Almost all layers do not care: the MLP, the norms and the projections work token by token. The only exception is attention, where every query needs the keys and values of all earlier tokens. So CP is really about one question: how does a GPU compute attention for its queries when the keys and values live on other GPUs? There are two main answers, and Llama 3 uses a third, simpler one.

    Ring attention

    Ring attention (Liu et al., 2023) arranges the \(P\) CP ranks in a ring. [Certain] Each rank keeps its own query block for the whole layer. The key and value blocks travel: at step \(t\), rank \(i\) holds the K,V block of rank \((i - t) \bmod P\). It computes attention of its queries against that block, and at the same time sends the block to rank \(i + 1\) and receives the next one from rank \(i - 1\). After \(P\) steps (\(P - 1\) sends) every query has seen every key.

    The partial results are merged exactly with the online softmax trick from FlashAttention. For each query row, keep a running maximum \(m\), a running sum \(\ell\) of exponentials, and a running output \(\mathbf{o}\). When a new block with scores \(\mathbf{s}\) and values \(V_j\) arrives:

    \[ m' = \max\big(m,\ \max_k s_k\big), \qquad \ell' = e^{m - m'}\,\ell + \sum_k e^{s_k - m'}, \qquad \mathbf{o}' = e^{m - m'}\,\mathbf{o} + \sum_k e^{s_k - m'}\,\mathbf{v}_k \tag{49.7} \]
    Read the symbols
    \(s_k\)
    score \(\mathbf{q} \cdot \mathbf{k}_k / \sqrt{d}\) of this query against key \(k\) of the new block (masked keys give \(-\infty\))
    \(m, \ell, \mathbf{o}\)
    running maximum, running sum of exponentials and running weighted sum of values for this query
    \(e^{m - m'}\)
    rescales the old partial results when the maximum grows, so all exponentials use the same reference

    At the end the output is \(\mathbf{o} / \ell\), exactly the softmax attention of a single GPU; no approximation. The memory per rank depends only on the block size, not on \(N\). That is how ring attention reaches contexts “device count times longer”. [Certain]

    Figure 2 runs ring attention with real numbers. There are \(P\) ranks, 2 tokens per rank and a head width \(d = 2\), so you can follow every number. Queries, keys and values are seeded random values with one decimal. Each rank keeps \(m, \ell, \mathbf{o}\) for its 2 queries and updates them with (49.7) every time a K,V block arrives. At the end the page divides \(\mathbf{o}\) by \(\ell\) and compares the result with ordinary softmax attention computed on one GPU.

    CP ranks \(P\):
    queries (stay)keys (travel)values (travel)just changed
    1. \(m \leftarrow -\infty,\ \ell \leftarrow 0,\ \mathbf{o} \leftarrow 0\); \((K, V) \leftarrow\) local block
    2. for \(t = 0, \dots, P-1\):
    3. if \(t \lt P-1\): async send \((K, V) \rightarrow\) rank \(i+1\), recv \(\leftarrow\) rank \(i-1\)
    4. \(s \leftarrow \mathbf{q} \cdot \mathbf{k} / \sqrt{d}\) for the keys in \(K\) // masked: \(-\infty\)
    5. \(m' \leftarrow \max(m, \max s)\); \(\ell \leftarrow e^{m-m'}\ell + \sum e^{s-m'}\); \(\mathbf{o} \leftarrow e^{m-m'}\mathbf{o} + \sum e^{s-m'}\mathbf{v}\) // (49.7)
    6. wait for recv; \((K, V) \leftarrow\) received block
    7. return \(\mathbf{y} \leftarrow \mathbf{o} / \ell\)
    Figure 2. Ring attention computed live. Top: the ranks of the ring. Each keeps its queries (blue) and holds one K,V block (orange, green) that moves one rank to the right at every step; the last rank sends to rank 0. Bottom left: the score matrix \(\mathbf{q}_a \cdot \mathbf{k}_b / \sqrt{d}\), filled block by block in the color of the rank that computes it; with the causal mask, keys after the query give \(-\infty\). Bottom right: the running state \(m, \ell, \mathbf{o}\) of every query and, at the end, the output \(\mathbf{y} = \mathbf{o}/\ell\). Click a row to watch that query in the box under the code.
    How to read Figure 2

    Defaults: \(P = 4\), causal mask, watching query 7 (the last token, on rank 3). Press Step. At \(t = 0\) every rank scores its own block; query 7 gets scores 0.488 and −0.240, so \(m = 0.488\), \(\ell = 1 + e^{-0.728} = 1.483\). At \(t = 1\) the block of rank 2 arrives with a larger score, 0.806: the maximum grows, so the old \(\ell\) and \(\mathbf{o}\) are multiplied by \(e^{0.488 - 0.806} = 0.727\) before the new terms are added, and \(\ell = 2.413\). At \(t = 2\) the maximum grows again, to 0.884. At \(t = 3\) no score beats it, the factor is 1, and \(\ell = 4.732\). The output is \(\mathbf{y} = (-0.190, -0.108)\), the same as softmax attention on one GPU (the readout prints the largest difference over all queries). Watch rank 0 with the causal mask: from \(t = 1\) on, every block it receives comes from later tokens, so it computes nothing and waits; this is the imbalance that Figure 3 fixes.

    When is the communication free? Per step, a rank computes \(4 d c^2\) FLOPs (scores and weighted values, for a block of \(c\) queries against \(c\) keys, with \(d\) the total width of the queries) and sends a K and a V block of \(c\) tokens each. Ring attention’s paper requires the compute time to cover the transfer time. [Certain] With grouped-query attention (GQA, session 26) the K,V width \(d_{kv}\) is smaller than \(d\), so the condition becomes

    \[ \frac{4 d c^2}{F} \ \ge\ \frac{2 \cdot 2\, c\, d_{kv}}{B} \quad\Longleftrightarrow\quad c \ \ge\ \frac{F}{B} \cdot \frac{d_{kv}}{d} \tag{49.8} \]
    Read the symbols
    \(c\)
    tokens per CP rank, \(N / P\)
    \(F\)
    FLOP/s of one GPU; \(B\): bytes per second of the link between ring neighbors
    \(d, d_{kv}\)
    width of all query heads together, width of all key (or value) heads together. With full multi-head attention \(d_{kv} = d\) and the condition is the paper’s \(c \ge F/B\).
    \(2 \cdot 2\)
    two tensors (K and V), 2 bytes each in BF16

    For an H100 (989 TFLOPS dense BF16 [Likely]) on 50 GB/s InfiniBand, multi-head attention needs \(c \ge 19{,}788\) tokens per rank; with Llama 3 8B’s GQA (\(d_{kv}/d = 1024/4096\)) about 4,945. Over NVLink at 450 GB/s per direction, about 550 tokens are enough. These use peak FLOP/s, so they are optimistic; real kernels run slower, which makes overlap easier.

    Causal attention needs a zig-zag split

    With a causal mask, the token at position 10,000 attends to 10,000 keys, the first token to one. If rank 0 holds the first quarter and rank 3 the last, rank 3 does almost all the work. In ring attention every step waits for the slowest rank, so the whole layer runs at the pace of rank 3.

    The fix: cut the sequence into \(2P\) chunks and give rank \(i\) chunk \(i\) and chunk \(2P - 1 - i\), one early and one late. Llama 3 does exactly this. [Certain] Count work in chunk-by-chunk blocks (a block on the diagonal counts one half, because of the mask). Chunk \(j\) costs \(j + \tfrac12\) blocks, so

    \[ W_i = \big(i + \tfrac12\big) + \big(2P - 1 - i + \tfrac12\big) = 2P \quad \text{for every rank } i \tag{49.9} \]

    Every rank does the same work, and Figure 3 shows that even every ring step is balanced: each rank computes 2 blocks per step. With a contiguous split, the step time is 2 blocks for step 0 and 4 for every later step, which gives \(2 + 4(P-1) = 14\) for \(P = 4\) against the ideal 8: 57% efficiency.

    CP ranks \(P\):
    Figure 3. Ring attention with a causal mask. Left: the attention matrix cut into \(2P\) chunks of queries (rows) and keys (columns); chunk numbers are colored by the rank that owns them. A block is computed by the rank that owns its query chunk, at the ring step when the key chunk arrives: bright = this step, faded = earlier steps, empty = not yet. Blocks above the diagonal are masked and never computed. Right: the work of each rank at this step.
    How to read Figure 3

    Start with the zig-zag split and \(P = 4\). Rank 0 owns chunks 0 and 7. Press Next: at every step every rank computes exactly 2 blocks, and the layer finishes in 8 block-times, the ideal. Switch to the contiguous split and step again: at step 0 each rank does its own diagonal (2 blocks), but at later steps the ranks with late chunks compute 4 blocks while rank 0 does nothing, because everything it receives is in its future. The layer needs 14 block-times. With \(P = 8\) the contiguous split gets worse (30 against 16, 53%).

    Algorithm 3: causal ring attention, one layer, seen from CP rank \(i\) of \(P\)
    1. input: local queries, keys, values for this rank’s chunks \(\{i,\ 2P-1-i\}\) // zig-zag split
    2. \(m \leftarrow -\infty,\ \ell \leftarrow 0,\ \mathbf{o} \leftarrow 0\) for every local query; \((K, V) \leftarrow\) local keys and values
    3. for \(t = 0, \dots, P-1\):
    4.   if \(t \lt P-1\): start sending \((K, V)\) to rank \(i+1\) and receiving the next block from rank \(i-1\) // asynchronous
    5.   scores of local queries against \(K\), masked by token positions; update \(m, \ell, \mathbf{o}\) with (49.7)
    6.   wait for the receive; \((K, V) \leftarrow\) the received block (it came from rank \((i - t - 1) \bmod P\))
    7. return \(\mathbf{o} / \ell\) // backward: pass K, V and their gradients around the ring again

    DeepSpeed-Ulysses: switch from a sequence split to a head split

    DeepSpeed-Ulysses (Jacobs et al., 2023) uses a different idea. [Certain] Attention heads are independent of each other. So before attention, do an all-to-all that turns “each rank has \(N/P\) tokens of all heads” into “each rank has all \(N\) tokens of \(H/P\) heads”. Now every rank runs ordinary attention (FlashAttention, any mask) on its heads, with no communication inside. After attention, a second all-to-all switches back to the sequence split. In total four all-to-alls per layer in the forward pass: Q, K, V before, the output after. Let us count the bytes each GPU sends, with the all-to-all from session 43 (each rank keeps \(1/P\) of its data and sends the rest):

    \[ V_{\text{Ulysses}} = \frac{N}{P}\cdot\frac{P-1}{P}\,(2d + 2d_{kv}) \cdot 2 \ \text{bytes}, \qquad V_{\text{ring}} = (P-1)\,\frac{N}{P}\, 2 d_{kv} \cdot 2 \ \text{bytes} \tag{49.10} \]
    Read the symbols
    \(2d + 2d_{kv}\)
    Ulysses moves Q and the output (width \(d\) each) and K and V (width \(d_{kv}\) each)
    \(2 d_{kv}\)
    ring attention moves only K and V, but \(P - 1\) times
    \(\cdot\, 2\) bytes
    BF16; both are per GPU, per attention layer, forward only

    Ulysses’ volume per GPU shrinks like \(N/P\): if you double both the sequence and the GPUs, it stays the same. That is the paper’s main claim. [Certain] Ring’s volume per GPU stays near \(2 N d_{kv}\) whatever \(P\) is. The ratio is \(V_{\text{ring}}/V_{\text{Ulysses}} = P\, d_{kv}/(d + d_{kv})\). With full multi-head attention, Ulysses sends \(P/2\) times less. With strong GQA, ring can send less: for Llama 3 8B (\(d_{kv}/d = 1/4\)) the ratio is \(P/5\), so ring wins below \(P = 5\). But ring’s traffic can hide behind compute (49.8), while Ulysses’ all-to-alls sit on the critical path.

    Ulysses has one hard limit: the CP degree cannot be larger than the number of heads, and with GQA the K,V heads must be copied once \(P\) passes the number of K,V heads (8 for all Llama 3 models). [Certain] All-to-all also wants high bandwidth between all pairs, which means one node. USP (Fang and Zhao, 2024) therefore combines both: Ulysses inside the node, ring attention across nodes, with CP = Ulysses degree × ring degree. [Certain]

    Link between ring neighbors:
    Figure 4. Bytes sent per GPU for one attention layer’s forward pass, by formula (49.10), and two checks: does Ulysses have enough heads, and is ring attention’s chunk large enough to hide its transfers, by (49.8)? Model widths: Llama 3 8B \(d = 4096, d_{kv} = 1024\); 70B \(d = 8192, d_{kv} = 1024\); MHA \(d = d_{kv} = 4096\).
    How to read Figure 4

    Defaults: Llama 3 8B, 128K tokens, \(P = 8\). Ulysses sends 294 MB and ring 470 MB per GPU (ratio \(1.6 = 8 \times 1024 / 5120\)). Raise \(P\) to 16: Ulysses falls to 157 MB, ring stays near 503 MB, but Ulysses now needs copies of the 8 K,V heads. Switch to MHA at \(P = 8\): ring sends 4 times more. Now set \(N\) = 32K and \(P = 64\) on InfiniBand: only 512 tokens per rank, far below the 4,945 needed, so ring attention cannot hide its traffic.

    The Llama 3 choice: all-gather K and V

    Llama 3 does not use a ring. Each CP rank all-gathers the keys and values of the whole sequence, then computes attention for its local queries (with the zig-zag split for balance). [Certain] The authors chose this because it is simpler and works with different masks, such as document masks [Likely], and because with GQA the K and V tensors are much smaller than Q, so the all-gather is cheap. [Certain] Its volume per GPU, \(\frac{P-1}{P} N \cdot 2 d_{kv}\), is the same as the ring’s; the cost is memory for the full K and V of one layer at a time.

    Expert parallelism: cut the experts

    A mixture-of-experts layer (session 29) replaces one MLP with \(E\) expert MLPs and a router that sends each token to its top \(k\) experts. Most parameters of an MoE model sit in the experts, but each token uses only \(k\) of them. Expert parallelism places the \(E\) experts on \(\text{EP}\) GPUs, \(E/\text{EP}\) experts per GPU, introduced at scale by GShard (Lepikhin et al., 2020), which trained a 600B-parameter MoE translation model on 2,048 TPU v3 chips. [Certain]

    The attention part of the layer still runs data-parallel: each GPU has its own tokens. So each MoE layer becomes:

    Algorithm 4: one MoE layer with expert parallelism, forward pass on EP rank \(r\)
    1. input: this rank’s tokens \(X_r\) (\(T\) tokens), router weights (replicated), the \(E/\text{EP}\) experts that live here
    2. scores \(\leftarrow \softmax(X_r W_{\text{router}})\); keep the top-\(k\) experts and weights of every token
    3. sort the token copies by destination rank (the owner of each chosen expert); drop copies beyond an expert’s capacity
    4. dispatch all-to-all: send each copy to its expert’s rank; receive the copies that chose my experts
    5. run each local expert on the copies it received // a grouped matrix multiply
    6. combine all-to-all: send each result back to the rank its token came from
    7. \(y_t \leftarrow \sum_{\text{kept slots}} w_{t,e}\,\text{expert}_e(x_t)\), plus the residual // backward: the same two all-to-alls in reverse

    With uniform routing, a fraction \((\text{EP}-1)/\text{EP}\) of the copies leave the GPU. Per MoE layer and per GPU, in the forward pass:

    \[ V_{\text{dispatch}} = V_{\text{combine}} \approx T\,k\,h \cdot \frac{\text{EP}-1}{\text{EP}} \cdot 2 \ \text{bytes}, \qquad C = \Big\lceil \text{CF} \cdot \frac{T_{\text{all}}\,k}{E} \Big\rceil \tag{49.11} \]
    Read the symbols
    \(T\), \(T_{\text{all}}\)
    tokens on one GPU, tokens on all GPUs of the EP group together
    \(k\)
    experts per token (top-\(k\)); \(h\): hidden size
    \(C\)
    the capacity of one expert: the most token copies it accepts in this step. Fixed-size buffers make the all-to-all and the expert matmul static and fast.
    CF
    the capacity factor, for example 1.25 (Switch Transformer). Copies beyond \(C\) are dropped: they skip the expert and pass only through the residual connection. [Certain]

    For a Mixtral-like layer (\(h = 4096\), top-2, 8 experts on EP = 8) with 8,192 tokens per GPU, the dispatch sends \(8192 \times 2 \times 4096 \times 7/8 \times 2\) bytes \(= 117\) MB per GPU, and the four all-to-alls of forward and backward 470 MB, for every MoE layer. Unlike TP’s all-reduces this traffic is irregular (it depends on the router) and touches every pair of GPUs. Figure 5 routes real (seeded) tokens.

    Figure 5. Expert parallelism on 4 GPUs with 8 experts (E0, E1 on GPU 0; E2, E3 on GPU 1; and so on), top-2 routing, 16 tokens per GPU. Router logits are seeded random numbers plus a skew toward low-numbered experts. Left: how many token copies each GPU sends to each GPU in the dispatch all-to-all (the dashed diagonal stays local). Right: the load of each expert, the capacity line, and dropped copies in red.
    How to read Figure 5

    With no skew and \(\text{CF} = 1.25\) (capacity 20), loads are uneven just by chance; read the dropped count in the readout. Most copies cross to another GPU: with 4 ranks, about 3/4 are expected to. Now raise the skew to 2: experts E0 and E1 get 52 and 34 copies against an average of 16, capacity drops 46 copies (36%), and GPU 0 receives 40 of the 82 kept copies while GPU 3 receives 2. (Copies are kept first come, first served, in rank order, so GPU 0’s own tokens win.) Set CF to “none”: nothing is dropped, but GPU 0 now does much more expert work than GPU 3, and every other GPU waits for it. This is why MoE training needs a load-balancing loss or bias (session 29).

    Where expert parallelism lives in the mesh

    The EP group usually reuses GPUs of the data-parallel group: the attention weights are replicated over DP as usual, while the expert weights are split over EP and replicated over the remaining DP / EP copies. [Likely] So EP does not multiply the GPU count; it changes how the expert weights are stored. DeepSeek-V3 is the clearest real example: 2,048 H800 GPUs, 16-way pipeline parallelism, 64-way expert parallelism spread over 8 nodes, ZeRO-1 data parallelism, and no tensor parallelism. [Certain] With 256 routed experts per layer on 64 GPUs, each GPU holds 4 routed experts of each layer. Because the network between nodes (50 GB/s InfiniBand) is about 3.2 times slower than NVLink (160 GB/s) in their cluster, each token may be sent to at most 4 nodes, and 20 of the GPU’s streaming multiprocessors are reserved for communication kernels. [Certain]

    Putting it together: 3D and 4D parallelism

    3D parallelism means DP × TP × PP, the recipe of Megatron-LM: it trained a 1-trillion-parameter model at 502 PFLOP/s on 3,072 A100 GPUs, 52% of peak (about 163 TFLOPS per GPU). [Certain] 4D adds CP for long sequences, as in Llama 3. The main rule for the layout is simple: the more a dimension communicates, the closer its GPUs must be.

    1. TP innermost, inside one node: 4 all-reduces of activations per layer. Llama 3’s order is [TP, CP, PP, DP], from innermost to outermost. [Certain]
    2. CP next: K,V traffic every attention layer, but it can overlap with compute.
    3. PP: only point-to-point activations at stage boundaries, across nodes.
    4. DP outermost: one gradient reduction per step (or FSDP gathers that can be prefetched), which tolerates the most latency. [Certain]

    “Innermost” means neighboring rank numbers. With the order [TP, CP, PP, DP], TP changes fastest:

    \[ r = t + \text{TP}\big(c + \text{CP}\,(q + \text{PP}\cdot d)\big), \qquad t = r \bmod \text{TP},\ \ c = \lfloor r/\text{TP} \rfloor \bmod \text{CP},\ \dots \tag{49.12} \]
    Read the symbols
    \(r\)
    global rank, 0 to \(N_{\text{GPU}} - 1\); with 8 GPUs per node, ranks 0–7 are node 0
    \(t, c, q, d\)
    the rank’s coordinates: TP index, CP index, pipeline stage, DP index
    a group
    all ranks that share three coordinates and differ in the fourth; for example the TP group of rank \(r\) is all ranks with the same \(c, q, d\)

    With TP = 8 and 8 GPUs per node, each TP group is exactly one node. Figure 6 lets you click any GPU and see its four groups.

    TP CP PP DP
    Highlight the group of:
    Figure 6. The rank layout of formula (49.12), with 8 GPUs per node. Each square is one GPU, colored by its pipeline stage (s) and labeled with its DP index (d). Click (or Tab to and press Enter on) a GPU; the GPUs of its chosen group light up. The readout lists all four groups and says whether each stays inside one node.
    How to read Figure 6

    Defaults: \(\text{TP} \times \text{CP} \times \text{PP} \times \text{DP} = 2 \times 2 \times 2 \times 2 = 16\) GPUs in 2 nodes. GPU 0’s TP group is {0, 1}, its CP group {0, 2}, its pipeline group {0, 4} and its DP group {0, 8}: only the DP group leaves the node. Set TP = 8: now each node is one TP group, and every other group crosses nodes, which is what you want, since TP traffic is the heaviest. Then try the bad order in your head: if DP were innermost, the TP all-reduces would cross the network 4 times per layer.

    Real layouts

    RunGPUsTPCPPPDPSequenceResult
    Llama 3 405B, short context8,1928116648,192430 TFLOPS/GPU, 43% BF16 MFU
    Llama 3 405B, short context16,38481161288,192400 TFLOPS/GPU, 41% MFU
    Llama 3 405B, long context16,384816168131,072380 TFLOPS/GPU, 38% MFU
    DeepSeek-V3 (MoE, 671B total)2,0481–16ZeRO-1, with EP 644K (pretraining)no TP at all; DualPipe; FP8

    The Llama 3 rows are Table 4 of the paper; every configuration keeps 16M tokens per batch: \(64 \times 32 \times 8{,}192\), \(128 \times 16 \times 8{,}192\) and \(8 \times 16 \times 131{,}072\) all equal 16,777,216. [Certain] Notice the long-context row: CP grew from 1 to 16 and DP shrank from 128 to 8, so the same GPUs process the same number of tokens, just as fewer, longer sequences. The DeepSeek-V3 row combines facts from its report: 671B total parameters, 4K pretraining sequence length. [Likely]

    MFU (model FLOPs utilization: the share of the GPU’s peak FLOP/s that goes into the model’s own math, see session 51) falls from 43% to 38% as the setup grows. That is the cost of more communication and more bubbles. Figure 7 lets you try layouts for the 405B model.

    TP CP
    PP DP
    Sequence Interleave \(V\)
    Figure 7. A simple 4D planner for Llama 3 405B (405.85B parameters, 126 layers) with a fixed batch of 16M tokens and one sequence per micro-batch. Model states per GPU: 4 bytes per parameter of the GPU’s \(\text{TP} \times \text{PP}\) slice (BF16 weights and gradients) plus 12 bytes (FP32 master weights and Adam moments) sharded over \(\text{DP} \times \text{CP}\), like ZeRO-1. Activations, buffers and the embedding imbalance are not included; this is a teaching model, not Meta’s exact memory layout.
    How to read Figure 7

    Press “8K context”: 16,384 GPUs, 3.17B parameters per GPU, about 13.0 GB of model states, \(m = 16\) micro-batches and a bubble of 94% with \(V = 1\). Raise \(V\) to 4: 23%. Now set PP = 4: memory jumps to about 52 GB of model states, but the bubble drops. Press “128K context”: the same 16,384 GPUs, but now with DP = 8 and CP = 16; the memory of model states is the same, because CP ranks still divide the optimizer states. Set CP back to 1 with 128K: the warning tells you that the activations of a 128K sequence would have to fit on one TP group.

    Worked example: model states of Llama 3 405B per GPU

    Parameters from the config (hidden 16,384, MLP 53,248, 126 layers, 128 query heads and 8 K,V heads of 128 dimensions, vocabulary 128,256, untied embeddings): each layer has \(2 \cdot 16384^2 + 2 \cdot 16384 \cdot 1024 + 3 \cdot 16384 \cdot 53248 + 2 \cdot 16384 = 3{,}187{,}703{,}808\) parameters, the embedding and the output layer \(128{,}256 \times 16{,}384 = 2{,}101{,}346{,}304\) each. Total: \(126 \times 3{,}187{,}703{,}808 + 2 \times 2{,}101{,}346{,}304 + 16{,}384 = 405{,}853{,}388{,}800\).

    With TP = 8 and PP = 16, each GPU owns \(405.85\text{B}/128 = 3.17\)B parameters. Without sharding over DP, mixed-precision AdamW costs 16 bytes each: 50.7 GB. Sharding the 12 bytes of FP32 states over DP = 128 leaves \(4 \times 3.17 = 12.7\) GB plus \(12 \times 3.17\text{B}/128 = 0.30\) GB, about 13.0 GB, so most of the 80 GB is left for activations. The 16,384 GPUs are \(8 \times 1 \times 16 \times 128\).

    How to choose the degrees

    The Megatron-LM paper gives practical rules, and they are still the starting point: [Certain]

    1. Use TP up to the number of GPUs in a node (usually 8), and not beyond.
    2. Then use PP across nodes until the model states and activations fit.
    3. Use the remaining GPUs for DP (with ZeRO or FSDP to shard the optimizer states).
    4. Choose the micro-batch size and \(m\) together: larger micro-batches use the GPU better, more micro-batches shrink the bubble.

    Add CP when one sequence’s activations do not fit, and EP for MoE layers. Then measure: the best layout depends on the network, the model shape and the batch size, and real teams search over a few candidates. [Likely]

    Code: the ideas in runnable PyTorch

    We cannot run 4D parallelism on a laptop, but every piece of math above can be checked on one CPU. First, ring attention with the zig-zag split and the online softmax of (49.7), against plain causal attention, and the two Ulysses all-to-alls as tensor reshuffles. We ran it with PyTorch 2.8: the ring result matches to about \(10^{-7}\), and both all-to-all checks print True.

    import torch
    torch.manual_seed(0)
    N, d, P = 16, 8, 4                                # sequence length, head dim, CP ranks
    q, k, v = torch.randn(3, N, d).unbind(0)
    
    def full_causal(q, k, v):                         # reference: one GPU sees everything
        s = q @ k.T / d**0.5
        s = s.masked_fill(torch.ones(N, N).triu(1).bool(), float("-inf"))
        return torch.softmax(s, -1) @ v
    
    # zig-zag split: 2P chunks, rank i keeps chunks i and 2P-1-i (balances the causal work)
    chunks = torch.arange(N).chunk(2 * P)
    own = [torch.cat([chunks[i], chunks[2 * P - 1 - i]]) for i in range(P)]   # token positions
    
    def ring_attention(q, k, v):
        out = [None] * P
        for i in range(P):                            # each rank i (simulated one after another)
            qi, pos_q = q[own[i]], own[i]
            m = torch.full((len(pos_q), 1), float("-inf"))     # running max     (online softmax)
            l = torch.zeros(len(pos_q), 1)                      # running sum of exp
            acc = torch.zeros(len(pos_q), d)                    # running weighted sum of values
            for t in range(P):                        # ring step t: rank i holds the K,V block of rank j
                j = (i - t) % P
                kj, vj, pos_k = k[own[j]], v[own[j]], own[j]
                s = qi @ kj.T / d**0.5
                s = s.masked_fill(pos_k[None, :] > pos_q[:, None], float("-inf"))   # causal mask
                m_new = torch.maximum(m, s.max(-1, keepdim=True).values)
                scale = torch.exp(m - m_new).nan_to_num(0.0)    # rescale old partial results
                p_ = torch.exp(s - m_new).nan_to_num(0.0)
                l = l * scale + p_.sum(-1, keepdim=True)
                acc = acc * scale + p_ @ vj
                m = m_new
                # (on real GPUs: send K,V to rank i+1 and receive from rank i-1 while computing)
            out[i] = acc / l
        y = torch.empty(N, d)
        for i in range(P): y[own[i]] = out[i]
        return y
    
    print("ring vs full, max diff:", (ring_attention(q, k, v) - full_causal(q, k, v)).abs().max().item())
    
    # DeepSpeed-Ulysses: all-to-all turns "sequence-sharded, all heads" into "all tokens, some heads"
    H, T, hd = 8, 16, 4                               # heads, tokens, head dim; P = 4 ranks
    x = torch.randn(T, H, hd)
    seq_shards = list(x.chunk(P, dim=0))              # before: rank r has T/P tokens, all H heads
    def all_to_all(shards, split_dim, cat_dim):       # rank r sends piece j of its tensor to rank j
        pieces = [s.chunk(P, dim=split_dim) for s in shards]
        return [torch.cat([pieces[src][dst] for src in range(P)], dim=cat_dim) for dst in range(P)]
    head_shards = all_to_all(seq_shards, split_dim=1, cat_dim=0)   # after: all T tokens, H/P heads
    print("after all-to-all:", tuple(head_shards[0].shape),
          "equal to slicing heads:", torch.equal(head_shards[1], x[:, 2:4]))
    back = all_to_all(head_shards, split_dim=0, cat_dim=1)         # second all-to-all undoes it
    print("round trip exact:", all(torch.equal(a, b) for a, b in zip(back, seq_shards)))

    Second, expert parallelism: route tokens on 4 simulated ranks, dispatch them to the rank that owns each expert, run the experts there, combine, and compare with a dense MoE that has all experts in one place. It prints the 4 × 4 send matrix (96 copies, 71 of them cross ranks, with this seed) and a maximum difference of about \(6 \times 10^{-8}\).

    import torch
    torch.manual_seed(0)
    EP, E, k, d, T = 4, 8, 2, 16, 12                 # EP ranks, experts, top-k, width, tokens per rank
    experts = [torch.nn.Linear(d, d) for _ in range(E)]   # expert e lives on rank e // (E // EP)
    router = torch.nn.Linear(d, E, bias=False)
    x = [torch.randn(T, d) for _ in range(EP)]       # each rank has its own tokens (data parallel)
    
    def moe_dense(x):                                 # reference: every expert on one device
        w, idx = torch.softmax(router(x), -1).topk(k, -1)
        y = torch.zeros_like(x)
        for slot in range(k):
            for e in range(E):
                sel = idx[:, slot] == e
                y[sel] += w[sel, slot, None] * experts[e](x[sel])
        return y
    
    with torch.no_grad():
        # 1) route locally on every rank
        routes = []
        for r in range(EP):
            w, idx = torch.softmax(router(x[r]), -1).topk(k, -1)
            routes.append((w, idx))
        # 2) dispatch all-to-all: rank r sends each (token, slot) to the rank that owns the expert
        per = E // EP
        inbox = [[] for _ in range(EP)]               # what each destination rank receives
        send = torch.zeros(EP, EP, dtype=torch.long)  # send[src, dst] = number of token copies
        for r in range(EP):
            w, idx = routes[r]
            for t in range(T):
                for slot in range(k):
                    dst = int(idx[t, slot]) // per
                    inbox[dst].append((r, t, slot, int(idx[t, slot]), x[r][t]))
                    send[r, dst] += 1
        # 3) each rank runs its own experts on what it received
        results = [[(r, t, slot, experts[e](xt)) for (r, t, slot, e, xt) in inbox[dst]] for dst in range(EP)]
        # 4) combine all-to-all: send outputs back, weight them, add the k slots
        y = [torch.zeros(T, d) for _ in range(EP)]
        for dst in range(EP):
            for (r, t, slot, out) in results[dst]:
                y[r][t] += routes[r][0][t, slot] * out
        print("send matrix (rows: from rank, cols: to rank):\n", send)
        print("copies that leave their rank:", int(send.sum() - send.diag().sum()), "of", int(send.sum()))
        print("max diff vs dense MoE:", max((y[r] - moe_dense(x[r])).abs().max().item() for r in range(EP)))

    Third, the pipeline schedules of Figure 1 in pure Python, and the rank mapping (49.12). It prints a bubble equal to \((p-1)/m\) for both schedules, stored micro-batches [4, 4, 4, 4] / [8, 8, 8, 8] / [16, 16, 16, 16] for GPipe against [4, 3, 2, 1] for 1F1B, and coordinates (2, 0, 10, 9) for rank 1,234 of the Llama 3 layout.

    # Simulate pipeline schedules with F = 1 and B = 2 time units per stage (no communication time).
    def schedule(kind, p, m):
        order = []
        for s in range(p):                            # the list of work, in order, for stage s
            if kind == "gpipe":                       # all forwards, then all backwards
                order.append([("F", i) for i in range(m)] + [("B", i) for i in range(m)])
            else:                                     # 1F1B: warm up, then alternate, then drain
                w = min(p - s - 1, m)
                o = [("F", i) for i in range(w)]
                for i in range(w, m): o += [("F", i), ("B", i - w)]
                o += [("B", i) for i in range(m - w, m)]
                order.append(o)
        return order
    
    def simulate(kind, p, m, tF=1.0, tB=2.0):
        order, end, clock, ptr = schedule(kind, p, m), {}, [0.0] * p, [0] * p
        live, peak = [0] * p, [0] * p                 # micro-batches with stored activations
        while any(ptr[s] < len(order[s]) for s in range(p)):
            for s in range(p):
                if ptr[s] == len(order[s]): continue
                op, i = order[s][ptr[s]]
                dep = (("F", s - 1, i) if s > 0 else None) if op == "F" else \
                      (("B", s + 1, i) if s < p - 1 else ("F", s, i))
                if dep is not None and dep not in end: continue    # wait for the neighbor stage
                start = max(clock[s], end.get(dep, 0.0))
                clock[s] = end[(op, s, i)] = start + (tF if op == "F" else tB)
                live[s] += 1 if op == "F" else -1
                peak[s] = max(peak[s], live[s]); ptr[s] += 1
        T, ideal = max(clock), m * (tF + tB)
        return T, (T - ideal) / ideal, peak
    
    for kind in ["gpipe", "1f1b"]:
        for p, m in [(4, 4), (4, 8), (4, 16)]:
            T, bub, peak = simulate(kind, p, m)
            print(f"{kind:5s} p={p} m={m:2d}  time={T:5.1f}  bubble/ideal={bub:.3f}"
                  f"  formula (p-1)/m={(p-1)/m:.3f}  stored micro-batches per stage={peak}")
    
    def coords(rank, TP, CP, PP, DP):                 # order [TP, CP, PP, DP]: TP changes fastest
        tp = rank % TP; cp = rank // TP % CP; pp = rank // (TP * CP) % PP; dp = rank // (TP * CP * PP)
        return tp, cp, pp, dp
    print("rank 1234 of Llama 3 (TP8 CP1 PP16 DP128) -> (tp, cp, pp, dp) =", coords(1234, 8, 1, 16, 128))

    On a real cluster, PyTorch has the building blocks: init_device_mesh for the 4D mesh and torch.distributed.pipelining with ScheduleGPipe, Schedule1F1B and ScheduleInterleaved1F1B. [Certain] A sketch (not run here; it needs GPUs, and the model-splitting function is yours):

    # Sketch for a GPU cluster (not run here): a 4D mesh and a 1F1B pipeline in PyTorch.
    # Launch: torchrun --nnodes=8 --nproc_per_node=8 train.py   (64 GPUs)
    import torch, torch.distributed as dist
    from torch.distributed.device_mesh import init_device_mesh
    from torch.distributed.pipelining import PipelineStage, Schedule1F1B
    
    dist.init_process_group("nccl")
    # outer -> inner: the LAST dimension changes fastest, so "tp" gets neighboring ranks (one node)
    mesh = init_device_mesh("cuda", (2, 4, 1, 8), mesh_dim_names=("dp", "pp", "cp", "tp"))
    tp_mesh, pp_group = mesh["tp"], mesh["pp"].get_group()   # TP plan uses tp_mesh; FSDP uses mesh["dp"]
    
    stage_id, n_stages = mesh["pp"].get_local_rank(), 4
    blocks = build_blocks_for_stage(stage_id, n_stages)     # your code: this stage's layers only
    stage = PipelineStage(blocks, stage_id, n_stages, device=torch.device("cuda"), group=pp_group)
    schedule = Schedule1F1B(stage, n_microbatches=16, loss_fn=loss_fn)
    
    if stage_id == 0:
        schedule.step(tokens)                               # first stage feeds the micro-batches
    elif stage_id == n_stages - 1:
        losses = []
        schedule.step(target=labels, losses=losses)         # last stage computes the loss
    else:
        schedule.step()                                     # middle stages only pass activations
    optimizer.step(); optimizer.zero_grad()

    Libraries such as Megatron-LM (Megatron-Core), DeepSpeed and TorchTitan wire all of this together, including CP and EP. [Likely]

    Where this is used

    SettingTypical layoutWhy
    Dense pretraining, 100B+ parametersTP 8 in the node, PP 8–16 across nodes, interleaved 1F1B, DP / FSDP outsideModel states and activations must be split beyond one node; PP traffic is light enough for the network
    Long-context extension (64K–1M tokens)Add CP 4–16 (ring, all-gather K,V, or Ulysses inside the node); shrink DP to keep tokens per batchActivations of one sequence are too large; Llama 3 went from CP 1 to CP 16 for 128K [Certain]
    MoE pretraining (DeepSeek-V3, Mixtral-style models)EP across the DP group, PP, often little or no TPExpert weights dominate; all-to-all traffic needs to be overlapped and node-limited
    Vision-language modelsVision encoder in the first pipeline stage, or replicated; LLM layers split by TP and PP [Likely]The encoder is small but its stage must be balanced against LLM stages
    Video-language models and video encoders (video retrieval, action recognition, key-moment detection over long videos, Video-RAG)CP over the frame tokens, for example Ulysses or ring attention [Likely]An hour of video can be hundreds of thousands of visual tokens, a natural fit for sequence splitting
    Video diffusion transformersUlysses or USP over the spatio-temporal tokens [Likely]Full (non-causal) attention over long token sequences; USP was designed with such models in mind [Likely]
    Fine-tuning a 70B model on 2–4 nodesOften FSDP alone, or FSDP + TP; PP rarely [Likely]The pipeline bubble hurts with small batches; FSDP is simpler

    Common mistakes

    • Too few micro-batches. With \(m \lt p\) the pipeline never fills; even \(m = p\) wastes almost half the step. Check \((p-1)/(v\,m)\) before launching.
    • Thinking 1F1B removes the bubble. It has the same bubble as GPipe. It saves activation memory, which lets you raise \(m\). Only interleaving, zero-bubble or DualPipe schedules shrink the bubble for a given \(m\).
    • Unbalanced stages. Putting the same number of layers on the stage that also holds the embedding or the large output layer and loss. The slowest stage sets the pace for all.
    • Contiguous context split with a causal mask. The last rank does most of the work, and ring attention runs at its speed (57% efficiency at CP = 4 in Figure 3). Use the zig-zag split.
    • Ulysses degree above the head count. CP cannot exceed the number of attention heads, and K,V heads must be copied past their count (8 for Llama 3). Use ring or USP beyond that.
    • TP across nodes. Four activation all-reduces per layer over InfiniBand make TP the bottleneck. Keep TP inside the node and put PP or DP across nodes.
    • Ignoring MoE load balance. Without a balancing loss or bias, a few experts get most tokens: tokens are dropped (with a capacity limit) or one GPU slows everybody down (without one).
    • Wrong loss scaling over micro-batches. The loss of each micro-batch must be divided by \(m\) (and averaged over DP) so the summed gradients equal one large batch.

    Interview questions

    What is the pipeline bubble, and how big is it?basic
    The idle time when the pipeline fills at the start of a step and drains at the end. With \(p\) stages and \(m\) micro-batches, a step takes \((m + p - 1)(t_f + t_b)\) instead of \(m(t_f + t_b)\), so the bubble is \((p-1)/m\) of the ideal time, or \((p-1)/(m+p-1)\) of the step. It shrinks with more micro-batches, fewer stages, or an interleaved schedule, which divides it by the number of chunks \(v\).
    GPipe and 1F1B have the same bubble. Why does everyone use 1F1B?core
    Memory. GPipe runs all \(m\) forwards before any backward, so every stage stores the activations of \(m\) micro-batches. 1F1B starts a backward as soon as possible and alternates one forward with one backward, so stage \(s\) holds at most \(p - s\) micro-batches, independent of \(m\). Since the bubble falls with \(m\), 1F1B lets you raise \(m\) (shrink the bubble) without paying more activation memory. Both are synchronous: the gradients are exactly those of one large batch.
    How does the interleaved schedule reduce the bubble, and what does it cost?core
    Each GPU holds \(v\) non-adjacent chunks of layers instead of one block (GPU 0: layers 1–2 and 9–10, for example). A micro-batch visits each GPU \(v\) times, each time for \(1/v\) of the work, so filling and draining the pipe takes \(v\) times less time: the bubble becomes \((p-1)/(v\,m)\). The cost is \(v\) times more point-to-point messages and somewhat more activation memory on early stages; in Megatron’s version \(m\) must be a multiple of \(p\). Megatron-LM reports over 10% higher throughput.
    Why does pipeline parallelism go across nodes while tensor parallelism stays inside a node?core
    Traffic per unit of work. TP all-reduces an activation tensor of size \(b\,s\,h\) twice per layer in forward and twice in backward, on the critical path, so it needs NVLink. PP sends one activation tensor per micro-batch per stage boundary, and a stage has many layers; the sends are point-to-point and can overlap. So PP needs far less bandwidth and fits the slower network. Megatron even sends only \(1/\text{TP}\) of the tensor across nodes and all-gathers it inside the receiving node.
    Explain ring attention. Is it exact?core
    The sequence is split over \(P\) ranks; each keeps its query block. K and V blocks rotate around a ring: at each of \(P\) steps a rank computes attention of its queries against the block it holds, while sending that block to the next rank and receiving the next one. Partial results are merged with the online softmax (running max, running sum, rescaled running output), so the final result equals full attention exactly. Memory per rank depends on the block size only. The transfers hide behind compute if the block is large enough: \(c \ge (F/B)(d_{kv}/d)\), about 20K tokens per rank for MHA on an H100 over 50 GB/s InfiniBand, far less on NVLink.
    Why is a contiguous sequence split bad for causal attention, and what is the fix?advanced
    With a causal mask, late tokens attend to many more keys than early ones. The rank with the last chunk does most of the work, and since each ring step waits for the slowest rank, the layer runs at that rank’s speed: \(2 + 4(P-1)\) block-times instead of \(2P\) (57% efficiency at \(P = 4\)). The fix is to cut the sequence into \(2P\) chunks and give rank \(i\) chunks \(i\) and \(2P-1-i\). Then every rank does \(2P\) blocks in total and, in ring attention, the same 2 blocks per step. Llama 3 uses this split.
    Ring attention vs DeepSpeed-Ulysses: when would you pick each?advanced
    Ulysses does an all-to-all from a sequence split to a head split before attention (Q, K, V) and back after it, so attention itself runs locally with any kernel and mask. Its traffic per GPU, \((N/P)\frac{P-1}{P}(2d + 2d_{kv})\), shrinks with \(P\), but it sits on the critical path, needs all-to-all bandwidth (one node), and the degree is limited by the number of heads (K,V heads must be copied beyond their count). Ring sends \((P-1)(N/P)\,2d_{kv}\) per GPU, which does not shrink with \(P\) but overlaps with compute and has no head limit. The ratio is \(P\,d_{kv}/(d + d_{kv})\): Ulysses sends less for MHA, while ring can send less with strong GQA at small \(P\). In practice: Ulysses inside a node, ring across nodes (USP).
    What communication does expert parallelism need, and why is it hard?core
    Two all-to-alls per MoE layer in forward (dispatch tokens to the ranks of their chosen experts, combine the results back) and two in backward. Per GPU each moves about \(T\,k\,h\,(\text{EP}-1)/\text{EP}\) elements. It is hard because the sizes depend on the router (irregular, unbalanced), every pair of GPUs talks, and with large EP it crosses nodes. Remedies: load-balancing losses or biases, capacity factors (drop overflow), node-limited routing (DeepSeek-V3 sends each token to at most 4 nodes), and overlapping all-to-all with computation of another micro-batch (DualPipe).
    What is the capacity factor in MoE training?basic
    Each expert accepts at most \(C = \lceil \text{CF} \cdot T_{\text{all}}\,k/E \rceil\) token copies per step, where \(T_{\text{all}}\,k/E\) is the average load. Fixed capacity gives static buffer shapes, which makes the all-to-all and the expert matmul fast and memory predictable. Copies beyond \(C\) are dropped: they skip the expert and only go through the residual. A larger CF drops fewer tokens but wastes compute and memory on padding; Switch Transformer used values like 1.0 to 1.25 in training [Likely]. Some modern MoE systems avoid dropping altogether with variable-size grouped matmuls.
    You must train a dense 70B model on 1,024 H100s (8 per node) with 8K sequences. Propose a layout.advanced
    Start from the Megatron rules. TP = 8 inside each node. 70B with TP 8 is about 8.75B parameters per GPU, 140 GB at 16 bytes, so we need more splitting: either PP = 4 (2.2B per GPU, 35 GB of model states, or much less with the optimizer sharded over DP) or FSDP/ZeRO over DP instead of PP. With TP 8 × PP 4, DP = 32. CP = 1 for 8K tokens. Use interleaved 1F1B with enough micro-batches: if the batch is 4M tokens = 512 sequences, each DP replica gets 16 sequences, so \(m = 16\) and the bubble is \(3/(16v)\): 19% with \(v = 1\), 5% with \(v = 4\). Then measure MFU and compare against TP 8 × FSDP 128 without PP.
    Why does Llama 3 put the dimensions in the order [TP, CP, PP, DP]?core
    The innermost dimension gets neighboring ranks, which share a node and its NVLink. TP needs the most bandwidth and lowest latency (activation all-reduces in every layer), so it is innermost. CP comes next (K,V traffic every attention layer, partly overlapped). PP only sends activations at stage boundaries. DP (FSDP in Llama 3) is outermost because it tolerates the most latency: weights can be prefetched and gradients reduced in the background.
    What are zero-bubble schedules and DualPipe?advanced
    They split the backward into B (gradient for the input, needed immediately by the previous stage) and W (gradient for the weights, needed only by the optimizer). W can be delayed into the idle slots, which fills the bubble: Qi et al. report up to 23% more throughput than 1F1B at similar memory. DualPipe (DeepSeek-V3) also feeds micro-batches from both ends of the pipeline and overlaps one micro-batch’s forward with another’s backward so that MoE all-to-alls and pipeline sends hide behind computation. Its bubble is \((PP/2-1)(F\&B + B - 3W)\) at the cost of two copies of the weights.

    Exercises

    1. A pipeline has \(p = 8\) stages and \(m = 32\) micro-batches. Compute the bubble as a fraction of the ideal time and of the step, for 1F1B and for an interleaved schedule with \(v = 4\).
    2. Same pipeline. How many micro-batches of activations does stage 0 store with GPipe and with 1F1B?
    3. Ring attention for Llama 3 8B (\(d = 4096\), \(d_{kv} = 1024\)) on GPUs with 989 TFLOPS and 50 GB/s between ring neighbors. What is the smallest chunk per rank that hides the transfers, by (49.8)? With CP = 16, what sequence length is that?
    4. With the zig-zag split and \(P = 4\), which chunks does rank 1 own? Show that its total causal work is \(2P = 8\) blocks.
    5. A DeepSeek-V3-like layer: \(h = 7168\), top-8 routing, EP = 64, 4,096 tokens per GPU. Using (49.11), how many bytes does one dispatch all-to-all send per GPU in BF16 (ignoring node-limited routing)?
    6. With the order [TP, CP, PP, DP] and TP 4 × CP 2 × PP 2 × DP 2, give the coordinates of rank 13 and its DP group.
    7. Check that each Llama 3 configuration in the table uses its stated number of GPUs and 16,777,216 tokens per batch.
    Answerscheck
    1. 1F1B: \(7/32 = 0.219\) of the ideal time, \(7/39 = 17.9\%\) of the step. Interleaved: \(7/(4 \times 32) = 0.055\) of the ideal time. 2. GPipe: all 32. 1F1B: \(\min(p - 0, m) = 8\), four times less. 3. \(c \ge (989 \times 10^{12} / 50 \times 10^9) \times 1024/4096 = 4{,}945\) tokens per rank; with CP = 16 that is about 79K tokens (\(16 \times 4945 = 79{,}120\)). 4. Chunks 1 and 6 (\(2P - 1 - 1 = 6\)). Chunk 1 costs \(1 + \tfrac12\), chunk 6 costs \(6 + \tfrac12\); together 8. 5. \(4096 \times 8 \times 7168 \times 63/64 \times 2 = 462\) MB per GPU, for each dispatch (and again for the combine). 6. \(t = 13 \bmod 4 = 1\), \(c = \lfloor 13/4 \rfloor \bmod 2 = 1\), \(q = \lfloor 13/8 \rfloor \bmod 2 = 1\), \(d = \lfloor 13/16 \rfloor = 0\). Its DP group is all ranks with \(t = 1, c = 1, q = 1\): {13, 29}. 7. \(8 \cdot 1 \cdot 16 \cdot 64 = 8{,}192\); \(8 \cdot 1 \cdot 16 \cdot 128 = 16{,}384\); \(8 \cdot 16 \cdot 16 \cdot 8 = 16{,}384\). Tokens: \(64 \cdot 32 \cdot 8192 = 128 \cdot 16 \cdot 8192 = 8 \cdot 16 \cdot 131072 = 16{,}777{,}216\).

    Key takeaways

    • A big run multiplies degrees: \(N_{\text{GPU}} = \text{TP} \times \text{CP} \times \text{PP} \times \text{DP}\) (49.1); expert parallelism reuses the DP group.
    • Pipeline parallelism splits layers into stages and pays a bubble of \((p-1)/m\) (49.3). 1F1B keeps that bubble but caps activations at \(p\) micro-batches (49.4); interleaving divides the bubble by \(v\) (49.5); zero-bubble and DualPipe fill it with weight-gradient work.
    • PP sends only activations at stage boundaries (49.6), so it crosses nodes; TP stays inside the node.
    • Context parallelism splits the sequence. Ring attention passes K,V around a ring and merges with the online softmax (49.7), hiding transfers when \(c \ge (F/B)(d_{kv}/d)\) (49.8). Causal masks need the zig-zag split (49.9).
    • Ulysses swaps a sequence split for a head split with all-to-alls (49.10): its traffic shrinks with \(P\), but its degree is limited by the heads. USP combines Ulysses inside nodes and ring across nodes.
    • Expert parallelism needs two all-to-alls per MoE layer per pass, with capacity limits and load balancing (49.11).
    • Order the dimensions by traffic: [TP, CP, PP, DP] from inside to outside (49.12). Llama 3 405B: TP 8, CP 1 or 16, PP 16, DP 128 or 8; DeepSeek-V3: PP 16, EP 64, ZeRO-1, no TP.

    Key formulas

    \[ \frac{T_{\text{bubble}}}{T_{\text{ideal}}} = \frac{p-1}{v\,m}, \qquad c \ge \frac{F}{B}\cdot\frac{d_{kv}}{d}, \qquad \frac{V_{\text{ring}}}{V_{\text{Ulysses}}} = \frac{P\,d_{kv}}{d + d_{kv}} \]
    \[ V_{\text{a2a}} \approx T k h \,\frac{\text{EP}-1}{\text{EP}}, \qquad C = \Big\lceil \text{CF}\,\frac{T_{\text{all}}\,k}{E} \Big\rceil, \qquad N_{\text{GPU}} = \text{TP}\cdot\text{CP}\cdot\text{PP}\cdot\text{DP} \]

    References for this session

    1. Huang et al. (2018). GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism
    2. Narayanan et al. (2021). Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM
    3. Liu et al. (2023). Ring Attention with Blockwise Transformers for Near-Infinite Context
    4. Jacobs et al. (2023). DeepSpeed Ulysses: System Optimizations for Enabling Training of Extreme Long Sequence Transformer Models
    5. Hugging Face (Nanotron team) (2025). The Ultra-Scale Playbook: Training LLMs on GPU Clusters
    6. Huang et al. (2018). GPipe: Efficient Training of Giant Neural Networks using Pipeline Parallelism
    7. Narayanan et al. (2021). Efficient Large-Scale Language Model Training on GPU Clusters Using Megatron-LM
    8. Harlap, Narayanan et al. (2018). PipeDream: Fast and Efficient Pipeline Parallel DNN Training
    9. Narayanan et al. (2021). Memory-Efficient Pipeline-Parallel DNN Training (PipeDream-2BW and PipeDream-Flush)
    10. Qi, Wan, Huang and Lin (2024). Zero Bubble Pipeline Parallelism
    11. Liu et al. (2023). Ring Attention with Blockwise Transformers for Near-Infinite Context
    12. Jacobs et al. (2023). DeepSpeed Ulysses: System Optimizations for Enabling Training of Extreme Long Sequence Transformer Models
    13. Fang and Zhao (2024). USP: A Unified Sequence Parallelism Approach for Long Context Generative AI
    14. Lepikhin et al. (2020). GShard: Scaling Giant Models with Conditional Computation and Automatic Sharding
    15. Fedus et al. (2021). Switch Transformers
    16. Llama Team, Meta (2024). The Llama 3 Herd of Models
    17. DeepSeek-AI (2024). DeepSeek-V3 Technical Report
    18. Shoeybi et al. (2019). Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism
    19. Hugging Face (Nanotron team) (2025). The Ultra-Scale Playbook: Training LLMs on GPU Clusters