Gauss-Seidel이 Jacobi보다 4~5배 느린 이유, 루프 언롤링으로 해결하다
Measuring Gauss-Seidel loop-carried dependency and fixing it via loop unrolling
Gauss-Seidel은 수렴에 절반의 반복만 필요하지만, 루프 전달 의존성 때문에 Jacobi보다 4~5배 느리다. OSACA 분석 결과 Gauss-Seidel은 12사이클의 지연에 묶여 있는 반면 Jacobi는 처리량에 묶여 있다. 단순한 루프 언롤링은 의존성을 제거하지 못하지만, 의존성을 재작성하면 하드웨어 효율을 되찾을 수 있다.
Gauss-Seidel의 더 빠른 수렴은 컴파일러가 스스로 깨뜨릴 수 없는, 요소당 12사이클의 직렬화된 의존성 체인이라는 대가를 통해 전적으로 얻어진다.