Measuring Gauss-Seidel loop-carried dependency and fixing it via loop unrolling
Summary
This technical post analyzes why Gauss-Seidel often lags behind Jacobi in practice due to loop-carried dependencies that hinder vectorization. Using OSACA, it measures CP and LCD to show Gauss-Seidel is latency-bound while Jacobi is throughput-bound, then demonstrates loop unrolling and algebraic rewrites to break the dependency. A degree-2 unrolled kernel for a 2D Poisson problem nearly matches Jacobi on a single core, preserving Gauss-Seidel’s faster convergence while improving per-sweep efficiency.