Introduction
Solving large-scale systems of linear equations ($Au = f$) is a cornerstone of modern scientific computing, essential for fields ranging from climate modeling to aerospace engineering. Algebraic Multigrid (AMG) methods are widely favored for these tasks due to their optimal $O(N)$ algorithmic scaling. However, as problem sizes grow, implementations face a significant "memory wall." GPU-accelerated solvers offer high throughput but are constrained by limited device memory (VRAM). Conversely, CPU-based solvers have access to vast system memory but lack the massive parallelism of GPUs.
This paper presents SParSH-AMG, a hybrid library that intelligently distributes workloads between CPUs and GPUs. By utilizing the GPU as a stream processor and overlapping data movement with computation, SParSH-AMG achieves high performance while maintaining a memory footprint up to 7x smaller than industry-standard GPU-only libraries like NVIDIA’s AMGX.
Methodology and Coarsening Strategies
The efficiency of an AMG solver depends heavily on the "coarsening" phase, where the original problem graph is simplified into a hierarchy of smaller systems. SParSH-AMG implements Heavy Edge Matching (HEM) coarsening, which identifies and collapses nodes with strong algebraic connections. This approach is particularly robust for anisotropic problems common in real-world engineering.
The library offers two primary hybrid execution modes:
- Hybrid CPU/GPU-CI (Compute Intensive): This mode minimizes GPU memory usage by storing only the current level of the multigrid hierarchy on the device.
- Hybrid CPU/GPU-MI (Memory Intensive): This mode maximizes performance by storing the entire hierarchy on the GPU, suitable for problems that fit within VRAM.
Hybrid Execution and Latency Hiding
A core innovation of SParSH-AMG is its ability to hide the latency associated with CPU-GPU data transfers. In the Hybrid CPU/GPU-CI mode, the library employs asynchronous CUDA streams to perform smoothing operations on the GPU while simultaneously transferring the next level's data from the CPU.
As illustrated in the workflow, this overlapping strategy ensures that the GPU remains productive, mitigating the bottleneck typically imposed by the PCIe bus. This allows the library to treat the GPU as a high-speed stream processor rather than a static storage bucket.
Experimental Results
The performance of SParSH-AMG was validated using synthetic matrices from finite element discretizations and real-world benchmarks from the SuiteSparse Matrix Collection.
- Performance Gains: SParSH-AMG achieved a 7-8x speedup compared to a multi-threaded CPU implementation (16 threads).
- Memory Efficiency: The Hybrid-CI variant required only 1/7th of the GPU memory used by AMGX, enabling the solution of much larger problems on standard hardware.
- Competitive Speed: When memory was not a constraint, the Hybrid-MI variant was 20–30% faster than AMGX.
- Scalability: The solver demonstrated robust scaling, maintaining a complexity of approximately $O(N^{1.1})$, close to the theoretical ideal.
Conclusion
SParSH-AMG provides a robust framework for solving massive linear systems by leveraging the complementary strengths of CPUs and GPUs. Its streaming architecture effectively bypasses the GPU memory wall, making high-performance AMG accessible for larger datasets. Future developments will focus on accelerating the setup phase and extending the library to distributed-memory multi-node environments.
Summary updated