Synthesizing Optimal Collective Algorithms

1 Introduction

• NCCL's manually written ring and tree algorithms do not necessarily perform best on different topologies, and extending them across primitives and hardware is infeasible.The paper identifies Alltoall and diverse hardware topologies as examples of the manual-extension challenge.Source: §1 · pp. 1–2
• SCCL encodes feasible algorithms for a graph topology and communication primitive as a quantifier-free SMT formula, then searches the latency–bandwidth Pareto frontier.The search trades off minimizing communication steps against decreasing the communication granularity at each step.Source: §1 · p. 2
• For combining collectives such as Reduce, SCCL reduces synthesis to the non-combining case, generalizing the construction of Reduce by inverting Broadcast.The encoding targets quantifier-free linear integer arithmetic.Source: §1 · p. 2
• On DGX-1, SCCL synthesizes latency-optimal 2-step Allgather and 4-step Allreduce, plus bandwidth-optimal 3-step Allgather and 6-step Allreduce algorithms.The paper reports these algorithms have no known counterparts at the same latency–bandwidth tradeoff and that SCCL beats NCCL in almost all cases.Source: §1 · p. 2
• The paper formalizes synthesis, develops scalable encodings, and generates implementations for NVIDIA and AMD GPUs.Its evaluation compares generated algorithms against NCCL on common server topologies for deep-learning workloads.Source: §1 · p. 2

2 Overview

• The overview traces how latency- and bandwidth-optimal algorithms can be synthesized, using DGX-1 Allgather as its running example.It develops the example through collective primitives, topology, a cost model, and two algorithm constructions.Source: §2 · p. 2

2.1 Collective Communication Primitives

• Allgather transfers each node's input data to every node; collective cooperation can be more efficient than each node sending independently.The efficiency depends on the network topology.Source: §2.1 · pp. 2–3

2.2 Topology

• DGX-1 has eight GPUs in two fully connected groups, with four inter-group links; its links form six logical single-NVLink rings.NCCL implements Allgather by running six simultaneous ring algorithms.Source: §2.2 · p. 3

2.3 Cost Model

• The cost model writes an algorithm's cost as a latency term plus a message-size-scaled bandwidth term, and defines optimality by minimizing either cost without worsening the other.The model expresses cost as a·α + b·L·β; Pareto optimality excludes another algorithm with equal latency and lower bandwidth cost, or equal bandwidth and lower latency cost.Source: §2.3 · p. 3

2.4 Bandwidth-Optimal Algorithm for DGX-1

• DGX-1's six-ring Allgather is bandwidth-optimal because each node must receive at least 7·L bytes over six incoming NVLinks; synthesis also finds a previously unknown Pareto-optimal algorithm among k-synchronous algorithms.The six-ring algorithm uses one chunk per ring and takes seven steps; the synthesized algorithm is presented as a distinct construction.Source: §2.4 · p. 3

2.5 Latency-Optimal Algorithm for DGX-1

• The synthesized Allgather algorithm is latency-optimal because the DGX-1 topology has diameter 2, and it is Pareto-optimal among k-synchronous algorithms.The paper states that a latency-optimal DGX-1 algorithm was not previously known.Source: §2.5 · p. 3

3.2 Non-combining Collective Instance

• A SynColl instance specifies chunk counts, steps and rounds, the node topology and bandwidth constraints, and pre- and postconditions for the collective.The bandwidth relation can express point-to-point links, aggregate outgoing bandwidth, or shared buses.Source: §3.2 · p. 4

3.2.2 Collective Specification.

• Collective specifications use global chunk identifiers and pre/post relations; for Allgather, Scattered input placement must satisfy the All destination relation.The global numbering also accommodates collectives without a single per-node chunk count, such as Allgatherv.Source: §3.2.2 · p. 5, Table 2 · p. 5

3.3 Candidate Solution

• A candidate algorithm pairs step-round counts with scheduled chunk sends, which update node holdings from the precondition toward the required postcondition under bandwidth limits.The total rounds across steps equal R, and each step’s sends must respect its bandwidth allowance.Source: §3.3 · p. 5

3.4 SMT Encoding for Non-combining Collectives

• The SMT encoding searches candidate schedules using integer availability times and Boolean send choices, with mixed constraints helping Z3 scale beyond an initial Boolean-only encoding.If the encoded instance is unsatisfiable, no algorithm exists for that instance.Source: §3.4 · pp. 5–6

3.5 Combining Collectives

• Combining collectives with a single root per chunk can be synthesized by reversing a related non-combining algorithm; Allreduce is built from Reducescatter followed by Allgather.The inversion procedure does not directly cover Allreduce because its result is replicated to all nodes.Source: §3.5 · p. 6

