M3-080M3: Deep Learning FoundationsDistributed Training BasicsMedium
⚡Flashcard Drill➔Mastery:

Collective Communication Primitives: All-Reduce, All-Gather, and Reduce-Scatter

🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
Next: M3-081 →
📐 Mathematical Definition
all-reduce=reduce-scatter+all-gather\text{all-reduce}=\text{reduce-scatter}+\text{all-gather}
⚡ One-Sentence Core Answer
All-Reduce computes sum across all ranks and distributes the full result to all; Reduce-Scatter computes sum and scatters shards; All-Gather collects distributed shards onto every rank.

📌 Key Takeaways

  • •
    All-Reduce: combines Reduce + Broadcast; transforms NN input buffers of size SS into NN identical summed buffers of size SS
  • •
    Reduce-Scatter: sums buffers across ranks and partitions the result so rank ii receives only shard ii (size S/NS/N)
  • •
    All-Gather: the exact inverse of Reduce-Scatter; collects NN local shards of size S/NS/N to reconstruct full buffer of size SS on all ranks

📐 Mathematical Derivations

Mathematical Identity and Ring Algorithms (Patarasuk & Yuan, 2009):
Let NN be the number of ranks, and SS be tensor size in bytes.
① The Core Equivalence:
All-Reduce(X)≡All-Gather(Reduce-Scatter(X))\text{All-Reduce}(X) \equiv \text{All-Gather}\Big( \text{Reduce-Scatter}(X) \Big).
② Ring-Based Communication Complexity:
Arrange NN GPUs in a logical ring. Each rank sends and receives S/NS/N bytes per step over N−1N-1 steps.
- Reduce-Scatter: Each rank starts with SS bytes. After N−1N-1 transfers, rank ii holds the reduced sum of slice ii. Communication volume per rank: 2N−1NS≈S2 \frac{N-1}{N} S \approx S bytes.
- All-Gather: Each rank starts with a shard of size S/NS/N. Over N−1N-1 ring steps, shards circulate until every rank has the full SS bytes. Communication volume per rank: N−1NS≈S\frac{N-1}{N} S \approx S bytes.
- Ring All-Reduce: Executes Reduce-Scatter followed by All-Gather. Total data transmitted per rank: 2(N−1N)S≈2S2 \left( \frac{N-1}{N} \right) S \approx 2 S bytes, completely independent of the number of ranks NN!

🏭 Production Trade-offs

Role in ZeRO / FSDP Architecture: ZeRO-3 decomposes standard DDP's All-Reduce into its constituent halves: Reduce-Scatter during backward pass (sharding gradients across ranks) and All-Gather during forward and backward passes (reconstructing parameter shards dynamically).
⚠️ Common Interview Pitfalls
  • ✕
    Assuming All-Reduce communication time scales linearly with cluster node count NN; under Ring-AllReduce, per-GPU transfer volume is independent of NN
  • ✕
    Confusing Reduce-Scatter (which performs algebraic summation) with Scatter (which merely partitions unsummed data)
🎯 Interviewer Follow-up Inquiries
  • ?
    Why is the communication volume per GPU under Ring-AllReduce asymptotically 2S2S, independent of cluster size NN?
  • ?
    How does Tree-AllReduce achieve lower latency than Ring-AllReduce for small message sizes?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM3-079: ZeRO (Zero Redundancy Optimizer): The Three Sharding Stages Explained📋 Back to BankNext →M3-081: Gradient Accumulation vs Data Parallelism: Mathematical Equivalence and Nuances