Ring
Description
The Ring algorithm connects all NPUs in a ring. Each NPU receives data from its left neighbor and sends data to its right neighbor. Data circulates to complete gradient accumulation, followed by another round of circulation for parameter synchronization.
The Ring algorithm applies to the star or fat-tree topology. It connects the single-port duplex links of all NPUs in series, forming a ring.
The following figure shows the process of implementing the AllReduce operator using the Ring algorithm. In each step, a data block is sent to the downstream. One full circle around the ring completes the ReduceScatter phase. A second circle around the ring completes the AllGather phase.
The time complexity of the Ring algorithm is O(n – 1), where n indicates the number of NPUs on the ring.
Required Time Calculation
All participating ranks form a ring. Each rank communicates only with its left and right ranks. If there are p ranks, they communicate p – 1 times, exchanging 
data each time.
|
Operation |
Time Required |
|---|---|
|
Scatter |
|
|
Gather |
|
|
Broadcast |
The implementation uses Scatter+AllGather, and the time required is as follows.
|
|
Reduce |
The implementation uses ReduceScatter+Gather, and the time required is as follows.
|
|
ReduceScatter |
|
|
AllGather |
|
|
Allreduce |
The implementation uses ReduceScatter+AllGather, and the time required is as follows.
|
