DCSolver: Accelerating Sparse Iterative Solvers via Divide-and-Conquer on GPUs
Open Access
- 19 September 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Architecture and Code Optimization
- Vol. 22 (3) , 1-25
Abstract
Sparse iterative solvers are commonly used in various fields. However, certain essential kernels of these solvers, such as sparse triangular solves (SpTRSV), present significant challenges for efficient parallelization due to data dependencies . Previous methods, like level-scheduling or multi-coloring, typically involve creating a Task Dependency Graph (TDG) to represent data dependencies and identify independent sets from the TDG for parallel execution. However, these approaches often result in limited parallelism with substantial synchronization overheads or negatively impact the solver convergence rate. This article introduces DCSolver , a Divide-and-Conquer (DC) framework designed to efficiently parallelize sparse solvers with data dependencies on GPUs. To achieve this, we break down the solver TDG into independent subgraphs, allowing us to exploit both coarse-grained and fine-grained parallelism. To efficiently allocate GPU threads for subgraphs with varying degrees of parallelism, we have developed an adaptive in-warp scheduling strategy. Additionally, we propose a hybrid parallelization scheme in DCSolver, which involves employing different parallel approaches for different DC recursions to achieve a more optimal balance between parallelism and convergence for solvers. To evaluate the effectiveness of DCSolver, we apply it to two preconditioned Krylov subspace solvers and an unstructured mesh Computational Fluid Dynamics (CFD) solver. Our results show that when compared with the state-of-the-art methods, DCSolver accelerates the time-to-solution of solvers by an average speedup of up to 26.19X.Keywords
Funding Information
- National Natural Science Foundation of China (62272474)
This publication has 35 references indexed in Scilit:
- Hierarchical block multi-color ordering: a new parallel ordering method for vectorization and parallelization of the sparse triangular solver in the ICCG methodCCF Transactions on High Performance Computing, 2020
- Performance modeling and optimization of parallel LU-SGS on many-core processors for 3D high-order CFD simulationsThe Journal of Supercomputing, 2016
- Computational Fluid Dynamics: Principles and Applications2015
- Parallelization of an unstructured Navier–Stokes solver using a multi-color ordering method for OpenMPComputers & Fluids, 2013
- GPU-accelerated preconditioned iterative linear solversThe Journal of Supercomputing, 2012
- Adapting Sparse Triangular Solution to GPUs2012
- StarPU: a unified platform for task scheduling on heterogeneous multicore architecturesConcurrency and Computation: Practice and Experience, 2010
- Block Red-Black Ordering: A New Ordering Strategy for Parallelization of ICCG MethodInternational Journal of Parallel Programming, 2003
- Ordering strategies and related techniques to overcome the trade-off between parallelism and convergence in incomplete factorizationsParallel Computing, 1999
- Renumbering unstructured grids to improve the performance of codes on hierarchical memory machinesAdvances in Engineering Software, 1997