×

A synchronization-free algorithm for parallel sparse triangular solves. (English) Zbl 1439.65035

Dutot, Pierre-François (ed.) et al., Euro-Par 2016: parallel processing. 22nd international conference on parallel and distributed computing, Grenoble, France, August 24–26, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9833, 617-630 (2016).
Summary: The sparse triangular solve kernel, SpTRSV, is an important building block for a number of numerical linear algebra routines. Parallelizing SpTRSV 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 overhead between the sets.
To address this, we propose in this paper a novel approach for SpTRSV 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. A comparison with the state-of-the-art library supplied by the GPU vendor, using 11 sparse matrices on the latest GPU device, show that our approach obtains an average speedup of 2.3 times in single precision and 2.14 times in double precision. The maximum speedups are 5.95 and 3.65, respectively. In addition, our method is an order of magnitude faster for the preprocessing stage than existing methods.
For the entire collection see [Zbl 1343.68006].

MSC:

65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65Y05 Parallel numerical computation
68M07 Mathematical problems of computer architecture
PDFBibTeX XMLCite
Full Text: DOI