通过数组缓存计算命中/未命中率

Question

通过数组缓存计算命中/未命中率

3

我正在阅读Bryant & O'Hallaron的《计算机系统》一书，其中有一道练习题的解答似乎是错误的。所以我想确认一下。

题目如下：

struct point {
  int x; 
  int y;  };


struct array[32][32];

for(i = 31; i >= 0; i--) {
   for(j = 31; j >= 0; j--) {
      sum_x += array[j][i].x;
      sum_y += array[j][i].y; }}

sizeof(int) = 4;

sizeof(int) 的值为 4。

我们有一个 4096 字节的缓存，块（行）大小为 32 字节。要求命中率。

我的推理是，我们有 4096/32 = 128 个块，每个块可以存储 4 个点（2*4*4 = 32），因此缓存可以存储数组的一半，即 512 个点（总共 32*32 = 1024）。由于代码按列主序访问数组，访问每个点都会出现缺失。所以我们有 array[j][i].x 总是缺失，而 array[j][i].y 是命中。最终的缺失率等于命中率等于 1/2。

问题：解决方案说命中率为 3/4，因为缓存可以存储整个数组。

但根据我的推理，缓存只能存储一半的点。

我错过了什么吗？

- cellka

sizeof(int) = 4; <-- 给定 - cellka

你是对的，存储顺序就是这样的。因此，通过读取 point[j][i].x，由于空间局部性（在我们的情况下 point = 数组），point[j][i].y 存储在缓存中。 - cellka

通过访问array[0][0].x，我们将array[0][0].y，array[0][1].x，array[0][1].y，...，array[0][3].x，array[0][3].y加载到第一个块中。 - cellka

@thb 我在等待。顺便说一下，我觉得很明显缓存无法存储整个数组，而解决方案却声称可以。 - cellka

2个回答

1

如果您正确地转录了程序，那么您是正确的，3/4的答案是错误的。

如果内部的sum += ...语句中的索引排列得最快，则3/4的答案将是正确的，例如：

    sum_x += array[i][j].x;
    sum_y += array[i][j].y;

在这种情况下，循环的第1、5、9…次迭代会错过，但每次错过时加载到缓存中的行将导致接下来的三次迭代命中。

然而，按照程序编写的方式，每次迭代都会错过。从内存中加载的每个缓存行仅为单个点提供数据，然后在访问该行中的任何其他三个点的数据之前，该行始终被替换。

作为一个例子（为了简单起见，假设第一个成员array[0][0]的地址与缓存开始对齐），第一次循环时对array[31][31]的引用是一次缺失，导致缓存的第127行被加载。此时，第127行包含了[31][28]、[31][29]、[31][30]和[31][31]的数据。然而，在获取array[15][31]之后，会覆盖掉array[31][30]被引用之前的第127行，所以当轮到[31][30]时，它也会缺失。然后，在[31][29]被引用之前，[15][30]的缺失会替换掉前一个线路。

你的1/2命中率过高，因为它将对.y坐标的访问计为一次命中。然而，原始的3/4答案并非如此。如果对.y坐标的获取被计为一次命中，那么原始答案将是7/8。相反，它将每个完整的点，或者可能是每个循环迭代，都视为命中或未命中。按照这种方式，程序在你的问题中的命中率是一个漂亮的0。

- ottomeister

你说得对，如果我们按照数组元素计算缺失率，那么缺失率将为0。但我认为我们应该按照读取操作来计算它。顺便感谢你的回答。 - cellka

顺便问一下，你是在使用这本书的“全球版”吗？作者在他们的网站http://csapp.cs.cmu.edu/3e/errata.html上有一份声明，说该版本中的练习已被出版商替换，并且已知存在错误。 - ottomeister

源代码是用C编写的，因此无法确定实际发生了什么（例如，编译器的优化器可能会转换循环，使得数组以良好的顺序模式访问）。 - Brendan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- thb · Accepted Answer

数组的前四行占用了缓存的一部分：

|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|*ooooooooooooooooooooooooooooooo|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx|
|...

上面是一个数组的示意图，如同一位应用数学家在纸上写的那样。每个元素由一个(x,y)对组成，即一个“点”。

图示中标记为“o”的四行共包含128个“点”，足以填满1024字节，仅占缓存的四分之一。但请注意：在您的代码中，变量i既是“主”循环计数器，也是数组的“行”索引（如在纸上写的那样）。

那么，让我们再次看一下这个图。您的嵌套循环如何按照图示遍历数组呢？

答案是：显然，您的循环从图示中的顶部行向右移动，其中j（列）是次要循环计数器。然而，正如您所观察到的，该数组是按列存储的。因此，当加载元素[j][i] == [0][0]时，将加载整个缓存行。那么，这个缓存行包含什么？它是图示中标记为“*”的四个元素。

因此，当您的内部循环按照图表遍历数组的顶行时，每次缓存都会缺失，每次获取四个元素。然后对于接下来的三行，全都是命中。

这不容易想到。这是一个好问题，我也不希望您立即理解我的答案，但是如果您仔细考虑我所解释的加载序列，经过一番思考后，应该开始有意义了。

在给定的循环嵌套中，命中率确实为3/4。

进一步讨论

在评论中，您提出了一个很好的后续问题：

您能写一个元素（例如`array[3][14].x`）来进行命中吗？

我可以。`array[j][i] == array[10][5]`将会命中。（`.x`和`.y`都会命中。）

我来解释一下。当array[j][i] == array[10][4]时，会错过，但array[10][5]、array[10][6]和array[10][7]最终会被访问到。为什么是“最终”呢？这很重要。虽然我提到的这四个元素都是由缓存硬件一次性加载的，但当访问array[10][4]时，你的代码（即CPU）并不会访问array[10][5]，而是在程序和CPU接下来访问array[11][4]之后才会访问array[10][5]。

实际上，程序和CPU只有在稍后才会访问array[10][5]。

如果你想一想，这其实很合理，因为这就是缓存的作用之一：它们现在静默地将额外的数据作为缓存行加载，以便CPU在以后快速访问这些额外的数据。

附录：FORTRAN/BLAS/LAPACK矩阵排序

在数值计算中，按列而不是按行存储矩阵是标准做法。这被称为“列优先”存储。不幸的是，与早期的Fortran编程语言不同，C编程语言最初并非为数值计算而设计，因此，在C中，要按列存储数组，必须编写array[column][row] == array[j][i] ——这种表示方法当然颠倒了应用数学家使用铅笔书写的方式。

这是C编程语言的一种特殊情况。这个特殊情况没有数学意义，但在C编程时，你必须记得键入[j][i]。[如果你正在使用现在大多已过时的Fortran编程语言，你会键入(i, j)，但这不是Fortran。]

列优先存储成为标准的原因与CPU执行标量浮点乘法和加法的顺序有关，当数学/铅笔术语中的矩阵[A]左作用于列向量x时。标准的基本线性代数子程序（BLAS）库（由LAPACK等使用）就是这样工作的。你和我也应该这样工作，不仅因为我们可能需要与BLAS和/或LAPACK进行接口交互，而且从数值上讲，这样更加平稳。