Measuring Gauss-Seidel loop-carried dependency and fixing it via loop unrolling
a day ago
- Gauss-Seidel converges in half the iterations of Jacobi, but naive implementation is 4-5x slower due to loop-carried dependencies that prevent vectorization.
- OSACA analysis reveals Gauss-Seidel has a 12-cycle loop-carried dependency per element, while Jacobi is throughput-bound at 3 cycles per 4 elements.
- Plain loop unrolling does not remove the dependency; algebraic rewriting of the update rule is needed to compute two points independently.
- A degree-2 unrolled Gauss-Seidel kernel reduces loop-carried dependency to 2 cycles per element, making the kernel throughput-bound and matching Jacobi's per-sweep speed.
- Experiments confirm the unrolled kernel achieves the same convergence as textbook Gauss-Seidel but with Jacobi-like efficiency, solving the problem faster overall.
- The optimized kernel still uses scalar instructions and has a residual pair-to-pair dependency, preventing vectorization and parallelization—a serial-only win.
- Future work: red-black ordering may enable vectorization and multithreading for Gauss-Seidel.