c++ - 数据大于缓存的 3D FFT

Question

我已经搜索了这个问题的答案，但没有找到任何可以直接帮助我的东西。

我正在使用 MKL 中包含的并行 FFT 库为非线性 PDE 开发 3D 数值积分器。

我的数组由 2^30 个数据点组成，比缓存大得多。这导致约 50% 的缓存引用未命中，这似乎增加了大量访问内存的开销。

有什么聪明的方法可以解决这个问题吗？使用这么大的数组是否预计会有 50% 的缓存未命中？

如有任何帮助，我们将不胜感激。

谢谢，

迪伦

Answer 1

单个 FFT 中的 2^30 个数据点算得上很大了!

数据加上指数和输出数组比 L3 缓存大几千倍，比 L1 大几百万倍。

鉴于这种差异，有人可能会争辩说 50% 的缓存未命中率实际上相当不错，尤其是对于像 FFT 这样以非顺序方式访问内存的算法。

我认为您对此无能为力。 MKL 非常好，我确信他们已经利用了现有的任何缓存提示指令。

您可以尝试联系 Mercury Systems Inc. (www.mrcy.com)，询问他们的科学算法库 (SAL)。他们有编写自己的数学库的习惯，根据我的经验，他们非常擅长。他们在 PowerPC 上的 FFT 比下一个最好的快 30%；相当大的成就。您可以免费试用未优化的 SAL 版本 (http://sourceforge.net/projects/opensal/)。不过，真正针对英特尔 SAL 优化的绝对不是免费的。

另请记住，无论算法多么聪明，对于这样大小的数据集，您总是会从根本上受限于主内存带宽，而不是缓存带宽。

GPU 可能值得一看，但您需要一个具有大量内存的内存来保存 2^30 个数据点(32 位复数值 = 2GB，输出数组同样如此，加上指数等)。