betaFeedback

WorksComputer Science

Triple Overlap in Pipelined Krylov Methods on Multi-GPU Systems

Abstract

We introduce a novel triple-overlap implementation of the pipelined preconditioned conjugate gradient (Pipe-PCG) and pipelined stabilized biconjugate gradient (Pipe-BiCGStab) solvers, methods widely used in scientific applications. By leveraging a collective communication library, our approach extends conventional computation-communication overlap to concurrently execute collective operations, irregular P2P communication, and compute kernels, enabling computation-communication-communication overlap across multiple GPUs. We evaluate the design on the MareNostrum 5 (H100) and Leonardo (A100) supercomputers, comparing against PETSc and the state-of-the-art two-stream NCCL implementation using SuiteSparse matrices and three massive instances scaled up to 512 GPUs. The three-stream design outperforms the two-stream baseline on every instance, with the margin widening from 2-6% at 4 GPUs to 18-47% at 64 GPUs. At 64 GPUs, the geometric-mean speedup over the two-stream baseline is 1.33x on MareNostrum 5 and 1.23x on Leonardo for Pipe-PCG, and reaches 1.30x for Pipe-BiCGStab. In large-scale experiments, we observed a speedup up to 35% in Pipe-PCG and up to 33% in Pipe-BiCGStab compared to the two-stream design. For PETSc, the margin is even wider, up to 3.27x speedup in both Pipe-PCG and Pipe-BiCGStab. Related code for the proposed method is available online: https://github.com/ParCoreLab/aCG

Introduction

Overlapping communication with computation is a well-established approach to reducing communication cost. A common example is the use of non-blocking send and/or receive operations to initiate individual message transfers, typically between neighboring processes to exchange halo data [1], [2]. When these messages make progress in the background, computation can proceed concurrently. This strategy is effective in both multi-CPU and multi-GPU settings. On CPUs, message progression relies on dedicated communication threads [3] or advanced MPI implementations [4]. On GPUs, overlap is typically realized with two concurrent streams, one for communication and one for computation [5], [6].

The conjugate gradient (CG) method [7], its preconditioned (PCG) variants and pipelined stabilized biconjugate gradient (Pipe-BiCGStab) methods are canonical Krylov subspace solvers for sparse linear systems, which makes them a central building block in large-scale scientific applications. Prior work on communication overlap in CG has largely treated its two communication types separately: global collective communication needed for parallelizing dot products and point-to-point (P2P) halo exchange in distributed sparse matrix-vector multiplications (SpMV). The literature on pipelined Krylov methods addresses the former to lower the global synchronization overhead, by overlapping non-blocking reductions with the SpMV and preconditioner operations, and this idea is further extended through deeper pipelines or fewer reductions per iteration [8]–[11]. The pipelined CG algorithm first presented in [8] is theoretically capable of overlapping both collective and P2P communication with computation. The authors of that work, however, focused only on hiding collective operations.

A separate line of work targets overlapping halo/P2P data exchanges with computation in iterative solvers and multigrid methods, primarily through scheduling and implementation techniques, such as specialized OpenMP threads [12], [13]. On GPUs, recent efforts improve the communication path through multi-GPU SpMV overlap, persistent kernels, and CPU- or GPU-initiated communication mechanisms [14]–[16]. However, none of these works jointly schedule collective communication, halo exchange, and computation as concurrent components of a single design.

In this work, we show that pipelined Krylov subspace solvers such as Pipe-PCG and Pipe-BiCGStab offer richer overlap opportunities than previously exploited. Beyond the traditional communication-computation overlap, they naturally allow communication–communication overlap, where collective reductions and P2P halo exchanges proceed concurrently alongside computation. To exploit this, we propose a novel three-stream implementation of Pipe-PCG and Pipe-BiCGStab that overlaps three components: collective reduction, halo exchange, and SpMV. Our design builds on the NVIDIA Collective Communication Library (NCCL) [17], which provides native stream support for GPU communication.

Our contributions are as follows:

  • We propose a three-stream overlap strategy for pipelined preconditioned CG and pipelined BiCGStab solvers that concurrently overlaps collective communication, P2P communication, and computation.

  • We evaluate our three-stream strategy against PETSc and a two-stream baseline [5]. Over this baseline, we achieve up to 35% (Leonardo, 256 GPUs) and 44% (MareNostrum 5, 64 GPUs) speedups for Pipe-PCG, with similar peak gains of 33% (MareNostrum5, 256 GPUs) and 42% (MareNostrum 5, 64 GPUs) for Pipe-BiCGStab compared to two-stream baseline.

Beyond Pipe-PCG and Pipe-BiCGStab, the three-stream design can be generalized to any application combining high-bandwidth local data exchange with high-latency global coordination (e.g., convergence checks or global updates).

Background and Motivation

Pipelined Preconditioned CG (Pipe-PCG)

Pipe-PCG methods [8] were developed to address the severe communication bottlenecks that limit the large-scale parallel scalability of standard PCG, where each iteration requires two separate dot products. In a distributed memory environment, each dot product forces a global synchronization event. These frequent synchronizations expose network latency and cause some processes to sit idle, creating a start-and-stop execution model that severely inhibits parallel efficiency [8].

Pipe-PCG directly targets this synchronization bottleneck by mathematically restructuring the solver to group the two dot products together, reducing the global synchronization to a single non-blocking phase per iteration. More importantly, this synchronization can be delayed until the preconditioner and SpMV are done. The Pipe-PCG implementation relies on the same fundamental compute kernels as the standard PCG method: vector additions (AXPY), dot products (DOT), and SpMV and a preconditioner. However, because Pipe-PCG restructures the algorithm, it introduces additional AXPY operations. Specifically, a single iteration of Pipe-PCG performs two DOT products combined, eight AXPY operations, one SpMV operation, and a preconditioning operation. The main computational difference from standard PCG is the use of eight AXPYs instead of three. Although these extra AXPYs increase the overall computational load, the benefit from reduced global synchronization amortizes this cost during large-scale executions [8].

