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

2018-06-12 17:20:58

在计算以下两段代码的命中率和缺失率时遇到一些困难。

给定信息：我们有一个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数组是行优先顺序），函数2应该更好。但我不明白如何计算命中/失败百分比。显然function1（）错过了50％的时间，而function2（）错过了25％的时间。

有人可以通过这些计算如何工作吗？我可以真正看到的是，一次不会有一半以上的网格适合高速缓存。此外，这个概念是否容易扩展到k路联合缓存？

谢谢。

数据如何存储在内存中
每个结构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标记，我们可以安全地假定映射应该看起来像这样
------------内存----------------------------缓存
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路联合缓存遵循相同的分析，尽管这可能更乏味。为了充分利用缓存系统，尝试启动一个很好的访问模式，比如说stride-1 ，并且在每次从内存加载期间尽可能使用数据。真实世界的CPU微架构采用其他智能设计和算法来提高效率。最好的方法是始终测量现实世界中的时间，转储核心代码并进行彻底分析。

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

你的结构是8字节长（2×4）。由于你的缓存块是16个字节，所以一个内存访问grid[i][j]将获取恰好两个结构入口（ grid[i][j]和grid[i][j+1] ）。因此，如果循环遍历第二个索引，则每四次访问都会导致读取内存。如果循环遍历第一个索引，则可能会丢弃已获取的第二个条目，这取决于内部循环中的提取数量与总体缓存大小。

现在我们还必须考虑缓存大小：你说你有64条直接映射的行。在函数1中，内部循环是16次提取。这意味着，第17次获取到网格[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问题的普遍答案：“这取决于”。

链接地址: http://www.djcxy.com/p/36355.html

上一篇: C cache optimization for direct mapped cache

下一篇: How many bytes does a Xeon bring into the cache per memory access?