Measuring Gauss-Seidel loop-carried dependency and fixing it via loop unrolling

It examines why Gauss-Seidel, despite requiring about half as many iterations as Jacobi on a 2D Poisson problem, runs several times slower in practice. The reason is loop-carried dependencies: Gauss-Seidel updates in place so each iteration reads freshly written neighbors, creating a 12-cycle dependency chain that prevents vectorization, whereas Jacobi reads from an untouched old array and vectorizes four points at a time. Static assembly analysis with OSACA shows identical critical-path length (24 cycles) for both kernels but a tiny loop-carried dependency for Jacobi (1 cycle) versus 12 cycles for Gauss-Seidel. That makes Gauss-Seidel latency-bound and Jacobi throughput- or bandwidth-bound; normalizing predicts a large per‑sweep slowdown that, once reduced by Gauss‑Seidel’s halved sweep count, aligns reasonably with measured wall‑clock results.

The write-up then explores loop unrolling as a way to expose more independent work to the compiler and scheduler, explaining the classical benefit of fewer branches and more instruction-level parallelism. A straightforward two‑way unroll of the Gauss‑Seidel inner loop, however, fails: the second unrolled statement immediately reads the value just computed by the first, turning the cross‑iteration dependency into an intra‑iteration one and leaving vectorization impossible. The piece frames two remedy paths to pursue next: aggressive compiler‑helping transformations like careful unrolling and a problem‑specific mathematical reorganization.