TL;DR
This paper presents highly efficient parallel implementations of block-relaxation methods—specifically Jacobi and "chaotic" Gauss-Seidel—tailored for 3D stencils on modern GPUs and multicore CPUs. By optimizing how grid patches are mapped to hardware threads, the authors achieve significant speedups, making these robust "smoothers" viable for large-scale multigrid solvers and Adaptive Mesh Refinement (AMR) applications.
What Problem Does This Paper Address?
When solving elliptic partial differential equations (like the Poisson equation used in gravity or heat flow simulations), researchers often use multigrid methods. These methods rely on "smoothers" to eliminate high-frequency errors in the solution.
While simple point-wise smoothers (updating one grid cell at a time) are easy to parallelize, they often struggle with complex problems or stretched grids. Block-relaxation methods, which update groups of cells simultaneously, are much more robust but computationally heavier. The challenge lies in implementing these block methods on modern hardware—GPUs and multicore CPUs—without letting the overhead of communication and synchronization destroy the performance gains.
Methods
The authors focus on two primary algorithms: Block Jacobi and Chaotic Block Gauss-Seidel.
- Exact Inversion: Unlike some previous works that use approximations, this paper performs an exact inversion of the diagonal blocks. Since they deal with constant-coefficient stencils, this inversion only needs to happen once.
- Chaotic Relaxation: In the Gauss-Seidel implementation, they use a "chaotic" approach. This means blocks are updated asynchronously without waiting for neighboring blocks to finish. This eliminates expensive synchronization bottlenecks on the GPU.
- Two-Level Parallelism: On CPUs, they use OpenMP to parallelize across both "patches" (large regions of the grid) and "blocks" (smaller sub-regions).
- GPU Mapping: For CUDA, they explored strategies for mapping spatial blocks directly to thread blocks, ensuring that the GPU's memory hierarchy (shared memory) is used effectively to compute residuals and perform matrix-vector multiplications.
Datasets
The paper does not use external datasets; instead, it evaluates performance using a standard 3D Poisson equation benchmark on structured uniform and adaptively refined grids.
- Hardware Benchmarks: The algorithms were tested on the NVIDIA Fermi (C2050) and Kepler (K20X) GPUs, as well as AMD Opteron multicore systems (Maranello and Interlagos architectures).
Key Insights and Ideas
- Asynchronicity is an Advantage: The "chaotic" nature of the Gauss-Seidel method is a perfect fit for GPUs. By allowing threads to use the most recently available data without strict locking, the algorithm achieves better hardware utilization while maintaining (and often exceeding) the convergence rates of Jacobi methods.
- The Block Size Sweet Spot: There is a fundamental trade-off between convergence and compute cost. Larger blocks (e.g., $8 \times 8 \times 8$) improve the "smoothing" quality but require more memory and FLOPs for the matrix-vector multiplication. The authors found that $8^3$ blocks provided a strong balance for 3D problems.
- AMR Load Balancing: In Adaptive Mesh Refinement (AMR), grid patches can vary in size. The authors observed that GPUs handle these "mixed" patch sizes much better than CPUs. On a CPU, threads often have to "join" or wait for the largest patch to finish, whereas the GPU can continuously stream through blocks asynchronously.
Key Results
- GPU vs. CPU: The NVIDIA Kepler GPU was approximately 2.2x faster than a 32-core AMD Interlagos CPU for the same problem size.
- Scaling: The multicore CPU implementation showed excellent strong scaling, reaching about 80% efficiency on a 24-core system.
- Throughput: On the Kepler GPU, the implementation could process over 67 million cells per second for a block size of $8^3$.
- Convergence: Chaotic Gauss-Seidel consistently outperformed Jacobi in terms of the number of iterations required to reach a target error, confirming that the lack of synchronization did not harm the mathematical robustness of the solver.
Limitations and Future Work
- Constant Coefficients: The current work assumes constant coefficients in the PDE, which allows the block inverses to be precomputed. If coefficients vary across the grid, the blocks would need to be re-inverted frequently, significantly increasing the computational load.
- Single Node Focus: The study is limited to single-node performance (one GPU or one multi-socket CPU). The authors note that extending this to distributed systems (using MPI) is a necessary next step.
- Hybrid Execution: Future work aims to explore "hybrid" models where the CPU and GPU work on different parts of the grid simultaneously to eliminate idle time during memory transfers.
Summary updated