Optimization of the diagonal incomplete Cholesky conjugate gradient method on GPU

The Diagonal Incomplete Cholesky Conjugate Gradient (DICCG) method is renowned for its efficiency in solving large-scale sparse symmetric positive definite linear systems. It has found extensive applications in various domains, including engineering computation and geosciences. However, the Sparse Triangular Solve (SpTRSV), which is a central component of the DICCG method, suffers from inherent seriality that poses a significant challenge for parallel processing on GPU. To tackle this challenge, we propose the Fixed-Level Scheduling (FLS) algorithm and the Increase-Level Scheduling (ILS) algorithm, these two algorithms can effectively enhance the multi-threaded parallelism of SpTRSV on GPU. To further enhance the computational efficiency of SpTRSV, the Approximate Minimum Degree (AMD) ordering algorithm is used to reorder the coefficient matrix before level scheduling. Additionally, to achieve efficient inter-block synchronization and optimal resource allocation, a hybrid inter-block synchronization method is proposed based on grid-level synchronization combined with kernel restarting. Numerical experiments show that, compared to the DICCG method implemented using only the level-set algorithm, the AMD-FLS-DICCG and AMD-ILS-DICCG methods can achieve overall speedups of 1.73 to 4.92 times and 1.87 to 5.84 times, respectively.