Supernodal sparse Cholesky factorization on graphics processing units

摘要

Sparse Cholesky factorization is the most computationally intensive component in solving large sparsernlinear systems and is the core algorithm of numerous scientific computing applications. A large numberrnof sparse Cholesky factorization algorithms have previously emerged, exploiting architectural features forrnvarious computing platforms. The recent use of graphics processing units (GPUs) to accelerate structuredrnparallel applications shows the potential to achieve significant acceleration relative to desktop performance.rnHowever, sparse Cholesky factorization has not been explored sufficiently because of the complexityrninvolved in its efficient implementation and the concerns of low GPU utilization.rnIn this paper, we present a new approach for sparse Cholesky factorization on GPUs. We present thernorganization of the sparse matrix supernode data structure for GPU and propose a queue-based approachrnfor the generation and scheduling of GPU tasks with dense linear algebraic operations. We also design arnsubtree-based parallel method for multi-GPU system. These approaches increase GPU utilization, thusrnresulting in substantial computational time reduction.rnComparisons are made with the existing parallel solvers by using problems arising from practicalrnapplications. The experiment results show that the proposed approaches can substantially improvernsparse Cholesky factorization performance on GPUs. Relative to a highly optimized parallel algorithm onrna 12-core node, we were able to obtain speedups in the range 1.59× to 2.31× by using one GPU andrn1.80× to 3.21× by using two GPUs. Relative to a state-of-the-art solver based on supernodal method forrnCPU-GPU heterogeneous platform, we were able to obtain speedups in the range 1.52× to 2.30× by usingrnone GPU and 2.15× to 2.76× by using two GPUs. Concurrency and Computation: Practice and Experience,rn2013.