N6Hard★ Distributed Infra Core · NCCL / DDPPart N · Data Pipelines & Production SysOps

Ring-AllReduce (Reduce-Scatter + All-Gather)

⚡Flashcard Drill➔

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?
Next: Vectorized Cumulative Cohort ARPU Matrix (SQL to NumPy) →
💡

Core Mental Anchor / Mnemonic

Reduce-scatter then all-gather over N ring slices -> approaches 2S per rank regardless of N.

📐 Mathematical Derivation & Core Formula

VRing=2⋅N−1N⋅Spayload,TRing=2(N−1)α+2N−1NSβV_{\text{Ring}} = 2 \cdot \frac{N - 1}{N} \cdot S_{\text{payload}}, \quad T_{\text{Ring}} = 2(N - 1)\alpha + 2\frac{N - 1}{N}\frac{S}{\beta}
### Bandwidth-Optimal Collectives Across NN GPUs
Splitting tensor size SS across NN ranks in a logical ring performs (N−1)(N-1) Reduce-Scatter hops plus (N−1)(N-1) All-Gather hops, moving 2N−1NS≈2S2\frac{N-1}{N}S \approx 2S bytes per GPU independently of cluster size NN once NN 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 α\alpha.

💻 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 2S/β2S/\beta, whereas latency (2N−2)α(2N-2)\alpha grows linearly with NN on tiny payloads; binary trees reduce hop latency to O(log⁡N)O(\log N).
⚡
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➔
← Prev: Multi-Tenant Token Bucket with Pre-Reserve & SettlementBack to Part N & All 105Next: Vectorized Cumulative Cohort ARPU Matrix (SQL to NumPy) →