PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

cloud distributedcomputing parallelcomputing

distributed computing, parallel computing, cloud

arXiv:2606.07019v1 [cs.DC] 5 Jun 2026

PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer William Won

Kartik Lakhotia

Madhu Kumar

[email protected] Georgia Institute of Technology Atlanta, GA, USA

[email protected] Intel Labs Santa Clara, CA, USA

[email protected] Intel Bengaluru, Karnataka, India

Sudarshan Srinivasan

Tushar Krishna

[email protected] Intel Bengaluru, Karnataka, India

[email protected] Georgia Institute of Technology Atlanta, GA, USA

Abstract Distributed machine learning has become increasingly important due to the massive scale of large-scale generative models. Both model parameters and data are distributed across many compute devices, which requires frequent collective communications to synchronize activations and parameter updates. Such collective communications have become a major bottleneck. While the performance of the collective algorithm depends on the physical network topology, the baseline collective algorithms in collective communication libraries are largely topology-agnostic. Collective algorithm synthesizers address this inefficiency by automatically generating topology-aware collective algorithms. However, prior works have largely overlooked that collective communication typically occurs only among a subset of devices, known as process groups. Additionally, most existing synthesizers are limited in the range of target collective patterns they can generate. We propose PCCL, a scalable and generic framework for synthesizing topology-aware collective algorithms. PCCL is process group-aware and capable of generating near-optimal collective algorithms even when only a subset of devices participates in collective operations. PCCL synthesizes arbitrary collective patterns, including 512-NPU All-to-All synthesis in 11.68 minutes.

Introduction

Generative artificial intelligence (AI) models have substantially increased the demand for training and serving large-scale workloads. Large language models (LLMs) with billions of parameters exemplify this trend [6, 52]. The mixture-of-experts (MoE) paradigm further facilitates massive model scaling while retaining manageable computational requirements [7, 50]. For example, frontier MoEbased LLMs often comprise trillions of parameters [10, 15]. Consequently, the computational requirements for machine learning (ML) model training have increased 4.7× on average per year [14]. Given the massive scale of target workloads, training or serving large-scale ML models on a single compute device is impractical [42]. This limitation has led to the widespread adoption of distributed ML approaches. In distributed ML, multiple compute devices are employed, with each device handling a subset of the model and data [53]. In this work, we use the term neural processing unit (NPU) as a general abstraction encompassing various compute devices, including graphics processing units (GPUs), tensor processing units (TPUs), and custom ML accelerators.

Table 1: Qualitative comparison of collective algorithm synthesizers (△ in scalability indicates linear programming).

Synthesizer SCCL [8] TACCL [48] Blink [54] MultiTree [19] ForestColl [61] TACOS [55] TE-CCL [31] PCCL (this work)

Scalable

Generic Topology

△ △ △ ✓ △ ✓

Generic Collective

Process Group Aware

✓ ✓

✓ ✓ ✓ ✓ ✓

✓

Table 2: Supported collective patterns by each synthesizer. (△ denotes synthesis is supported but is not scalable as the solution uses an NP solution). Pccl further supports custom collectives, i.e., arbitrary pre/postconditions such as multicasts, point-to-point, and All-to-Allv. Synthesizer

Reduce-Scatter

All-Gather

All-Reduce

All-to-All

SCCL [8] TACCL [48] Blink [54] MultiTree [19] ForestColl [61] TACOS [55] TE-CCL [31] PCCL (this work)

△ △

✓ ✓ ✓ △

△ △ ✓ ✓ ✓ ✓ △

✓

The parallelization strategy defines how computations and data are distributed across the cluster. For instance, model parallelism partitions the ML model across a subset of NPUs, while data parallelism distributes input data across multiple NPUs [53]. As multiple NPUs process distinct shards of models and data, they must periodically synchronize their computation results, such as forward and backward pass activations and weight gradients [62]. These synchronization steps are carried out through collective communication operations (collectives for short) [60], as defined by the message passing interface (MPI) [1]. Specifically, a process group [29] is the set of NPUs involved in executing the collective. Modern data center ML clusters comprise more than 100,000 NPUs [58]. As a result, collective communication among NPUs has

William Won, Kartik Lakhotia, Madhu Kumar, Sudarshan Srinivasan, and Tushar Krishna

become the most significant bottleneck in both ML training and inference [30, 34, 46]. Collective communication algorithms define how traffic should be routed over the physical network to execute collective communications [55], and the optimal collective algorithm is highly dependent on the system’s underlying network topology [16, 45]. This further underscores the importance of topology-aware collective algorithms. For this reason, many collective communication libraries (CCLs) [4, 21, 36] include customized collective algorithms tailored for their target topologies, and manually designed collective algorithms specialized for target networks have also been proposed [11, 26, 32, 45]. Unfortunately, manually designing topology-aware collective algorithms for every network topology is prohibitive, not only requiring expert knowledge but also incurring engineering and validation costs [8, 55]. This has led to the development of topology-aware collective algorithm synthesizers [8, 19, 31, 48, 54, 55, 61]. These synthesizers take a target topology as input and autonomously generate topology-aware collective algorithms. We identify the following desired metrics for a collective synthesizer. 1. Scalability. Synthesizers must be scalable to handle the scale of ML clusters, which often comprise tens of thousands of NPUs, i.e., support topologies with many NPUs. The pattern of collective communication calls changes frequently as the underlying network topology and target workload change [9]. Even if collective synthesis is an offline process, if it takes hours for only tens of NPUs, the applicability would be limited. 2. Supporting Generic Topologies. Network topologies in ML clusters are often (i) heterogeneous, where links can vary in bandwidth and latency, and (ii) asymmetric, where each NPU may have different numbers or shapes of connections [55]. Synthesizers should be able to model heterogeneous and asymmetric topologies. 3. Supporting Generic Collectives. Due to their use in both tensor and data parallelism, All-Reduce, Reduce-Scatter, and All-Gather are among the most common collective patterns in distributed ML [25]. However, MoE-based models require All-to-All (and sometimes All-to-Allv) collectives for their use of expert parallelism [15, 28]. These All-to-All communications have already emerged as a key bottleneck in MoE-based workloads [18]. 4. Process Group Awareness. Parallelization strategies assign parts of the workload to subsets of NPUs. Collective communication is typically performed within these subsets, known as process groups [29]. It is uncommon for all NPUs in the cluster to participate in a single collective operation. Therefore, it is essential for a synthesizer to recognize and exploit process group information. Table 1 and Table 2 show a qualitative comparison of previously proposed collective synthesizers. Unfortunately, existing synthesizers fail to meet one or more of the metrics defined above. Most of these synthesizers make trade-offs between scalability and generality of supported topologies and collective patterns. This is an artifact of the modeling limitations of existing synthesizers: for example, integer linear programming (ILP)-based solutions [31, 48] model heterogeneous networks but are limited in scalability since ILP is a non-polynomial (NP) problem [38]. Spanning tree-based approaches [19, 54, 61] improve the scalability at the tradeoff in their heterogeneous network and switch modeling capabilities. Moreover, none of the existing synthesizers exploit process group information; they assume that a single collective communication is executed

across the entire network. Users may employ existing synthesizers by manually defining a smaller topology of interest (i.e., a subgraph) consisting only of the NPUs in the process group. However, this approach yields suboptimal synthesis results because the synthesizer cannot leverage available network resources outside the subgraph. For example, ILP-based synthesizers often assume symmetric network topologies and collectives to compensate for their scalability limitations, assumptions that can be invalidated by arbitrary process groups or collectives such as multicasts or All-to-Allv. A more comprehensive analysis is presented in Section 7. This work aims to develop a topology-aware collective synthesizer that is both scalable and generic, while leveraging process group information. We propose Pccl: a scalable and generic Process group-aware Collective Communica-tion Library. Pccl adopts the time-expanded network (TEN) data structure [55], which integrates temporal and spatial information into a unified representation. Building on this foundation, Pccl employs a breadthfirst search (BFS)-based pathfinding algorithm to synthesize generic collective algorithms while natively modeling heterogeneous and asymmetric networks with and without switches. Moreover, the BFS pathfinding algorithm naturally incorporates process group information into the synthesis process. To summarize, this work makes the following contributions: • We motivate the core requirements of collective algorithm synthesizers: scalability, support for generic topologies and collectives, and process group awareness. • Pccl is a collective algorithm synthesizer that satisfies all these core objectives. Pccl is built on the TEN representation, which captures both temporal and spatial information of arbitrary network topologies. • Pccl introduces a BFS pathfinding algorithm that is both scalable and generic. The BFS pathfinding algorithm supports arbitrary collectives, including All-to-All, and automatically incorporates process group information. • Process group-aware Pccl synthesized an All-to-All algorithm 2.68× faster for 2D Mesh topology, on average. • Pccl All-to-All algorithm synthesis takes 11.68 minutes for an 512-NPU cluster, more than three orders of magnitude faster than a state-of-the-art synthesizer.

2 Background 2.1 Collective Communication Pattern MPI defines several synchronization patterns among NPUs [1]. These are known as collective communication patterns and are extensively used in distributed ML clusters [60, 62]. Figure 1 illustrates the MPI collective patterns. Each circle represents a chunk, which is a logical unit of network transfers in collective communication. The precondition specifies the initial buffer contents of NPUs, while the postcondition describes the final buffer status after the collective operation. All-to-Allv is a generalized version of Allto-All where each NPU can have different numbers of chunks in the pre/postcondition, common in MoE-based LLMs [28]. Some collective patterns (Reduce, Reduce-Scatter, and All-Reduce) require the reduction of chunks, typically using arithmetic addition in the context of distributed ML.

PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer

Precondition

Postcondition

Precondition

Broadcast (from=1) 1

2 c

