Ring-AllReduce Performance Study

A from-scratch implementation and benchmark of the Ring-AllReduce collective communication algorithm on CPU (C++20, std::thread/std::barrier) and GPU (CUDA 12+, multi-device), with Nsight Systems/Compute profiling and a CPU-vs-GPU performance comparison across a wide data-size sweep.

Status: complete. Both CPU and real multi-GPU ring-allreduce data are in, at GPU node counts of 2 and 4 — see Benchmark results below.

Architecture

The Ring-AllReduce algorithm

Ring-AllReduce sums (or otherwise reduces) a buffer across N nodes arranged in a logical ring, without any node ever needing the full buffer from every peer at once. Each node's buffer is split into N chunks, and the operation runs in two phases of N-1 steps each:

graph LR
    N0((Node 0)) -->|chunk k| N1((Node 1))
    N1 -->|chunk k| N2((Node 2))
    N2 -->|chunk k| N3((Node 3))
    N3 -->|chunk k| N0

Loading

1. Reduce-scatter (N-1 steps): at step k, every node accumulates one chunk received from its left neighbor into its own matching chunk. After N-1 steps, each node holds the fully-reduced value for exactly one chunk — the chunks are "scattered" across the ring, one fully-summed chunk per node.
2. All-gather (N-1 steps): the same ring and direction, but now each step copies (not accumulates) a chunk from a node's left neighbor — the neighbor is guaranteed to already hold that chunk's final value, from either reduce-scatter or an earlier all-gather step. After N-1 more steps, every node holds every chunk's final value.

Both implementations in this repo (cpu/, gpu/) derive chunk boundaries from the same function, chunk_range — it splits a buffer of total_size elements into num_chunks pieces that differ in length by at most one element, so the algorithm works correctly even when the buffer size doesn't divide evenly by N. GPU code includes this CPU header directly (the function is inline) rather than duplicating the math, so both backends are guaranteed to compute identical chunk boundaries.

This structure is what makes the algorithm bandwidth-optimal: every node sends and receives about 2*(N-1)/N times the buffer size in total, which approaches 2x the buffer size as N grows — independent of N — unlike a naive "everyone sends to one reducer" approach, where the reducer alone must receive N-1 full copies of the buffer. See References for the original bandwidth-optimality proof.

Two independent implementations, one shared core

graph TD
    CR["chunk_range (cpu/include/ring_allreduce/ring_allreduce.hpp)"]

    subgraph CPU["CPU -- cpu/"]
        CT["one std::jthread per logical node"] --> CB["std::barrier: global sync after every step"]
        CB --> CR
    end

    subgraph GPU["GPU -- gpu/"]
        GP["cudaSetDevice: one physical GPU per logical node"] --> GM["cudaMemcpyPeerAsync: real ring link"]
        GM --> GK["add_kernel: on-device reduction"]
        GK --> GE["cudaEvent + cudaStreamWaitEvent: pairwise sync"]
        GE --> CR
    end

Loading

• CPU (cpu/src/ring_allreduce.cpp): spawns one std::jthread per logical node — not per chunk — reused across both phases. All N threads share one process's address space, so a "ring link" is just thread i reading thread (i-1)'s std::vector<float> directly at the chunk boundary chunk_range computes for that step; no explicit copy call is needed to move the bytes. Correctness depends entirely on ordering: a single std::barrier(N) is shared by all threads, and every one of the 2*(N-1) total steps (across both phases) ends with arrive_and_wait(), so no thread can start reading its neighbor's chunk for step k+1 until every thread (including that neighbor) has finished writing step k.
• GPU (gpu/src/ring_allreduce.cu): one real CUDA device per logical node (cudaSetDevice), each with its own device-resident buffer — a genuinely distinct memory space, unlike the CPU's shared address space. Ring links are real cudaMemcpyPeerAsync transfers, routed directly over NVLink or PCIe depending on what the device pair supports (cudaDeviceCanAccessPeer + cudaDeviceEnablePeerAccess are called for every pair up front, in enable_peer_access). Reduction happens on-device: a custom kernel (add_kernel, 256 threads/block) does dst[idx] += src[idx] immediately after a chunk lands, so no host round-trip is needed during reduce-scatter. All-gather reuses the same per-node cudaStream/cudaEvent pair but skips the kernel — those copies are overwrites, not accumulations.
  • Synchronization is deliberately not a global barrier. Step k on node i only ever depends on step k-1 on node i-1 — not on all N nodes — so each GpuNode records a cudaEvent after its step completes, and the next node's next step does a single targeted cudaStreamWaitEvent on that specific event rather than waiting on everyone. This is both correct (it captures the only real dependency) and allows more cross-node overlap than the CPU's all-threads barrier, since nodes that aren't adjacent on the current step's dependency chain can keep running.