Pipelined Stabilized Biconjugate Gradient (Pipe-BICGSTAB)

Standard BICGSTAB suffers from even greater latency exposure than PCG, which requires three separate global reduction phases to compute four dot products per iteration. When scaled across distributed-memory architectures, these repeated synchronization points expose inter-GPU communication latency and force processors into idle wait states, which inhibits the parallel performance at large scale.

To overcome these communication stalls, Cools and Vanroose Cools and Vanroose [18] introduced Pipe-BICGStab, which restructures the recurrences. By incorporating auxiliary vectors, the algorithm successfully fuses the dot products into just two global reduction phases. Moreover, these reductions are formulated as non-blocking collectives that execute concurrently with the method’s two SpMVs, effectively hiding the network latency behind useful computation.

While using the same core kernels (AXPY, DOT, SpMV), this reformulation increases local computational intensity. Each Pipe-BICGStab iteration executes six dot products (in two collective phases), eight AXPYs, and two SpMVs. Compared to standard BICGStab, it requires four extra AXPYs and expands vector storage from seven to eleven arrays. Despite increased resource demands, hiding inter-GPU communication behind computation yields substantial performance gains on massively parallel systems [18].

Beyond Traditional Computation-Communication Overlap

Since these pipelined Krylov subspace solvers offer more overlap opportunities beyond the conventional computation–communication model, this observation raises the question of whether multiple communication types can be overlapped for greater performance gains.

To answer this question, we first collected some results from nccl-tests and BabelStream microbenchmarks [19] to give an indication of relevant computation and communication costs. Specifically, on a system with 64 GPUs, nccl-test’s allreduce measurements show that it takes about 45.4 μs to perform an allreduce operation for two double-precision floating-point numbers, which is required to complete the global dot products during a Pipe-PCG iteration. The benchmark also shows that a single P2P message takes approximately the same amount of time when the message size is between 256 KiB and 512 KiB. Finally, based on BabelStream, simple computations such as AXPY and DOT can process about 68.6 MB of data (corresponding to double arrays with ∼8.6 million entries) in the same amount of time, i.e., 45 μs. This gives a rough idea of the amount of P2P communication or computation that will be needed to fully hide the collective (allreduce) communication that occurs in Pipe-PCG.

Furthermore, we developed a custom three-stream microbenchmark that concurrently executes P2P communication, collective communication, and computation, to see the overlap effect. Specifically, the benchmark consists of an allreduce collective on two double-precision scalars (16 bytes), a send/recv operation forming a simple ring topology with a payload of 32,000 doubles (256 KiB), and a DAXPY compute kernel processing 64 MB of data. The baseline for comparison is a traditional two-stream overlap strategy: a compute stream containing the allreduce and the DAXPY kernel, alongside a communication stream dedicated to P2P transfers, i.e., DAXPY is overlapped with P2P transfers but the allreduce

1  Input: $A^{(p)} = \bar{A}^{(p)} + \hat{A}^{(p)}$, $b^{(p)}$, $x_0^{(p)}$, $M$, $\epsilon$
2  $r_0 \leftarrow b - Ax_0$, $u_0 \leftarrow M^{-1}r_0$, $w_0 \leftarrow Au_0$
3  For $i = 0, 1, 2, \ldots$ Do
4      GPU DOT: $\gamma_i^{(p)} \leftarrow r_i \cdot u_i$
5      GPU DOT: $\delta_i^{(p)} \leftarrow w_i \cdot u_i$
6      SYNC: Wait for dot products to complete
7      ALLREDUCE: $\gamma_i \leftarrow \sum_p \gamma_i^{(p)}$, $\delta \leftarrow \sum_p \delta_i^{(p)}$ (non-blocking)
8      GPU Preconditioner: $m_i \leftarrow M^{-1}w_i$
9      SYNC: Wait until $m_i$ is ready
10     P2P PACK: Pack halo $\hat{m}_i$ for sending
11     P2P COMM: Start sending halo $\hat{m}_i$ to remote GPUs
12     GPU SpMV: $n_i \leftarrow \bar{A}^{(p)} * m_i$ (Diagonal)
13     SYNC: Wait until $\hat{m}_i$ is received
14     GPU SpMV: $n_i \leftarrow n_i + \hat{A}^{(p)} * \hat{m}_i$ (Off-diagonal)
15     SYNC: Wait until allreduce is done
16     CPU: If $\lVert r_i\rVert \leq \epsilon\lVert r_0\rVert$ Then Exit: Converged
17     GPU FUSED AXPY:
18         If $i == 0$: $\alpha_0 \leftarrow \gamma_0/\delta$, $\beta_0 = 0$
19         Else: $\alpha_i \leftarrow \gamma_i/(\delta - \beta_i\gamma_i/\alpha_{i-1})$, $\beta_i \leftarrow \gamma_i/\gamma_{i-1}$
20         $z_i \leftarrow n_i + \beta_i z_{i-1}$
21         $q_i \leftarrow m_i + \beta_i q_{i-1}$
22         $s_i \leftarrow w_i + \beta_i s_{i-1}$
23         $p_i \leftarrow u_i + \beta_i p_{i-1}$
24         $x_{i+1} \leftarrow x_i + \alpha_i p_i$
25         $r_{i+1} \leftarrow r_i - \alpha_i s_i$
26         $u_{i+1} \leftarrow u_i - \alpha_i q_i$
27         $w_{i+1} \leftarrow w_i - \alpha_i z_i$
28  End For
Pseudo-code of the multi-GPU three-stream Pipe-PCG implementation