Reduce-Scatter 2

1 a

Postcondition

Figure 2: Two process groups over a six-NPU cluster. Process group {1, 2, 3} is executing Reduce-Scatter, while process group {4, 5, 6} is running All-Gather. (chunk 𝑎, 𝑏, and 𝑐 are defined in Figure 1).

All-Gather 2

Chunk

3 7 8 9

NPU

2 4 5 6

Precondition

All-Reduce

1 1 2 3

Process Group Process Group {1, 2, 3} {4, 5, 6}

Gather (to=2)

Process Group Process Group {1, 2, 3} {4, 5, 6}

2 3

Scatter (from=1) 2

2 a

Reduce (to=2)

Postcondition

t=0

3 t=1

t=2

(a) Unidirectional Ring All-Gather collective algorithm over a unidirectional Ring topology.

1 2

All-to-All a = 1 + 4 + 7

3 t=0

1 1

2 t=1

4 4

1 t=2

(b) Unidirectional Ring All-Gather collective algorithm over a custom 8-link topology.

b = 2 + 5 + 8

c = 3 + 6 + 9

Figure 1: Definition of MPI collective communication patterns. Each square denotes an NPU, whereas each circle denotes a chunk.

1 4 4

2 2 3

3 t=0

1 2

4 4

1 t=1

Utilized Underutilized

Figure 3: Examples of topology-aware and topology-unaware All-

2.2

Process Group

Examples in Figure 1 are depicted by using a cluster of three NPUs, and all three NPUs are involved in the collective communication. In practice, since parallelization strategies distribute a job across subsets of NPUs, collective communication typically runs in a more localized fashion; not all NPUs in the cluster execute a single collective communication. Instead, a small set of NPUs in the cluster executes collective communication amongst themselves. Process group is the term used to denote each such set of NPUs executing a collective communication [29]. As an example, Figure 2 shows two process groups over a six-NPU cluster. NPUs {1, 2, 3} execute Reduce-Scatter among themselves, forming a process group. Another process group, composed of NPUs {4, 5, 6}, is running All-Gather.

2.3

Collective Communication Algorithm

A collective communication algorithm defines how each chunk should traverse (i.e., be sent and received) over the network to execute a target collective pattern [55]. As an example, the Ring All-Gather algorithm [51] is shown in Figure 3(a). The Ring algorithm assumes NPUs are logically connected in a Ring. Each NPU sends a chunk to its neighbor while receiving a chunk from its other neighbor. This process is repeated for 𝑁 − 1 steps, where 𝑁 is the number of NPUs in the process group, until every NPU receives all chunks to satisfy their All-Gather postcondition. Direct [44], Recursive

Gather collective algorithms. (a) Topology-aware (unidirectional) Ring algorithm over a Ring topology. (b) Ring algorithm is not topology-aware over an example custom topology, resulting in network underutilization. (c) Example of topology-aware All-Gather algorithm, showing 50% speedup over the Ring algorithm.

Halving-Doubling (RHD) [51], and Double Binary Tree (DBT) [22] are additional examples of All-Reduce collective algorithms.

2.4

Topology-Aware Collective Algorithm

Note that the physical topology in Figure 3(a) is also a unidirectional Ring. Consequently, the Ring collective algorithm utilizes 100% of the available network bandwidth and incurs no network congestion. In this case, the Ring algorithm is a topology-aware collective algorithm for the Ring topology—it fully leverages the physical network without network congestion, yielding optimal collective performance [57]. In contrast, Figure 3(b) shows the same Ring algorithm executed over an arbitrary physical network with eight links. Although it performs a valid All-Gather collective, it underutilizes the available network resources and therefore does not achieve optimal performance. In this context, the Ring algorithm is not topology-aware. Figure 3(c) shows an example of a topology-aware All-Gather algorithm tailored for the same custom network, achieving a 50% speedup compared to the topology-unaware Ring algorithm.

William Won, Kartik Lakhotia, Madhu Kumar, Sudarshan Srinivasan, and Tushar Krishna

2.5

2.6

Motivation

In this section, we motivate the key requirements that a collective algorithm synthesizer should satisfy to be practically deployable, and define the problem statement for Pccl.

3.1

Scalability

Modern ML clusters comprise tens to hundreds of thousands of NPUs [27, 58]. Over such a cluster, training and inference jobs are distributed using model and data parallelism strategies. Each model-parallel process group may include tens of NPUs [35], while the remaining NPUs are often organized into data-parallel process groups, resulting in a set of hundreds to even thousands of NPUs [12, 40]. Specifically, due to the changes in model architecture, network topology, optimization techniques, and hyperparameter tuning, collective patterns issued by the workload experiences frequent changes [9]. Consequently, it is critical for a synthesizer to support targets with hundreds to thousands of NPUs in a tractable time.

3.2

t=0

t=1

t=2

t=3

t=0

t=1

t=2

t=3

Chunk

3 b

(a) Network Topology

(b) Time-Expanded Network

Figure 4: (a) Unidirectional Ring topology with four NPUs. (b) Timeexpanded network (TEN) representation of (a), expanded up to time three. (c) Two chunk transfer operations represented over the TEN.

Time-Expanded Network

Introduced to the domain of collective communication by [55], a TEN is a data structure that captures both spatial and temporal information of a network in a unified representation. Figure 4 illustrates an example of a TEN representation of a four-NPU cluster. Figure 4(a) is the spatial layout of a four-NPU unidirectional Ring network. The TEN representation of this network topology is drawn in Figure 4(b). All endpoints in a network topology comprise a column, which is then duplicated across multiple timesteps (from 𝑡 = 0 to 𝑡 = 3 in this example). Spatial connectivities between devices are encoded as edges that span across timesteps. TEN enables intuitive modeling of network traffic. Figure 4(c) shows two such operations: chunk 𝑎 is sent from NPU 1 to NPU 2 at 𝑡 = 0, and chunk 𝑏 is sent from NPU 4 to NPU 1 at 𝑡 = 2.

NPU

Collective Algorithm Synthesizer

As discussed in Section 2.4, executing topology-aware collective algorithms can maximize collective performance for a given target topology. However, manually designing such algorithms is costly, requiring significant engineering and validation effort [8, 55]. To address this challenge, collective algorithm synthesizers have been proposed [8, 19, 31, 48, 54, 55, 61]. Rather than relying on human experts, synthesizers are automated frameworks that generate topology-aware collective algorithms. A synthesizer takes the target network topology as input and autonomously produces optimized, topology-aware collective algorithms.

Table 3: Collectives required by each parallelization strategy. Parallelism Data Tensor Expert Pipeline

3.3

Reduce-Scatter

All-Gather

All-Reduce

All-to-All

Pt-to-Pt

✓ ✓

✓ ✓ ✓

Generic Collective Support

Different ML model architectures and parallelization strategies require different sets of collective patterns to be executed. Such a paradigm is summarized in Table 3. For example, MoE-based generative models [12, 39, 41] have gained their popularity since they can retain the computation requirement while massively increasing the model parameters [50], and it comes with the All-to-All communication cost to assign input tokens to appropriate experts [15]. In fact, All-to-All communication takes more than 60% of the total execution time as the cluster size increases [18]. However, it is surprising to note that no CCLs implement specific collective algorithms for the All-to-All pattern [4, 21, 36]. Instead, Direct (i.e., pairwise send-receive) patterns are manually implemented using the CCL’s send-receive operations.

3.4

Process Group Awareness

ML models are dispatched across the AI cluster through parallelization strategies, such as model and data parallelism. Collective communication often runs locally within the parallelization group, known as a process group. For example, All-Reduce is run across data parallel groups, and All-Gather is often executed across tensor parallel groups. Therefore, synthesizers must reflect this and should be process group aware, rather than synthesizing collective algorithms across the entire provided cluster.

Generic Topology Support

AI supercomputers often utilize multiple networking technologies. On-package [47] high-bandwidth links, NPU-to-NPU direct memory access (DMA) links [3, 20, 37], scale-out interconnects [2, 33], even photonic networks [23], are all being leveraged within a single system. Due to such diverse network technology and connectivity options, the network topologies employed in ML clusters are captured as highly asymmetric and heterogeneous [55]. Therefore, the synthesizer should not be limited to symmetric and homogeneous networks and should support generic topology options.

3.5

Problem Statement

Design a collective algorithm synthesizer that autonomously generates topology-aware collective algorithms when the network topology is provided. Such a synthesizer should be: • Scalable to hundreds to thousands of NPUs • Support generic (heterogeneous/asymmetric) topologies • Covers all collective patterns, including All-to-All • Synthesize collective algorithms tailored for process groups

PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer

Broadcast - chunk: 1

Algorithm 1 TEN Functionality src: 1 dests: { 1

Scatter - chunk: 1

src: 1 dests: { 1 }

- chunk: 2

src: 2 dests: { 2 }

- chunk: 3

src: 3 dests: { 3 }

3 }

All-Gather - chunk: 1

src: 1 dests: { 1

3 }

- chunk: 2

src: 2 dests: { 1

3 }

- chunk: 3

src: 3 dests: { 1

3 }

All-to-All - chunk: 1

src: 1 dests: { 1 }

- chunk: 2

src: 1 dests: { 2 }

- chunk: 3 - chunk: 8

src: 1 dests: { 3 } ••• src: 3 dests: { 2 }

- chunk: 9

src: 3 dests: { 3 }

Figure 5: Defining collectives in Figure 1 in a list of conditions. Each condition defines a chunk’s source NPU and destination NPUs.

