What does NCCL actually do when you call all-reduce, and how does it decide which algorithm to use?

TL;DR: On the first collective, NCCL discovers what the machine is: which GPUs share an NVLink domain, which are behind the same PCIe switch, which network interfaces are nearest each GPU. From that graph it builds rings and trees that follow the fast links, splits the message into several parallel channels so more than one link is busy at once, and chooses a wire protocol by message size. Then it selects an algorithm per call, again by size and rank count. Ring moves the theoretical minimum bytes and pays a latency for every one of its 2(N-1) steps, so it wins on large messages. Tree finishes in a number of steps proportional to the logarithm of the rank count, so it wins on small ones where latency dominates. At 1,024 ranks the ring's latency term alone is on the order of ten milliseconds, which is why a small all-reduce should never use one. Everything is overridable through NCCL_ALGO, NCCL_PROTO and the topology variables, and NCCL_DEBUG=INFO prints every decision it made.

How to approach it

Answer in the order the library works, because the four decisions depend on each other: topology first, then the rings and trees built on it, then channels, then the per-call algorithm and protocol. Give the two cost models rather than a rule, since the rule follows from them. Close with how to see the decisions, because that is what turns this from trivia into a debugging skill.

A strong answer

A typical situation: a team moves a job from one cluster to another with the same GPU count, and the same all-reduce takes three times longer. Nothing in their code changed. The new cluster reports network interfaces in a different order, so the rings NCCL built cross between sockets on every hop, and the library had no way to know that was wrong.

The four decisions:

1. topology discovery
   Reads the PCIe tree, NVLink connectivity, NUMA layout and the network interfaces, and
   builds a graph whose edges carry bandwidths. This is why the first collective in a job is
   slower than the rest: the discovery and the ring construction happen once.

2. rings and trees
   Lays out paths through that graph so that a step between neighbors uses the fastest
   available link. Inside a node it prefers NVLink at 900 GB/s per GPU; between nodes it uses
   the network interface nearest each GPU, which on a rail-optimized fabric keeps traffic on
   one rail.

3. channels
   Splits the message across several independent rings, so several links and several
   copy engines are busy at once. More channels raise bandwidth utilization and cost SM
   resources, which is why NCCL_MIN_NCHANNELS and NCCL_MAX_NCHANNELS exist.

4. algorithm and protocol, per call
   algorithm: ring, tree, collnet, or nvls where hardware supports it
   protocol: LL for tiny messages (data and a flag in one flit, no separate synchronization),
             LL128 for medium on NVLink-capable paths, Simple for large where full bandwidth
             matters and the extra flag traffic would cost

The two cost models that decide algorithm, which is the part worth being able to derive:

S bytes, N ranks, per-link bandwidth B, per-hop latency a

ring all-reduce
  each rank sends and receives 2(N-1)/N x S bytes in total, which is the minimum any
  algorithm can move, and it does so in 2(N-1) pipelined steps
  time  = 2(N-1)/N x S/B  +  2(N-1) x a
tree all-reduce
  a reduce up the tree and a broadcast down, so the step count is proportional to log2(N)
  time  ~ 2 x S/B  +  2 log2(N) x a

at N = 1,024 with a per-hop latency of about 5 microseconds:
  ring latency term  = 2 x 1,023 x 5 us = 10.2 ms, paid regardless of message size
  tree latency term  = 2 x 10 x 5 us    = 0.1 ms
so a 1 MB all-reduce over a ring spends 10 ms on latency to move bytes that need well under
a millisecond, and the tree is the correct choice. For a 140 GB gradient reduction the
bandwidth term dominates completely and the ring's minimal traffic wins
sanity: the crossover moves with rank count and with the fabric's latency, which is why NCCL
        keeps tuned tables rather than a single threshold, and why overriding NCCL_ALGO by
        hand is usually worse than leaving it alone

Ring vs Tree All-Reduce derives both models in full; NCCL and Collective Algorithms covers the rest of the library's behavior.

Seeing what it decided is the practical skill, and it is one environment variable:

NCCL_DEBUG=INFO
  prints the topology it found, the rings it built, the channel count, and for each collective
  the algorithm and protocol chosen. The lines to read:
    "NCCL INFO Channel 00 : 0[0] -> 1[1] -> 2[2] ..."   the ring, in rank order
    "NCCL INFO Using network IB"                        the transport it selected
    "NCCL INFO Ring 00 : ... via NET/IB/0/GDRDMA"       whether GPUDirect is in use
NCCL_DEBUG_SUBSYS=INIT,GRAPH,TUNING   narrows the output to the decisions
NCCL_ALGO=Tree / Ring                 force one, for an A-B test rather than as a setting
NCCL_PROTO=Simple / LL / LL128        same
NCCL_TOPO_FILE=...                    hand the library a topology description when its own
                                      discovery is wrong, which is the fix for the scenario above

In the scenario at the top, the ring printed by NCCL_DEBUG=INFO showed ranks ordered so that consecutive hops crossed the inter-socket link. Naming the interfaces per rank with NCCL_IB_HCA, or supplying a topology file, restored the intended layout. Topology-Aware Communication covers the mapping from ranks to hardware that this depends on.

The reversal condition: none of this tuning matters if the collective is not the bottleneck. Measure first with nccl-tests at the message sizes your job actually uses, compare against the fabric's rated bandwidth, and only then reach for the variables. A job whose all-reduce already runs at 90% of line rate has nothing to gain here, and the time is better spent on whether the reduction overlaps the backward pass at all.

What interviewers probe next

• "Why is the first collective slow?" Topology discovery, graph search and buffer allocation happen once. Some jobs deliberately run a small warm-up collective so the first real step is not distorted.
• "What is a channel?" One independent ring or tree through the topology. Several run concurrently so more than one link and copy engine is busy, at the cost of SMs used by the communication kernels.
• "When would you set NCCL_ALGO by hand?" To test a hypothesis, or when the tuning tables are wrong for an unusual fabric. As a permanent setting it usually loses, because the library adapts per message size and a fixed choice cannot.
• "What does NVLS do?" Uses NVSwitch hardware to perform the reduction in the switch rather than on the GPUs, which cuts the traffic each GPU must move on supported systems.

Common mistakes

• Describing all-reduce as a single algorithm rather than a selection made per call.
• Assuming the ring is always right, when its latency term is ten milliseconds at 1,024 ranks.
• Tuning environment variables before measuring against the fabric's rated bandwidth.
• Ignoring that the ring order printed at startup encodes the topology decision, which is where a misconfigured cluster shows itself.

Key takeaways

• Four decisions: topology discovery, ring and tree construction, channel count, then algorithm and protocol per call.
• Ring moves 2(N-1)/N times S per rank in 2(N-1) steps; tree finishes in steps proportional to log2(N). Ring wins on bandwidth, tree on latency.
• At 1,024 ranks the ring pays about 10 ms of latency regardless of size, so small collectives must not use it.
• NCCL_DEBUG=INFO prints the rings, the transport and the per-call choices, which is where a bad topology becomes visible.