Figure 1. Pseudo-code of the multi-GPU three-stream Pipe-PCG implementation. Colors indicate the stream on which each operation is executed: the compute stream in green, the P2P stream in purple, the collective stream in brown, and host-side CPU operations in blue.

collective is executed without any overlap. To mitigate the impact of noise and outlier measurements, we executed both microbenchmarks for 10510^5 iterations.

We conducted experiments on a single node with four GPUs, comparing the total execution time of the traditional two stream communication-computation overlap with that of our proposed three-way overlap. The three-stream implementation outperformed the two-stream baseline by approximately 5%. We then inspected the execution using the NVIDIA Nsight Systems profiler. The profiler trace demonstrates clear overlap among all three streams: compute, P2P, and allreduce.

Implementation

This section describes the two-stream and three-stream Pipe-PCG and Pipe-BICGSTAB implementations in detail. We use the two-stream design as the baseline because it achieves state-of-the-art performance among CG implementations [5].

We implement both the two- and three-stream designs for NVIDIA GPUs using NCCL [17] for communication, which natively supports GPU streams for asynchronous and overlapping GPU operations. Previous work [5], [20] showed that on supercomputers NCCL exhibits comparable performance to GPU-aware MPI.

Multi-GPU Pipelined PCG and Pipelined BICGSTAB

Executing Pipe-PCG and Pipe-BICGStab in a distributed-memory parallel setting requires partitioning the sparse matrix and its associated vectors. We utilize a row-wise partitioning strategy to divide the sparse matrix AA, distributing the assigned rows to corresponding vector segments to each rank. Following this distribution, each GPU becomes responsible for its specific partition, allowing the rest of the computations to take place locally within each GPU’s memory.

Computation

  1. Computation: In GPU implementations of CG methods, the best practice [21] is to offload the compute kernels to the GPU and handle intermediate steps such as convergence checks and scalar calculations on the CPU. For the aforementioned compute kernels, we rely on vendor-optimized BLAS libraries, using cuBLAS for local dot product and cuSPARSE for SpMV, which employs merge-based SpMV kernels [22].

Although vendor libraries offer easier implementation in AXPY operations, going back and forth between host and device to launch the kernels and move scalars between host and device after their calculation may introduce an additional overhead as pointed out by Trotter et al. [5]. Therefore, we fused the eight AXPY operations in a single compute kernel together with calculations of α\alpha and β\beta scalars on the device to mitigate this inefficiency in Pipe-PCG. A similar fusion approach is also applied in Pipe-BICGSTAB, but it is structured differently due to its algorithmic difference. The AXPY operations are grouped into three distinct fused kernels as it can be seen in Figure 1-b, while the scalar computations are performed in a separate CUDA kernel rather than being fused with the AXPYs.

For the preconditioning step in Pipe-PCG, we selected the Jacobi preconditioner due to its simplicity and low computational overhead. It is defined as the diagonal of the system matrix (M=diag⁡(A)M = \operatorname{diag}(A)) and its inverse M−1M^{-1} is obtained by taking the reciprocals of the diagonal elements. Since it is not available in vendor libraries, we implemented it ourselves.

Communication

  1. Communication: Parallel dot product operations require collective allreduce operations to sum up the partial dot product results from every GPU into a single global value to ensure the mathematical correctness of the distributed algorithm.

The second type of the communication required in pipelined CG and pipelined BICGSTAB concerns SpMV. More specifically, in a distributed SpMV (y=Axy = Ax) with row-wise partitioning, each GPU computes a partial output vector from its assigned rows. Because GPUs only require elements of the vector xx that correspond to the non-zero columns in their assigned matrix partition, SpMV generates an irregular point-to-point communication pattern. To manage this efficiently and hide network latency, the assigned matrix partition is conceptually divided into local and remote components, often referred to as diagonal and off-diagonal parts, respectively. Each GPU first multiplies the local (diagonal) matrix component with locally available xx values. Simultaneously, it initiates P2P communication to fetch the missing remote xx values. Once the transfer is completed, the GPU multiplies the off-diagonal matrix component with the newly received data. This strategy allows us to overlap local computation with halo communication, and we utilize it throughout our implementations.

Two-stream vs three-stream design of Pipelined Preconditioned CG and Pipelined BICGSTAB

Figure 1 (PDF p. 4). Two-stream vs Three-stream design of Pipelined Preconditioned CG and Pipelined BICGSTAB

Two-Stream Approach

We exploit the opportunity to overlap the irregular P2P communication of distributed memory SpMV with computation on the local part of the sparse matrix using GPU streams, as illustrated in Figure 1. Our implementation builds on a state-of-the-art approach [5], which combines CUDA streams with NCCL to avoid host-side synchronizations. Since NCCL is stream-aware, GPU kernels for packing, sending, receiving and unpacking messages can be queued asynchronously from the CPU without incurring CPU-GPU synchronization overhead. Dependencies between the P2P stream and compute stream are handled asynchronously through CUDA events (cudaEventRecord and cudaStreamWaitEvent), which further eliminates CPU-GPU synchronization and hides kernel launch latencies.

As shown in Figure 1-a for Pipe-PCG, once the preconditioning step completes, synchronization is established by asynchronously recording an event on the compute stream and making the P2P stream wait on that event. Conversely, the P2P stream records an event upon completing the P2P communication, and the compute stream thus waits on this event before proceeding with the off-diagonal part of the SpMV. Similarly in Pipe-BICGSTAB as shown in Figure 1-b, once the first group of fused AXPY operations complete, compute stream signals to P2P stream and initiates the halo exchange operations. This ensures that the required vector data is ready for both the SpMV operation and the P2P transfer. Non-blocking point-to-point communication is implemented using grouped calls to ncclSend and ncclRecv, enclosed by ncclGroupStart and ncclGroupEnd.

