NHR

Description

Because the communication steps of the Ring algorithm scale linearly with the number of ranks, implementing it within a large-scale network inherently results in substantial latency. Consequently, the Ring algorithm's data chunking mechanism is inefficient for small-packet workloads and is far better suited for large-packet transmission scenarios. If the cluster scale is not an integral power of 2, using the RHD algorithm will introduce extra communication steps and overheads. As a result, the communication performance of an (N – 1)-scale cluster is worse than that of an N-scale cluster. In addition, the RHD algorithm alters objects in each communication phase, changing the communication link. In heavy-traffic scenarios, this can lead to switch traffic conflicts and reduce bandwidth.

The Nonuniform Hierarchical Ring (NHR) algorithm constructs N spanning trees for N ranks to build the optimal communication relationship. The tree depth (that is, the number of communication steps) is , and data chunks are sent in an aggregated manner after being rearranged to ensure the optimal theoretical performance of the communication algorithm.

The maximum communication traffic of this algorithm is concentrated between ranks that are close to each other in physical locations. This effectively utilizes the performance advantages brought by the physical distance and reduces traffic conflicts. In addition, the NHR algorithm can fully utilize link resources regardless of whether the cluster scale is a power of 2. For small-data-packet communication, the NHR algorithm is further optimized to construct only one tree for N ranks. In this way, the number of data packets on the network and the number of tasks concurrently executed by the chip are reduced, improving communication efficiency.

The following figure shows the communication process of the NHR algorithm when the rank size is an integral power of 2 (for example, 4). In each step, exactly one data segment is sent and one is received because contiguous data chunks can be transferred sequentially.

The following figure shows the communication process of the NHR algorithm when the rank size is not an integral power of 2 (for example, 5). Most data chunks can be sent and received contiguously, leaving only a few inter-device data chunks non-contiguous.

The NHR algorithm is also applicable to the star or fat-tree topology, with the time complexity .

Required Time Calculation

NHR is an unbalanced hierarchical ring algorithm. Its time complexity remains whether the cluster scale is an integral power of 2 or not. If there are ranks, communication steps are required. For the ReduceScatter operator, data is exchanged in the first step, and the data size halves with each step, down to only one data segment in the last step. The AllGather operator works in the opposite way compared to ReduceScatter.

Table 1 Time required for each operation in the NHR algorithm