Block-Relaxation Methods for 3D Constant-Coefficient Stencils on GPUs and Multicore CPUs

Manuel Birke, Bobby Philip, Zhen Wang, M. BerrillarXiv 2012 · DOI · arXiv

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

Abstract

Block iterative methods are extremely important as smoothers for multigrid methods, as preconditioners for Krylov methods, and as solvers for diagonally dominant linear systems. Developing robust and efficient algorithms suitable for current and evolving GPU and multicore CPU systems is a significant challenge. We address this issue in the case of constant-coefficient stencils arising in the solution of elliptic partial differential equations on structured 3D uniform and adaptively refined grids. Robust, highly parallel implementations of block Jacobi and chaotic block Gauss-Seidel algorithms with exact inversion of the blocks are developed using different parallelization techniques. Experimental results for NVIDIA Fermi GPUs and AMD multicore systems are presented.
BibTeX
@misc{birke2012block,
  author = {Manuel Birke and Bobby Philip and Zhen Wang and M. Berrill},
  title = {{Block-Relaxation Methods for 3D Constant-Coefficient Stencils on GPUs and Multicore CPUs}},
  year = {2012},
  eprint = {1208.1975},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1208.1975},
}

Loading related content...

Figure