Three-Stream Approach

In the two-stream strategy, the collective communication required for the dot products remains a synchronization bottleneck, unable to be overlapped with other data transfers or computations. To achieve the triple overlap, we propose a novel three-stream implementation of Pipe-PCG and Pipe-BICGSTAB. As illustrated in Fig. 1, the collective operations are offloaded to a dedicated Collective stream. The core mathematical computations are maintained in the primary Compute stream, and the P2P data transfers remain isolated in their own dedicated P2P stream. Listing 1 shows the pseudocode of the multi-GPU three-stream implementations for Pipe-PCG and Pipe-BICGSTAB.

However, placing the collective in a separate stream is not sufficient to achieve true overlap with P2P transfers. Figure 2 shows the profiling results for a naive three-stream design based on a single NCCL communicator. In this case, only one communication operation overlaps with computation, while the others remain queued until the active transfer finishes. As discussed in Sec. III-A2, irregular P2P communication is required to fetch remote xx values, which are packed before transfer and unpacked on arrival. In the naive design, however, NCCL serializes the two communication operations, and in this case, prioritizes the collective. Consequently, in Pipe-PCG implementation, the P2P transfer is delayed until the Allreduce completes, which in turn causes the off-diagonal SpMV to execute much later than the diagonal SpMV because the required remote xx values are not yet available. Similarly in Pipe-BICGSTAB, as shown in Fig. 1-b, we start overlapping halo exchange operations after the first group of AXPYs, and since NCCL serializes communications in the background, Allreduce delays until the completion of halo exchange operations and we waste the opportunity of having a wider overlap window. Rather than overlapping diagonal SpMV, Allreduce and P2P together we end up overlapping halo exchanges with AXPYs, DOT products and diagonal SpMV; and Allreduce with off-diagonal SpMV.

Nsight Systems profiling results of naive three-stream vs our three-stream implementation

Figure 2. Nsight Systems profiling results of naive three-stream vs our three-stream implementation

To address this problem, separate communicators must be used for different communication operations. There are two ways to achieve this. The first is to create two independent communicators and use each for a different type of communication. However, this approach requires additional resource management as well as careful handling of possible deadlocks due to the order of host-side launches. The second is to split an existing communicator using NCCL’s ncclCommSplit feature. ncclCommSplit partitions an existing communicator into multiple sub-communicators, enabling different communication operations to proceed on separate communicators and thereby allowing true overlap. This overlap is illustrated in Figure 2-b in the profiling results. In our implementation, we adopt ncclCommSplit because it simplifies resource management internally and avoids possible deadlocks.

MareNostrum5 (ACC)Leonardo (Booster)
CPU2×2 \times Xeon Platinum 8460Y+ (40c)1×1 \times Xeon Platinum 8358 (32c)
GPU4×4 \times H100, 64 GB HBM2e4×4 \times A100 SXM4, 64 GB @ 1,640 GB/s
Intra-nodeNVLink 4.0, 300 GB/s bi-dir. per pairNVLink 3.0, 200 GB/s per pair
NICConnectX-7, 200 Gb/s uni-dir. per GPU2×2 \times dual-port HDR100 ConnectX-6, 400 Gb/s
NetworkNDR IB, 3-layer fat-tree [23]IB [24]
SoftwareHPC SDK 25.1, CUDA 12.6, HPC-X 2.21, NCCL 2.18.5HPC SDK 24.3, CUDA 12.3, HPC-X 2.17.1, NCCL 2.18.5

Table 1. System configurations.

Experiments and Evaluation

We compare our proposed three-stream implementation with the state-of-the-art two-stream Pipe-PCG and Pipe-BiCGStab and the PETSc’s implementations, which are based on NCCL and CUDA-aware MPI, respectively.

Experimental Setup

a) Supercomputers: We evaluated our implementations on two leading supercomputers, MareNostrum5 and Leonardo. Table IV details their configurations and software stacks.

MareNostrum5 (ACC)Leonardo (Booster)
CPU2× Xeon Platinum 8460Y+ (40c)1× Xeon Platinum 8358 (32c)
GPU4× H100, 64 GB HBM2e4× A100 SXM4, 64 GB @ 1,640 GB/s
Intra-nodeNVLink 4.0, 300 GB/s bi-dir. per pairNVLink 3.0, 200 GB/s per pair
NICConnectX-7, 200 Gb/s uni-dir. per GPU2× dual-port HDR100 ConnectX-6, 400 Gb/s
NetworkNDR IB, 3-layer fat-tree [23]IB [24]
SoftwareHPC SDK 25.1, CUDA 12.6, HPC-X 2.21, NCCL 2.18.5HPC SDK 24.3, CUDA 12.3, HPC-X 2.17.1, NCCL 2.18.5

Table IV. System configurations.

b) Matrices: We use two groups of test instances. The first is taken from Suitesparse [25] where we select the six largest positive definite symmetric real-valued matrices. Since

MatrixRowsNonzerosNonzeros/Row
Queen_41474,147,110316,548,96276.33
Bump_29112,911,419127,729,89943.87
Flan_15651,564,794114,165,37272.96
audikw_1943,69577,651,84782.28
Serena1,391,34964,131,97146.09
Geo_14381,437,96060,236,32241.89
poisson3da_12144,515,6632,239,624,24915.5
heart15874,424,4457,185,411,5418.2
heart12139,589,9392,144,835,46115.4

