Tree All-Reduce, in depth: NCCL's double binary tree built bit by bit, a simulator, the pipelined cost model and when rings win

Why trees: the latency term

Use the alpha-beta model: sending m bytes over one link costs alpha + m times beta, where alpha is a fixed per-message latency (software, NIC and switch hops) and beta is the inverse bandwidth. The ring all-reduce in Ring All-Reduce, in depth moves S/N bytes per step for 2(N - 1) steps, so its cost is 2(N - 1) alpha + 2S beta (N - 1)/N. The bandwidth term is optimal, and it hardly changes with N. The latency term grows linearly.

For small messages, such as late gradient buckets, optimizer scalars, or anything at thousands of ranks, the 2(N - 1) alpha term is the whole cost. A tree replaces it with roughly 2D alpha. The catch is bandwidth: in one binary tree the leaves, about half the ranks, send once and receive once, and their links sit idle most of the time.

Building the tree from rank bits

NCCL builds its first tree from the binary representation of each rank, with root 0. For a rank r, find its lowest set bit b. Its parent is (r xor b) or (2b): clear the low bit and set the next one up. If that falls outside the rank count, the parent is r xor b. Its children are r - b/2 and r + b/2, with the right child shrunk toward r if it falls out of range. Odd ranks have b = 1 and therefore no children: they are the leaves. Here is a direct Python port of ncclGetBtree from NCCL's src/graph/trees.cc:

def btree(n, rank):
    """Port of ncclGetBtree: returns (parent, child0, child1); -1 means none."""
    bit = 1
    while bit < n and not (bit & rank):
        bit <<= 1
    if rank == 0:
        return -1, -1, (bit >> 1 if n > 1 else -1)
    up = (rank ^ bit) | (bit << 1)
    if up >= n:
        up = rank ^ bit
    low = bit >> 1
    d0 = -1 if low == 0 else rank - low
    d1 = -1 if low == 0 else rank + low
    while d1 >= n:
        d1 = -1 if low == 0 else rank + low
        low >>= 1
    return up, d0, d1

For 14 ranks this produces the tree drawn in NCCL's source comment. Rank 0 is the root with a single child, 8. Rank 8 has children 4 and 12, rank 4 has 2 and 6, rank 12 has 10 and 13, and every odd rank is a leaf. The depth is 4 for 14 or 16 ranks and 6 for 64. The pattern needs no communication to compute and keeps neighbouring ranks, which usually share a leaf switch, close together in the tree.

The second tree: mirror or shift

The double binary tree, from Sanders, Speck and Träff's two-tree algorithms, fixes the idle leaves. Split the buffer in half and give each half its own tree, built so that ranks which are leaves in one tree are interior in the other. NCCL's ncclGetDtree does it in two ways. If N is even it mirrors the first tree, mapping rank r to N - 1 - r. Odd ranks, the leaves of tree 0, become even positions and so interior nodes of tree 1. If N is odd, mirroring would map an even rank to an even rank, so it shifts every rank by one instead.

def dtree(n, rank):
    """Port of ncclGetDtree: tree 0 is btree; tree 1 is mirrored (n even) or shifted (n odd)."""
    t0 = btree(n, rank)
    if n % 2:
        u, a, b = btree(n, (rank - 1) % n)
        t1 = tuple(-1 if x == -1 else (x + 1) % n for x in (u, a, b))
    else:
        u, a, b = btree(n, n - 1 - rank)
        t1 = tuple(-1 if x == -1 else n - 1 - x for x in (u, a, b))
    return t0, t1

Running this for N from 2 to 64 shows that for even N no rank is interior in both trees. For odd N such as 7 or 13, exactly one rank is, so the balance is close but not perfect.

Traffic per rank and a pipelined cost model

Count bytes per rank. Each tree carries S/2 bytes. A rank that is interior in tree 0 receives S/2 from each of two children and S/2 from its parent on the way down, and sends S/2 up and S/2 to each child. As a leaf in tree 1 it sends S/2 up and receives S/2 down. In total it receives 2S and sends 2S, the same as the ring's 2S (N - 1)/N for large N. NVIDIA's phrasing, that each rank receives at most half the data twice and sends at most half the data twice, counts one phase: in the reduce a rank takes S/2 from each child and sends S/2 up each tree. The broadcast repeats that in reverse.

Time needs pipelining. Cut each half into m chunks of c bytes, so m = S/(2c). Chunk k starts up the tree while chunk k - 1 is one level higher, and the broadcast of a chunk starts as soon as the root finishes it. The last chunk reaches the leaves after about 2D + m - 1 chunk steps. In steady state a rank's NIC receives about 4c bytes per step across both trees, which gives this model:

T_tree(S) ~= (2D + m - 1) * (alpha + 4 * c * beta),   m = S / (2c)
T_ring(S)  = 2(N - 1) * alpha + 2 * S * beta * (N - 1) / N

Small chunks shorten the pipeline fill but pay alpha many times; large chunks do the reverse. As S grows the tree cost approaches 2S beta, the ring's limit, so the tree's structural advantage is only the latency term. In practice trees also lose some bandwidth to fan-in, because two children arrive at the same NIC, to more connections per rank, and to the reduction work on the critical path. That is why NCCL measures and switches rather than always using trees.

Worked example: where the crossover falls

