直接映射缓存的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-way关联缓存吗？

谢谢。

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]

与data相比，缓存组织

对于缓存，每个块为16字节，其大小与数组的两个元素大小相同。整个缓存为1024字节，是整个数组大小的一半。由于缓存是直接映射的，这意味着如果我们将缓存块标记为从0到63，我们可以安全地假设映射应该如下所示

-缓存

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!).So on，因此错失率为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微体系结构采用了其他智能设计和算法来提高效率。最好的方法总是测量真实世界中的时间，转储核心代码，并进行彻底的分析。

Answer 2

好吧，我的计算机科学讲座有点遥远，但我想我已经弄明白了(实际上这是一个非常简单的例子)。

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

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

好吧，如果我的推理是正确的，那么给你的答案应该是错误的。这两个函数都应该以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;

这可以被计为一次存储器访问。因此，我提出了所有CS问题的通用答案：“视情况而定。”