HiDAP-BILU: Hierarchical Dependency-Aware Parallelism for Block ILU Preconditioner on GPUs
Open Access
- 22 March 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 23 (1) , 1-24
Abstract
The block incomplete LU (BILU(0)) preconditioner is widely adopted for solving large-scale block-sparse linear systems arising from coupled partial differential equations (PDEs). However, strong inherent data dependencies and high memory bandwidth requirements of block matrix operations in the preconditioner pose significant challenges for efficient implementation on GPUs. Existing methods face the tradeoff between parallelism and convergence, and efforts to leverage the block properties remain limited. In this work, we introduce HiDAP-BILU for dependency-aware BILU(0) preconditioner on GPUs. HiDAP-BILU employs a block-centric hierarchical parallelism strategy to maximize concurrency. A block-to-block waiting scheme is proposed to preserve inter-block dependencies, while warp-level data distribution operations are utilized to maintain intra-block dependencies. Aligned with block-centric hierarchical parallelism, various architecture-aware optimizations are designed to minimize warp divergence and ensure coalesced memory access. Experiment results demonstrate that HiDAP-BILU achieves up to 4.77x and 3.10x speedups compared with state-of-the-art general methods for factorization and triangular solve, respectively. Additionally, it provides an average speedup of 3.11x in end-to-end BILU-preconditioned iterative solvers.Keywords
Funding Information
- National Natural Science Foundation of China (12402347)
- National Numerical Wind Tunnel Project of China
This publication has 32 references indexed in Scilit:
- AmgT: Algebraic Multigrid Solver on Tensor Cores2024
- DBSR: An Efficient Storage Format for Vectorizing Sparse Triangular Solvers on Structured Grids2024
- YuenyeungSpTRSV: A Thread-Level and Warp-Level Fusion Synchronization-Free Sparse Triangular SolveIEEE Transactions on Parallel and Distributed Systems, 2021
- A two-level ILU preconditioner for electromagnetic applicationsJournal of Computational and Applied Mathematics, 2017
- GPU-accelerated preconditioned iterative linear solversThe Journal of Supercomputing, 2012
- Comparison Criteria for Parallel Orderings in ILU PreconditioningSIAM Journal on Scientific Computing, 2005
- Independent columns: A new parallel ILU preconditioner for the PCG methodParallel Computing, 1997
- Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods1994
- Multicolor ICCG Methods for Vector ComputersSIAM Journal on Numerical Analysis, 1987
- The Conjugate Gradient Method for Linear and Nonlinear Operator EquationsSIAM Journal on Numerical Analysis, 1967