Plug illustrative numbers into the model. Assume alpha = 10 microseconds per hop and 25 GB/s per NIC, about a 200 Gb/s link. Neither is a measurement of any particular cluster. Try 16 nodes (D = 4) and 64 nodes (D = 6), and for the tree pick the best power-of-two chunk size. These figures come from running the formulas, not from a benchmark:

The crossover moves with scale: 16 MiB favours the ring at 16 nodes and the tree at 64, because the ring's latency term grows with N and the tree's with log2 N. At large messages the two are close, so real bandwidth effects decide. A fixed threshold cannot be right. NCCL 2.4 shipped NCCL_TREE_THRESHOLD, but it was removed in 2.5 in favour of an internal cost model that picks the algorithm and protocol per call from message size, rank count and topology.

How NCCL runs trees on a real cluster

In NCCL the tree spans nodes, not GPUs: ncclGetDtree is called with the node count and the node index. Inside each node the GPUs form a chain over NVLink, and the chain's head carries the inter-node tree edges. A reduction flows up the chain to that GPU, up the inter-node tree, then back down both. NCCL's topology search also chooses whether one GPU or two carry the node's NIC traffic, and work is spread over several channels so several NICs and SMs run in parallel.

Algorithm and protocol selection is controlled by NCCL_ALGO and NCCL_PROTO. NCCL_ALGO takes a comma-separated list from Ring, Tree, CollnetChain, CollnetDirect, NVLS, NVLSTree and PAT, depending on version, and a leading ^ excludes instead of includes. NCCL_PROTO takes LL, LL128 and Simple. The low-latency LL protocols matter for trees, because trees win on small messages. NVIDIA discourages setting NCCL_PROTO except to rule out a suspect protocol; forcing LL128 on unsupported platforms can corrupt data.

# Compare algorithms on the same allocation with nccl-tests (one process per GPU)
mpirun -np 64 -N 8 ./build/all_reduce_perf -b 8 -e 1G -f 2 -g 1          # NCCL decides
# OpenMPI: -x exports a variable to every remote rank (srun exports the environment by default)
mpirun -np 64 -N 8 -x NCCL_ALGO=Ring ./build/all_reduce_perf -b 8 -e 1G -f 2 -g 1
mpirun -np 64 -N 8 -x NCCL_ALGO=Tree ./build/all_reduce_perf -b 8 -e 1G -f 2 -g 1

# See which algorithm and protocol NCCL picked, and the tree it built
mpirun -np 64 -N 8 -x NCCL_DEBUG=INFO -x NCCL_DEBUG_SUBSYS=INIT,TUNING ./your_training_job

A simulator to check it

Before trusting any tree code, simulate it. This reduces up and broadcasts down each tree on plain lists; on random buffers for every N from 2 to 64 it leaves the exact sums on every rank.

def tree_allreduce(bufs, tree):
    """Reduce to the root, then broadcast. tree[r] = (parent, c0, c1)."""
    n = len(bufs)
    kids = {r: [c for c in tree[r][1:] if c != -1] for r in range(n)}
    root = next(r for r in range(n) if tree[r][0] == -1)

    def reduce(r):                     # children before parent
        acc = list(bufs[r])
        for c in kids[r]:
            acc = [x + y for x, y in zip(acc, reduce(c))]
        return acc

    total, out, stack = reduce(root), [None] * n, [root]
    while stack:                       # broadcast top-down
        r = stack.pop()
        out[r] = list(total)
        stack.extend(kids[r])
    return out

def double_tree_allreduce(bufs):
    n, half = len(bufs), len(bufs[0]) // 2
    trees = [dtree(n, r) for r in range(n)]
    lo = tree_allreduce([b[:half] for b in bufs], [t[0] for t in trees])
    hi = tree_allreduce([b[half:] for b in bufs], [t[1] for t in trees])
    return [lo[r] + hi[r] for r in range(n)]

Trees and rings add partial sums in different orders, so switching algorithms changes floating-point results in the last bits, which breaks bitwise reproducibility tests unless you pin NCCL_ALGO.

Failure modes

In a ring a slow rank slows every step equally. In a tree an interior rank is on the critical path for its whole subtree, so a throttled GPU or flapping link can appear as a tree-only regression. Compare per-algorithm busbw when hunting a slow node.

Trade-offs

Rings give the best bandwidth and pay latency linear in N. Double binary trees give logarithmic latency at nearly the same theoretical bandwidth, with fan-in costs in practice. In-network reduction removes most of the traffic altogether, by summing in the switch: CollNet with SHARP over InfiniBand, and NVLS over NVLink switches. It needs that hardware and its resource limits, as covered in SHARP in-network reductions. The physical network matters too: tree edges crossing the spine of a fat tree see more contention than edges inside a leaf. For communicator setup, transports and fault handling see NCCL, in depth.

What to do next

1. Port btree and dtree, print the trees for your node count, and run the simulator.
2. Run all_reduce_perf from 8 bytes to 1 GB three times: unset, NCCL_ALGO=Ring and NCCL_ALGO=Tree. Plot busbw and latency, and find your crossover.
3. Check NCCL_DEBUG=INFO with the TUNING subsystem in a real job, to see which algorithm and protocol your gradient buckets actually use.
4. Fit alpha and beta to your small- and large-message results, and use the cost model to predict the crossover at the next cluster size.
5. Leave NCCL_ALGO and NCCL_PROTO unset in production unless a measured regression justifies pinning them.
6. Add per-rank collective timing so a slow interior node is visible before it costs a day.