FastTwoSum Is Faster Than TwoSum
a year ago
- #algorithms
- #floating-point
- #performance
- 浮点运算存在精度问题，但TwoSum和FastTwoSum这类算法能通过同时计算总和与舍入误差来量化不精确性。
- TwoSum需6次浮点运算（延迟15-20周期），而FastTwoSum仅需3次运算（延迟9-12周期）但要求输入值按绝对值排序。
- 若输入未排序，分支预测错误惩罚会使FastTwoSum慢于TwoSum，但无分支条件操作可缓解此问题。
- 苹果M1处理器测试显示TwoSum耗时15周期，FastTwoSum为9周期，排序版介于两者之间。
- 在Intel Coffee Lake架构上，GCC编译的FastTwoSum基础排序版表现优异，但Clang因分支生成差异导致性能波动。
- SIMD实现相比无分支条件移动操作未能显著提升性能。
- 最优FastTwoSum变体在ARM和Intel平台均比TwoSum快20%以上，但需精心优化编译器以避免分支。
- 若硬件直接实现TwoSum或等效功能，可大幅降低双精度浮点加法的运算开销。