Require: 𝑇 𝐸𝑁 [𝑡] [𝑠] [𝑑]=true: 𝑇 𝐸𝑁 has a link 𝑠 → 𝑑 at 𝑡 1: function NextDevices(𝑇 𝐸𝑁 , 𝑛𝑝𝑢, 𝑡𝑖𝑚𝑒) 2: return {𝑛𝑒𝑥𝑡: 𝑇 𝐸𝑁 [𝑡𝑖𝑚𝑒] [𝑛𝑝𝑢] [𝑛𝑒𝑥𝑡]=true} 3: end function 4: 5: function Available(𝑇 𝐸𝑁 , 𝑛𝑝𝑢, 𝑡𝑖𝑚𝑒)

if |Neighbors(𝑇 𝐸𝑁 , 𝑛𝑝𝑢, 𝑡𝑖𝑚𝑒)| > 0 then return true 8: else 9: return false 10: end if 11: end function 6: 7:

12:

Section 7.1 summarizes previously proposed collective algorithm synthesizers and articulates the compromises each synthesizer makes with respect to these objectives.

PCCL

This section discusses how Pccl synthesizes topology-aware collective algorithms. Specifically, we first define the notion of a collective condition. Then, we describe how a collective algorithm can be synthesized using a BFS pathfinding algorithm, initially targeting homogeneous networks. Finally, we generalize the synthesis process to support switch modeling and heterogeneous networks.

4.1

Condition

We first focus on collective patterns that do not require reduction operations (discussed later in Section 4.5), such as All-Gather or All-to-All. As illustrated in Figure 1, a chunk in these non-reduction collectives resides in only one NPU in the precondition. In the postcondition, a chunk may reside in either a single NPU (e.g., Scatter or All-to-All) or multiple NPUs (e.g., Broadcast or All-Gather). We propose defining collective communication patterns using a condition-based representation. Preconditions and postconditions are NPU-centric—describing which chunks each NPU holds before and after collective communication, respectively. Meanwhile, the condition-based view is chunk-centric. Each condition specifies a chunk’s source NPU and its set of destination NPUs. A collective communication pattern consists of one or more collective conditions. Figure 5 shows examples of collective patterns expressed using condition-based notation. For instance, a Scatter contains three conditions, each describing a single source and destination pair for a chunk. All-Gather, on the other hand, also has three conditions, but each chunk is destined for multiple NPUs instead of just one.

4.2

TEN Representation

Pccl leverages the TEN representation to synthesize collective algorithms. In this section, we formally define the TEN structure and introduce three essential operations for processing a given TEN. These operations are illustrated in Algorithm 1. TEN is a three-dimensional boolean matrix: 𝑇 𝐸𝑁 [𝑡] [𝑠] [𝑑]. A value of true at 𝑇 𝐸𝑁 [𝑡] [𝑠] [𝑑] indicates that there is a link from NPU 𝑠 to NPU 𝑑 at timestep 𝑡, meaning that NPU 𝑠 can initiate a chunk transfer to

13: function NextAvailableTime(𝑇 𝐸𝑁 , 𝑛𝑝𝑢, 𝑡𝑖𝑚𝑒)

𝑡 ← 𝑡𝑖𝑚𝑒 while not Available(𝑇 𝐸𝑁 , 𝑛𝑝𝑢, 𝑡) do 16: 𝑡 ←𝑡 +1 17: end while 18: return time 19: end function 14: 15:

Algorithm 2 BFS Pathfinding Algorithm Require: Network 𝑇 𝐸𝑁 , Condition 𝑐 Ensure: Synthesized path 𝑝𝑎𝑡ℎ𝑠 for 𝑐 1: 𝑡 ← NextAvailableTime(𝑇 𝐸𝑁 , 𝑐.𝑠𝑟𝑐, 0) 2: 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 ← {(𝑐.𝑠𝑟𝑐)} 3: 𝑝𝑎𝑡ℎ𝑠 ← {𝑐.𝑠𝑟𝑐 : []} 4: while 𝑐.𝑑𝑒𝑠𝑡𝑠 ⊈ 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 do 5: for 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 in 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 do 6: for 𝑛𝑒𝑥𝑡 in NextDevices(𝑇 𝐸𝑁 , 𝑐𝑢𝑟𝑟𝑒𝑛𝑡, 𝑡) do 7: if 𝑛𝑒𝑥𝑡 ∈ 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 then 8: continue 9: end if 10: Add 𝑛𝑒𝑥𝑡 to 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 11: Add (𝑛𝑒𝑥𝑡 : [𝑝𝑎𝑡ℎ𝑠 [𝑐𝑢𝑟𝑟𝑒𝑛𝑡], (𝑡, 𝑛𝑒𝑥𝑡)]) to 𝑝𝑎𝑡ℎ𝑠 12: end for 13: 𝑡 ←𝑡 +1 14: end for 15: end while 16: return 𝑝𝑎𝑡ℎ𝑠

𝑑 at that time. Given this representation, we define the following utility procedures: • NextDevices(𝑇 𝐸𝑁 , 𝑛𝑝𝑢, 𝑡𝑖𝑚𝑒): Returns the set of destination NPUs to which 𝑛𝑝𝑢 can send a chunk at timestep 𝑡𝑖𝑚𝑒 (i.e., all 𝑑 such that 𝑇 𝐸𝑁 [𝑡𝑖𝑚𝑒] [𝑛𝑝𝑢] [𝑑] is true). • Available(𝑇 𝐸𝑁 , 𝑛𝑝𝑢, 𝑡𝑖𝑚𝑒): Returns a boolean indicating whether 𝑛𝑝𝑢 is available to send a chunk at timestep 𝑡𝑖𝑚𝑒 (i.e., whether there exists at least one valid destination NPU at 𝑡𝑖𝑚𝑒). • NextAvailableTime(𝑇 𝐸𝑁 , 𝑛𝑝𝑢, 𝑡𝑖𝑚𝑒): Returns the earliest time 𝑡 ≥ 𝑡𝑖𝑚𝑒 at which 𝑛𝑝𝑢 becomes available to initiate a chunk transfer. For example, NextAvailableTime(𝑇 𝐸𝑁 ,

William Won, Kartik Lakhotia, Madhu Kumar, Sudarshan Srinivasan, and Tushar Krishna

2 1

3 5

(a) Target 5-NPU topology with 8 unidirectional links - chunk: 2

t=0

t=1

t=2

t=3

(b) TEN representation of (a)

src: 2 dests: { 1

3 }

t=1

t=2

t=3

2 2

Algorithm 3 Synthesizing Collective Algorithm Require: Network 𝑇 𝐸𝑁 , Conditions Set 𝐶 Ensure: Synthesized Collective Algorithm 𝐴 1: for condition 𝑐 in 𝐶 do 2: 𝑐.𝑑𝑖𝑠𝑡 ← 0 3: for 𝑑𝑒𝑠𝑡 in 𝑐.𝑑𝑒𝑠𝑡𝑠 do 4: 𝑐.𝑑𝑖𝑠𝑡 ← 𝑚𝑎𝑥 (𝑐.𝑑𝑖𝑠𝑡, ShortestPath(𝑐.𝑠𝑟𝑐, 𝑑𝑒𝑠𝑡)) 5: end for 6: end for 7: Sort 𝐶 in descending order by 𝑐.𝑑𝑖𝑠𝑡 8: 9: 𝐴 ← {}

Paths: - 1: (0, 3), (1, 5), (2, 1) - 2: [ ] - 3: (0, 3) - 4: (0, 4) - 5: (0, 3), (1, 5) (t, n): send to n at t

10: for 𝑐 in 𝐶 do

𝑝 ← 𝐵𝐹𝑆 (𝑇 𝐸𝑁 , 𝑐) Add 𝑝 to 𝐴 13: Remove 𝑝 from 𝑇 𝐸𝑁 14: end for 15: return 𝐴 11: 12:

(d) BFS pathfinding result after finding all dests of (c)

t=0

t=1

t=2

t=3

1 Paths: - 1: (0, 3), (1, 5), (2, 1) 2 - 2: [ ] 3 - 3: (0, 3) - 4: (0, 4) 4 - 5: (0, 3), (1, 5) (t, n): send to n at t 5

(e) Synthesized path of chunk 2, from NPU 2 to NPUs {1, 2, 3}.

Figure 6: BFS search algorithm to find the path of a chunk. (a) Example target topology with 5 NPUs. (b) TEN representation of (a), expanded up to timestep 3. (c) A target condition to find the route. (d) BFS search history to reach all destinations (NPUs {1, 2, 3}) of a condition. (e) Final chosen path of chunk 2.

𝑛𝑝𝑢, 0) returns the first timestep at which 𝑛𝑝𝑢 is capable of sending out a chunk. 𝑛𝑝𝑢𝑠 in these TEN functionalities are later generalized as 𝑑𝑒𝑣𝑖𝑐𝑒𝑠 to accommodate network switches. This is explained in Section 4.7.

4.3

BFS Pathfinding Algorithm

With the TEN representation as a foundation, Pccl determines the paths to satisfy the condition. The objective of the BFS pathfinding algorithm is to determine the exact route for a chunk to travel from the source 𝑐.𝑠𝑟𝑐 to all destinations in 𝑐.𝑑𝑒𝑠𝑡𝑠, where 𝑐 is a collective condition. Pccl represents a path as an ordered list of tuples (𝑡, 𝑛), indicating that the chunk is sent from its current location to NPU 𝑛 at timestep 𝑡. For example, consider 𝑝𝑎𝑡ℎ = [(1, 2), (4, 3)] for a condition whose 𝑐.𝑠𝑟𝑐 = 6. This path indicates that the chunk is first transferred to NPU 2 from NPU 6 at 𝑡 = 1, and then from NPU 2 to NPU 3 at 𝑡 = 4. Pccl pathfinding algorithm aims to construct a dictionary of such paths, 𝑝𝑎𝑡ℎ𝑠 = {𝑑𝑒𝑠𝑡 : 𝑝𝑎𝑡ℎ}, where each entry maps the

