1

我的应用程序对大尺寸矩阵进行了一些操作。我最近遇到了缓存的概念以及它可以通过这个答案产生的性能影响。我想知道什么是对我的案例缓存友好的最佳算法。

Algorithm 1:
for(int i = 0; i < size; i++)
{
    for(int j = i + 1; j < size; j++)
    {
        c[i][j] -= K * c[j][j];//K is a constant double variable
    }//c is a 2 dimensional array of double variables
}

Algorithm 2:
double *A = new double[size];
for(int n = 0; n < size; n++)
    A[n] = c[n][n];

for(int i = 0; i < size; i++)
{
    for(int j = i + 1; j < size; j++)
    {
        c[i][j] -= K * A[j];
    }
}

我的数组大小超过 1000x1000。在我的笔记本电脑上进行基准测试显示，对于 5000x5000 尺寸，算法 2 优于 1。请注意，我对我的应用程序进行了多线程处理，因此一组行由一个线程操作。

For example: For array of size 1000x1000.
thread1 -> row 0 to row 249
thread2 -> row 250 to row 499
thread3 -> row 500 to row 749
thread4 -> row 750 to row 999
4

2 回答 2

2

如果您的基准测试显示第二种情况有显着改善，那么它很可能是更好的选择。但是，当然，要知道“平均 CPU”，我们必须知道对于可以称为平均的大量 CPU - 没有其他方法。这实际上取决于平均 CPU 的定义。我们是在谈论“任何 x86 (AMD + Intel) CPU”还是“我们可以在任何东西中找到的任何随机 CPU，从手表到 x86 范围内最新的超快速创建”？

“复制数据c[n][n]”方法很有帮助，因为它有自己的地址，并且当代码遍历更大的矩阵时不会被抛出（L1）缓存[以及乘法所需的所有数据是“紧靠在一起”。如果你 walk c[j][j]，每j一步都会在每次迭代中跳转sizeof(double) * (size * j + 1)字节，所以如果 size 大于 4，则需要的下一个项目不会在同一个缓存行中，因此需要另一个内存读取来获取该数据。

换句话说，对于任何具有适当大小的缓存（大于size * sizeof(double)）的东西，这是一个明确的好处。即使使用较小的缓存，它也很有可能带来一些好处，但缓存副本被c[i][j].

总之，第二种算法很可能对几乎所有选项都更好。

于 2013-09-21T09:24:39.303 回答
2

算法 2 受益于所谓的“空间局部性”，将对角线移动到一维数组中，使其以连续地址驻留在内存中，从而：

  1. 享受每个高速缓存行（大概 64 字节，取决于您的 CPU）获取多个有用元素的好处，更好地利用高速缓存和内存 BW（而 c[n][n] 也会获取大量无用数据，因为它在相同的行）。

  2. 享受硬件流预取器的好处（假设存在于您的 CPU 中），它积极地在您的代码之前沿着页面运行，并将数据提前带到较低的缓存级别，从而改善内存延迟。

应该指出的是，将数据移动到 A 并不一定会提高缓存能力，因为 A 仍然会与不断来自 c 的大量数据竞争并破坏缓存。然而，由于它被反复使用，一个好的 LRU 算法很有可能让它保留在缓存中。您可以通过对数组 c 使用流式内存操作来帮助实现这一点。应该注意的是，这些是非常不稳定的性能工具，如果使用不当，在某些情况下可能会导致性能下降。

另一个潜在的好处可能来自在到达每个新阵列线之前稍微混合 SW 预取。

于 2013-09-21T09:51:44.253 回答