Table 2. Sparse matrices used in experiments.

they are not large enough to scale beyond 64 GPUs, we also add three very large test instances. The first is a matrix from discretising a 3D Poisson equation on a unit cube geometry. The other two are derived from a 3D cardiac monodomain simulation of the human heart at different resolutions [26]. They represent an unstructured, tetrahedral mesh based and are thus highly irregular and very sparse. Table II lists the instances, their sizes, and their nonzero distribution by row.

c) Measurement: Execution time is measured on the host CPU for each MPI process using clock_gettime. To ensure accurate timings, all solvers execute 10 warmup iterations, followed by an MPI barrier and CPU-GPU synchronization (e.g., cudaDeviceSynchronize), before the timer begins. A final CPU-GPU synchronization occurs before stopping the timer to guarantee that all GPU tasks are fully completed. We then report the maximum execution time across all participating processes.

We evaluate all solvers including PETSc within the same job submission for a given matrix and GPU count. This ensures the use of identical matrix partitioning, compute nodes, and GPUs. We repeat each measurement three times and report the average with error bars showing the range across three runs. To avoid outliers across the iterations with the solver loop, we ran each solver for 10,000 iterations for Pipe-PCG runs and 1,000 iterations for Pipe-BiCGStab. Finally, for an in-depth analysis of the two-stream and three-stream implementations, we conducted additional fine-grained measurements of individual GPU kernel times using cudaEventRecord.

Experimental Results

We first present experimental results for the Suitesparse matrices. Figure 3 shows results on MareNostrum5. In all

Figure 3. Performance of the proposed Three-Stream design compared with PETSc and the state-of-the-art Two-Stream implementation [5] on SuiteSparse matrices on the MareNostrum5 supercomputer. Numbers above the Three-Stream bars show the speedup over PETSc (orange) and Two-Stream implementation (green).

In all cases, Three-Stream is ahead of the Two-Stream implementation. Furthermore, the gap widens consistently with growing number of GPUs, from 2–6% at 4 GPUs to 18–47% at 64 GPUs, with only Geo_1438 on MareNostrum5 constituting an outlier due to unstable results (as evidenced by the large variability between the runs).

Since the cost of allreduce grows with the number of GPUs, so does the benefit of overlapping it with P2P communication, confirming that the Three-Stream design works as intended. While the relative benefit should be larger for shorter total running times, the 64-GPU running times are too similar across instances for this effect to be visible.

In addition to the figures, Table 3 shows the speedups including the speedup versus PETSc, which uses GPU-aware MPI rather than NCCL. While PETSc is almost always slower than the stream-based implementations, the difference is much more pronounced on Leonardo, where Three-Stream is up to 93% faster with a geometric mean of 1.72 whereas the speedup over Two-Stream is much lower.

MatrixMareNostrum5 (H100) vs. PETScMareNostrum5 (H100) vs. 2-streamLeonardo (A100) vs. PETScLeonardo (A100) vs. 2-stream
Queen_41471.08×1.08\times1.25×1.25\times1.93×1.93\times1.12×1.12\times
Bump_29111.69×1.69\times1.23×1.23\times1.69×1.69\times1.18×1.18\times
Flan_15651.31×1.31\times1.42×1.42\times1.56×1.56\times1.47×1.47\times
audikw_11.26×1.26\times1.32×1.32\times1.82×1.82\times1.31×1.31\times
Serena1.80×1.80\times1.33×1.33\times1.66×1.66\times1.26×1.26\times
Geo_13281.30×1.30\times1.44×1.44\times1.68×1.68\times1.09×1.09\times
Geomean1.381.331.721.23

Table 3. Speed-ups of three-stream (ours) over PETSc and two-stream for Pipe-PCG on MareNostrum5 (H100) and Leonardo (A100) using 64 GPUs.

All matrices show some performance scaling initially, but only for the largest instance, Queen_4147, the scaling is close to linear. None of the instances show any noticeable improvement at 64 GPUs, which implies that our experiments have reached the limits of scalability for these matrices.

For Pipe-BiCGStab, Three-Stream again outperforms Two-Stream on every instance and GPU count (Figure 4), with the margin growing from 1–5% at 4 GPUs to 17–42% at 64 GPUs, where the geometric-mean speedup reaches 1.30× over Two-Stream and 2.01× over PETSc.

Figure 4. Performance of the proposed Three-Stream design for Pipe-BICGSTAB compared with PETSc and the state-of-the-art Two-Stream implementation [5] on SuiteSparse matrices on the MareNostrum5 supercomputer. Numbers above the Three-Stream bars show the speedup over PETSc (orange) and Two-Stream implementation (green).

For the large matrix instances, Figure 5 shows Pipe-PCG results on Leonardo, while Figure 6 shows the Pipe-BiCGStab results on MareNostrum5. Since these problems require more computation, the relative communication overhead is small at lower GPU counts, and the three-stream advantage starts modestly, but grows to 1.52×, 1.06×, and 1.50× at 256 GPUs on heart12, heart15, and poisson3da_12, respectively as the collective communication becomes more expensive relative to the computation, leaving more latency for the third stream to hide.

Figure 5. Performance of the proposed Three-Stream design compared with PETSc and the state-of-the-art Two-Stream implementation [5] on larger matrices on the Leonardo supercomputer. Numbers above the Three-Stream bars show the speedup over PETSc (orange) and Two-Stream implementation (green).

Figure 6. Performance of the proposed Three-Stream design for Pipe-BiCGStab compared with PETSc and the state-of-the-art Two-Stream implementation [5] on larger matrices on the MareNostrum5 supercomputer. Numbers above the Three-Stream bars show the speedup over PETSc (orange) and Two-Stream implementation (green).

