caching - 缓存大小和数组大小如何影响数组上数学运算的性能？

Question

我正在尝试学习缓存的用法。从我通过做一些示例实验程序看到的情况来看，如果我将数组大小增加到超过特定值，那么执行迭代数组并对元素执行一些操作所花费的时间会突然增加很多。谁能简单地解释一下术语缓存大小和数组大小如何影响数组上数学运算的性能？

Answer 1

如果缓存无法累积数组，则对那些未累积元素的任何引用都将导致缓存未命中。访问数组元素的方式也有所不同，因为每次未命中时，处理器都会将数据块带入缓存，并认为可能很快需要这些数据，从而为避免未来的缓存未命中做好准备。

例子 ：

如果您对来自连续位置的元素进行操作，性能将会提高。因为根据缓存行的大小，处理器将在第一次缓存未命中时获取一块内存。

例如，以矩阵乘法为例，我们按以下方式进行。

假设：矩阵太大而无法在缓存中累积。

 for (i = 0; i < N; i = i + 1)
      for (j = 0; j < N; j = j + 1)
          A[i*N + j] = (double) random() / SOME_NUMBER;     

 for (i = 0; i < N; i = i + 1)
   for (j = 0; j < N; j = j + 1)
       B[i*N + j] = (double) random() / SOME_NUMBER;


 for (i = 0; i < N; i = i + 1)
    for (j = 0; j < N; j = j + 1)
       for (k = 0; k < N; k = k + 1)
           C[i*N + j] = C[i*N + j] + A[i*N + k]*B[k*N + j];

在这里，在为每一行相乘时，我们继续访问第二个矩阵列。在B第一列中存储B[0],[N-1],B[2N-1].......等等，它们不是连续的内存位置。因此会有很多缓存未命中。因此，如果我们可以塑造解决方案，以便我们处理连续的内存位置并可以获得一些性能提升。我们可以将第二个矩阵存储在“列主要形式”中，即转置形式，而不是将第二个矩阵存储在“行主要形式”中。所以现在所有的列元素都在连续的位置。

A将按行访问B并将按列访问，因此我们将它们所有的“各自的东西”放在连续的内存位置。

因此，当处理器遇到第一次未命中时，它将获取一块内存，因此将避免下一次未命中。在这里，我们利用了“空间局部性”，因此也利用了“缓存阻塞”。

现在，如果我们将代码更改如下，性能将会有显着提升

以转置形式存储 B：

   B[j*N + i] = random() / SOME_NUMBER;

您还必须按该顺序访问转置数组：

  C[i*N + j] = C[i*N + j] + A[i*N + k]*B[j*N + k];