具有潜在性能优化的浮点算法

Question

对于大学讲座,我正在寻找具有已知渐近运行时的浮点算法,但是可以进行低级(微)优化.这意味着优化,例如最小化缓存未命中和寄存器溢出,最大化指令级并行性以及利用新CPU上的SIMD(向量)指令.优化将特定于CPU,并将使用适用的指令集扩展.

经典的教科书示例是矩阵乘法,通过简单地重新排序存储器访问序列(以及其他技巧)可以实现极大的加速.另一个例子是FFT.不幸的是,我不允许选择其中任何一个.

任何人有任何想法,或可以使用提升的算法/方法？

我只对可以想象每线程加速的算法感兴趣.通过多线程并行解决问题很好,但不是本讲座的范围.

编辑1:我走的过程中,没有教它.在过去几年中,有不少项目在性能方面成功超越了当前最佳实施.

编辑2:本文列出了(从第11页开始)七类重要的数值方法和一些使用它们的相关算法.至少一些提到的算法是候选者,但是很难看出哪个算法.

---

编辑3:谢谢大家的好建议!我们建议实施曝光融合算法(2007年的论文),我们的提案被接受了.该算法创建类似HDR的图像,主要包括小核卷积,然后是源图像的加权多分辨率混合(在拉普拉斯金字塔上).我们感兴趣的是,该算法已经在广泛使用的Enfuse工具中实现,该工具现在的版本为4.1.因此,我们将能够验证和比较我们的结果与原始结果,也可能有助于工具本身的开发.如果可以的话,我将在未来更新这篇文章.

Answer 1

最简单的例子:

• 积累一笔钱.使用多个累加器和矢量化展开允许在典型的流水线架构上加速(ADD延迟)*(SIMD矢量宽度)(如果数据在缓存中;因为没有数据重用,如果您正在读取数据,它通常无济于事记忆),很容易就是一个数量级.可爱的事情要注意:这也会降低结果的平均误差!相同的技术适用于任何类似的减少操作.

一些来自图像/信号处理的经典:

• 小内核的卷积(特别是小的2d卷积,如3x3或5x5内核).在某种意义上,这是作弊,因为卷积是矩阵乘法,并且与FFT密切相关,但实际上高性能小内核卷积的细节算法技术与两者完全不同.

• 腐蚀和扩张.

• 人们称之为"伽马校正"的形象; 这实际上是对指数函数的评估(可能是零线性段接近零).在这里你可以利用这样的事实:图像数据通常完全处于一个很好的有界范围,如[0,1],并且使用更便宜的函数近似很少需要亚ulp精度(低阶分段极小极大多项式是常见的).