A CUDA project that implements and optimizes the sparse triangular solve — solving Lx = B
for a sparse lower-triangular matrix L and a dense right-hand-side matrix B. SpTRSV is
hard to parallelize because each row depends on the results of earlier rows, so most of the
work here is about exposing parallelism despite those dependencies. The project builds up
four GPU kernels, each faster than the last, and benchmarks them against a sequential CPU
reference.
Speedup over the sequential CPU implementation (higher is better), measured across three
sparse matrices (small = rajat18, medium = parabolic_fem, large = tmt_sym) and three
right-hand-side widths (128 / 256 / 512 columns). The final column is the geometric mean
across all nine configurations.
| Kernel | Strategy | small 128/256/512 | medium 128/256/512 | large 128/256/512 | geomean |
|---|---|---|---|---|---|
| kernel1 | level-scheduling | 41 / 82.4 / 133 | 228 / 305 / 420 | 0.40 / 0.98 / 2.4 | 28.5× |
| kernel2 | + cached level analysis | 53 / 153 / 268 | 331 / 1611 / 1558 | 0.84 / 1.7 / 4.4 | 60.8× |
| kernel3 | + refined level cache | 52.5 / 864 / 1137 | 256 / 1245 / 1339 | 3.6 / 6.8 / 22.6 | 132.0× |
Each optimization roughly doubled the previous kernel's speedup, ending at a ~132× geometric-mean speedup over the CPU. In the class benchmark, kernel3 placed at the top of our milestone group.
- kernel0 — the first parallel version. One block per RHS column; the outer loop over rows runs sequentially while threads parallelize the scatter within a column (CSC format). It works, but the sequential row loop leaves a lot of parallelism on the table.
- kernel1 — level-scheduling. The matrix is analyzed into dependency levels: rows
that don't depend on each other end up in the same level and can be solved simultaneously.
Each level is launched as a grid (one block per row in the level), with threads spread over
the columns of
B(CSR format). This is where the big jump in parallelism comes from. - kernel2 — the same level-scheduled kernel, but the (expensive) level analysis is cached and reused across calls instead of being recomputed every solve, so repeated solves on the same matrix are much faster.
- kernel3 — a refined level cache (a dedicated cache struct, dataset-size aware) that cuts the remaining setup overhead further. This is the fastest version.
kernelCPU.cu is the sequential reference used both to check correctness and as the speedup
baseline. main.cu verifies every GPU result against it before reporting timings.
Three real sparse matrices, selectable at runtime:
-d s—rajat18(small)-d m—parabolic_fem(medium)-d l—tmt_sym(large)
Needs the CUDA toolkit and an NVIDIA GPU.
cd sptrsv
make
Run the CPU reference plus a GPU kernel on a chosen dataset, e.g. kernel3 on the small matrix:
./sptrsv -d s -s -3
Flags: -d s|m|l selects the dataset, -s runs the CPU reference, and -0 / -1 / -2 /
-3 each run the corresponding GPU kernel. Combine several kernel flags in one run to compare
them side by side.
Group project (group name: "Can we do better?") — team members: Ali Rida Awad, Ali Daher, Mohamad Hussein Karnib.