直接映射缓存的 C 缓存优化

Question

在计算以下两段代码的命中率和未命中率时遇到了一些麻烦。

给定信息:我们有一个 1024 字节的直接映射缓存， block 大小为 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 路关联缓存？

谢谢。

Answer 1

数据在内存中的存储方式
每个结构 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]

与数据相比的缓存组织
对于缓存，每个 block 为 16 字节，与数组的两个元素大小相同。整个缓存为 1024 字节，是整个数组大小的一半。由于缓存是直接映射的，这意味着如果我们将缓存 block 从 0 标记为 63，我们可以放心地假设映射应该如下所示
------------ 内存---------------------------- 缓存
pos[0][0] pos[0][1] -----------> block 0< br/>pos[0][2] pos[0][3] -----------> block 1< br/>pos[0][4] pos[0][5] -----------> block 2< br/>pos[0][14] pos[0][15] --------> block 7
.......
pos[1][0] pos[1][1] -----------> block 8< br/>pos[1][2] pos[1][3] -----------> block 9< br/>.......
pos[7][14] pos[7][15] --------> block 63
pos[8][0] pos[8][1] -----------> block 0< br/>.......
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。缓存是cold的，所以第一列x总是miss，而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 路关联缓存遵循相同的分析，尽管这可能更乏味。为了充分利用缓存系统，请尝试启动一个良好的访问模式，例如 stride-1，并在每次从内存加载期间尽可能多地使用数据。现实世界的 cpu 微架构采用其他智能设计和算法来提高效率。最好的方法总是在现实世界中测量时间，转储核心代码，并进行彻底的分析。