arXiv CS open access

Configurable and Hierarchical Allreduce

2026 · arxiv_cs

arXiv CS · Papers · 2026

cloud distributed-computing parallel-computing

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Configurable and Hierarchical Allreduce Valentino Guerrini∗‡ , Ke Fan† , Sidharth Kumar∗ ∗ University of Illinois Chicago, Chicago, IL, USA

Email: {vguer24, sidharth}@uic.edu † Temple University, Philadelphia, PA, USA

Email: ke.fan@temple.edu

arXiv:2608.02884v1 [cs.DC] 3 Aug 2026

‡ Politecnico di Milano, Milan, Italy

Abstract—MPI_Allreduce is among the most performancecritical collectives in large-scale scientific computing and distributed machine learning, yet the small- and medium-message regime remains challenging: latency, synchronization depth, and strong hardware hierarchy between intra- and inter-domain communication all compound per-invocation cost. We present CH I A R A, a configurable hierarchical Allreduce that encodes hardware hierarchy through a logical batch–lane topology and executes a staged schedule in which only a bounded portion of the reduction vector is active at a time. Inter-batch communication is distributed across multiple ranks via a rotating-root lane primitive, avoiding centralized leaders. CH I A R A further enables a semi-composed Rabenseifner-style Allreduce by preserving a lanealigned intermediate layout across the Reduce-Scatter/Allgather boundary, eliminating redundant intra-domain reorganization. We evaluate CH I A R A on Polaris, Aurora, and Fugaku, achieving speedups of up to 1.94×, 13.43×, and 13.48× over vendor MPI_Allreduce, and up to 2.2× end-to-end speedup in a parallel k-means application.

I. INTRODUCTION Collective communication is a critical component of largescale scientific computations, data-intensive workflows, and distributed machine learning. Operations such as Allreduce, Allgather, and Reduce-Scatter are invoked repeatedly to exchange intermediate values, synchronize algorithmic state, and compute global reductions. Representative applications include Krylov subspace solvers [1], [2], multidimensional FFT-based simulations [3], ensemble and multi-trajectory workflows [4], and distributed deep learning systems [5]. These workloads may issue tens of thousands of collectives during a single execution, so even modest inefficiencies can accumulate into substantial runtime overhead at scale. Achieving high performance in the small- and mediummessage regime (roughly 64 B to 32 KB per rank in our experiments) remains particularly challenging. Unlike large messages where bandwidth dominates, small messages are sensitive to both the latency term α and the per-round overheads implied by the α–β model[6], including synchronization and message-matching costs. Modern HPC platforms [7], [8] amplify this challenge by exposing strong communication hierarchy: exchanges within a fast shared-memory domain (e.g., within a socket or node) are fundamentally cheaper than exchanges that traverse the network fabric (e.g., Slingshot, InfiniBand, or Tofu-D). As a result, reducing global synchronization depth and restricting expensive communication to a

P0 P1 P2 00 01 02

10 11 12

20 21 22

+ Reduce-Scatter

P0 P1 P2

30 33 36

33 36 Allreduce

30 33 36

Allgather

Fig. 1: Rabenseifner-style Allreduce decomposition into Reduce-Scatter and Allgather [9]. structured subset of the algorithm are central to improving performance in this regime. State-of-the-art implementations of Allreduce are typically built on classical tree- and ring-based algorithms, as well as composite schemes that trade latency for bandwidth across message-size regimes [10]. Modern MPI libraries already incorporate hierarchical designs that distinguish between intranode and inter-node communication to exploit shared memory within nodes. However, these hierarchies are often implicit, fixed by the library implementation, and not directly exposed to algorithm designers or users. Building on this observation, prior work has proposed nodeand topology-aware collectives that optimize these hierarchical strategies by improving aggregation, scheduling, and topology mapping [11], [12]. While these approaches demonstrate substantial performance benefits, they typically rely on predefined hierarchical decompositions and focus on optimizing specific levels of the hierarchy, offering limited flexibility to adapt the overall communication structure to varying node sizes, socket counts, or system scales. More recent research has explored generalized collective frameworks that expose algorithmic parameters, such as radix, to better exploit modern hardware features. Wilkins et al. propose system-agnostic generalized communication kernels with tunable radix values, demonstrating that variable-radix designs can outperform fixed-structure implementations across multiple platforms [13]. While effective at improving generality and adaptability, this work does not explicitly target hierarchical decomposition within nodes or coordinated tuning across Allreduce phases. Overall, existing Allreduce implementations address different parts of the performance space, but with complementary limitations. Latency- and bandwidth-optimized algorithms rely on largely fixed communication structures, while topologyaware approaches operate at the granularity of whole col-

lectives rather than exposing control over their hierarchical organization. On modern HPC systems with strong asymmetry between intra- and inter-node communication, these limitations restrict the ability to systematically balance latency, bandwidth, and hierarchy. This gap motivates Allreduce designs that expose a small set of explicit parameters and directly encode hierarchical structure. This work is driven by the observation that, on modern hierarchical HPC systems, the performance of MPI_Allreduce in the small- and medium-message regime is primarily limited by synchronization depth and redundant data movement across locality boundaries rather than by peak bandwidth. While bandwidth-efficient designs based on Reduce-Scatter followed by Allgather are widely used, their hierarchical realizations typically introduce additional intra-node reorganization steps between phases and often centralize cross-domain communication on a small subset of ranks, creating injection and progress bottlenecks. To address this gap, we develop CH I A R A, a Configurable Hierarchical Allreduce Algorithm inspired by the ReduceScatter + Allgather factorization popularized by Rabenseifner [9] (Figure 1). CHiArA is built on three insights. First, expressing hierarchy through a logical batch–lane topology exposes locality while allowing inter-batch communication to be distributed across multiple ranks instead of a single leader. Second, staging the reduction vector bounds the working set and decouples the inter-batch schedule from the full message size. Third, preserving a lane-aligned intermediate layout across Reduce-Scatter and Allgather eliminates redundant intra-batch reorganization, enabling a semi-composed Allreduce that reduces synchronization and local data movement without altering the inter-batch communication pattern. This paper makes the following contributions: 1) We present CH I A R A, a hierarchical Allreduce with a configurable batch–lane topology that confines the majority of communication to fast shared-memory and exposes a set of tuning parameters, including batch size and independent intra-batch radices for Reduce-Scatter and Allgather. 2) We introduce a staged Reduce-Scatter and Allgather design that preserves a lane-aligned intermediate layout, enabling a semi-composed Allreduce that eliminates redundant intrabatch reorganization otherwise incurred when composing standalone hierarchical collectives. 3) We evaluate CHiArA on three leadership-class systems (Polaris, Aurora, and Fugaku), demonstrating speedups of up to 1.94×, 13.43×, and 13.48×, respectively, over vendor MPI_Allreduce. 4) We integrate CHiArA as a drop-in replacement into an open-source MPI+OpenMP k-means implementation, achieving end-to-end iteration speedups. II. BACKGROUND This section reviews the collective communication algorithms and patterns that form the basis of the hierarchical and parameterized design developed in this paper. We focus on

