Measuring Gauss-Seidel loop-carried dependency and fixing it via loop unrolling
a day ago
- 高斯-赛德尔迭代的收敛速度是雅可比迭代的两倍，但由于循环携带的依赖性阻碍了向量化，朴素实现的速度慢了4到5倍。
- OSACA分析显示，高斯-赛德尔每个元素存在12个时钟周期的循环携带依赖，而雅可比每次处理4个元素仅需3个时钟周期，受吞吐量限制。
- 简单的循环展开无法消除依赖；需要代数重写更新规则才能独立计算两个点。
- 二阶展开的高斯-赛德尔核心将每个元素的循环携带依赖减少到2个时钟周期，使核心受吞吐量限制，达到与雅可比每次扫描相当的速度。
- 实验证实，展开的核心实现了与教科书上高斯-赛德尔相同的收敛效果，但具有雅可比般的效率，整体上更快地解决了问题。
- 优化后的核心仍使用标量指令，并存在残余的成对依赖，阻碍了向量化和并行化——仅适用于串行场景。
- 未来工作：红黑排序可能实现高斯-赛德尔的向量化和多线程处理。