Finally, PETSc is highly competitive on these large instances, even beating our design on heart12 at 64 GPUs (where we reach only 0.67× of its performance). This exposes the pipelined approach’s weak point: massive local work, cheap collectives, and unamortized extra vector operations. At 128 and 256 GPUs, however, this effect disappears, and our three-stream design outpaces PETSc by 1.49× and 1.74× on the same matrix.

Performance Analysis

To better understand the scaling behavior observed in the last section, we profiled the Pipe-PCG experiments on MareNostrum5 at 4 and 64 GPUs for the Queen_4147 and Flan_1565 matrices. We measured the time spent in compute kernels directly using CUDA events. The same method cannot isolate communication time, because such measurements would also capture synchronization and load-imbalance effects among the communicating GPUs. Instead, we estimated the overall communication (i.e., non-compute) time by subtracting the compute-kernel times from the total solver time.

To better understand the scaling behavior observed in the last section, we profiled experiments for Pipe-PCG conducted on the MareNostrum5 supercomputer using 4 and 64 GPUs for the Queen_4147 matrix and Flan_1565 matrices. We measure the time spent in compute kernels directly using CUDA events. The same method cannot be used to provide isolated measurements of the communication time, because such measurements would also include effects of synchronization and load imbalance among the communicating GPUs. Instead, we estimate the overall time spent in communication (i.e., non-compute) by subtracting the times for the compute kernels from the total solver time.

The effective memory bandwidth of the local SpMV drops from 82% of the theoretical peak at 4 GPUs to 65% at 64 GPUs for Queen_4147, and from 56% to 9.8% for Flan_1565, indicating that the latter matrix is too small to run efficiently at this scale. For reference, our BabelStream measurements show that a single GPU reaches about 90% of the theoretical maximum: SpMV approaches this value only under ideal conditions, and not all matrices can do so without reordering [27].

The remaining compute kernels (preconditioner, diagonal SpMV, off-diagonal SpMV, and AXPYs) hardly scale with the number of GPUs. For the off-diagonal SpMV, this is because the number of halo elements to be communicated grows with the number of GPUs. For the others, the work per kernel invocation becomes so small at 64 GPUs that launch overheads dominate. Since these overheads, like Allreduce, are independent of the instance size, the 64-GPU running times cluster around 1.5 secs for all instances except the much larger Queen_4147 (∼\sim2 secs).

For communication, even at 4 GPUs on Queen_4147, Three-Stream communication is 28% faster than Two-Stream. However, since communication accounts for only 14% (TwoStream) and 12% (Three-Stream) of the total time, the overall improvement is marginal. At 64 GPUs, in contrast, communication is %48 faster and accounts for 55% (Two-Stream) and 46% (Three-Stream) of the total time, yielding the overall speedup of 24%.

Related Works

The Pipelined-CG was introduced to reduce the cost of global synchronization in Krylov methods. Ghysels and Vanroose reformulated PCG so that a single nonblocking reduction is issued per iteration and overlapped with the matrix-vector product and preconditioner [8]. Later work extended this idea with deep pipelines that hide a reduction behind multiple future SpMVs when one iteration does not provide sufficient work [9]. More recent pipelined-PCG variants further reduce reduction frequency by overlapping one allreduce with work from two iterations [10]. However, this line of work only targets global dot product latency. Moreover, although non-blocking collectives were introduced in MPI-3, their effectiveness on CPU clusters depends on factors such as asynchronous progress and runtime support [28].

A separate line of work focuses on halo/P2P communication overlap in iterative solvers and multigrid methods. These approaches aim to overlap halo exchange in the SpMV or smoother/preconditioner phases with computation. For example, Nakajima et al. combine halo overlap with OpenMP dynamic loop scheduling [12], and later study process/thread allocation in hybrid MPI+OpenMP settings to optimize communication-computation overlap in a CG solver with a multigrid preconditioner [13]. Thus, these works do not address the joint scheduling of halo exchange and collective reductions.

On GPU systems, Bernaschi et al. combine communication-reduced CG with overlap in the multi-GPU SpMV [14]. Ismayilov et al. use persistent kernels, device-side barriers, and device-initiated communication to remove the CPU from the critical path in multi-GPU CG [15]. Trotter et al. [5] compare CPU- and GPU-initiated communication strategies for CG and pipelined CG across GPU-aware MPI, NCCL/RCCL, and NVSHMEM. However none of these works consider triple overlap in their implementations.

The closest prior work to ours is Selvitopi et al. [29], who propose a rearrangement for iterative solvers in which irregular SpMV P2P messages are embedded into a collective communication phase so that P2P and collective communication can be performed in a single phase. Although this mixes the two communication classes, it is not a pipelined-CG formulation that treats collective reduction, halo exchange, and SpMV as three concurrent components.

Outside CG, MPI+ULT [30] argues that user-level threads can overlap computation with both P2P and collective MPI communication, but it does not demonstrate a true three-way overlap of collective, P2P, and compute. Lina [31] studies distributed Mixture-of-Experts training, where all-to-all and allreduce coexist with computation on separate streams. It shows that naive concurrency between these communication classes can hurt performance due to network contention, and therefore prioritizes all-to-all over allreduce. Our approach differs in that we overlap collective communication with P2P exchange, yielding a different communication pattern and less pressure on the network bandwidth.

Conclusion

We have introduced the three-stream technique for overlapping two different types of communication - high volume, bandwidth limited P2P messages and low volume latency limited collectives. The idea can be implemented efficiently on GPU systems using three separate streams for concurrency, making use of modern GPU communication libraries such as NCCL or RCCL which can handle communication in streams. Our experimental results on Pipe-PCG and Pipe-BICGStab indicate that the technique works as intended, yielding substantial performance improvements when scaling to a large number of GPUs. In future work, we intend to explore other applications and plan to implement the three-stream technique for AMD GPUs.