the algorithmic building blocks used for Allgather, ReduceScatter, and Allreduce. (a) Recursive doubling and recursive halving: Recursive doubling is a classic logarithmic collective algorithm with radix 2, commonly used for Allgather and Allreduce in latency-dominated regimes. In each of log2 P rounds, a process exchanges data with a single partner whose rank differs by a power of two. Recursive halving is the reduction analogue and forms the basis of many Reduce-Scatter implementations. These algorithms are primarily used for small messages, where latency dominates. By completing in O(log P ) rounds, recursive doubling minimizes synchronization overhead and outperforms linear schemes in latency-dominated regimes[14], [15]. For Allgather, the exchanged payload grows across rounds, whereas for Reduce-Scatter via recursive halving the payload shrinks as the vector is progressively partitioned. (b) Ring-based algorithms: Ring algorithms arrange processes in a logical cycle and perform nearest-neighbor communication over P −1 rounds. Each process sends and receives a fixed-size data chunk per round, enabling efficient pipelining and high bandwidth utilization. Ring-based collectives are widely used in production MPI libraries and form the core of bandwidth-optimal Allreduce implementations for large messages, where minimizing total data volume dominates performance. (c) Rabenseifner’s Allreduce: A widely adopted approach for implementing Allreduce is Rabenseifner’s method[9], which decomposes the operation into a Reduce-Scatter followed by an Allgather (two phases). This factorization reduces redundant communication and allows combining bandwidth-efficient algorithms for the two phases. Rabenseifner style Allreduce is used in MPICH, OpenMPI, and vendor MPI implementations and provides the structural foundation for the Allreduce design studied in this work. (d) Recursive exchange and radix-k algorithms: Recursive exchange generalizes recursive doubling by allowing an arbitrary radix 2 ≤ k ≤ P − 1. Each round communicates with k − 1 peers, reducing the number of rounds to ⌈logk P ⌉ at the cost of increased per-round data movement. This defines a continuous design space between logarithmic-depth algorithms and high-fanout, low-depth exchanges. Radix-k exchange patterns form the basis of several generalized Allgather, ReduceScatter, and Allreduce schemes proposed in the literature[13]. (e) Hierarchical collectives: Modern MPI implementations exploit node-level hierarchy by separating intra-node and inter-node communication. Collective operations are decomposed into local shared-memory phases and global network phases, reducing inter-node traffic and improving locality. However, this hierarchical decomposition is typically fixed at the physical node granularity and implemented using a small set of predefined algorithms (e.g., master-based intranode reduction)[11], with limited exposure of algorithmic parameters for tuning or adaptation.

TABLE I: Definitions of Notations P PPN b B x i m Xd I ρ kRS , kAG

Total number of ranks (processes) Number of ranks per node Batch size (ranks per batch) Number of batches (B = P/b) Batch id of rank r (x = ⌊r/b⌋) Lane id of rank r (i = r mod b) Elements contributed per rank Block d of the input vector (size m/B) Number of stages (I = ⌈B/b⌉ = ⌈P/b2 ⌉) Root batch for stage t, lane i (ρ = tb + i) Radices for Reduce-Scatter and Allgather

≥1 0 ≤ PPN < P 1 ≤ b ≤ bmax B≥1 0≤x<B 0≤i<b ≥0 0≤d<B ≥1 0 ≤ ρ; active if ρ < B 2 ≤ kRS , kAG ≤ b − 1

III. D ESIGN OF CH I A R A CH I A R A revisits the classical Rabenseifner Allreduce under modern HPC hierarchical systems. While Rabenseifner achieves communication efficiency through a two-phase decomposition consisting of Reduce-Scatter followed by Allgather, practical implementations (e.g., in MPICH [16] and OpenMPI [17]) incorporate hierarchy using fixed intraand inter-node data exchanges. However, such designs rely on fixed decomposition boundaries and treat the two phases independently, resulting in excessive synchronization depth, redundant data movement at the phase boundary, and imbalanced inter-node communication (see Section II (c) for details). CH I A R A addresses these limitations by jointly introducing explicit and tunable hierarchy. The design overview of CH I A R A is detailed in Section III-A. Specifically, CH I A R A designs an efficient batch–lane structure that exposes hardware hierarchy while distributing global communication across ranks to maximize network utilization (Section III-B). It further introduces a staged execution model that decomposes data into smaller blocks, limiting the working set and balancing workload across ranks (Section III-C). Finally, CH I A R A enables a small set of tunable parameters that directly control the hierarchy granularity and the communication schedules to adapt to various hardware and workloads (Section III-D). A. Design Overview The core design principle of CH I A R A is to enable hierarchical, fully distributed communication with explicit tunable control, eliminating centralized bottlenecks while adapting to hardware and workload diversity. At a high level, the algorithm decomposes into four structured phases: local reduce-scatter, global reduction, global broadcast, and local allgather. The first two phases together realize a hierarchical Reduce-Scatter, while the latter two implement a hierarchical Allgather. Local reduce-scatter first combines data within small local groups, reducing the data volume per participant in global communication and exposing parallelism. Global reduction then

aggregates these partial results across groups, distributing communication across multiple participants to avoid centralized bottlenecks. Global broadcast subsequently disseminates the reduced results back to all groups without introducing additional coordination overhead. Finally, local allgather reconstructs the full result within each group, leveraging efficient local communication. With this design, ranks are grouped into batches that serve as locality domains and map communication onto fast intranode bandwidth. The batch size is tunable from 1 to the number of ranks per node (PPN), allowing flexible control over the locality granularity. This grouping separates communication into intra-batch and inter-batch phases, enabling locality-aware execution. However, routing inter-batch communication through a single representative per batch leads to serialization and underutilization of network bandwidth. To address this limitation, CH I A R A introduces lanes: ranks with the same intra-batch index across batches form independent communication paths, allowing multiple ranks to participate in inter-batch reduction and broadcast concurrently. This design distributes communication load across participants and eliminates centralized bottlenecks. Together, batches and lanes form the essential batch–lane structure of CH I A R A. Importantly, this structure aligns naturally with the Reducescatter/Allgather boundary. Lane-parallel inter-batch reduction produces disjoint sets of fully reduced blocks, and inter-batch broadcast reuses the same lanes to redistribute them. As a result, no additional data reorganization is required between phases, and both proceed with the same distributed execution pattern without introducing extra synchronization overhead. To map computation onto this structure, the input vector per rank is uniformly partitioned into blocks, one per batch, ensuring balanced workload distribution. Execution proceeds in stages, each activating a subset of lanes to process their assigned blocks. This staged execution bounds the working set, enables pipelined progress, and reduces global synchronization depth. We now formalize these structural concepts used in CH I A R A. B. Logical batch–lane Topology We organizes ranks into two logical dimensions, batch and lane. Let P be the number of MPI ranks. CH I A R A partitions ranks into batches of size b (batch-size), yielding B = P/b batches. To keep intra-batch communication inside the intended fast domain, b should not larger than P P N . Formally, each rank r ∈ [0, P ) is mapped to: r = xb + i, where x is the batch ID and i is the lane ID (position within a batch). All ranks with the same i across batches form a lane. This induces a logical B × b grid: rows are batches and columns are lanes. Figure 2 (left) illustrates this mapping for P = 9 and b = 3. Each three ranks in a row with the same color is defined as a batch, while each three ranks in a column with the same shape pattern is defined as a lane. Batches are a logical partition computed by integer division and modulo and do not require communicator splits.

N1 Fig. 2: Batch–lane topology and staged block mapping. Left: P = 9 (from 2 nodes) and b = 3 form B = 3 batches (colors) and b = 3 lanes (patterns), with rank r = xb + i. Right: each rank partitions X[0:m) N0 N1 into B blocks {Xd }. Bz

B0 P0 P1

x00

y00

100

500

x01

y01

102

502

x02

y02

104

504

x03

B1 P2 P3

B2 P4 P5

B3 P6 P7

900

1300

902

1302

904

