C语言中直接映射缓存的优化

Question

我在理解下面两段代码的命中率和失效率方面遇到一些困难。

已知信息：我们有一个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路组相联高速缓存？

谢谢。

- JDS

---

由于预取和关联等影响，缓存未命中很难预测。更容易的方法是使用分析器并从硬件上计算它们。 - Mysticial

一般来说，当您不知道硬件的详细信息或它足够复杂时，我想是这样的。但这本应该是一个简单的教科书练习 =( - JDS

对于教科书练习，只要与书后的内容匹配就可以了。:P 但是90%的时间，现实中的数字将完全不同。 - Mysticial

现在我有点忙，如果没有人回答，稍后我会提供一个简单的分析。就像Mysticial所说，现实世界可能更加复杂，但是理解原则确实值得付出。 - WiSaGaN

Answer 1

数据在内存中的存储方式
每一个结构体pos的大小为8字节，因此pos[16][16]的总大小为2048字节。数组按照如下顺序排列：
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字节，这与数组的两个元素大小相同。整个缓存大小为1024字节，是整个数组大小的一半。由于缓存是直接映射的，那么如果我们将缓存块从0到63标记，我们可以安全地假设映射应该如下所示：
------------ memory----------------------------cache
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]的访问已经清除了前面的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路相联缓存的分析方式相同，尽管这可能更加繁琐。为了充分利用缓存系统，请尝试启动良好的访问模式，例如 步长-1，并尽可能在每次从内存加载时使用数据。现实世界中的CPU微架构采用其他智能设计和算法以增强效率。最佳方法始终是在真实环境中测量时间，转储核心代码并进行彻底分析。

- WiSaGaN

---

讲解得非常清楚，现在我明白了我的错误所在（由于直接映射，第二列、第四列等被覆盖）。我认为我的答案适用于>2关联高速缓存。 - Michel Müller

Answer 2

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

您的结构体长度为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%的未命中率。也许有人能找到更好的答案，但如果你理解了我的推理，我建议你向助教询问。

编辑：再次思考，我们应该首先定义什么才算未命中/命中。当你看到

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;

这可以被视为一次内存访问。因此，我建议对所有计算机科学问题都给出一个通用答案：“这取决于情况。”

- Michel Müller