Fast synchronization‐free algorithms for parallel sparse triangular solves with multiple right‐hand sides
Authors:
- 30 July 2017
- journal article
- research article
- Published by Wiley in Concurrency and Computation: Practice and Experience
- Vol. 29 (21)
Abstract
Summary: The sparse triangular solve kernels, SpTRSV and SpTRSM, are important building blocks for a number of numerical linear algebra routines. Parallelizing SpTRSV and SpTRSM on today's manycore platforms, such as GPUs, is not an easy task since computing a component of the solution may depend on previously computed components, enforcing a degree of sequential processing. As a consequence, most existing work introduces a preprocessing stage to partition the components into a group of level‐sets or colour‐sets so that components within a set are independent and can be processed simultaneously during the subsequent solution stage. However, this class of methods requires a long preprocessing time as well as significant runtime synchronization overheads between the sets. To address this, we propose in this paper novel approaches for SpTRSV and SpTRSM in which the ordering between components is naturally enforced within the solution stage. In this way, the cost for preprocessing can be greatly reduced, and the synchronizations between sets are completely eliminated. To further exploit the data‐parallelism, we also develop an adaptive scheme for efficiently processing multiple right‐hand sides in SpTRSM. A comparison with a state‐of‐the‐art library supplied by the GPU vendor, using 20 sparse matrices on the latest GPU device, shows that the proposed approach obtains an average speedup of over two for SpTRSV and up to an order of magnitude speedup for SpTRSM. In addition, our method is up to two orders of magnitude faster for the preprocessing stage than existing SpTRSV and SpTRSM methods.Keywords
Funding Information
- U.S. Department of Energy (66150)
This publication has 42 references indexed in Scilit:
- Direct Methods for Sparse Matrices2017
- Parallel Transposition of Sparse Data Structures2016
- Speculative segmented sum for sparse matrix-vector multiplication on heterogeneous processorsParallel Computing, 2015
- CSR52015
- SMAT2013
- A Fast Dense Triangular Solve in CUDASIAM Journal on Scientific Computing, 2013
- Direct Methods for Sparse Linear Systems2006
- Iterative Methods for Sparse Linear Systems2003
- An overview of the sparse basic linear algebra subprogramsACM Transactions on Mathematical Software, 2002
- Numerical Methods for Least Squares Problems1996