3.6 Cost Model

• The cost model evaluates schedules using link latency and bandwidth terms, with each step’s rounds scaling the data-transfer component.The model uses α for link latency and β for time to send a byte along a unit-bandwidth link.Source: §3.6 · p. 6

3.7 Pareto-optimal Algorithms

• The algorithm’s steps and rounds jointly determine its latency and bandwidth costs, so latency- or bandwidth-optimal schedules need not lie on the Pareto frontier.The frontier’s preferred algorithm can depend on input size and the topology’s α and β parameters.Source: §3.7 · p. 6
• The synthesis framework searches k-synchronous algorithms for Pareto-optimal tradeoffs between latency and bandwidth cost, using topology lower bounds to guide enumeration.For some topologies and collectives, the procedure may not terminate because the Pareto frontier can contain an unbounded number of algorithms.Source: §3.7 · p. 6

4 Code Generation

• SCCL converts each synthesized schedule’s chunk, source, destination, step, and reduction commands into SPMD multi-process C++ code with CUDA kernels.Each GPU has its own code, and CUDA IPC shared pointers enable communication through remote GPU memory.Source: §4 · p. 7
• DMA transfers can provide higher bandwidth at higher initial latency, while push transfers were found up to 10% faster than pull transfers.On NVLink, DMA-engine bandwidth is about 10% better than kernel-copy bandwidth; push may require extra memory.Source: §4 · p. 7
• SCCL fuses communication steps into one kernel and uses shared flags for fine-grained GPU synchronization, avoiding the overhead of launching a separate kernel per step.A system fence precedes the remote flag that signals transfer completion.Source: §4 · p. 7
• The number of thread blocks assigned per link affects performance across input sizes, so SCCL empirically searches configurations for each size.The same number of blocks is used for a link at each step.Source: §4 · p. 7

5 Evaluation

• The evaluation examines topology modeling, implementation transports, and synthesized Pareto-frontier algorithms on two multi-GPU systems with proprietary interconnects.The systems are described as being used for training large deep-learning models.Source: §5 · p. 7

5.1 Hardware

• The hardware section introduces the topologies modeled for the NVIDIA and AMD machines.The subsequent system descriptions specify their GPUs, processors, memory, and interconnects.Source: §5.1 · p. 7

5.1.1 NVIDIA DGX-1: 8 V100 GPUs.

• The DGX-1 has eight V100 GPUs connected by two non-overlapping NVLink cycles; PCIe links to the CPUs are excluded from the model.Each GPU has six 25 GB/s NVLink ports; the passage gives approximate per-GPU NVLink and PCIe bandwidths of 150 GB/s and 14 GB/s, respectively.Source: §5.1.1 · p. 7

5.1.2 Gigabyte Z52: 8 AMD MI50 GPUs.

• The Gigabyte Z52 has eight MI50 GPUs; its xGMI links form two disconnected islands, and PCIe 4.0 links connect the rings.The system uses PCIe links with measured bandwidth of approximately 27 GB/s, near xGMI’s approximately 33 GB/s.Source: §5.1.2 · pp. 7–8, Figure 3 · p. 8

NVIDIA DGX-1 bandwidth model

• For DGX-1, the model assigns capacity one per round to each NVLink pair in one cycle and capacity two to pairs in the other.Each NVLink connection is point-to-point.Source: §5.2 · p. 8

Gigabyte Z52 bandwidth model

• For the Z52, SCCL models direct xGMI connections and PCIe-connected rings, while omitting xGMI routing and shared-link effects from the topology model.The passage says the model ignores dotted xGMI connections because it could not use xGMI and PCIe simultaneously; it also describes an optional per-socket PCIe constraint.Source: §5.2 · p. 8
• The AMD model assigns the same β cost to xGMI and PCIe and assumes every link can send one chunk per step.This is the stated simplifying link-capacity assumption for the modeled topology.Source: §5.2 · p. 8

Baselines

• NCCL 2.7.8-1 and RCCL from ROCm 3.5.0 serve as the NVIDIA and AMD baselines, respectively.RCCL is a ROCm HIP port of NCCL; both libraries share core algorithms and differ in how they interact with hardware.Source: §5.3 · p. 8

NCCL algorithms

• NCCL’s algorithms are based on rings or trees, but the DGX-1 table lists rings because its trees are simple paths and no better than rings for any input size.The chunk and step analysis comes from manual inspection of NCCL source.Source: §5.3 · p. 8

