对于大学讲座，我正在寻找具有已知渐近运行时间但具有低级(微)优化潜力的浮点算法。这意味着优化，例如最小化高速缓存未命中和寄存器溢出、最大化指令级并行性以及在新 CPU 上利用 SIMD(矢量)指令。优化将特定于 CPU，并将使用适用的指令集扩展。
这方面的经典教科书示例是矩阵乘法，其中可以通过简单地重新排序内存访问顺序(以及其他技巧)来实现极大的加速。另一个例子是 FFT。不幸的是，我不能选择其中任何一个。
任何人有任何想法或可以使用提升的算法/方法吗？
我只对可以想象每线程加速的算法感兴趣。通过多线程并行处理问题很好，但这不是本讲的范围。
编辑 1:我正在上这门类(class)，而不是教它。在过去几年中，有相当多的项目在性能方面成功地超越了当前的最佳实现。
编辑 2:这 paper列出(从第 11 页开始)七类重要的数值方法和一些使用它们的相关算法。至少有一些提到的算法是候选的，但是很难看出是哪一个。
编辑 3:谢谢大家的宝贵建议!我们提议实现曝光融合算法 (paper from 2007)，我们的提议被接受了。该算法创建类似 HDR 的图像，主要由小核卷积组成，然后是源图像的加权多分辨率混合(在拉普拉斯金字塔上)。对我们来说有趣的是，该算法已经在广泛使用的 Enfuse 中实现。工具，现在是 4.1 版。因此，我们将能够验证我们的结果并将其与原始结果进行比较，并且还可能为工具本身的开发做出贡献。如果可以的话，我会在以后用结果更新这篇文章。
最佳答案
最简单的例子:
- 累积一笔款项。使用多个累加器展开和矢量化允许在典型的流水线架构上加速(ADD 延迟)*(SIMD 矢量宽度)(如果数据在缓存中；因为没有数据重用，如果您从内存)，这很容易达到一个数量级。值得注意的是:这也降低了结果的平均误差!相同的技术适用于任何类似的归约操作。
一些来自图像/信号处理的经典:
使用小内核进行卷积(尤其是像 3x3 或 5x5 内核这样的小 2d 卷积)。从某种意义上说，这是作弊，因为卷积 是 矩阵乘法，并且与 FFT 密切相关，但实际上高性能小核卷积的本质算法技术与两者完全不同。
侵 eclipse 和扩张。
人们称之为“ Gamma 校正”的图像；这实际上是对指数函数的评估(可能具有接近零的分段线性段)。在这里，您可以利用这样一个事实，即图像数据通常完全在一个很好的有界范围内，如 [0,1]，并且很少需要亚 ulp 精度来使用更便宜的函数逼近(低阶分段极小极大多项式很常见)。
关于performance - 具有性能优化潜力的浮点算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/22129503/