RHD

Description

When the network scale increases, for example, the number of ranks increases to 4000, it is difficult to form a full-mesh network with 4000 ranks (so that operations can be completed in one clock cycle). In addition, the resource overhead (link resources, switching resources, and synchronization resources) is too large, and the computing power may not match the resource overhead. The ring topology saves resources (using only the left and right devices to send and receive data). However, it requires too many operations, making it slow. Large-scale cluster computing features a large amount of server data on a long ring. Dividing data blocks using the ring topology is no longer advantageous.

The RHD algorithm uses recursive doubling and halving for data exchange between NPUs. It consumes fewer resources than the Mesh algorithm and is more efficient than the Ring algorithm.

The preceding figure shows the implementation process of the RHD algorithm. Assume that there are five (2² + 1) ranks. First, the data of rank 1 is merged into rank 0, reducing the ranks to four (2²). Then, the four ranks exchange half-size data and sum their data in pairs, which is called the ReduceScatter operation. Next, these four ranks pairwise concatenate their data using the AllGather operation. Finally, the data of rank 0 is copied to rank 1. In this way, each rank has the sum of all ranks.

The RHD algorithm is also applicable to the star or fat-tree topology. The time complexity of the algorithm is $\text{[math]}$ .

Required Time Calculation

The RHD algorithm is a recursive halving and doubling algorithm. For the integral power of 2, the Vector/Distance Halving/Doubling policy is used. For the non-integral power of 2, ranks are divided into two parts: 2r (part1) and p-2r ( $\text{[math]}$ ). First, part1 is merged into r, so that the sum of the remaining ranks is p-r (block). Then, the Halving-Doubling (HD) algorithm of the integral power of 2 is executed. Finally, 2r is restored in part1 to obtain the final result.

**Table 1** Time required for each operation in the RHD algorithm
Operation	Time Required
Broadcast	Determine whether the rank of part 1 involved in the block is an odd or even rank based on whether the root rank is an odd or even rank. Perform Distance Halving in the block first and then send the data to the remaining ranks. The total time required is as follows. $\text{[math]}$
ReduceScatter	Vector Doubling + Distance Halving (ensure the Scatter sequence) Integral power of 2 $\text{[math]}$ Non-integral power of 2 Step 1 (Reduce): $\text{[math]}$ Step 2 (non-uniform ReduceScatter, where some ranks hold two data segments) $\text{[math]}$ communication times are required. The maximum data size exchanged each time is as follows. $\text{[math]}$ , The total time required is as follows. The calculation in this step is complex. The lower and upper limits are provided here. Lower limit: Upper limit: Step 3 (Scatter):
AllGather	The time required is the same as that of ReduceScatter, and there is no γ-related part.
AllReduce	ReduceScatter + AllGather: The splitting here involves incomplete ReduceScatter and AllGather, as scattering to all ranks is not required. Vector Halving + Distance Doubling can be used. (The time required is short in a hierarchical network, but data ordering cannot be guaranteed, which is not required for splitting.) Integral power of 2 $\text{[math]}$ Non-integral power of 2 Step 1 (Reduce): $\text{[math]}$ ReduceScatter: $\text{[math]}$ AllGather: $\text{[math]}$ Last step: Total time required:
Reduce	The current implementation uses ReduceScatter + Gather. Integral power of 2 Non-integral power of 2 Step 1 (Reduce): $\text{[math]}$ ReduceScatter: Gather: Total time required:

Parent topic: Collective Communication Algorithms