Gauss-SeidelはなぜJacobiより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の依存連鎖は本質的にアルゴリズムに組み込まれているのであって、コンパイラが見落としたスケジューリング上の事故ではない。
HNでの議論
22- mota7
「…そしてこれがすべての核心だ：」、「すぐに飛び出せ」、「…そしてそのアイデアは驚くほどシンプルだ」などなど。
Claude AIによって書かれている。これは問題だ。なぜならClaudeのテキストはエンゲージメントを狙った釣りやフィラーだらけで、読むのがうんざりするからだ。
- hwita
この分析は逐次過緩和法（SOR）にも拡張できそうだ。対称逐次過緩和法にも拡張できるのだろうか？
- sheafification
ごく例外的なケースを除けば、CPUバウンドな問題において、実際に動かすアーキテクチャ向けにきちんと書かれたLAPACK実装よりも良い結果を出せるとは思えない。
もしかすると教育が目的だったのか？ 記事からはあまりそういう意図は読み取れなかった。AIを通すことで意図の一部が失われたのかもしれない。