NB

Description

In collective communication, the number of communication steps of the Ring algorithm is , where N indicates the number of ranks involved in collective communication. As the network scale increases, the communication overhead increases significantly. Although the RHD algorithm reduces the number of communication steps to , data merging is required when the number of ranks is not a power of 2. As a result, the communication data size increases. The Nonuniform Bruck (NB) algorithm uses a multi-ring structure with dynamically adjusted steps to ensure that the number of communication steps remains regardless of the number of ranks. In addition, this algorithm can avoid extra communication data growth.

The following figure shows the communication process of the NB algorithm when the rank size is a power of 2 (for example, 4).

Figure 1 Communication process of the NB algorithm when the rank size is 4

The following figure shows the communication process of the NB algorithm when the rank size is not a power of 2 (for example, 5).

Figure 2 Communication process of the NB algorithm when the rank size is 5

For the ReduceScatter and AllGather operators, the number of communication steps is .

• For the ReduceScatter operator, in each communication step, each device sends data to the target device at a communication stride of , with data segments sent per step.
• For the AllGather operator, the communication stride decreases while the data size increases per step. If the number of devices is not a power of 2, the data size in the last step is .

The NB algorithm is also applicable to the star and fat-tree topologies, with the time complexity .

Required Time Calculation