Repository layout

ring-allreduce-perf-study/
├── CMakeLists.txt               top-level build: C++20, conditional CUDA detection
├── LICENSE
├── cpu/                         CPU ring-allreduce (std::jthread + std::barrier)
│   ├── include/ring_allreduce/ring_allreduce.hpp   public API + chunk_range (shared with gpu/)
│   ├── src/ring_allreduce.cpp   reduce_scatter / all_gather / allreduce_sum
│   ├── src/demo_main.cpp
│   └── tests/test_ring_allreduce.cpp
├── gpu/                         GPU ring-allreduce (CUDA, multi-device)
│   ├── include/ring_allreduce/ring_allreduce.cuh     public API + GpuNode
│   ├── include/ring_allreduce/reduction_kernel.cuh
│   ├── src/ring_allreduce.cu    reduce_scatter / all_gather / allreduce_sum / peer access
│   ├── src/reduction_kernel.cu  elementwise-add CUDA kernel
│   ├── src/demo_main.cu
│   └── tests/test_ring_allreduce.cu
├── benchmark/
│   ├── cpu_benchmark.cpp
│   ├── gpu_benchmark.cu           real multi-GPU ring sweep
│   ├── gpu_kernel_bandwidth.cu    single-GPU kernel throughput sweep (not a ring measurement)
│   └── results/                   CSVs, charts, and result notes -- see Benchmark results below
├── profiling/
│   ├── notes.md                   Nsight rehearsal notes + real 2-GPU/4-GPU run history
│   ├── gpu_2gpu_nsys_stats.txt
│   └── gpu_4gpu_nsys_stats.txt
└── scripts/
    └── plot_results.py            matplotlib charts, reads benchmark/results/*.csv

Benchmark results

Both series below are genuine measurements — no simulated or same-device ring. Re-run python3 scripts/plot_results.py to regenerate from whatever CSVs are present in benchmark/results/.

• CPU: rented GCP e2-standard-8 VM (8 vCPU AMD EPYC 7B12, 32 GB RAM, us-central1-a), N=4 threads. See benchmark/results/NOTES.md for why this was moved off the local dev machine. Raw data: benchmark/results/cpu_results.csv.
• GPU: rented RunPod pod, 2x NVIDIA A100 SXM 80GB connected via NVLink (nvidia-smi topo reports NV12, 12 bonded links), CUDA 12.4, driver 590.48.01, N=2 physical devices — the first genuine multi-GPU data in this project after AWS, GCP, and Azure quota requests each only ever granted 1 real GPU (RunPod has no quota system). Raw data: benchmark/results/gpu_results.csv.

Max speedup: 29.3x (GPU vs. CPU wall-clock time at the 1 GiB buffer size — 11.3 ms vs. 331.7 ms). Note CPU and GPU sweeps use different N (4 vs. 2), so the bandwidth axis isn't directly apples-to-apples (the ring formula's 2*(N-1)/N factor differs: 1.5 for CPU, 1.0 for GPU) — the wall-clock time comparison above is the fair one.

Correctness (gpu_tests) was also verified for the first time with genuine cross-device peer access (cudaMemcpyPeerAsync/cudaDeviceEnablePeerAccess between distinct physical GPUs, not the same-device modulo trick used earlier), on top of the existing single-GPU cross-validation on AWS g4dn.2xlarge (1x T4) and GCP g2-standard-4 (1x L4). Single-GPU kernel throughput data (a different, non-ring measurement) is still in benchmark/results/GPU_NOTES.md.

Nsight Systems profiling of the real 2-GPU run — including peer-to-peer memcpy timing — is summarized in profiling/gpu_2gpu_nsys_stats.txt (the raw .nsys-rep, viewable in the Nsight Systems GUI, is gitignored like other binary profiling artifacts — see profiling/notes.md for how to regenerate it and the full rehearsal/run history). Nsight Compute kernel-level counters were blocked by the cloud host's NVreg_RestrictProfilingToAdminUsers driver policy (standard on shared multi-tenant GPU hosts, not fixable from inside a guest container).

N=2 vs N=4 GPU scaling

A follow-up run added 4x A100 SXM (same NVLink-connected pod family, all 6 pairs report NV12) to see how ring-allreduce bandwidth scales with node count. Both series below are genuine measurements, reproduced across two back-to-back runs each:

Bandwidth does not scale linearly with N — at 1 GiB, N=2 reaches ~95 GB/s vs. N=4's ~49 GB/s, even though the ring formula already accounts for the different data-per-hop (2*(N-1)/N is 1.0 for N=2 vs. 1.5 for N=4). The remaining gap is synchronization overhead: N=4 has 6 total ring steps (3 reduce-scatter + 3 all-gather) vs. N=2's 2, and Nsight Systems (profiling/gpu_4gpu_nsys_stats.txt) shows 24 real peer-to-peer transfers for the 4-GPU case vs. 4 for the 2-GPU case — more, smaller hops per byte moved. Raw data: benchmark/results/gpu_4gpu_results.csv.

Building

cmake -S . -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build
ctest --test-dir build

CPU always builds. The gpu/ subdirectory only builds when a CUDA compiler is detected — ctest then also runs gpu_tests alongside cpu_tests automatically, no extra flags needed. On a machine with 2+ real GPUs:

./build/gpu/gpu_demo                # correctness demo across all visible devices
./build/gpu/gpu_benchmark            # real ring-allreduce sweep -> benchmark/results/gpu_results.csv
./build/gpu/gpu_kernel_bandwidth     # single-GPU kernel throughput sweep (not a ring measurement)
python3 scripts/plot_results.py      # regenerate all charts from whatever CSVs are present

References

Algorithm:

• Patarasuk, P. and Yuan, X., "Bandwidth Optimal All-reduce Algorithms for Clusters of Workstations", Journal of Parallel and Distributed Computing, 2009 — the original proof that a ring-based schedule is bandwidth-optimal; the 2*(N-1)/N bandwidth formula used throughout this project's benchmarks comes from here.
• Gibiansky, A., "Bringing HPC Techniques to Deep Learning" (Baidu SVAIL, 2017) — the widely-cited practical write-up that popularized ring-allreduce for distributed deep learning training.
• Sergeev, A. and Del Balso, M., "Horovod: fast and easy distributed deep learning in TensorFlow", 2018 — a production ring-allreduce implementation for DL training.

Implementation:

• NVIDIA Collective Communications Library (NCCL) — production-grade multi-GPU ring/tree collectives; a useful comparison point for this project's from-scratch gpu/ implementation.
• NVIDIA CUDA C++ Programming Guide — cudaMemcpyPeerAsync, streams, events, and peer-access APIs used throughout gpu/src/ring_allreduce.cu.
• cppreference: std::jthread and std::barrier — the C++20 primitives underlying cpu/src/ring_allreduce.cpp.