Acknowledgments

Authors from Koç University have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 949587).

We acknowledge EuroHPC Joint Undertaking for awarding access to the MareNostrum5 supercomputer in Spain and the Leonardo supercomputer in Italy (Project IDs: EHPC-DEV-2024D10-091, EUHPC_D21_118).

Various AI-based tools, including Claude Opus, OpenAI’s ChatGPT, and Google’s Gemini Pro, were used throughout the preparation of this manuscript to assist with language editing and LaTeX formatting. All scientific content, data, analyses, and conclusions were independently reviewed and verified by the authors.

Overview of Contributions and Artifacts

Computational Artifacts

All computational artifacts have been archived on Zenodo:

A1A_1 https://doi.org/10.5281/zenodo.22973787

A2A_2 https://doi.org/10.5281/zenodo.22973707

The main computational artifacts are included in A1A_1. Additional input files are provided in A2A_2, related to the matrix poisson3da_12, which is used for some of the large-scale experiments in the paper.

Artifact Identification

Computational Artifact A1

Relation To Contributions

Artifact A1A_1 includes:

  1. Source code for the solvers, which implement the various two-stream and three-stream multi-GPU CG solvers that are used for the performance benchmarks presented in the paper.

  2. This dataset contains the row partitioning files for six matrices selected from the SuiteSparse Collection [1]: Bump_2911, Geo_1438, Flan_1565, Queen_4147, Serena, and audikw_1. Using the METIS graph partitioner [2], each matrix was partitioned into 4, 8, 16, 32 and, 64 parts.

  3. Included here are the job submission scripts used to benchmark the multi-GPU CG solvers (two- and three-stream implementations and PETSc) on the MareNostrum 5, and Leonardo clusters.

Expected Results

By executing the two-stream, three-stream, and PETSc experiments using the provided source code and open datasets, users can reproduce the solver runtimes and speedups illustrated in the paper.

Expected Reproduction Time (in Minutes)

The anticipated computational time for the SuiteSparse matrix experiments ranges from 30 seconds to 15 minutes for each combination of solver, matrix, and GPU count. For the large-scale experiments, executing each solver and GPU configuration requires approximately 10 to 15 minutes for the ”poisson3da_12”, ”heart12” and ”heart15” matrices on the MareNostrum 5 and Leonardo clusters.

Artifact Setup (incl. Inputs)

Hardware and their configurations used in the experiments can be seen in Table IV.

Computational Artifact A1

Software: Introduce all required software packages, including the computational artifact. For each software package, specify the version and provide the URL.