path of the chunk to reach 𝑑𝑒𝑠𝑡 from 𝑐.𝑠𝑟𝑐. The pseudocode of the procedure is presented in Algorithm 2, where a condition 𝑐 is given and the goal is to find a path to each destination in 𝑐.𝑑𝑒𝑠𝑡𝑠. The algorithm initializes (i) 𝑡: the first available timestep for NPU 𝑐.𝑠𝑟𝑐, and (ii) 𝑣𝑖𝑠𝑖𝑡𝑒𝑑: the set of visited NPUs. It then performs a BFS search over the 𝑇 𝐸𝑁 to expand the 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 set until all 𝑐.𝑑𝑒𝑠𝑡𝑠 have been reached. Each time a new NPU 𝑛𝑒𝑥𝑡 is visited, it is added to the 𝑝𝑎𝑡ℎ𝑠 dictionary by appending the edge from its predecessor 𝑛𝑝𝑢, building upon the path already found for 𝑛𝑝𝑢, as shown in line 11 of Algorithm 2. Figure 6 visually illustrates this process. Figure 6(a) shows an asymmetric 5-NPU network, and Figure 6(b) displays the TEN representation expanded up to timestep 3. The target condition in Figure 6(c) specifies that a chunk starts at NPU 2 and must reach NPUs {1, 2, 3}. Figure 6(d) shows the BFS traversal process: starting from source NPU 2, traversing the 𝑇 𝐸𝑁 until all destinations in 𝑐.𝑑𝑒𝑠𝑡𝑠 are visited. Glimpsed in Figure 6(d) is how the BFS pathfinding algorithm may end up visiting more NPUs than the requested destinations of the condition. For example, the BFS result in Figure 6(d) visited all five NPUs, although the condition only requires visiting NPUs {1, 2, 3}. Consequently, not all paths constructed during the pathfinding process are meaningful, and only the useful paths should be retained to finalize the chunk’s actual path. Simply, the process iterates over the actual destinations of the condition 𝑐.𝑑𝑒𝑠𝑡𝑠, and selects the paths associated with them. Figure 6(e) shows the filtering result. 𝑇 𝐸𝑁 [0] [2] [4] was filtered out, since such communication is meaningless given that 4 is not in the destination set of the condition. However, note that the chunk transfer to NPU 5 remains in the path—albeit not in the destination set. It is because NPU 5 acts as an intermediate node to forward the chunk to NPU 1, one of the destinations. This explains how the BFS pathfinding algorithm captures the process group information: it first tries to construct paths utilizing the entire network, then filters out only the meaningful paths to 𝑐.𝑑𝑒𝑠𝑡𝑠.

PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer

- chunk: 3

src: 3 dests: { 1

3 }

t=0

t=1

t=2

t=3

t=0

t=1

t=2

t=3

t=0

t=1

t=2

t=3

Paths: 2 - 1: (0, 5), (1, 1) - 2: (0, 5), (1, 1), (2, 2) 3 - 3: [ ] - 4: (0, 4) 4 - 5: (0, 5)

(a) Synthesized Path of a condition by BFS pathfinding algorithm

(b) Used TEN paths by chunk 2 removed from the TEN - chunk: 1

t=0

t=1

t=2

t=3

src: 1 dests: { 1

t=0

t=1

t=2

t=3

(d) Used TEN paths by chunk 3 removed from the TEN

3 } 2

Paths: 2 - 1: [ ] - 2: (0, 2) 3 - 3: (0, 3) 4 - 4: - 5: 5

3 3

3 5

2 3

2 5

t=0 t=1 t=2 (f) Synthesize process group-aware All-Gather collective algorithm

(e) Synthesized path of chunk 1 by BFS pathfinding algorithm over (d)

Figure 7: Synthesizing a All-Gather collective algorithm for process group {1, 2, 3}, based on the topology shown in Figure 6.

4.4

Synthesizing Collective Algorithm

Figure 6 visualized the synthesis process of a Broadcast algorithm for a chunk from NPU 2 to NPUs {1, 2, 3}. However, as shown in Figure 5, a collective pattern may consist of multiple conditions, unlike a simple Broadcast. Synthesizing collective algorithms for such patterns can be achieved by repeatedly applying the BFS pathfinding algorithm. Note that two chunks occupying the same TEN link lead to network congestion, as it indicates a conflict where multiple chunks attempt to use the same physical link at the same time. In other words, a specific TEN link can only be occupied by a single chunk. Therefore, to avoid link congestion in the resulting collective algorithm, any TEN links chosen during a previous BFS pathfinding step are removed from subsequent BFS searches. The pseudocode for this process is shown in Algorithm 3. Since multiple chunks must be mapped over the TEN, Pccl must first determine which chunk should have its path synthesized first. To assign the order, Pccl first computes a distance 𝑑𝑖𝑠𝑡 to each condition 𝑐, defined as the maximum shortest-path distance between 𝑐.𝑠𝑟𝑐 and 𝑐.𝑑𝑒𝑠𝑡𝑠. Then, it sorts the set of conditions 𝐶 in descending order of 𝑐.𝑑𝑖𝑠𝑡. This strategy aims to maximize network resource utilization by assigning paths to chunks that must traverse the network for the longest duration first. Chunks that traverse shorter distances can then utilize the remaining unoccupied TEN links, thereby heuristically maximizing bandwidth utilization, as motivated in [48]. Figure 7 showcases an example by extending Figure 6 to the AllGather collective among a process group {1, 2, 3}. Figure 7(a) shows the synthesized path for chunk 2, as presented in Figure 6(e). Since these links are occupied by chunk 2, they are removed from the TEN before conducting the next BFS pathfinding step, as illustrated in Figure 7(b). Subsequently, the BFS algorithm is run for chunk 3 in Figure 7(c), and the resulting links are also removed from the TEN, as depicted in Figure 7(d). Note that the number of available TEN links decreases as Pccl schedules more conditions across the

t=0

t=1

t=2

(a) Synthesized broadcast collective algorithm

t=2

t=1

t=0

1 1

2 2

3 3 3 4 4 4

NPU Chunk a = 2 + 3 + 4 b = 1 + 2 + 3 + 4

(b) Reduce algorithm by reversing broadcast

Figure 8: (a) Example Broadcast collective algorithm for a 4-NPU cluster. (b) Synthesized Reduce operation by reversing the directions of (a) and applying reduction operations.

network. Figure 7(e) shows the path for chunk 1, obtained through an additional BFS pathfinding phase. Finally, Figure 7(f) summarizes the synthesized topology-aware All-Gather algorithm, constructed through this iterative BFS pathfinding process. Note that Pccl successfully synthesizes a process group-aware All-Gather algorithm. While Figure 7(f) illustrates the All-Gather operation among NPUs {1, 2, 3}, the synthesized algorithm flexibly utilizes network links outside this set—for example, the links 3 → 5 and 5 → 1 are used even though NPU 5 is not part of the source or destination NPUs. Furthermore, as Pccl assumes no specific characteristics of a condition, it is inherently generic and can be applied to any collective pattern, including All-to-All.

4.5

Reduction Operations

Collective patterns involving reductions can be supported by synthesizing their corresponding non-reduction collective algorithms, following the paradigm introduced in [8, 48, 55]. Figure 8 illustrates this approach. To synthesize a Reduce algorithm, Pccl first generates the corresponding Broadcast algorithm, as shown in Figure 8(a). By reversing the direction of all transfers and applying reduction operations, the Reduce algorithm can be automatically constructed,

William Won, Kartik Lakhotia, Madhu Kumar, Sudarshan Srinivasan, and Tushar Krishna

50 GB/s 30 GB/s 2 µs 0.5 µs

NPU

t=0

t=1

t=2

t=3

t=4

t=5

Chunk = 1 MB

20 µs

35 µs

(b) Alpha-beta model

(a) Heterogeneous network topology t=0

t=20

t=35

t=40

t=55

t=60

t=70

Figure 10: Removing TEN links in a heterogeneous network. If a TEN link from 𝑡 = 1 to 𝑡 = 3 is taken, other TEN links overlapping with this timestep (e.g., 𝑇 𝐸𝑁 [0] [1] [2] and 𝑇 𝐸𝑁 [2] [1] [2]) must be disabled to prevent network congestion.

4.7 (c) Heterogeneous TEN representation

Figure 9: (a) A heterogeneous network with two links of different bandwidths and latencies. (b) Application of the 𝛼-𝛽 model with a chunk size of 1 MiB. (c) TEN representation of (b). Note that the timesteps reflect the timing information from the 𝛼-𝛽 model.

as depicted in Figure 8(b). Similarly, Reduce-Scatter can be synthesized by reversing All-Gather, and All-Reduce is realized by composing Reduce-Scatter followed by All-Gather [48].

4.6

Heterogeneous Networks

