* Based on the paper: "Loop-Carried Dependence Transformation for Parallel Sparse Solvers on GPUs" by Da Ma, Mohammad Mahdi Salehi Dezfuli, Amir Mohammad Tavakkoli, Samirasadat Jamalidinan, Hossein Albakri, Mary Hall, and Kazem Cheshmi at SC'26.

Parallelism Challenge for Scientific Solvers on GPUs

Modern scientific simulations such as climate modeling and structural engineering, rely heavily on solving massive systems of equations. GPUs are the undisputed powerhouses for these heavy computations thanks to thousands of parallel processing cores. However, scientific code frequently runs into a major obstacle: loop-carried dependences. This happens when a loop iteration needs a result calculated in a previous step, forcing operations to wait step-by-step rather than running all at once. Because sparse matrices (where most entries are zero) have unpredictable memory patterns, squeezing parallel performance out of these algorithms on GPUs has historically required manual, complex engineering.

Figure 1 demonstrates a simple scintific solver, sparse lower triangular solve kernel. The outermost loop is sequential due to read and write operations targeting the solution vector x within iterations. However, because the column and row indices stem from a sparse matrix, the coupling between iterations is relatively sparse. These sparse inter-iteration dependences create opportunities for concurrent execution. For instance, iterations that do not cause unresolvable read-after-write dependencies can run in parallel. Iterations 0 and 1 can be independently computed using different thread blocks; however, since both write to x[3], an atomic operation is needed to ensure correctness. On the other hand, iterations 0 and 2 cannot run in parallel because iteration 0 writes to x[2], which iteration 2 reads from. Thus, iteration 2 must wait until iteration 0 completes. This is often ensured through barriers or other synchronization methods.

Loop-Carried Dependence Parallelism (LCD) Transformation

To address this challenge, we, a group of researchers from McMaster University and the University of Utah developed LCD, a compiler framework and transformation technique. LCD acts as an intelligent translator that automatically transforms sequential sparse loops into highly parallelized GPU programs. Implemented as a Python Just-In-Time (JIT) compiler, LCD analyzes code annotations at runtime, constructs a directed acyclic graph (DAG) of calculations, and maps out the safest and fastest way to distribute work across GPU threads without breaking computational dependencies.

The overall LCD transformation pipeline is shown in Figure 2. As shown, LCD has a two-tiered management pipeline guided by an analytical scheduler:

• Block Manager: Maps larger computational chunks to GPU thread-blocks and decides between synchronization models, such as barrier-free execution that tracks dependencies using atomic counters, to avoid expensive kernel restarts.
• Thread Manager: Parallelize inner loops down to individual GPU threads and warps, leveraging hardware-level shuffle instructions and loop unrolling to maximize data locality.
• Smart Scheduler: Evaluates matrix structure and hardware latency at runtime to select the optimal strategy before execution.

In extensive benchmarks on NVIDIA H100 GPUs across 230+ sparse matrices, LCD-generated code outperformed industry-standard libraries like cuSPARSE, achieving geometric mean speedups ranging from 1.60× to 4.56× across core operations like sparse triangular solves, Gauss-Seidel iterations, and ILU preconditioning. Crucially, the compiler's initial inspection overhead to analyze matrix structures is amortized almost instantly—often breaking even after just one or two solves in real-world iterative applications.

By bridging the gap between high-level Python expressiveness and low-level GPU hardware tuning, LCD demonstrates that developer-friendly compiler abstractions can unlock hardware efficiency for complex scientific computing workloads.

For more detailed information about LCD, please refer to the LCD paper.

LCD paper: SC26 Draft
LCD code repository: https://github.com/swiftWare-Lab/lcd