直接映射缓存的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]

缓存组织与数据
进行比较对于缓存,每个块是16字节,这与数组的两个元素的大小相同.整个缓存是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]访问已经逐出前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-way关联缓存遵循相同的分析,尽管这可能更乏味.为了充分利用缓存系统,尝试启动一个很好的访问模式,比如说stride-1,并在每次从内存加载时尽可能多地使用数据.真实世界的cpu微体系结构采用其他智能设计和算法来提高效率.最好的方法是始终测量现实世界中的时间,转储核心代码,并进行全面分析.