1304

y03

106

506

906

1306

x04

y04

108

508

908

1308

x05

y05

110

510

910

x06

y06

x07

112

512

y07

114

514

x08 2 y08

116

516

912

1314

916

1316

y09

118

518

918

1318

x10

y10

120

520

920

1320

Phase II

B1 P2

P3 2824

2808

2832

2816

2840

N1 B2 B3 P5 P6 P7

2848

2872

2856

2880

1310

914

B0 P1

2800

1312

x09

Phase I

2864

Phase III

Fig. 3: Hierarchical Reduce-Scatter follows a three-phase structure. Phase I illustrates intra-batch local reduction using two neighboring ranks, Px and Py , within a batch Bz containing m = 11 elements. Phase II captures inter-batch reduction across four batches (B0 –B3 ) spanning two nodes (N0 , N1 ). Phase III completes the process by redistributing the reduced blocks within each batch, ensuring that each block is delivered to its designated owner. Both Phase I and Phase II adopt a staged execution model with two stages (indicated by blue and orange boxes). Color coding consistently tracks blocks according to their destination ranks throughout all phases. C. Block and stage decomposition. CH I A R A processes the input vector in stages, rather than as a single operation. Each rank contributes a vector X[0:m), which is partitioned into B contiguous blocks evenly (one per batch); the last few blocks may contain fewer elements when m is not divisible by B (Figure 2 right). At stage t, each lane i operates on a block d: d = t · b + i. In each stage, at most one block is assigned per lane, enabling up to b blocks to be processed with b lanes in parallel. As a result, processing all B blocks requires ⌈B/b⌉ stages, and the number of stages is I = ⌈B/b⌉ = ⌈P/b2 ⌉. This design bounds the active working set that improves data locality, keeps work balanced across lane, reduces global synchronization overhead by decomposing computation into fine-grained steps, and maximizes parallel utilization of the batch–lane topology. Example: Consider P = 24 processes with batch size b = 3, yielding B = 8 batches. Suppose each rank r holds 23

elements. We partition X[0 : 23) into 8 blocks, where the first 7 blocks contain 3 elements each and the last block contains 2 elements. In this case, the algorithm proceeds in I = ⌈B/b⌉ = 3 stages, with the stage index t ranging from 0 to 2. While the first two stages (t = 0, 1) handle 3 blocks each, the last stage handles 2 blocks. Each batch contains three lanes indexed by 0, 1, 2. At stage t, lane i operates on block d = tb+i (whenever d < B). Thus, stage 0 assigns blocks 0, 1, 2 to lanes 0, 1, 2, respectively; stage 1 assigns blocks 3, 4, 5 to lanes 0, 1, 2; and stage 2 assigns blocks 6, 7 to lanes 0, 1. D. Tunable Parameters While the design above defines an efficient communication structure, its performance depends on several key tradeoffs, including the balance between intra- and inter- batch communication, and between communication depth and perround overhead. These trade-offs vary across communication configurations, making a single fixed configuration suboptimal. To expose and control these trade-offs, CH I A R A introduces a small set of tunable parameters that directly shape the communication structure. Batch-size: CH I A R A first introduce a tunable batch-size b, which controls the number of ranks per batch, determining the granularity of hierarchical decomposition. A larger b increases work performed within fast intra-batch communication, reducing inter-batch communication rounds, but raises intra-batch cost and may exceed fast hardware domain capacity. A smaller b reduces intra-batch overhead at the cost of more global stages and higher synchronization overhead. Thus, b provides a direct mechanism to balance intra-domain efficiency against interdomain communication cost. Intra-batch radices: CH I A R A further exposes independent radix parameters for intra-batch communication in the ReduceScatter and Allgather phases, denoted as kRS and kAG . These parameters control the fanout of intra-batch communication. A larger radix reduces communication rounds and synchronization depth but increases per-round volume and contention; a smaller radix has the opposite effect. Crucially, kRS and kAG are tuned independently, reflecting the distinct communication characteristics of each phase. IV. P ROPOSED A LGORITHMS OF CH I A R A Building on the design in Section III, CH I A R A has two hierarchical building blocks: Reduce-Scatter and Allgather. Each of them consists of both intra- and interbatch communication, following the same batch-lane topology and staged execution model. This unified structure enables intra-batch communication to be mapped onto high-bandwidth shared-memory domains, while inter-batch communication is distributed across lanes through a rotating lane-root assignment, allowing multiple ranks to participate concurrently and improving network utilization. In this section, we present the algorithms underlying CH I A R A. We begin with the hierarchical algorithmic structure of the two hierarchical building blocks (Section IV-A), and then describe their concrete realizations. For intra-batch

N0 B0 B1 P1 P2 P3

N0 B0 B1 P0 P1 P2 P3 00

N1 B2 B3 P4 P5 P6 P7

Px 00 10

10 20

By Px+1

B2 P5

Phase I

P7 2

60 50

B3 P6

20 30

60 70

Phase II

60 70

Phase III

Fig. 4: Hierarchical Allgather (example) with eight ranks (P0 –P7 ) spanning two nodes (N0 , N1 ) and four batches (B0 – B3 ). Each rank initially holds its scattered partition, with numeric labels denoting example data values. Each stage t (block d = tb + i) proceeds in three phases: Phase I redistributes blocks within each batch so that each lane rank holds the block assigned to its lane (required only for standalone Allgather); Phase II broadcasts along lanes across batches via L ANE O P(BCAST), with root batch ρ = tb + i sending its block to all other batches; Phase III replicates all stage blocks within a generic batch By via radix-kAG intra-batch recursive exchange, so that every rank in the batch holds the complete result. Color coding groups blocks by their originating rank throughout all three phases. communication, CH I A R A designs distinct algorithms for Reduce-Scatter and Allgather, each parameterized by a tunable radix (Section IV-B). For inter-batch communication, both building blocks share a unified communication primitive, L ANE O P (Section IV-C), which enables fully distributed cross-batch reduction and broadcast. Finally, CH I A R A introduces a semi-composed execution algorithm that preserves a structured intermediate layout across Reduce-Scatter and Allgather, eliminating redundant data movement between phases (Section IV-D). A. Algorithmic Structure of the Hierarchical Building Blocks This section outlines the algorithmic structure of the two hierarchical building blocks, Reduce-Scatter and Allgather, followed by their integration via a semicomposed execution that eliminates redundant phases. Hierarchical Reduce-Scatter performs global reduction and produces a distributed partition of the result. It is decomposed into three phases: intra-batch reduction, inter-batch reduction, and intra-batch redistribution. The first phase aggregates partial results within each batch. The second phase completes the reduction across batches to produce globally reduced data. The final phase redistributes the reduced data within each batch to match the output layout required by Reduce-Scatter. Figure 3 illustrates this three-phase structure. Hierarchical Allgather replicates distributed data such that every rank obtains the full result. It follows a symmetric threephase structure: intra-batch alignment, inter-batch broadcast, and intra-batch allgather. The first phase prepares the local data layout for global communication. The second phase

