10

在确定以下两个代码片段的命中率和未命中率时遇到了一些麻烦。

给定信息：我们有一个 1024 字节的直接映射缓存，块大小为 16 字节。这样就产生了 64 行（在这种情况下为集合）。假设缓存开始为空。考虑以下代码：

struct pos {
    int x;
    int y;
};

struct pos grid[16][16];
int total_x = 0; int total_y = 0;

void function1() {
    int i, j;
    for (i = 0; i < 16; i++) {
         for (j = 0; j < 16; j++) {
             total_x += grid[j][i].x;
             total_y += grid[j][i].y;
         }
    }
}

void function2() {
    int i, j;
    for (i = 0; i < 16; i++) {
         for (j = 0; j < 16; j++) {
             total_x += grid[i][j].x;
             total_y += grid[i][j].y;
         }
    }
}

我可以从一些基本规则（即 C 数组是行优先顺序）中看出 function2 应该更好。但我不明白如何计算命中/未命中百分比。显然 function1() 错过了 50% 的时间，而 function2() 只错过了 25% 的时间。

有人可以告诉我这些计算是如何工作的吗？我真正能看到的是，一次不会超过一半的网格可以放入缓存中。此外，这个概念是否易于扩展到 k 路关联缓存？

谢谢。

4

2 回答 2

12

数据如何存储在内存中
每个结构pos的大小为 8 Bytes，因此总大小pos[16][16]为 2048 Bytes。并且数组的顺序如下：
pos[0][0] pos[0][1] pos[0][2]………………………………pos[0][15] pos[1]0[]pos[1][15]pos[15][0]pos[15][15]

缓存组织对比数据
对于缓存，每个块为 16 Bytes，与数组的两个元素大小相同。整个缓存为 1024 字节，是整个数组大小的一半。由于缓存是直接映射的，这意味着如果我们将缓存块标记为 0 到 63，我们可以放心地假设映射应该如下所示
------------ memory------ ----------------------缓存
pos[0][0] pos[0][1] -----------> block 0
pos[0][2] pos[0][3] -----------> block 1
pos[0][4] pos[0][5] --- --------> block 2
pos[0][14] pos[0][15] --------> block 7
.......
pos[1][0] pos[1][1] -----------> block 8
pos[1][2] pos[1][3] -----------> block 9
。 ......
pos[7][14] pos[7][15] --------> block 63
pos[8][0] pos[8][1] -----------> block 0
.......
pos[15][14] pos[15][15] -----> block 63

如何function1操作内存
循环遵循按列的内部循环，这意味着第一次迭代加载pos[0][0]和pos[0][1]缓存block 0，第二次迭代加载pos[1][0]和pos[1][1]缓存block 8。缓存是冷的，所以第一列x总是未命中，而y总是命中。第二列数据应该在第一列访问期间全部加载到缓存中，但事实并非如此。由于pos[8][0]access 已经驱逐了前一个pos[0][0]页面（它们都映射到block 0！）。依此类推，未命中率为 50%。

如何function2操作内存
第二个函数有很好的stride-1访问模式。这意味着当pos[0][0].x pos[0][0].y pos[0][1].x pos[0][1].y仅访问第一个时由于冷缓存而未命中。下面的模式都是一样的。所以失误率只有25%。

K路关联缓存遵循相同的分析，尽管这可能更乏味。为了充分利用缓存系统，请尝试启动一个良好的访问模式，例如stride-1，并在每次从内存加载期间尽可能多地使用数据。现实世界的 cpu 微架构采用其他智能设计和算法来提高效率。最好的方法总是在现实世界中测量时间，转储核心代码，并进行彻底的分析。

于 2012-07-10T12:13:59.133 回答
1

好的，我的计算机科学课程离我有点远，但我想我明白了（当你考虑它时，这实际上是一个非常简单的例子）。

您的结构是 8 字节长 (2 x 4)。由于您的缓存块是 16 字节，因此内存访问grid[i][j]将准确获取两个结构条目（grid[i][j]和grid[i][j+1]）。因此，如果您循环遍历第二个索引，则只有每 4 次访问才会导致内存读取。如果您遍历第一个索引，您可能会丢弃已提取的第二个条目，这取决于内部循环中的提取次数与整体缓存大小。

现在我们还必须考虑缓存大小：您说您有 64 行直接映射。在函数 1 中，一个内部循环是 16 次获取。这意味着，第 17 次获取到 grid[j][i+1]。这实际上应该是一个命中，因为自上次内部循环遍历以来它应该一直保存在缓存中。因此，每隔一个内循环应该只包含命中。

好吧，如果我的推理是正确的，那么已经给你的答案应该是错误的。这两个函数都应该以 25% 的未命中率执行。也许有人会找到更好的答案，但如果你理解我的推理，我会问 TA。

编辑：再想一想，我们应该首先定义什么才是真正的未命中/命中。当你看

total_x += grid[j][i].x;
total_y += grid[j][i].y;

这些是定义为两个内存访问还是一个？具有优化设置的体面编译器应将其优化为

pos temp = grid[j][i];
total_x += temp.x;
total_y += temp.y;

这可以算作一次内存访问。因此，我建议所有 CS 问题的通用答案：“视情况而定”。

于 2012-07-10T06:37:57.807 回答