Technical Papers Archive

Loop-Carried Dependence Transformation for Parallel Sparse Solvers on GPUs


Authors: Da Ma and Mohammad Mahdi Salehi Dezfuli (McMaster University), Amir Mohammad Tavakkoli (University of Utah), Samirasadat Jamalidinan and Hossein Albakri (McMaster University), Mary Hall (University of Utah), and Kazem Cheshmi (McMaster University)

Abstract: Loop-carried dependences create significant computational bottlenecks in scientific solvers, hindering the effective utilization of massive GPU parallelism. Existing libraries are typically restricted to specific numerical methods or matrix types, making them difficult to scale, while previous compiler techniques often target only fully parallel loops or multicore CPUs. We propose a loop-carried dependence parallelism (LCD) transformation that automatically enables GPU parallelism for loops within sparse solvers. LCD lowers identified loops from a broad range of sparse operations, mapping them to thread-blocks and warps while implementing efficient and correct synchronization strategies. This framework utilizes a thread-block manager and a thread manager, both orchestrated by a central scheduler. Implemented as a Python just-in-time (JIT) compiler, the code generated by LCD achieves a geometric mean speedup of 1.60x-4.56x over the cuSPARSE library on H100 GPUs across various operations.


Presentation: file

Back to Technical Papers Archive Listing