disseminates data across batches so that all batches receive the required intermediate results. The final phase completes replication within each batch. Figure 4 illustrates this process. Semi-composed execution is then introduced by CH I A R A that preserves a lane-aligned intermediate layout across the boundary of the two building blocks. This design eliminates the need for the intra-batch redistribution phase in Reduce-Scatter and the intra-batch alignment phase in Allgather. As a result, the combined execution proceeds in four phases, reducing redundant data movement and synchronization while remaining consistent with the design described in Section III-A. Figure 5 illustrates the four-phase. B. Intra-batch Algorithms This section presents the intra-batch communication algorithms used in the local phases of both hierarchical building blocks, including intra-batch reduction in Reduce-Scatter and intra-batch allgather in Allgather. Within each batch, communication is performed using radix-parameterized recursive exchange, enabling efficient use of shared-memory bandwidth while providing flexible control over communication depth and per-round cost. In all algorithms, we assume ranks have been organized into batch-lane topology with B batches and b lanes. The input vector per rank is also partitioned into B contiguous blocks, and and execution proceeds stage by stage (as defined in Section III). Intra-batch Reduce-scatter: Algorithm 1 describes the intra-batch reduction procedure. For stage t, at most one block d = tb + i is assigned to each lane i (line 1). Within each batch, the ranks collaboratively reduce the active blocks using a radix-kRS recursive-exchange schedule. The radix kRS determines that each active rank communicates with up to (kRS − 1) other ranks per round, for a total of ⌈logkRS b⌉ rounds. In each round, ranks exchange only a slice of the active blocks in the current stage for a specific target rank and immediately apply the reduction operator in-place (lines 9-12). Radix-kRS recursive exchange requires the number of participating ranks to be a power of kRS to form complete communication groups per round. Thus, when b is not a power of kRS , not all ranks in the batch can participate in the data exchange. In that case, a non-participating rank sends its active blocks to a participating rank in the same batch, which is referred to as fold (lines 5-6). After the exchange completes, the reduced result corresponding to each non-participating rank is sent back, which is referred to as unfold (lines 14). This phase produces a lane-aligned state: for each active lane i in stage t, rank i in each batch holds the batch-local reduced result for block d = tb + i, thereby combining reduction and local scattering. Intra-batch Allgather: Algorithm 3 describes the intrabatch allgather procedure. Due to the same batch-lane topology, this algorithm also enables each lane i handles one reduced block d per stage t (line 1). Within each batch, the ranks collaboratively replicate the active blocks using a radix-kAG recursive-exchange schedule, which proceeds in ⌈logkAG b⌉ rounds (line 5). In each round, a rank communicates with up

Px x00

N0 B0 B1 P0 P1 P2 P3

y00

100

500

x01

y01

102

502

x02

y02

104

504

Stage

x03

Stage

N1 B2 B3 P4 P5 P6 P7

N0 B0 B1 P0 P1 P2 P3

900

1300

2800

902

1302

2808

904

1304

2816

y03

106

506

906

1306

2824

x04

y04

108

508

908

1308

2832

x05

y05

110

510

910

1310

2840

x06

y06

112

512

x07

y07

114

514

x08 2 y08

116

516

2816

2848

914

1314

2856

916

1316

2864

118

518

918

1318

x10

y10

120

520

920

1320

Phase II-a (LaneOP REDUCE)

2824

2840

1312

y09

Bz Px+1

2832

912

x09

Phase I

N1 B2 B3 P4 P5 P6 P7

Phase II-a (LaneOP BCAST)

2864 2 2872

2872

2880

Phase III

Fig. 5: Semi-composed hierarchical Allreduce example. Allreduce is executed in four phases with this design: intra-batch Reduce-Scatter, inter-batch lane reduction, inter-batch lane broadcast, and intra-batch Allgather. Algorithm 1 Intra-batch Radix-kRS Reduce-Scatter

Algorithm 2 Rotating-root inter-batch lane operation

1: d ← tb + i 2: if d ≥ B then 3: return 4: end if 5: if non-participating then 6: send active blocks to a participating rank ▷ fold 7: end if 8: reduce folded data (if any) 9: for each ⌈logkRS b⌉ rounds do 10: exchange slices of active blocks with up to (kRS − 1) target ranks 11: apply reduction in-place 12: end for 13: U ← block d 14: send U to folded ranks (if any) ▷ unfold 15: return U

Require: mode ∈ {REDUCE, BCAST}, stage t, batch id x, lane id i Require: B batches, batch size b, local block V (size m/B), reduction ⊕ Ensure: updated block V ′ (reduced at root / broadcast to all) 1: ρ ← tb + i ▷ root batch 2: if ρ ≥ B then 3: return V 4: end if 5: root ← ρ · b + i ▷ lane root rank 6: if mode = REDUCE then 7: if x = ρ then ▷ root accumulates 8: A←V 9: for y = 0 to B − 1, y ̸= x do 10: recv T from rank (y · b + i); A ← A ⊕ T 11: end for 12: return A 13: else 14: send V to rank root; 15: return V 16: end if 17: else ▷ mode = BCAST 18: if x = ρ then ▷ root distributes 19: for y = 0 to B − 1, y ̸= x do 20: send V to rank (y · b + i) 21: end for 22: else 23: recv V from rank root 24: end if 25: return V 26: end if

to (kAG −1) peers (line 6). Specifically, for each neighbor, the rank receives a contiguous segment of blocks and sends out its currently available prefix of blocks (lines 5–9). After each round, the number of blocks available at a rank increases by a factor of kAG (line 8). When b is not a power of kAG , some communication groups in a round may be incomplete. In that case, the exchanged segment size is clipped to avoid exceeding the valid block range (line 7). After all rounds complete, each rank holds all active blocks for the current stage. A final local reindexing step restores the blocks to their natural lane order (line 10), completing the intra-batch allgather. C. Inter-batch Algorithm (LaneOp) Both hierarchical Reduce-Scatter and hierarchical Allgather require inter-batch communication. CH I A R A expresses all such inter-batch traffic through L ANE O P (Algorithm 2), which is invoked in two complementary modes: REDUCE for lanewise accumulation (used by Reduce-Scatter) and BCAST for lane-wise distribution (used by Allgather). Formally, for each stage t and lane i, L ANE O P selects a unique root batch ρ = tb + i (line 1). If ρ ≥ B, lane i is inactive and L ANE O P returns immediately. Otherwise, the corresponding lane root rank is root = ρb + i (line 5). In REDUCE mode, the root rank accumulates values across

batches: it initializes the accumulator with its local value and receives contributions from all other batches along the same lane, applying the reduction operator upon arrival (lines 6– 10). Non-root ranks simply send their local value to root (line 15). In BCAST mode, the communication pattern is reversed: the root rank sends its value to all other batches, while non-root ranks receive from root (lines 17–23). Because ρ depends on (t, i), the root responsibility rotates across lanes and stages, distributing inter-batch communication across ranks rather than concentrating it on a fixed leader.

Algorithm 4 CH I A R A: Semi-composed hierarchical Allreduce

Algorithm 3 Intra-batch Radix-kAG Allgather 1: d ← tb + i 2: if d ≥ B then return 3: end if 4: G ← {block d} 5: for each ⌈logkAG b⌉ rounds do 6: exchange subsets of G with up to (kAG − 1) neighbors 7: clip exchanged blocks for non-powers of kAG 8: expand G by a factor of kAG 9: end for 10: U ← block d 11: reorder G to natural block order 12: return G

▷ unfold

