AHC

Description

In cluster networks featuring hierarchical topologies with inter-layer bandwidth convergence, collective communication confronts two primary technical challenges. First, traditional single-level collective algorithms suffer from severe performance degradation induced by cross-region bandwidth convergence. Second, conventional hierarchical algorithms become inapplicable due to the asymmetric distribution of compute units—specifically, device-count asymmetry—across different regions. For example, in a cluster, a communicator may span two SuperPoDs with different numbers of devices (for example, one SuperPoD has 64 devices and the other has 128 devices). This poses great challenges to the performance of the collective communication algorithm.

In the preceding figure, AHC regroups NPUs within a communicator and partition the data on each NPU in a topology-aware manner. It fully uses the high-speed network bandwidth for intra-group communication, while enabling an asymmetric combination across groups leveraging logical devices with identical IDs. The implementation involves the following three steps:

1. Group compute units based on the physical topology. Adjacent NPUs are organized into a group, allowing for variable group sizes. Furthermore, the available inter-group bandwidth may be converged compared to that within each group.
   1. Calculate the least common multiple (LCM) of all groups. If there are G groups, the data is partitioned into LCM × G chunks. As shown in the preceding figure, with group sizes of 2 and 3, the LCM is 6 and G equals 2, partitioning the data into 12 chunks.
   2. Execute the standard ReduceScatter inside each group in parallel.
2. Classify logical devices with identical IDs and implement inter-group AllReduce based on these logical devices.
   1. Within each group, segment the data designated for the Reduce operation along the data boundaries of individual NPUs, creating several non-uniform data chunks.
   2. Each data chunk within a given group has a corresponding counterpart of identical size in every other group. According to the data mapping, NPUs in different groups also have a mapping relationship. NPUs tied by this relationship are defined as "logical devices with identical IDs."
   3. Execute the AllReduce operation between logical devices with identical IDs.
3. Execute the AllGather operation among NPUs in each group.

The algorithm of the intra-group and inter-group ReduceScatter, AllGather, and AllReduce operations can be any known algorithm, such as NB, NHR, and Ring. Currently, the AHC algorithm selects a stitching algorithm with better performance based on the scenario and policy.

Required Time Calculation

When the NB algorithm is used for both intra-group and inter-group operations, the time required by the AllReduce operator is as follows.