CPU缓存命中优化之循环交换

概述

这是一道来自《多处理器编程的艺术》(TAOMP)的题目:习题222:

考虑一个具有16个缓存块的直接映射高速缓存,索引为0~15,每个缓存块包含32个字。考虑一个32x32的二维字数组a。该数组在内存中被排列为a[0,0]的下一个元素时a[0,1],以此类推。假设该高速缓存初始为空,但a[0,0]被映射到0号缓存块的第一个字。(注意字与字节的不同之处)

考虑下面的列优先遍历:

1
2
3
4
5
6
int sum = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < 32; j++) {
sum += a[i,j]; // 2nd dim changes fastest
}
}

以及下面的行优先遍历:

1
2
3
4
5
6
int sum = 0;
for (int i = 0; i < 32; i++) {
for (int j = 0; j < 32; j++) {
sum += a[j,i]; // 1st dim changes fastest
}
}

比较两次遍历的缓存缺失个数,假设最早的缓存块被最优先替换。

分析

  • 结果等价:首先这两段代码的实现上有不同,但最后的结果是等价的。
  • 实现不等价:但是实现上却不等价,容易想到二者的缓存缺失率不一样。
  • 原因:题目的描述”该数组在内存中被排列为a[0,0]的下一个元素时a[0,1],以此类推”说明了,在内存中数据是按照列优先存储的。按照一般的缓存抓取原则,一般会把当前所使用的数据附近的数据一并抓入。所以,问题就来了:第二段代码被抓取的整个数据块几乎都是同行不同列的数据,当缓存失效时,会造成大量的缓存缺失。定量分析看,第一段的缓存缺失会小于第二段。
  • 定性计算,假设使用LRU置换策略:(我不太会算,请大神指出错误,计组没学好)
    • 因为每个block包含有32个字,所以列优先存储的数组的一行附近连续的部分都会被抓取到缓存块中。这么看在第一次处理数组内层循环时没有缺失,也就是第一块除a[0,0]外完全命中。以此类推,缓存共有32次缺失。a[0,0]~a[31,0]共32个。
    • 第二段程序不同在于缓存仍然抓取了按照列优先存储的一整行,但是缓存从内存中抓取的整个数据块几乎都是同行不同列的数据,而这些数据在接下来的内循环中完全无法被重复利用(来自wiki),所以缺失是 32 * 32 = 1024 个。(如果说缓存不是16个块而是32个块就不一样了,二者的缺失数是一致的)

解决方法

循环顺序交换,首先要知道,c/c++语言是按照行优先存储数组数据的;而fortran正相反是列优先。当使用行优先存储时,列优先遍历会快一些,反之亦然。所以如果遇到这个问题需要合理的进行循环顺序交换。对于不同语言交换方式不同,c/c++与fortran正好相反。总的来说,这是个不难解决的问题。(END)