D. Semi-composed Execution Algorithm The above building blocks can be composed to implement Allreduce. However, a naive composition introduces redundant intra-batch work at the boundary between Reduce-Scatter and Allgather. In particular, hierarchical Reduce-Scatter performs a batch-local redistribution to place reduced blocks on their final scattered owners, while hierarchical Allgather begins with a batch-local lane-alignment step to reconstruct the layout required for lane-wise broadcast. CH I A R A avoids both these redundant steps by preserving the lane-aligned intermediate layout, as shown in Algorithm 4. In Phase I (lines 4–9), each batch performs an intra-batch Reduce-Scatter. Each batch locally reduces the corresponding blocks using radix-kRS recursive exchange, producing a lane-aligned partial result Rt . In Phase II-a (lines 10–12), the reduction is completed across batches. For each stage, L ANE O P is invoked in REDUCE mode to aggregate the lanealigned values across batches, producing the globally reduced block Ut at the lane root. In Phase II-b (lines 13–15), the reduced result is distributed back to all batches. L ANE O P is invoked in BCAST mode so that each batch obtains the reduced block at its corresponding lane rank (x, i), preserving the lane-aligned layout. In Phase III (lines 16–18), each batch performs an intra-batch Allgather using radix-kAG recursive exchange. Starting from the lane-aligned blocks, each rank replicates the stage blocks within the batch, producing the final output segments Yt . After Phase II-b, each batch already holds the reduced stage blocks in the exact layout required by Phase III, enabling a direct composition of Reduce-Scatter Phases I–II with Allgather Phases II–III without any intermediate local reorganization. Importantly, this semi-composition does not constrain the intra-batch algorithms: the reduction and replication phases remain independent, exposing separate radices kRS and kAG , while sharing the same inter-batch lane schedule. V. E VALUATION We evaluate CH I A R A using microbenchmarks on three leadership-class systems: Polaris and Aurora at Argonne Leadership Computing Facility (ALCF), and Fugaku at RIKEN R-CCS. Polaris is an HPE Cray Slingshot 11 system with single-socket AMD EPYC (Zen3) CPUs (32 cores per node), Aurora is an HPE Cray Slingshot 11 system with dual-socket