Pccl leverages the 𝛼-𝛽 network model [17] to support heterogeneous networks, as suggested in [48, 55]. The 𝛼-𝛽 model estimates the transfer time of a link as 𝛼 + (𝑚 × 𝛽), where 𝛼 represents the link latency, 𝛽 is the reciprocal of the link bandwidth, and 𝑚 is the message size (i.e., chunk size for the synthesizers). Figure 9(a) depicts a heterogeneous network topology with two distinct links. For such a network, the 𝛼-𝛽 model is used to capture the transfer time of each link as a single value, as illustrated in Figure 9(b). Figure 9(c) shows the TEN representation corresponding to Figure 9(b), where the timesteps in 𝜇s are from the 𝛼-𝛽 model. For heterogeneous TEN representations, Pccl’s BFS pathfinding is applicable with only marginal modifications. Such modifications mostly arise from the timing considerations when a chunk arrives at the next NPU, and which TEN links to disable to avoid network congestion. Chunk Arrival Time. Since each link can have a different transfer time, Pccl must track the exact arrival time of each chunk at every device. As a result, the 𝑣𝑖𝑠𝑖𝑡𝑒𝑑 set is extended to include the 𝑡𝑖𝑚𝑒 information representing the timestep at which the chunk reaches each device. During the BFS process, whenever a 𝑐𝑢𝑟𝑟𝑒𝑛𝑡 device is processed, it must be ensured that the chunk has actually arrived at this source. Removing TEN Links. Additional care must also be taken when removing TEN links during subsequent BFS pathfinding passes. When a TEN link is used, not only that specific link, but also all other links overlapping with its timestep must be removed to avoid network congestion. This scenario is illustrated in Figure 10. If a chunk is sent at 𝑡 = 1 from NPU 1 to 2, 𝑇 𝐸𝑁 [0] [1] [2] and 𝑇 𝐸𝑁 [2] [1] [2] are also disabled to avoid network congestion.

Modeling Switches

Switch modeling remains an open question in collective synthesizers today. Most past works unroll a switch into direct-connect links[48, 55, 61]. Unfortunately, this limits modeling switch-specific considerations (e.g., finite buffers, or unicast versus multicast support). In Pccl, while we inherently support unrolling, we also add explicit support to model switches via two classes of TEN nodes: NPUs and switches. We track the number of chunks “buffered" at each switch node, and the BFS pathfinding algorithm skips visiting a TEN node at a given timestep if the switch node exceeds the provided buffer size. Furthermore, if the switch node does not support multicast, the BFS algorithm visits only one next neighbor when the node type is a switch. Even under this restriction, as the BFS algorithm visits other nodes in subsequent timesteps (i.e., rather than visiting all next neighbors at once, it visits next nodes one by one), the algorithm can still successfully synthesize a collective algorithm.

4.8

Translating Synthesis Results

It is important to note that Pccl does not specifically target GPUcentric networking, but rather contributes to the algorithmic foundations for synthesizing arbitrary collective algorithms at scale. Nevertheless, this section illustrates that Pccl synthesis results can be translated into other representations to execute on a specific target system. For GPU-based systems, as an example, we propose to use MSCCL [13] and MSCCL++ [49] representations. Both frameworks enable the usage of scratch buffers and multiple threadblocks per GPU for concurrent communications. For further optimization, MSCCL++ even allows a single threadblock to concurrently put messages to multiple peers. Meanwhile, MSCCL not only provides send and receive operations but also compound operations such as receive-copy-send, all suitable to represent Pccl chunk operations. Therefore, by leveraging MSCCL and MSCCL++, Pccl synthesis results can be readily represented and executed on GPU systems without any modifications to the synthesizer itself.

5 Methodology 5.1 Experimental Infrastructure We use ASTRA-sim, a distributed ML systems simulator for the evaluation of this work [44, 56], similar to the setup of [55]. ASTRAsim simulation has been validated over a real system comparison using a 128 NVIDIA H100 cluster with the accuracy of 97% [5]. We also validated the correctness of the Pccl-synthesized algorithm by executing the MSCCL-IR over 16 and 32-GPU clusters via the MSCCL executor [13].

PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer

4,404x

1 0.1

250x

0.01 0.001

16 25 36 #NPUs PCCL TE-CCL

All-to-All Bandwiddth (GB/s)

100 10

3D Hypercube

8000 7000 6000 5000 4000 3000 2000 1000 0

𝟑

𝑶(𝒏 ) R² = 0.9954

500 #NPUs

2 PCCL

CCLs

Speedup

0.5

4 0

1000

1.5

Speedup

Synthesis Time (sec)

2D Mesh 1000

0 2 (16)

4 8 16 (32) (64) (128) #Pods (#NPUs)

32 (256)

Figure 13: All-to-All bandwidth of Pccl vs. CCLs and collective

Synthesis Time (sec)

small 2D Mesh. For a small 6×6 (36 NPU) topology, Pccl is already 4,404× faster over TE-CCL. Further topology scalability analysis of Pccl is also shown using 3D Hypercube. 1000 2D Mesh

100

3D Hypercube

10 1

speedup over heterogeneous 2D Switch topology. Each node size is 8 NPU, and the network size spans 16–256 NPUs by increasing the number of nodes in the cluster. Normalized All-to-All Bandwidth

Figure 11: All-to-All synthesis time of Pccl vs. TE-CCL time for

0.1 1 2 4 8 16 32 64 (8 MB) (16 MB) (32 MB) (64 MB) (128 MB) (256 MB) (512 MB) #Chunks/NPU (Buffer Size [MB])

1.2 0.8 0.4 0 2x2 (4)

3x3 (9)

