Using analysis information in the synchronization‐free GPU solution of sparse triangular systems. (28th August 2019)

• Record Type: Journal Article
• Authors: Dufrechou, Ernesto; Ezzatti, Pablo
• Other Names: Merelli Ivan guestEditor.; Liò Pietro guestEditor.; Kotenko Igor guestEditor.; D'Agostino Daniele guestEditor.
• Is Part Of: Concurrency and computation. Volume 32:Number 10(2020)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2019-08-28
• Subjects: graphics processors (GPUs) -- level‐set analysis -- Sparse triangular linear systems -- synchronization‐free methods; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.5499
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: The solution of sparse triangular linear systems is one of the most important building blocks for a large number of science and engineering problems. For these reasons, it has been studied steadily for several decades, principally in order to take advantage of emerging parallel platforms. In the context of massively parallel platforms such as GPUs, the standard strategy of parallel solution is based on performing a level‐set analysis of the sparse matrix, and the kernel included in the nVidia cuSparse library is the most prominent example of this approach. However, a weak spot of this implementation is the costly analysis phase and the constant synchronizations with the CPU during the solution stage. In previous work, we presented a self‐scheduled and synchronization‐free GPU algorithm that avoided the analysis phase and the synchronizations of the standard approach. Here, we extend this proposal and show how the level‐set information can be leveraged to improve its performance. In particular, we present new GPU solution routines that attack some of the weak spots of the self‐scheduled solver, such as the under‐utilization of the GPU resources in the case of highly sparse matrices. The experimental evaluation reveals a sensible runtime reduction over cuSparse and the state‐of‐the‐art synchronization‐free method.