Require: rank r, size P , input : m), op ⊕, batch b, radixes kAG , kRS LX[0 −1 Ensure: output Y [0 : m) = P p=0 Xp 1: i ← r mod b; x ← ⌊r/b⌋ ▷ lane ID, batch id 2: B ← P/b; I ← ⌈B/b⌉ ▷ = ⌈P/b2 ⌉ 3: split X into B equal blocks {Xd }B−1 (each size m/B) d=0 4: for t = 0 to I − 1 do ▷ Phase I: intra-batch Reduce-Scatter 5: d←t·b+i 6: if d < B then 7: Rt ← I NTRA RSk i, b, kRS , {Xtb , . . . , Xmin((t+1)b,B)−1 }, ⊕ 8: end if 9: end for 10: for t = 0 to I − 1 do ▷ Phase II-a: inter-batch lane reduction 11: Ut ← L ANE O P(REDUCE, t, x, i, B, b, Rt , ⊕) 12: end for 13: for t = 0 to I − 1 do ▷ Phase II-b: inter-batch lane broadcast 14: Rt ← L ANE O P(BCAST, t, x, i, B, b, Ut , ⊕) 15: end for 16: for t = 0 to I − 1 do ▷ Phase III: intra-batch Allgather (radix k) 17: Yt ← I NTRA AGk (i, b, kAG , Rt ) ▷ b blocks for stage t 18: end for

Intel Xeon Max CPUs (104 cores per node), and Fugaku uses Fujitsu A64FX CPUs (48 user-accessible cores per node) interconnected by the Tofu-D 6D mesh/torus network. All measurements use CPU-resident MPI collectives and run at full node concurrency (one rank per core). Since CH I A R A uses a logical batch mapping based on contiguous rank ids (Section III), ranks are placed so that contiguous rank groups map to the intended locality domain (socket on multi-socket nodes, node on single-socket systems). Each reported runtime is the median over 50 iterations. The evaluation follows the design structure in Section III. We first study the batchsize parameter b (Section V-A), which defines the batch– lane decomposition and controls the number of inter-batch stages I = ⌈P/b2 ⌉. We then examine radix selection for the hierarchical building blocks (Section V-B), focusing on the distinct behaviors of kAG for Allgather and kRS for ReduceScatter. Next, we quantify the end-to-end benefit of semicomposition in CH I A R A (Section V-C). Finally, we compare CH I A R A against vendor MPI_Allreduce implementations on all three systems (Section V-D). Message-size convention. Unless stated otherwise, all plots report the per-rank segment size S (in doubles) used by the staged schedule. This S corresponds to the Allgather send count (equivalently, the Reduce-Scatter receive count). The equivalent MPI_Allreduce element count is P · S. A. Batch Decomposition The batch size b defines the logical batch–lane topology in Section III: ranks are grouped into contiguous batches of size b, and inter-batch communication occurs along lanes in I = ⌈P/b2 ⌉ stages. Increasing b reduces √ √ the number of stages, with I = 1 once b ≥ P . For b < P , multiple full stages are required and the final stage may be partial. At the same time, larger b increases the cost of the intra-batch phases because more ranks participate in each recursive-exchange round. To keep intra-batch communication inside the intended fast domain, we additionally restrict b ≤ bmax , where bmax is

b=16 b=32 256 procs (8 nodes)

10.0

1.0

0.10 0.1 1

b=13 208 procs (2 nodes)

256 4096

send count

b=16 b=26 832 procs (8 nodes)

256 4096

b=52 3328 procs (32 nodes) 1000

10.0

100

1.0

1.00

send count

0.10 1

256 4096

0.1

256 4096

Per-rank segment size (Doubles)

256 4096

Fig. 6: Sensitivity of hierarchical Allgather runtime to the batch size b on Polaris (top) and Aurora (bottom). the maximum number of ranks placed on a single socket (and equals ranks per node on single-socket systems). Figure 6 shows the sensitivity of hierarchical Allgather runtime to b on Polaris (top) and Aurora (bottom) for representative process counts. Two trends are consistent √ across configurations. First, the best-performing b lies near P , reflecting the reduction in inter-batch stages I = ⌈P/b2 ⌉. Second, choosing b beyond the socket limit degrades performance because the intra-batch phases spill into slower locality levels; this effect is visible on systems where candidate b values exceed bmax . Across segment sizes, the best-performing b is stable and its neighbors are the next-best choices, with runtimes degrading as b moves away from the optimum. Based on these results, all subsequent experiments select b using a simple rule consistent with the cost-model guidance: among √ divisors of P , choose the value b ≤ bmax that is closest to P (breaking ties toward the larger b). This behavior holds for Reduce-Scatter since it shares the same stage structure and inter-batch schedule. B. Radix Sensitivity of the Building Blocks We now examine how the intra-batch radices affect the two hierarchical building blocks. Recall that CH I A R A exposes two independent radices: kRS for the intra-batch ReduceScatter phase and kAG for the intra-batch Allgather phase. This separation matters because the two collectives stress different parts of the communication stack and have different dependency structures. Figure 7 sweeps kAG for hierarchical Allgather on all three systems. For small segment sizes, √ the best-performing radix consistently clusters near kAG ≈ b. In this latencydominated regime, a moderate fanout balances the reduction in communication depth against per-round synchronization and message-matching overhead. As the per-rank segment size increases, the optimum shifts toward larger radices, and for medium to large messages the minimum is attained near the upper end of the admissible range, with kAG often close to b − 1. This trend reflects the recursive-exchange tradeoff: larger kAG reduces the number of rounds ⌈logkAG b⌉ but

Time (ms)

256 4096

Time (ms)

send count

Time (ms)

0.1

Time (ms)

1.00

b=64 1024 procs (32 nodes)

Time (ms)

b=8

Time (ms)

Time (ms) -- log scale Time (ms) -- log scale

b=4 64 procs (2 nodes)

0.2

Polaris 0.4

P = 1024, B = 32, S = 32

0.2

0.3

0.2

10 20 P = 1024, B = 32, S = 128

0.7

0.5

0.2

1.2

Radix (k)

3.2

Radix (k)

P = 832, B = 26, S = 512

2.1

0.6

5 10 15 20 P = 832, B = 26, S = 1024

4.5

3.8

1.5 9.8

5 10 15 20 P = 832, B = 26, S = 2048

8.1

3.2

Radix (k)

6.7

0.9

Fugaku 1.6 P = 1536, B = 48, S = 128

0.7

1.4 0

10 20 30 40 P = 1536, B = 48, S = 512

2.5 2.2

Aurora 2.9

P = 832, B = 26, S = 256

0.9

2.8

10 20 30 P = 1024, B = 32, S = 1024

5.6 4.2

0.4

0.6

P = 1024, B = 32, S = 64

1.2 5.4

Radix (k)

P = 1536, B = 48, S = 256

10 20 30 40 P = 1536, B = 48, S = 1024

4.7 0

Radix (k)

4.1

Radix (k)

Fig. 7: Radix sensitivity of hierarchical Allgather on different systems. Execution time is shown as a function of kAG for representative process counts and and per-rank segment sizes. increases per-round fanout and data per round. For larger messages, the optimum therefore depends on whether the platform can sustain the higher fanout; in our measurements it typically shifts toward kAG close to b − 1. Reduce-Scatter shows markedly different behavior. Figure 8 plots the three best-performing radices for hierarchical Reduce-Scatter on each system. On all platforms and per-rank segment sizes, the radix kRS = 2 consistently minimizes runtime. Intuitively, the reduction dependency structure limits the benefit of aggressive fan-in, while larger radices increase perround message pressure and local reduction overhead without sufficient depth reduction to compensate. Consequently, we fix kRS = 2 in the remainder of the evaluation and treat kAG as the primary message-size-dependent tuning knob. C. Impact of Semi-Composition We next quantify the benefit of semi-composition in CH I A R A. As shown in Section IV-D, CH I A R A preserves the lane-aligned intermediate layout produced by inter-batch

Polaris

Time (ms)

7.4

k=4

k=3

ring

103.5

P = 64, b = 8

0.4

k=2

k=5

0.1

211

Send count (Doubles)

Time (ms)

37.1

k=4

k=6

210

Send count (Doubles)

k=2

k = 51

k=9

P = 1664, b = 52

0.2

212

Time (ms)

k=2

k=3

k=4

210

212

Send count (Doubles)

16.1

P = 96, b = 12

0.3 0.0

k=2

210

212

k=6

k = 10

P = 2304, b = 48

0.2

Per-rank segment size (Doubles)

210

Per-rank segment size (Doubles)

Fig. 8: Radix sensitivity of hierarchical Reduce-Scatter. Each panel shows the three best-performing kRS values (selected by overall runtime across per-rank segment sizes) for a small and a large configuration on each system. In all cases, the binary radix kRS = 2 is optimal across segment sizes.

Time (ms)

Polaris P=1024 Hierarchical RS+AG (total) Hierarchical AG Hierarchical RS CHiArA

101 100

64 12 8 25 6 51 2 10 24 20 48 40 96

10 1

128

512

20484096

128

Per-rank segment size (Doubles)

512

20484096

overheads are most visible. D. Comparison with Vendor MPI_Allreduce

2.0

Fig. 10: Allreduce latency versus per-rank segment size for 512 and 4096 processes. The default MPI_Allreduce in MPICH closely tracks the fastest internal algorithm across message sizes, motivating its use as the baseline.

Fugaku 2.8

101 100

211

5.6

102

205.6

1.4

MPI_Allreduce

4096 processes

Send count (Doubles)

P = 208, b = 13

0.1

rec_mul (best k)

103

Aurora k=2

rec_dbl

512 processes

P = 1024, b = 32

2.7

0.0

rs+ag

k=8

time (ms)

k=2

Per-rank segment size (Doubles)

Fig. 9: Effect of semi-composition on Allreduce runtime. reduction and reuses it as the input to the inter-batch broadcast and the final intra-batch replication. This removes the redundant boundary work that would otherwise occur when composing standalone Reduce-Scatter and standalone Allgather. Figure 9 compares CH I A R A against a naive hierarchical Allreduce constructed as standalone Reduce-Scatter followed by standalone Allgather, and also shows the corresponding phase components. Across segment sizes, semi-composition consistently reduces runtime by eliminating redundant intrabatch data movement and synchronization at the ReduceScatter to Allgather boundary, with the largest relative gains appearing in the small to medium regime where intra-batch

We now compare the final CH I A R A configuration against the vendor MPI_Allreduce on each platform. All CH I A R A parameters are fixed according to the sensitivity studies above: b is selected by the batch rule in Section V-A, kRS is fixed to 2 based on Figure 8, and kAG is selected based on the message-size trends observed in Figure 7. We use vendor MPI_Allreduce as the baseline because it performs internal algorithm selection as a function of per-rank segment size and scale; Figure 10 explicitly validate that this baseline tracks the best available MPICH variants across the studied regimes. Figures 11 report the speedup of CH I A R A relative to the baseline as a function of process count and per-rank segment size. Each heatmap cell reports the ratio between the median runtime of the vendor MPI_Allreduce and that of CH I A R A for the same configuration; values larger than 1 indicate configurations where CH I A R A is faster. On Polaris (Figure 11 (left)), CH I A R A provides consistent gains in the small to medium regime and at scale, reaching up to about 1.9×. Aurora (Figure 11 (right)) shows substantially larger improvements, with speedups exceeding 10× in several regions and peaking above 13×, reflecting the deeper effective hierarchy and higher sensitivity to synchronization depth at scale. Fugaku (Figure 11 (center)) shows a similar pattern, with the strongest gains concentrated in small to medium send counts and moderate to large process counts. For very large messages, speedups approach 1 as bandwidth dominates and baseline implementations approach peak throughput. VI. A PPLICATION C ASE S TUDY: PARALLEL K-M EANS To complement the microbenchmarks in Section V, we evaluate CH I A R A in an end-to-end application by integrating it into an open-source parallel MPI+OpenMP implementation of Lloyd-style k-means clustering[18]. In each iteration, every rank (i) assigns its local points to the closest centroid, (ii) accumulates per-cluster membership counts and per-cluster coordinate sums, and (iii) forms updated global centroids via collective reductions. Concretely, the implementation invokes MPI_Allreduce three times per iteration: a reduction of the cluster counts (length K integers), a reduction of the centroid

1.2 1.1 1.0

8 16 32 64 12 8 25 6 51 2 10 24 20 48 40 96

Per-rank segment size (Doubles)

6 5 4 3 2 1

5408

3328 1.74× 1.13× 10.41× 1.08× 4.27× 1.51× 1.35× 1.02× 1.11× 1.04× 2704 2.02× 1.51× 1.09× 1.01× 3.66× 5.32× 4.28× 1.12× 1.34× 1.10× 1664

1.75× 1.26× 1.06× 1.01× 3.80× 1.02× 4.65× 4.27× 2.07× 1.07×

832 1.40× 1.89× 1.22× 1.22× 1.03× 1.07× 1.81× 8.84× 1.79× 1.04× 416 1.13× 1.87× 2.28× 1.35× 1.15× 1.16× 1.09× 1.28× 0.98× 0.69× 208 0.97× 1.42× 1.71× 2.08× 1.67× 1.14× 0.88× 0.63× 0.61× 0.65×

6 5 Speedup (×)

1.3

1.83× 1.80× 13.33× 8.70× 5.63× 1.57× 1.33× 1.01× 1.02× 1.06×

4 3 2 1

64 12 8 25 6 51 2 10 24 20 48 40 96

1.4

Speedup (×)

1.5

6656 1.69× 13.43× 1.09× 3.25× 1.08× 1.03× 1.12× 1.00× 1.12× 1.00×

8 16

1.6

Speedup vs MPI_Allreduce

Number of Processes

4096 0.74×1.11×1.20×1.39×1.55×1.33×1.22×1.14×1.08×1.01× 2048 0.95×1.00×1.07×1.94×1.29×1.86×1.42×1.43×1.20×0.81× 1024 1.12×1.11×1.14×1.51×1.14×1.59×1.30×1.34×1.08×1.02× 512 1.04×1.08×1.00×1.12×1.36×1.27×1.20×1.23×1.14×0.80× 256 1.64×1.36×1.21×1.11×1.16×1.14×1.07×1.05×1.03×0.50× 128 1.29×1.27×1.25×1.20×1.20×1.19×1.16×1.14×0.99×0.36× 64 1.31×1.91×1.67×1.40×1.49×1.23×1.33×1.17×1.22×0.90×

3072 11.88×2.51× 2.79× 1.97× 1.73× 1.39× 1.24× 1.04× 1.64× 1.74× 2304 10.67×3.41× 3.58× 3.21× 2.81× 2.46× 2.37× 2.05× 2.02× 2.04× 1536 7.94×11.65×3.74× 3.91× 2.92× 2.56× 2.42× 2.41× 2.10× 2.00× 768 3.02× 5.36× 8.57× 2.96× 3.07× 2.28× 1.86× 1.83× 1.77× 1.49× 576 4.77× 8.37×13.48×3.83× 3.82× 2.33× 2.01× 1.96× 2.14× 1.82× 384 2.19× 3.84× 6.99× 9.70× 4.30× 3.78× 2.45× 2.32× 2.28× 2.22× 192 1.33× 2.12× 3.47× 5.77× 7.89× 4.76× 4.32× 2.93× 2.68× 2.51× 144 1.51× 2.37× 4.14× 6.41× 9.46× 4.00× 3.30× 1.92× 2.09× 2.00× 96 0.89× 1.16× 1.67× 2.60× 3.83× 4.80× 4.44× 3.85× 2.44× 2.41×

Speedup (×)

1.7

8 16 32 64 12 8 25 6 51 2 10 24 20 48 40 96

Number of Processes

8192 0.82×1.06×1.10×1.31×1.21×1.27×1.18×1.12×1.05×0.89×

Number of Processes

Speedup vs MPI_Allreduce

Per-rank segment size (Doubles)

Fig. 11: Speedup of CH I A R A relative to vendor MPI_Allreduce on Polaris (left), fugaku (center) and Aurora (right).

Time (s)

1.5

polaris

k-means(MPI) k-means(CHiArA) Allreduce time 1.57s 1.51s 1.45s var=0.001 var=0.000 var=0.033 1.27s var=0.000

1.0 0.5 0.0

256

Number of processes

2048

K-means runtime breakdown

Time (s)

K-means runtime breakdown 2.0

14 12 10 8 6 4 2 0

k-means(MPI) 10.32s var=0.091

4.88s var=0.132

576

fugaku

k-means(CHiArA) Allreduce time 11.20s var=0.022

Number of processes

5.04s var=0.133

2304

Fig. 12: End-to-end impact of CH I A R A in Parallel KMeans. Runtime breakdown for two scales on Polaris (left) and Fugaku (right), comparing the vendor MPI_Allreduce against CH I A R A for all Allreduce calls in the iteration loop. Stacked bars show the iteration-phase wall-clock time on the critical path; the hatched portion is the cumulative time spent inside the three Allreduce operations per iteration (counts, centroid sums, and convergence), and the remaining portion is local compute and other MPI overheads. Numbers above bars report the mean runtime and the observed run-to-run variance. sums (length K · D doubles), and a scalar reduction used for convergence detection. The centroid-sum Allreduce is the dominant communication in this workload, and it is exactly the pattern targeted by CH I A R A: repeated dense Allreduces on CPU-resident buffers inside a bulk-synchronous loop. We integrated CH I A R A as a drop-in replacement by introducing a wrapper that preserves MPI_Allreduce semantics for the datatypes and operator used by the application (here, MPI_INT and MPI_DOUBLE with MPI_SUM) and dispatches at runtime either to the vendor MPI_Allreduce or to CH I A R A. This isolates the effect of the collective implementation: the computation, data distribution, and convergence logic are identical across runs. CH I A R A is configured using the same parameter-selection strategy derived in Section V. We run synthetic instances to ensure controlled, repeatable communication volume while exercising the full iterative path. Each iteration performs three Allreduces: (i) a cluster-count reduction of K integers, (ii) a centroid-sum reduction of K · D doubles, and (iii) a convergence reduction of one integer. On Polaris, we use D = K = 256 and 100 points per rank, so the three collectives operate on 256 integers (1 KiB), 65,536 doubles (512 KiB), and 1 integer (4 B) per iteration, respectively. We evaluate P = 256 (8 nodes) and P = 2048 (64 nodes). On Fugaku, we use D = K = 192 with the same points-per-rank, yielding 192 integers (768 B), 36,864 doubles (288 KiB), and 1 integer (4 B) per iteration,

and evaluate P = 576 (12 nodes) and P = 2304 (48 nodes). Each configuration is executed for 10 runs after 2 warmup runs; we report the per-run wall-clock time on the critical path (maximum across ranks) and summarize run-to-run variability. Figure 12 shows that the iteration time is strongly Allreduce-dominated, especially on Fugaku, and that substituting CH I A R A reduces the Allreduce portion directly, translating into end-to-end gains. On Polaris, CH I A R A reduces the total iteration time from 1.51 s to 1.27 s at P = 256 (1.19×) and from 1.57 s to 1.45 s at P = 2048 (1.08×). On Fugaku, where the collective fraction is larger, CH I A R A reduces the iteration time from 10.32 s to 4.88 s at P = 576 (2.11×) and from 11.20 s to 5.04 s at P = 2304 (2.22×). These results confirm that CH I A R A improves not only microbenchmarks but also the runtime of a real iterative workload whose performance is bottlenecked by repeated global reductions. VII. R ELATED W ORK Hierarchy-aware and node-aware collectives in MPI libraries aim to exploit fast locality domains while limiting expensive cross-domain traffic, often by aggregating locally and restricting the off-domain collective to a subset of processes. Bienz et al. analyze node-aware Allreduce schemes in which only few ranks participate in the inter-node phase; while this reduces redundant off-node messages, it can concentrate injection/progress responsibility and leave many ranks idle, particularly for small reductions [11]. A related modeling perspective is provided by Träff’s k-lane formulation, which makes explicit that multiple processes per node can act as concurrent “lanes” for inter-node communication, and contrasts this capability with k-ported assumptions for hierarchical networks [19]. CH I A R A adopts the same guiding principle, avoiding a single fixed leader on the cross-domain path, by distributing inter-batch communication across lanes and rotating root across stages. A further line of work shows that collective performance depends on tunable algorithmic parameters and that robust performance requires selection policies rather than a single fixed template. Faraj and Yuan demonstrate that automatically generating and empirically tuning collective variants can improve robustness across platforms and topologies [20], while Wilkins et al. argue for generalized, parameterized collective families (including variable-radix constructions) to span depth–fanout trade-offs on modern systems [13]. CH I A R A

aligns with this philosophy by exposing a small set of hardware-relevant knobs (batch size and independent intrabatch radices) while retaining a fixed, analyzable hierarchical schedule. Orthogonal approaches either synthesize topologyspecific collective schedules [21] or reduce host overhead via in-network reduction mechanisms such as SHArP and Flare [22], [23]; CH I A R A instead focuses on a portable host-driven design that can be deployed and tuned within standard MPI environments. R EFERENCES [1] I. Yamazaki, M. Hoemmen, P. Luszczek, and J. Dongarra, “Improving performance of gmres by reducing communication and pipelining global collectives,” in 2017 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW), 2017, pp. 1118–1127. [2] S. Lockhart, A. Bienz, W. Gropp, and L. Olson, “Performance analysis and optimal node-aware communication for enlarged conjugate gradient methods,” 2022. [Online]. Available: https://arxiv.org/abs/2203.06144 [3] A. Ayala, S. Tomov, M. Stoyanov, A. Haidar, and J. Dongarra, “Accelerating multi - process communication for parallel 3-d fft,” in 2021 Workshop on Exascale MPI (ExaMPI), 2021, pp. 46–53. [4] J. M. Wozniak, M. Dorier, R. Ross, T. Shu, T. Kurc, L. Tang, N. Podhorszki, and M. Wolf, “Mpi jobs within mpi jobs: A practical way of enabling task-level fault-tolerance in hpc workflows,” Future Generation Computer Systems, vol. 101, pp. 576–589, 2019. [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S0167739X1830757X [5] T. Akiba, S. Suzuki, and K. Fukuda, “Extremely large minibatch sgd: Training resnet-50 on imagenet in 15 minutes,” 2017. [Online]. Available: https://arxiv.org/abs/1711.04325 [6] R. W. Hockney, “The communication challenge for mpp: Intel paragon and meiko cs-2,” Parallel Computing, vol. 20, no. 3, pp. 389– 398, 1994. [Online]. Available: https://www.sciencedirect.com/science/ article/pii/S0167819106800219 [7] M. Sato, Y. Kodama, M. Tsuji, and T. Odajima, “Co-design and system for the supercomputer “fugaku”,” IEEE micro, vol. 42, no. 2, pp. 26–34, 2021. [8] C. Bertoni, J. Kwack, T. Applencourt, A. Bagusetty, Y. Ghadar, B. Homerding, C. Knight, Y. Luo, M. Thavappiragasam, J. Tramm et al., “Early application experiences on aurora at alcf: Moving from petascale to exascale systems,” in Proceedings of the Cray User Group, 2024, pp. 12–23. [9] R. Rabenseifner, “Optimization of collective reduction operations,” in Computational Science - ICCS 2004, M. Bubak, G. D. van Albada, P. M. A. Sloot, and J. Dongarra, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004, pp. 1–9. [10] P. Patarasuk and X. Yuan, “Bandwidth optimal all-reduce algorithms for clusters of workstations,” J. Parallel Distrib. Comput., vol. 69, no. 2, p. 117–124, Feb. 2009. [Online]. Available: https://doi.org/10. 1016/j.jpdc.2008.09.002 [11] A. Bienz, L. N. Olson, and W. D. Gropp, “Node-aware improvements to allreduce,” 2019. [Online]. Available: https://arxiv.org/abs/1910.09650 [12] B. Goglin, J. Hursey, and J. M. Squyres, “ Netloc: Towards a Comprehensive View of the HPC System Topology ,” in 2014 43nd International Conference on Parallel Processing Workshops (ICCPW). Los Alamitos, CA, USA: IEEE Computer Society, Sep. 2014, pp. 216–225. [Online]. Available: https://doi.ieeecomputersociety.org/10. 1109/ICPPW.2014.38 [13] M. Wilkins, H. Wang, P. Liu, B. Pham, Y. Guo, R. Thakur, P. Dinda, and N. Hardavellas, “Generalized collective algorithms for the exascale era,” in 2023 IEEE International Conference on Cluster Computing (CLUSTER), 2023, pp. 60–71. [14] S.-M. Hammer, S. Schmid, R. Singh, and V. Addanki, “Shortcircuiting rings for low-latency allreduce,” 2025. [Online]. Available: https://arxiv.org/abs/2510.03491 [15] R. Thakur, R. Rabenseifner, and W. Gropp, “Optimization of collective communication operations in MPICH,” International Journal of High Performance Computing Applications, vol. 19, no. 1, pp. 49–66, 2005.