x 4x4 5x5 6x6 7x7 (16) (25) (36) (49) Mesh Size (#NPUs)

x 8x8 (64)

x x x x x 9x9 10x10 12x12 14x14 16x16 (81) (100) (144) (196) (256) PCCL CCLs TE-CCL

Figure 14: Normalized All-to-All bandwidth when the entire 2D Mesh cluster is executing a All-to-All collective.

Figure 12: Pccl synthesis time of All-to-All algorithm (8–512 MiB) for 64-NPU 2D Mesh and 3D Hypercube topologies, by increasing the number of 128 KiB chunks per each NPU.

5.2

Baseline Collectives

We mostly evaluate Pccl by targeting the All-to-All collective pattern, as (i) most synthesizers fail to synthesize such an algorithm, especially at scale, and (ii) no collective algorithm exists in CCLs. Pccl mechanism is still applicable to generic collective patterns and to showcase that, we also have All-to-Allv and All-Gather results as well. We use Direct, a pairwise point-to-point send-receive algorithm, as the baseline collective algorithm to compare All-to-All performance, as such a mechanism is what CCLs use today.

Results

In this section, we evaluate the performance and efficacy of the Pccl synthesizer. Specifically, we emphasize checking the four practical objectives for collective synthesizers discussed in Section 3: scalability, generic topology support, generic collective support, and process group awareness.

6.1

Scalability

Firstly, we evaluate the scalability of the Pccl synthesizer. For the scalability analysis, we evaluated All-to-All collective pattern as it has the largest search space and thereby most synthesizers struggle to synthesize. Therefore, we mainly target TE-CCL [31], the stateof-the-art in All-to-All synthesis, for main scalability comparison. Topology Size. We measured the All-to-All synthesis time of Pccl by increasing the size of 2D Mesh and 3D Hypercube target topologies. Figure 11 summarizes the observed synthesis time. Notably, only at 36-NPU cluster scale, Pccl was already more than 3 orders of magnitude faster than the state-of-the-art TE-CCL. Further scaling the target topology shows that Pccl can synthesize an All-to-All

algorithm for a 512-NPU cluster in just 11.68 minutes, and 1,000NPU cluster in 2.01 hours. The complexity to synthesize All-to-All algorithm was 𝑂 (𝑛 3 ). Specifically, we measured TE-CCL taking 3 minutes for a 36-NPU (6×6 Mesh) target and more than 30 minutes for 49 NPUs. Although TE-CCL was able to synthesize a 256-GPU target in 25 minutes [31], Cao et al. [9] report that TE-CCL takes 4.4–49.5 minutes and 3.8 minutes–8.7 hours for 16- and 32-GPU systems, respectively. This indicates that TE-CCL synthesis time heavily depends on the synthesizer setup and hyperparameters, including the search policy, number of chunks per collective, and target network topologies. Given this large variability, we expect Pccl to demonstrate consistently better scalability than optimizerbased synthesizers. Collective Size. We also measured the scalability of the target collective pattern. Specifically, we synthesized All-to-All algorithms for an 8×8 Mesh. The algorithm buffer size spans 8–512 MiB by fixing each chunk size to 128 KiB and increasing the number of chunks per NPU from 1 to 64. The synthesis time is summarized in Figure 12. Notably, Pccl synthesized a 512 MiB All-to-All algorithm for a 3D Hypercube topology in 1.83 minutes. As this experiment is done by setting each chunk size to 128 KiB, the synthesis time can further be decreased by increasing the chunk size and reducing the number of chunks per NPU.

6.2

Supporting Generic Topology

In Section 6.1, we already evaluated two homogeneous, asymmetric topologies: 2D Mesh and 3D Hypercube. In this section, we show the applicability of Pccl towards more classes of topologies: notably, 2D Switch topology, which is heterogeneous. Figure 13 showcases the same experiment by using a heterogeneous 2D switch topology: each node size is 8, and the cluster size spans 16–256 NPUs by increasing the number of nodes in the cluster. For this setup,

William Won, Kartik Lakhotia, Madhu Kumar, Sudarshan Srinivasan, and Tushar Krishna

3 6

4 8

10 12

t=0 0

7 0

3 6 0 11 9 12

1 4 7

t=1 3

Figure 17: 6

t=2

t=3

Figure 15: Pccl-synthesized collective algorithm of two process

Normalized link utilization heat map of Pcclsynthesized vs. Direct collective algorithms, when two process groups are executing All-to-All amongst them. Unlike Pcclsynthesized All-to-All algorithm, Direct fails to leverage the entire network outside the process group, resulting in 2.8× speedup.

4 PCCL

CCLs

0.6 0.4 0.2

1 0 4x4 (1)

6x6 8x8 10x10 12x12 14x14 (2) (3) (4) (5) (6) Mesh Size (#Process Groups)

Pccl showed consistent speedup over the baseline CCLs, 1.33× on average.

Supporting Generic Collective

In this section, we explain the applicability of Pccl for generic collective patterns. First, we evaluate the performance of All-to-All pattern, with the largest search space, in more detail. Figure 14 compares the normalized All-to-All bandwidth of Pccl, CCLs, and state-of-the-art TE-CCL synthesizer. For small-sized Meshes, Pccl and TE-CCL showed comparable performance. However, TE-CCL synthesis breaks after 5×5 Mesh since it is set to search for the very first satisfiable All-to-All algorithm due to scalability considerations, which, even after this setup, is 3 orders of magnitude slower than Pccl (explained in Section 6.1). After 7×7 Mesh, TE-CCL synthesis takes more than 30 minutes (explained in Section 6.1), and Pccl continuously shows better performance than the baseline CCL algorithm.

Synthesis with Process Group

We then showcase the capabilities of Pccl with a simple synthesis example. Over a 3× Mesh, we overlaid two process groups of size

0.8 0.6 0.4 0.2 0

2000000 4000000 Time (ns) PCCL

algorithm over the baseline Direct, as the 2D Mesh size and the number of process groups gradually increase.

6.4

0.8

All-to-All (128 MB), 32 NPUs over 8x8 Mesh 1

Figure 16: Normalized All-to-All bandwidth of Pccl-synthesized

6.3

All-to-All (128 MB), 64 NPUs over 8x8 Mesh 1 Network Utilization

Normalized All-to-All Bandwidth

groups, running All-to-Allv (NPUs 0–2) and All-Gather (NPUs 6–8). NPUs 3–5 network resources are actively used, even though they are not in any of the process group.

Direct

PCCL-Synthesized

Network Utilization

Conditions src dest 0 0 1 1 0 2 2 0 1 Process 3 0 2 Group 1 4 1 2 (All-to-Allv) 5 1 2 6 2 0 7 2 0 8 6 {7, 8} 9 6 {7, 8} Process 10 7 {6, 8} Group 2 (All-Gather) 11 7 {6, 8} 12 8 {6, 7} 13 8 {6, 7}

CCLs

6000000

1000000 2000000 Time (ns) PCCL

3000000

CCLs

Figure 18: Network bandwidth utilization over time, when running 128 MiB All-to-All collective over an 8×8 2D Mesh, with processing group of size 64 and 32, respectively.

three each: group 1 running All-to-Allv (NPUs 0–2, with NPU 0 transmitting twice as much data as NPUs 1–2), and group 2 executing All-Gather (NPUs 6–8), with two chunks per collective. The synthesis result is depicted in Figure 15. Pccl generated a congestion-free collective algorithm over an asymmetric 2D Mesh topology. Pccl also supports arbitrary collectives, provided that pre-/postconditions are specified, as illustrated in this example with All-to-Allv. Finally, note the process group awareness of Pccl: (i) multiple process groups running independent collectives are naturally supported, and (ii) NPUs 3–5 and their associated links, even though not part of any process group, are actively leveraged by the Pccl-generated collective algorithm to maximize performance and resource utilization. We also evaluate the benefits of process group-aware Pccl through All-to-All collective. A large ML cluster with many NPUs often follows this scheme, where multiple groups of collectives are concurrently run, rather than the entire cluster executing a single collective communication. We measured the All-to-All bandwidth of pairwise Direct algorithm (namely CCLs) as well as Pccl-generated algorithms. In doing so, we increased both the size of the target 2D Mesh topology as well as the concurrent numbers of process groups (we set the process group size equal to the Mesh width in this experiment). The normalized algorithmic bandwidth is summarized in Figure 16. Notably, Pccl-synthesized algorithm showed 2.33–3.03× speedup over the baseline Direct (2.68× average). This can be explained by the link utilization heat map captured in Figure 17. When there are two process groups running All-to-All within themselves, Pccl still leverages the entire network resources

Normalized All-to-All Bandwidth

PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer

4 PCCL

transformation that replaces switches with multiple direct links. This enables limited switch modeling but inherits LP scalability constraints and applies only to symmetric networks.

CCLs

3 2 1 0 1

3 4 5 6 #Process Groups

Optimizer-based. Tree-based synthesis provides scalability but limited generality. Optimizer-based methods assign chunk paths using global optimization, supporting arbitrary collectives including All-to-All, at the cost of NP-complete formulations [38]. • SCCL [8] uses satisfiability modulo theories (SMT) to express collective constraints, supporting all patterns but with poor scalability due to NP-hardness [43]. It assumes homogeneous, symmetric, switch-free topologies. • TACCL [48] replaces SMT with ILP and supports heterogeneous networks. Switches are again substituted with multiple direct links. ILP’s NP-hardness restricts scalability; e.g., TACCL fails on a 16-NPU All-to-All within 30 minutes. • TE-CCL [31] uses a multi-commodity flow model that natively represents switch devices. It reduces All-to-All synthesis to LP, yielding moderate scalability for this pattern, but retains ILP for other collectives. For example, TE-CCL synthesizes a 128-NPU All-to-All in 43 minutes but requires over 350 GiB of memory.

Figure 19: Normalized All-to-All bandwidth over CCLs, when the number of 128 MiB All-to-All process groups of size 8 increases over an 8×8 Mesh topology.

to maximize the performance of both All-to-All executions. However, the traffic pattern generated by the Direct algorithm only utilizes localized network resources, resulting in huge network underutilization. The same is applicable to all other previous collective algorithm synthesizers, as none of the synthesizers consider process group and only generate localized collective algorithms. This is further explained in Figure 18. Even when running All-toAll over an entire topology (64 NPUs over an 8×8 2D Mesh), Pccl still outperformed in terms of network resource utilization over the baseline Direct algorithm, showcasing shorter collective time. However, even when the process group is smaller than the topology, unlike the baseline which underutilizes the network, Pccl still maximizes resource utilization, finishing the collective 1.88× faster. The same trend is also exemplified by a sensitivity analysis shown in Figure 19. Here, we fixed the target topology to 8×8 Mesh, and varied the number of concurrent 128 MiB All-to-All process groups (each of size 8). Since Pccl can leverage a lot of free network resources, when there was only one process group executing the collective, Pccl showed 3.05× speedup. As more network resources start to conflict across process groups, the benefit of Pcclsynthesized algorithm decreases as the concurrent process group increases.

7 Related Work 7.1 Collective Algorithm Synthesizers Existing synthesizers fall into three categories based on their synthesis strategy. Tree-based. A spanning tree provides the routing structure for reducing and broadcasting data [51], so tree-based synthesizers generate such trees for the target topology. • Blink [54] constructs multiple disjoint spanning trees, enabling parallel chunk processing. It uses LP to maximize the number of disjoint trees. LP dependence limits scalability— despite polynomial theoretical complexity, practical solvers scale superlinearly [59]. Blink only applies to direct-connect topologies and All-Reduce. • MultiTree [19] improves generality by generating a spanning tree rooted at each NPU, supporting All-Gather and Reduce-Scatter. Its greedy construction is highly scalable but restricted to homogeneous topologies. • ForestColl [61] similarly generates per-NPU spanning trees and extends support to switch-based topologies via an LP

Greedy-based. Greedy synthesizers maximize scalability by heuristically selecting each chunk’s path. • TACOS [55] uses the TEN representation and greedily matches chunks to links. It is highly scalable but supports only AllGather, Reduce-Scatter, and All-Reduce. Switches are modeled using the same indirect substitution approach as ForestColl and TACCL. Overall, prior synthesizers ignore process group structure and assume whole-cluster collectives. They also face trade-offs between scalability and generality.

7.2

Customized Collective Algorithms

Several works manually design topology-specific collective algorithms. BlueConnect [11] and Themis [45] target symmetric multidimensional networks. Three Tree All-Reduce [26] and PAARD [32] specialize All-Reduce for 2D Mesh and DragonFly [24], respectively. MSCCLang [13] and MSCCL++ [49] provide DSLs for manually specifying such algorithms. These approaches require substantial engineering effort and lack portability across diverse or evolving topologies. In contrast, synthesizers like Pccl automatically generate optimized collectives for a given network.

Conclusion

Designing and executing topology-aware collective algorithms is pivotal to optimizing collective communication, which is a major bottleneck in distributed ML. This paper proposes Pccl, a scalable and generic collective algorithm synthesizer. Pccl leverages a BFS pathfinding algorithm over a TEN, resulting in a scalable, generic, and process group-aware synthesizer.

References [1] MPI 4.1. 2023. Introduction and Overview. https://www.mpi-forum.org/docs/ mpi-4.1/mpi41-report/node114.htm.

William Won, Kartik Lakhotia, Madhu Kumar, Sudarshan Srinivasan, and Tushar Krishna

[2] ADC Telecommunications. 2009. Fundamentals of Ethernet Technology. https: //www.adckcl.com/in/en/library/White_Papers/Enterprise/401270IN.pdf. [3] AMD. 2020. AMD Infinity Fabric Link. https://www.amd.com/content/dam/ amd/en/documents/instinct-tech-docs/other/56978.pdf. [4] AMD. 2025. RCCL documentation. https://rocm.docs.amd.com/projects/rccl/en/ docs-6.3.3/index.html. [5] ASTRA-sim. [n. d.]. ASTRA-sim Validation. https://astra-sim.github.io/astrasim-docs/validation/validation.html. [6] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020. Language models are few-shot learners. In Proceedings of the 34th International Conference on Neural Information Processing Systems (Vancouver, BC, Canada) (NIPS ’20). Curran Associates Inc., Red Hook, NY, USA, Article 159, 25 pages. [7] Weilin Cai, Juyong Jiang, Fan Wang, Jing Tang, Sunghun Kim, and Jiayi Huang. 2025. A Survey on Mixture of Experts in Large Language Models. IEEE Transactions on Knowledge and Data Engineering, 1–20. doi:10.1109/tkde.2025.3554028 [8] Zixian Cai, Zhengyang Liu, Saeed Maleki, Madanlal Musuvathi, Todd Mytkowicz, Jacob Nelson, and Olli Saarikivi. 2021. Synthesizing optimal collective algorithms. In Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Virtual Event, Republic of Korea) (PPoPP ’21). Association for Computing Machinery, New York, NY, USA, 62–75. doi:10.1145/3437801. 3441620 [9] Jiamin Cao, Shangfeng Shi, Jiaqi Gao, Weisen Liu, Yifan Yang, Yichi Xu, Zhilong Zheng, Yu Guan, Kun Qian, Ying Liu, Mingwei Xu, Tianshu Wang, Ning Wang, Jianbo Dong, Binzhang Fu, Dennis Cai, and Ennan Zhai. 2025. SyCCL: Exploiting Symmetry for Efficient Collective Communication Scheduling. In Proceedings of the ACM SIGCOMM 2025 Conference (New York, NY, USA, 2025-08-27) (SIGCOMM ’25). Association for Computing Machinery, 645–662. doi:10.1145/3718958.3750499 [10] Cerebras. 2024. Cerebras Demonstrates Trillion Parameter Model Training on a Single CS-3 System - Cerebras. https://www.cerebras.ai/press-release/cerebrasdemonstrates-trillion-parameter-model-training-on-a-single-cs-3-system. [11] M. Cho, U. Finkler, M. Serrano, D. Kung, and H. Hunter. 2019. BlueConnect: Decomposing all-reduce for deep learning on heterogeneous network hierarchy. IBM Journal of Research and Development 63, 6 (2019), 1:1–1:11. doi:10.1147/JRD. 2019.2947013 [12] Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sashank Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, Emily Reif, Nan Du, Ben Hutchinson, Reiner Pope, James Bradbury, Jacob Austin, Michael Isard, Guy Gur-Ari, Pengcheng Yin, Toju Duke, Anselm Levskaya, Sanjay Ghemawat, Sunipa Dev, Henryk Michalewski, Xavier Garcia, Vedant Misra, Kevin Robinson, Liam Fedus, Denny Zhou, Daphne Ippolito, David Luan, Hyeontaek Lim, Barret Zoph, Alexander Spiridonov, Ryan Sepassi, David Dohan, Shivani Agrawal, Mark Omernick, Andrew M. Dai, Thanumalayan Sankaranarayana Pillai, Marie Pellat, Aitor Lewkowycz, Erica Moreira, Rewon Child, Oleksandr Polozov, Katherine Lee, Zongwei Zhou, Xuezhi Wang, Brennan Saeta, Mark Diaz, Orhan Firat, Michele Catasta, Jason Wei, Kathy MeierHellstern, Douglas Eck, Jeff Dean, Slav Petrov, and Noah Fiedel. 2023. PaLM: scaling language modeling with pathways. J. Mach. Learn. Res. 24, 1, Article 240 (Jan. 2023), 113 pages. [13] Meghan Cowan, Saeed Maleki, Madanlal Musuvathi, Olli Saarikivi, and Yifan Xiong. 2023. MSCCLang: Microsoft Collective Communication Language. In ASPLOS 2023 (Vancouver, BC, Canada) (ASPLOS 2023). Association for Computing Machinery, New York, NY, USA, 502–514. doi:10.1145/3575693.3575724 [14] Epoch AI. 2023. Key Trends and Figures in Machine Learning. https://epoch.ai/ trends. Accessed: 2025-04-11. [15] William Fedus, Barret Zoph, and Noam Shazeer. 2022. Switch transformers: scaling to trillion parameter models with simple and efficient sparsity. J. Mach. Learn. Res. 23, 1, Article 120 (Jan. 2022), 39 pages. [16] E. Gabrielyan and R.D. Hersch. 2003. Network topology aware scheduling of collective communications. In Proceedings of the 10th International Conference on Telecommunications (ICT ’03). 1051–1058. doi:10.1109/ictel.2003.1191583 [17] Roger W. Hockney. 1994. The communication challenge for MPP: Intel Paragon and Meiko CS-2. Parallel Comput. 20, 3 (1994), 389–398. doi:10.1016/S01678191(06)80021-9 [18] Haiyang Huang, Newsha Ardalani, Anna Sun, Liu Ke, Hsien-Hsin S. Lee, Anjali Sridhar, Shruti Bhosale, Carole-Jean Wu, and Benjamin Lee. 2023. Towards MoE Deployment: Mitigating Inefficiencies in Mixture-of-Expert (MoE) Inference. In arXiv:2303.06182 [cs.DC]. https://arxiv.org/abs/2303.06182 [19] Jiayi Huang, Pritam Majumder, Sungkeun Kim, Abdullah Muzahid, Ki Hwan Yum, and Eun Jung Kim. 2021. Communication Algorithm-Architecture Co-Design

for Distributed Deep Learning. In 2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA). 181–194. doi:10.1109/ISCA52012. 2021.00023 [20] Ian Cutress. 2019. Analyzing Intel’s Discrete Xe-HPC Graphics Disclosure: Ponte Vecchio, Rambo Cache, and Gelato. https://www.anandtech.com/show/15188/ analyzing-intels-discrete-xe-hpc-graphics-disclosure-ponte-vecchio/5. [21] Intel. 2021. Intel oneAPI Collective Communications Library. https://www.intel.com/content/www/us/en/docs/oneccl/developer-guidereference/2021-15/overview.html. [22] Sylvain Jeaugey. 2019. Massively Scale Your Deep Learning Training with NCCL 2.4. https://developer.nvidia.com/blog/massively-scale-deep-learning-trainingnccl-2-4/. [23] Norm Jouppi, George Kurian, Sheng Li, Peter Ma, Rahul Nagarajan, Lifeng Nai, Nishant Patil, Suvinay Subramanian, Andy Swing, Brian Towles, Clifford Young, Xiang Zhou, Zongwei Zhou, and David A Patterson. 2023. TPU v4: An Optically Reconfigurable Supercomputer for Machine Learning with Hardware Support for Embeddings. In Proceedings of the 50th Annual International Symposium on Computer Architecture (Orlando, FL, USA) (ISCA ’23). Association for Computing Machinery, New York, NY, USA, Article 82, 14 pages. doi:10.1145/3579371.3589350 [24] John Kim, Wiliam J. Dally, Steve Scott, and Dennis Abts. 2008. TechnologyDriven, Highly-Scalable Dragonfly Topology. In 2008 International Symposium on Computer Architecture. 77–88. doi:10.1109/ISCA.2008.19 [25] B. Klenk, N. Jiang, G. Thorson, and L. Dennison. 2020. An In-Network Architecture for Accelerating Shared-Memory Multiprocessor Collectives. In Proceedings of the 47th Annual International Symposium on Computer Architecture (ISCA ’20). 996–1009. doi:10.1109/isca45697.2020.00085 [26] Sabuj Laskar, Pranati Majhi, Sungkeun Kim, Farabi Mahmud, Abdullah Muzahid, and Eun Jung Kim. 2024. Enhancing Collective Communication in MCM Accelerators for Deep Learning Training. In 2024 IEEE International Symposium on High-Performance Computer Architecture (HPCA). 1–16. doi:10.1109/HPCA57654. 2024.00069 [27] Kevin Lee and Shubho Sengupta. 2022. Introducing the AI Research SuperCluster — Meta’s cutting-edge AI supercomputer for AI research. https://ai.meta.com/ blog/ai-rsc/. [28] Yiran Lei, Dongjoo Lee, Liangyu Zhao, Daniar Kurniawan, Chanmyeong Kim, Heetaek Jeong, Changsu Kim, Hyeonseong Choi, Liangcheng Yu, Arvind Krishnamurthy, Justine Sherry, and Eriko Nurvitadhi. 2025. FAST: An Efficient Scheduler for All-to-All GPU Communication. In arXiv:2505.09764 (2025-10-10). arXiv. version: 2. arXiv:2505.09764 [cs] doi:10.48550/arXiv.2505.09764 [29] Shen Li, Yanli Zhao, Rohan Varma, Omkar Salpekar, Pieter Noordhuis, Teng Li, Adam Paszke, Jeff Smith, Brian Vaughan, Pritam Damania, and Soumith Chintala. 2020. PyTorch distributed: experiences on accelerating data parallel training. Proc. VLDB Endow. 13, 12 (Aug. 2020), 3005–3018. doi:10.14778/3415478.3415530 [30] Youjie Li, Iou-Jen Liu, Yifan Yuan, Deming Chen, Alexander Schwing, and Jian Huang. 2019. Accelerating Distributed Reinforcement Learning with In-Switch Computing. In Proceedings of the 46th International Symposium on Computer Architecture (ISCA ’19). 279–291. doi:10.1145/3307650.3322259 [31] Xuting Liu, Behnaz Arzani, Siva Kesava Reddy Kakarla, Liangyu Zhao, Vincent Liu, Miguel Castro, Srikanth Kandula, and Luke Marshall. 2024. Rethinking Machine Learning Collective Communication as a Multi-Commodity Flow Problem. In Proceedings of the ACM SIGCOMM 2024 Conference (Sydney, NSW, Australia) (ACM SIGCOMM ’24). Association for Computing Machinery, New York, NY, USA, 16–37. doi:10.1145/3651890.3672249 [32] Junchao Ma, Dezun Dong, Cunlu Li, Ke Wu, and Liquan Xiao. 2021. PAARD: Proximity-Aware All-Reduce Communication for Dragonfly Networks. In 2021 IEEE Intl Conf on Parallel and Distributed Processing with Applications, Big Data and Cloud Computing, Sustainable Computing and Communications, Social Computing and Networking (ISPA/BDCloud/SocialCom/SustainCom). 255–262. doi:10.1109/ISPA-BDCloud-SocialCom-SustainCom52081.2021.00045 [33] Mellanox Technologies. 2008. InfiniBand Technology Overview. https://network. nvidia.com/pdf/whitepapers/WP_InfiniBand_Technology_Overview.pdf. [34] Hiroaki Mikami, Hisahiro Suganuma, Pongsakorn U-chupala, Yoshiki Tanaka, and Yuichi Kageyama. 2019. Massively Distributed SGD: ImageNet/ResNet-50 Training in a Flash. In arXiv:1811.05233 [cs.LG]. [35] Deepak Narayanan, Mohammad Shoeybi, Jared Casper, Patrick LeGresley, Mostofa Patwary, Vijay Korthikanti, Dmitri Vainbrand, Prethvi Kashinkunti, Julie Bernauer, Bryan Catanzaro, Amar Phanishayee, and Matei Zaharia. 2021. Efficient large-scale language model training on GPU clusters using megatronLM. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (St. Louis, Missouri) (SC ’21). Association for Computing Machinery, New York, NY, USA, Article 58, 15 pages. doi:10.1145/3458817.3476209 [36] NVIDIA. 2025. NVIDIA Collective Communications Library. https://developer. nvidia.com/nccl. [37] NVIDIA. 2025. NVLink and NVLink Switch. https://www.nvidia.com/en-us/datacenter/nvlink/.

PCCL: Process Group-Aware Scalable and Generic Collective Algorithm Synthesizer

[38] Anselm Paulus, Michal Rolínek, Vít Musil, Brandon Amos, and Georg Martius. 2021. CombOptNet: Fit the Right NP-Hard Problem by Learning Integer Programming Constraints. In Proceedings of the 38th International Conference on Machine Learning (ICML ’21), Vol. 139. 8443–8453. [39] Sundar Pichai and Demis Hassabis. 2024. Our next-generation model: Gemini 1.5. https://blog.google/technology/ai/google-gemini-next-generation-modelfebruary-2024/. [40] Jack W. Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d’Autume, Yujia Li, Tayfun Terzi, Vladimir Mikulik, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, Chris Jones, James Bradbury, Matthew Johnson, Blake Hechtman, Laura Weidinger, Iason Gabriel, William Isaac, Ed Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving. 2022. Scaling Language Models: Methods, Analysis, and Insights from Training Gopher. In arXiv:2112.11446 [cs.CL]. https://arxiv.org/abs/2112.11446 [41] Samyam Rajbhandari, Conglong Li, Zhewei Yao, Minjia Zhang, Reza Yazdani Aminabadi, Ammar Ahmad Awan, Jeff Rasley, and Yuxiong He. 2022. DeepSpeedMoE: Advancing Mixture-of-Experts Inference and Training to Power NextGeneration AI Scale. In arXiv:2201.05596 [cs.LG]. https://arxiv.org/abs/2201.05596 [42] Samyam Rajbhandari, Jeff Rasley, Olatunji Ruwase, and Yuxiong He. 2020. ZeRO: memory optimizations toward training trillion parameter models. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (Atlanta, Georgia) (SC ’20). IEEE Press, Article 20, 16 pages. [43] Emil Rakadjiev, Taku Shimosawa, Hiroshi Mine, and Satoshi Oshima. 2015. Parallel SMT Solving and Concurrent Symbolic Execution. In 2015 IEEE Trustcom/BigDataSE/ISPA, Vol. 3. 17–26. doi:10.1109/Trustcom.2015.608 [44] Saeed Rashidi, Srinivas Sridharan, Sudarshan Srinivasan, and Tushar Krishna. 2020. ASTRA-SIM: Enabling SW/HW Co-Design Exploration for Distributed DL Training Platforms. In 2020 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 81–92. doi:10.1109/ISPASS48437.2020. 00018 [45] Saeed Rashidi, William Won, Sudarshan Srinivasan, Srinivas Sridharan, and Tushar Krishna. 2022. Themis: a network bandwidth-aware collective scheduling policy for distributed training of DL models. In Proceedings of the 49th Annual International Symposium on Computer Architecture (New York, New York) (ISCA ’22). Association for Computing Machinery, New York, NY, USA, 581–596. doi:10. 1145/3470496.3527382 [46] Amedeo Sapio, Marco Canini, Chen-Yu Ho, Jacob Nelson, Panos Kalnis, Changhoon Kim, Arvind Krishnamurthy, Masoud Moshref, Dan R. K. Ports, and Peter Richtárik. 2019. Scaling Distributed Machine Learning with In-Network Aggregation. In arXiv:1903.06701 [cs.DC]. [47] Justin Selig. 2022. The Cerebras Software Development Kit: A Technical Overview. https://f.hubspotusercontent30.net/hubfs/8968533/Cerebras%20SDK% 20Technical%20Overview%20White%20Paper.pdf?utm_campaign=Tech% 20Leadership%20PR%202022&utm_source=SDK_WP. [48] Aashaka Shah, Vijay Chidambaram, Meghan Cowan, Saeed Maleki, Madan Musuvathi, Todd Mytkowicz, Jacob Nelson, Olli Saarikivi, and Rachee Singh. 2023. TACCL: Guiding Collective Algorithm Synthesis using Communication Sketches. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). USENIX Association, Boston, MA, 593–612. https: //www.usenix.org/conference/nsdi23/presentation/shah [49] Aashaka Shah, Abhinav Jangda, Binyang Li, Caio Rocha, Changho Hwang, Jithin Jose, Madan Musuvathi, Olli Saarikivi, Peng Cheng, Qinghua Zhou, Roshan Dathathri, Saeed Maleki, and Ziyue Yang. 2025. MSCCL++: Rethinking GPU Communication Abstractions for Cutting-edge AI Applications. In arXiv:2504.09014 (2025-08-21). arXiv. arXiv:2504.09014 [cs] doi:10.48550/arXiv.2504.09014 [50] Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoc Le, Geoffrey Hinton, and Jeff Dean. 2017. Outrageously Large Neural Networks: The Sparsely-Gated Mixture-of-Experts Layer. In arXiv:1701.06538 [cs.LG]. https: //arxiv.org/abs/1701.06538 [51] Rajeev Thakur, Rolf Rabenseifner, and William Gropp. 2005. Optimization of Collective Communication Operations in MPICH. Int. J. High Perform. Comput. Appl. 19, 1 (Feb. 2005), 49–66. doi:10.1177/1094342005051521 [52] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. LLaMA: Open and Efficient Foundation Language Models. In

arXiv:2302.13971 [cs.CL]. https://arxiv.org/abs/2302.13971 [53] Joost Verbraeken, Matthijs Wolting, Jonathan Katzy, Jeroen Kloppenburg, Tim Verbelen, and Jan S. Rellermeyer. 2020. A Survey on Distributed Machine Learning. ACM Comput. Surv. 53, 2, Article 30 (March 2020), 33 pages. doi:10.1145/ 3377454 [54] Guanhua Wang, Shivaram Venkataraman, Amar Phanishayee, Nikhil Devanur, Jorgen Thelin, and Ion Stoica. 2020. Blink: Fast and Generic Collectives for Distributed ML. In Proceedings of Machine Learning and Systems, I. Dhillon, D. Papailiopoulos, and V. Sze (Eds.), Vol. 2. 172–186. https://proceedings.mlsys. org/paper_files/paper/2020/file/cd3a9a55f7f3723133fa4a13628cdf03-Paper.pdf [55] William Won, Midhilesh Elavazhagan, Sudarshan Srinivasan, Swati Gupta, and Tushar Krishna. 2024. TACOS: Topology-Aware Collective Algorithm Synthesizer for Distributed Machine Learning. In 2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO). 856–870. doi:10.1109/MICRO61859. 2024.00068 [56] William Won, Taekyung Heo, Saeed Rashidi, Srinivas Sridharan, Sudarshan Srinivasan, and Tushar Krishna. 2023. ASTRA-sim2.0: Modeling Hierarchical Networks and Disaggregated Systems for Large-model Training at Scale. In 2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 283–294. doi:10.1109/ISPASS57527.2023.00035 [57] William Won, Saeed Rashidi, Sudarshan Srinivasan, and Tushar Krishna. 2024. LIBRA: Enabling Workload-Aware Multi-Dimensional Network Topology Optimization for Distributed Training of Large AI Models. In 2024 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS). 205–216. doi:10.1109/ISPASS61541.2024.00028 [58] xAI. 2025. Colossus. https://x.ai/colossus. [59] Zikai Xiong. 2025. High-Probability Polynomial-Time Complexity of Restarted PDHG for Linear Programming. In arXiv:2501.00728 [math.OC]. https://arxiv. org/abs/2501.00728 [60] Jinsun Yoo, William Won, Meghan Cowan, Nan Jiang, Benjamin Klenk, Srinivas Sridharan, and Tushar Krishna. 2024. Towards a Standardized Representation for Deep Learning Collective Algorithms. In 2024 IEEE Symposium on HighPerformance Interconnects (HOTI). 33–36. doi:10.1109/HOTI63208.2024.00017 [61] Liangyu Zhao, Saeed Maleki, Ziyue Yang, Hossein Pourreza, and Arvind Krishnamurthy. 2025. ForestColl: Throughput-Optimal Collective Communications on Heterogeneous Network Fabrics. In arXiv:2402.06787 [cs.NI]. https: //arxiv.org/abs/2402.06787 [62] Xiaoyang Zhao, Zhe Zhang, and Chuan Wu. 2024. AdapCC: Making Collective Communication in Distributed Machine Learning Adaptive. In 2024 IEEE 44th International Conference on Distributed Computing Systems (ICDCS). 25–35. doi:10. 1109/ICDCS60910.2024.00012

Record · ID 266145 · SHA-256 a201986ac5b19ed3
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.