SCCL coverage

• SCCL synthesizes NCCL’s collectives and also supports Scatter, Gather, and Alltoall.For Reduce and Broadcast, NCCL uses pipelined algorithms whose bandwidth optimality improves as the multiplier increases.Source: §5.3 · p. 8

5.4 Synthesizing Collective Algorithms

• Tables 4 and 5 enumerate synthesized algorithms across collectives and latency–bandwidth trade-offs for DGX-1 and AMD hardware.The tables include chunks, steps, rounds, and synthesis time; Scatter and Reducescatter chunk counts should be multiplied by 8.Source: §5.4 · p. 8, Table 4 · p. 9, Table 5 · p. 9

5.4.1 Optimality.

• For Allgather, the 2-step latency-optimal algorithms dominate in the α cost term, while bandwidth-optimal algorithms have a rounds-to-chunks ratio of 7/6.The paper synthesizes 0-synchronous algorithms, where R = C, to simplify code generation.Source: §5.4.1 · pp. 8–9
• For Allgather, Broadcast, and Reduce, synthesized bandwidth-optimal algorithms are better than NCCL’s; synthesized latency-optimal algorithms generally have no NCCL counterpart.The synthesized bandwidth-optimal Allgather algorithm has 6 chunks, 3 steps, and 7 rounds.Source: §5.4.1 · p. 9

5.4.2 Synthesizing All Collectives.

• SCCL synthesizes Alltoall, Gather, and Scatter, for which NCCL has no corresponding algorithms.The authors frame synthesis as a way to extend library algorithms through search rather than manually implementing each topology and primitive.Source: §5.4.2 · p. 9

5.4.3 Synthesis time.

• The longest reported synthesis takes just over 2 minutes, while most take under 10 seconds.For a 24-chunk, 8-step bandwidth-optimal Alltoall, the improved encoding finishes in just over 2 minutes; a direct encoding did not finish within 60 minutes.Source: §5.4.3 · p. 9

• The evaluation compares SCCL with NCCL’s simple protocol, testing single-kernel and per-step cudaMemcpy lowerings and selecting the best thread-block and size combinations.Source: §5.5 · pp. 9–10
• SCCL’s Allgather is up to 2.2× faster than NCCL on small inputs and 1.14× faster on larger inputs.The comparison includes different lowering choices, and performance can improve by switching implementations based on input size.Source: §5.5 · p. 10
• For Allreduce, SCCL beats NCCL by up to 1.8× on small inputs and 1.06× on large inputs, except at four middle sizes.The reported comparison uses an 8-chunk algorithm for small inputs and a 48-chunk algorithm for large inputs.Source: §5.5 · p. 10
• For Alltoall, SCCL exceeds NCCL speedup of 6.8× on large inputs and 1.4× on small inputs, depending on the latency- or bandwidth-optimal choice.Source: §5.5 · p. 10
• On the AMD Gigabyte workstation, SCCL is faster than RCCL for large Allgather inputs but slower for medium and small inputs.The (1, 4, 4) algorithm has lower latency at small sizes, while (2, 7, 7) is faster at large sizes.Source: §5.5 · p. 10
• Across the graphs, SCCL synthesizes algorithms along the Pareto-optimal frontier and lowers them to hardware implementations competitive with a hand-optimized baseline.Source: §5.5 · p. 10

• MPI implementations provide portable collective primitives, while NCCL and RCCL offer efficient implementations for limited algorithm sets and hardware ecosystems.Source: §6 · p. 10
• Earlier hybrid mesh algorithms switch between latency- and bandwidth-optimal methods, but the paper says they do not target Pareto-optimal algorithms for a given topology.Source: §6 · p. 10
• Hierarchical approaches such as Horovod, BlueConnect, and PLink address multi-node systems; this paper focuses on single-node, multi-GPU synthesis.Source: §6 · pp. 10–11
• Blink synthesizes bandwidth-efficient collectives using spanning-tree packing, but its heuristic selection is not guaranteed bandwidth-optimal and it does not target latency-optimal algorithms.Blink implements Allreduce as reduce followed by broadcast; SCCL targets both latency- and bandwidth-optimal algorithms.Source: §6 · p. 11

• SCCL systematically synthesizes algorithms across the Pareto frontier from latency-optimal to bandwidth-optimal for a collective on an input topology.Source: §7 · p. 12
• The paper characterizes a broad class of algorithms and proves Pareto-optimality for both known and newly synthesized algorithms.Source: §7 · p. 12
• Automatically generated implementations are competitive with manually hand-tuned communication kernels in use today.Source: §7 · p. 12