[16] W. Gropp, E. R. Lusk, R. Thakur, P. Balaji, T. Gillis, Y. Guo, R. Latham, K. Raffenetti, and H. Zhou, “Mpich,” [Computer Software] https://doi.org/10.11578/dc.20200514.13, jun 2023. [Online]. Available: https://doi.org/10.11578/dc.20200514.13 [17] R. L. Graham, T. S. Woodall, and J. M. Squyres, “Open mpi: A flexible high performance mpi,” in Parallel Processing and Applied Mathematics, R. Wyrzykowski, J. Dongarra, N. Meyer, and J. Waśniewski, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006, pp. 228–239. [18] T. Scarlatti and A. Russo Introito, “k-means-parallel: A parallel implementation of the clustering algorithm k-means with openmp and mpi,” GitHub repository, 2019, accessed: 2026-02-06. Last commit on master: d83490c (2019-09-24). License: Apache-2.0. [Online]. Available: https://github.com/tmscarla/k-means-parallel [19] J. L. Träff, “k-ported vs. k-lane broadcast, scatter, and alltoall algorithms,” 2020. [Online]. Available: https://arxiv.org/abs/2008.12144 [20] A. Faraj and X. Yuan, “Automatic generation and tuning of mpi collective communication routines,” in Proceedings of the 19th Annual International Conference on Supercomputing, ser. ICS ’05. New York, NY, USA: Association for Computing Machinery, 2005, p. 393–402. [Online]. Available: https://doi.org/10.1145/1088149.1088202 [21] Z. Cai, Z. Liu, S. Maleki, M. Musuvathi, T. Mytkowicz, J. Nelson, and O. Saarikivi, “Synthesizing optimal collective algorithms,” in Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, ser. PPoPP ’21. New York, NY, USA: Association for Computing Machinery, 2021, p. 62–75. [Online]. Available: https://doi.org/10.1145/3437801.3441620 [22] R. L. Graham, L. Levi, D. Burredy, G. Bloch, G. Shainer, D. Cho, G. Elias, D. Klein, J. Ladd, O. Maor, A. Marelli, V. Petrov, E. Romlet, Y. Qin, and I. Zemah, “Scalable hierarchical aggregation and nbsp;reduction protocol (sharp)tm streaming-aggregation hardware design and evaluation,” in High Performance Computing: 35th International Conference, ISC High Performance 2020, Frankfurt/Main, Germany, June 22–25, 2020, Proceedings. Berlin, Heidelberg: Springer-Verlag, 2020, p. 41–59. [Online]. Available: https://doi.org/10. 1007/978-3-030-50743-5 3 [23] D. De Sensi, S. Di Girolamo, S. Ashkboos, S. Li, and T. Hoefler, “Flare: flexible in-network allreduce,” in Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, ser. SC ’21. ACM, Nov. 2021, p. 1–16. [Online]. Available: http://dx.doi.org/10.1145/3458817.3476178

Configurable and Hierarchical Allreduce

Analyze & explore related research in Conceptio

Related documents