Ring-AllReduce

Technical Overview of Ring-AllReduce

Ring-AllReduce is a fundamental bandwidth-optimal communication algorithm used in distributed deep learning to synchronize gradients across multiple worker nodes (GPUs).

In data-parallel training, each GPU processes a different batch of data and calculates local gradients. Before weights can be updated, these gradients must be averaged across all nodes. Instead of transmitting all gradients to a central parameter server, which creates network bottlenecks, Ring-AllReduce structures the nodes in a logical ring topology. Each GPU communicates only with its immediate successor and predecessor, maximizing bandwidth efficiency.

Key Architecture & Implementation

The algorithm runs in two consecutive phases, assuming $N$ workers are connected:

1. Scatter-Reduce Phase:
   • Gradients on each GPU are divided into $N$ equal segments.
   • Nodes pass segments around the ring $N - 1$ times.
   • At the end of this phase, each GPU holds the fully summed gradients for exactly one segment of the model parameters.
2. All-Gather Phase:
   • The fully summed segments are circulated around the logical ring $N - 1$ times.
   • At the end of this phase, all GPUs receive the aggregated gradients for all parameter segments.

[ GPU 0 ] ===> [ GPU 1 ] ===> [ GPU 2 ] ===> [ GPU 3 ] ===> [ GPU 0 (Logical Ring) ]

Core Parameters & Equations

• Total Data Transferred: The total volume of network traffic sent by each GPU is: ext{Data Sent} = 2 imes rac{N - 1}{N} imes |K| Where $|K|$ is the total model size in bytes. This is independent of the number of GPUs ($N$), making the algorithm highly scalable.
• Bandwidth Utilization: Network cards (NICs/NIC links) run at peak theoretical speed since communication is point-to-point.

Real-world Applications

• Distributed Libraries: Powering PyTorch DDP (Distributed Data Parallel), Horovod, and Megatron-LM.
• Hardware Interconnects: Optimized for clusters using NVIDIA NVLink inside nodes, and InfiniBand or RoCE v2 across nodes.