The following software is used on all systems:

  • CG Solvers: (https://doi.org/10.5281/zenodo.22973787)

  • PETSc 3.21.5 (https://petsc.org/release/)

  • METIS 5.1.0 (https://github.com/KarypisLab/METIS)

On the different clusters, we also use some additional software packages, which are provided by their respective module environments. They can be seen in Table IV, software row.

Datasets / Inputs: Input matrices can be downloaded from the SuiteSparse collection at https://sparse.tamu.edu/, in the Matrix Market file format. The following six matrices from SuiteSparse are used: Bump_2911, Geo_1438, Flan_1565, Queen_4147, Serena, and audikw_1. For each matrix, partitionings are included in artifact A1A_1.

Installation and Deployment: To install the program the following minimum software dependencies must be satisfied:

  • CMake 3.12 or newer

  • A C/C++ compiler compatible with C++-17

  • For NVIDIA GPUs: NVIDIA CUDA Compiler (NVCC), cuBLAS and cuSPARSE from CUDA Toolkit 11.6 or newer

The following optional software packages are needed to enable some features:

  • METIS 5.1.0 is required for multi-GPU matrix partitioning, unless using precomputed partitions (e.g., from artifact A1A_1).

  • NVIDIA Collective Communications Library (NCCL) version 2.18.5 or newer is needed to use NCCL-based communication for NVIDIA GPUs

  • PETSc 3.17 or newer with CUDA support enabled is needed to use PETSc’s PIPE-PCG solver

  • zlib is needed to use gzip-compressed Matrix Market files as input

  • If the compiler supports OpenMP, then it can be enabled to use multiple threads to speed up preprocessing steps.

Artifact Execution

The experimental workflow consists of a single task: running the compiled executable three times for each matrix, solver, and GPU configuration. The program outputs detailed metrics, such as runtime and iteration counts. For further details and the job submission scripts used on the three clusters, please refer to artifact A1_1.

Artifact Analysis (incl. Outputs)

To analyze the experimental outputs, we extract the solver runtimes from the log files and calculate the average across the three trials for each configuration of matrix, solver, and GPU count. Using these average runtimes, we compute the performance speedup for NN GPUs by dividing the baseline two-stream runtime by the runtime of the three-stream implementation for that specific matrix and GPU allocation.

Artifact Evaluation (AE)

Computational Artifact A1_1

Artifact Setup (incl. Inputs)

All commands are run from the root directory of the artifact, ${artifact_root}, on a login node of the cluster. Below, ${system} is marenostrum5 or leonardo. Each system directory scripts/${system}/ contains a README with further details.

Environment setup: METIS 5.1.0 and PETSc 3.21.5 (with 32-bit indices) must be installed in a directory given by ACG_PKGS_DIR (default: ${HOME}/pkgs), in the subdirectories metis-32-5.1.0 and petsc-32-3.21.5; on Leonardo, glibc-2.29 is also needed. The module files for these packages are included in scripts/${system}/modulefiles and are loaded from there. The Slurm account is given through environment variables:

$ export ACG_PKGS_DIR=/path/to/pkgs
$ export SBATCH_ACCOUNT=<project>
$ export SBATCH_QOS=acc_ehpc

where the QOS is needed on MareNostrum 5 only and depends on the type of allocation. The environment is then set up by sourcing the script for the system, which loads the modules and creates the directory logs/ for the Slurm output:

$ . scripts/${system}/envsetup-${system}.sh

aCG Library Install: aCG is built with the build script for the system:

$ scripts/${system}/build-acg-cuda.sh

The script copies src/aCG to build/${system}/src, applies scripts/${system}/${system}.patch (which disables NCCL CollNet for the split communicators, and on Leonardo also the internal profiling, as in the binaries used for the paper), configures the CUDA version of aCG with CMake and compiles it. The executable is installed as bin/acg-cuda. On MareNostrum 5, the configuration uses nvc, CUDA 12.9 nvcc and an empty CMAKE_BUILD_TYPE; on Leonardo, it uses nvc, CUDA 12.3 nvcc, CMAKE_BUILD_TYPE=release and CMAKE_CUDA_ARCHITECTURES=80.

Input matrices and partitions: The six SuiteSparse matrices (audikw_1, Bump_2911, Flan_1565, Geo_1438, Queen_4147 and Serena) are not included in the artifact because of their size; only their METIS row partitions are. Before running any job, download the matrices in Matrix Market format from the SuiteSparse Matrix Collection [25] by running, from the artifact root directory:

scripts/download-matrices.sh

The script downloads each matrix from https://sparse.tamu.edu/MM/{group}/{matrix}.tar.gz, extracts it to data/suitesparse/mtx/<matrix>.mtx, decompresses the partitions in data/suitesparse/partitions/, and verifies all files against the checksums in data/SHA256SUMS. It requires curl and about 3.5 GB of disk space for the downloads and 11 GB for the extracted matrices; the downloaded archives are deleted after extraction unless --keep-tarballs is given. Individual matrices can be downloaded by naming them, e.g. scripts/download-matrices.sh Queen_4147. Re-running the script skips matrices that are already present.

The matrix poisson3da_12 and its partitions are obtained by downloading and unpacking A2_2 and placing the files at:

data/poisson3da/mtxbin32/
  poisson3da_12_A.mtxbin32.gz
data/poisson3da/partitions/
  poisson3da_12_A_rowpart_metis_
  <num_of_part>_parts.mtx.gz

Artifact Execution

Each experiment is a Slurm job script that runs the six solver variants, three times each, for one matrix and one number of nodes. The job scripts are located in

scripts/${system}/suitesparse/${matrix}/
scripts/${system}/poisson3da/poisson3da_12/

and are named ${matrix}-rtol-0-${nodes}-nodes-${gpus}-procs.sh where ${nodes} and ${gpus} are zero-padded to three and four digits. For example, Queen_4147 on 4 nodes (16 GPUs) of Leonardo is run with:

$ sbatch scripts/leonardo/suitesparse/
  Queen_4147/
  Queen_4147-rtol-0-004-nodes-
  0016-procs.sh

There are 30 SuiteSparse jobs per system (6 matrices on 1, 2, 4, 8 and 16 nodes) and 3 (MareNostrum 5: 16, 32 and 64 nodes) or 4 (Leonardo: 16, 32, 64 and 128 nodes) jobs for poisson3da_12. All jobs of a system can be submitted with:

$ for j in scripts/${system}/*/*/*.sh; do
  sbatch $j; done

Within the 8-hour evaluation budget, we suggest running the 30 SuiteSparse jobs on one system (about 30 node hours) and, if the allocation permits, the 16-node poisson3da_12 job. The output of each run is written to results/acg/${date}/${variant}/${matrix}/ A run that exits with a non-zero status keeps the suffix .tmp; this is expected for the PCG variants, which stop at the iteration limit, and these files are used in the analysis.

Artifact Analysis (incl. Outputs)

The solver times of all runs of a given date are collected into a CSV file, with one row per variant, matrix and number of GPUs and one column per run:

$ python3 scripts/collect/collect_results.py
results/acg/${date} H100 > results.csv

(A100 on Leonardo). From this file, the figures of the paper are produced with Python 3, pandas and matplotlib. The script figure2x3.py plots the six SuiteSparse matrices and figure1x3_large_matrices.py the large matrices, for the solver family given by --solver, for example:

$ python3 scripts/figures/figure2x3.py
results.csv --solver pcg
--system MareNostrum5 -o ss_pcg

which writes ss_pcg.png and ss_pcg.pdf. Each bar is the mean of the three runs, with the standard deviation as error bar, and the speedups of the three-stream solver are printed under each panel. The variants PIPE-*-PETSC, PIPE-*-nccl and PIPE-*-nccl-split correspond to “PETSc”, “Two-Stream” and “Three-Stream” in the paper. For the SuiteSparse matrices, the resulting figures correspond to Figure 3 and Figure 4 (MareNostrum 5); for poisson3da_12, they correspond to the poisson3da_12 panels of Figure 5, Figure 6.The three-stream solvers are expected to have the lowest solver times, with speedups over the two-stream and PETSc solvers similar to those reported in the paper.

References

  1. [1]Davis, T. A. and Y. Hu. 2011. The University of Florida Sparse Matrix Collection. ACM Trans Math Softw. 38, 1.DOI
  2. [2]Karypis, G., and V. Kumar. 1998. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J Sci Comput. 20, 1.DOI

Paper details

vlnc:W_ujvadnxv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus, OpenAI’s ChatGPT, Google’s Gemini Pro

View statement
Looking for related papers…
Contents