N6Hard★ Distributed Infra Core · NCCL / DDPPart N · Data Pipelines & Production SysOps
Ring-AllReduce (Reduce-Scatter + All-Gather)
Simulate two-phase bandwidth-optimal Ring AllReduce achieving asymptotically constant 2S per-rank payload transfer.
⏱️ Time:
O(N^2)💾 Space:
O(N^2)🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
import numpy as np
def ring_allreduce_sim(grad_chunks_per_rank: np.ndarray) -> tuple:
"""
Simulate bandwidth-optimal Ring AllReduce (Reduce-Scatter + All-Gather) across N ranks.
grad_chunks_per_rank: shape (N, N) where row r holds rank r's N partitioned chunks.
Returns (reduced_matrix_shape_N_N, total_bytes_moved_in_elements) with exact sum on every rank.
"""
n_ranks, n_chunks = grad_chunks_per_rank.shape
assert n_ranks == n_chunks, "Payload must split cleanly into N chunks"
buf =
elements_sent = 0
# Phase 1: Reduce-Scatter (N - 1 ring hops)
for step in range(n_ranks - 1):
next_buf = buf.copy()
for r in range(n_ranks):
chunk_idx = (r - step) % n_ranks
dst = (r + 1) % n_ranks
next_buf[dst, chunk_idx] += buf[r, chunk_idx]
elements_sent += 1
buf = next_buf
# Phase 2: All-Gather (N - 1 ring hops broadcast completed shards)
for step in range(n_ranks - 1):
next_buf = buf.copy()
for r in range(n_ranks):
chunk_idx = (r + 1 - step) % n_ranks
dst =
next_buf[dst, chunk_idx] = buf[r, chunk_idx]
elements_sent += 1
buf = next_buf
return buf, elements_sent
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: Why does NCCL combine Tree and Ring topologies at very large node counts?
💡
Core Mental Anchor / Mnemonic
Reduce-scatter then all-gather over N ring slices -> approaches 2S per rank regardless of N.
📐 Mathematical Derivation & Core Formula
### Bandwidth-Optimal Collectives Across GPUs
Splitting tensor size across ranks in a logical ring performs Reduce-Scatter hops plus All-Gather hops, moving bytes per GPU independently of cluster size once grows large.
Splitting tensor size across ranks in a logical ring performs Reduce-Scatter hops plus All-Gather hops, moving bytes per GPU independently of cluster size once grows large.
🔄 Tensor Dimensions & Shape Flow
chunks [N, N] -> N-1 reduce-scatter hops -> N-1 all-gather hops -> uniform reduced matrix [N, N]
🛡️ Numerical Stability & Pitfalls Checklist
- Snapshot ring buffers per hop cleanly so in-flight receives never overwrite un-forwarded shard inputs within the same round.
- Fuse tiny gradient tensors into 25MB buckets in real DDP to amortize per-hop network latency .
💻 Reference Code Implementation
import numpy as np
def ring_allreduce_sim(grad_chunks_per_rank: np.ndarray) -> tuple:
"""
Simulate bandwidth-optimal Ring AllReduce (Reduce-Scatter + All-Gather) across N ranks.
grad_chunks_per_rank: shape (N, N) where row r holds rank r's N partitioned chunks.
Returns (reduced_matrix_shape_N_N, total_bytes_moved_in_elements) with exact sum on every rank.
"""
n_ranks, n_chunks = grad_chunks_per_rank.shape
assert n_ranks == n_chunks, "Payload must split cleanly into N chunks"
buf = grad_chunks_per_rank.astype(np.float64).copy()
elements_sent = 0
# Phase 1: Reduce-Scatter (N - 1 ring hops)
for step in range(n_ranks - 1):
next_buf = buf.copy()
for r in range(n_ranks):
chunk_idx = (r - step) % n_ranks
dst = (r + 1) % n_ranks
next_buf[dst, chunk_idx] += buf[r, chunk_idx]
elements_sent += 1
buf = next_buf
# Phase 2: All-Gather (N - 1 ring hops broadcast completed shards)
for step in range(n_ranks - 1):
next_buf = buf.copy()
for r in range(n_ranks):
chunk_idx = (r + 1 - step) % n_ranks
dst = (r + 1) % n_ranks
next_buf[dst, chunk_idx] = buf[r, chunk_idx]
elements_sent += 1
buf = next_buf
return buf, elements_sent
🧪 Runnable Assertions & Validation
Copy and run directly in Python / Jupyter:
import numpy as np
# 4 ranks, each holding 4 local gradient chunks
mat = np.array([
[1.0, 2.0, 3.0, 4.0],
[10.0, 20.0, 30.0, 40.0],
[100.0, 200.0, 300.0, 400.0],
[1000.0, 2000.0, 3000.0, 4000.0],
])
out, sent = ring_allreduce_sim(mat)
expected = mat.sum(axis=0, keepdims=True).repeat(4, axis=0)
assert np.allclose(out, expected), f"Ring AllReduce mismatch: {out} vs {expected}"
# Each rank sends 2*(N-1) single-chunk messages -> 2*3*4 = 24 element-chunks total
assert sent == 2 * (4 - 1) * 4, f"Expected 24 chunk transfers, got {sent}"
print("✓ Ring AllReduce Reduce-Scatter + All-Gather assertion passed")🎯 Core Follow-up Inquiries & Reference Answers
Q1:Why does NCCL combine Tree and Ring topologies at very large node counts?
Ring minimizes bandwidth bottlenecks , whereas latency grows linearly with on tiny payloads; binary trees reduce hop latency to .
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.