编写高速缓冲友好的代码

发表于 更新于

做一点总结

高速缓存运行机制简单介绍

一种层次存储结构，利用时间，空间局部性：

  1. 高速缓存通过 -直接映射高速缓存，-组相联高速缓存，-全相联高速缓存 三种方式在缓存中进行查找。

  2. 如果命中（hit）进行读或写包括write though，write back等方式进行后续处理。

  3. 若没命中（cache miss）有两种可能：冷不命中时执行放置策略，但是放置策略可能引起冲突不命中（即有空位但却不使用），不是空缓存的话会执行替换策略（有LRU，LFU，随机等方法）。同时有write allocate，not write allocate等方式进行后续处理。

  4. 评价高速缓存性能有命中率，不命中率，命中时间，不命中惩罚。

  5. 影响高速缓存性能的有 块的大小，相联度，写策略缓存大小等。

基本方法

  1. 关注核心函数的循环
  2. 在每个循环最内部的缓存不命中数量最小
  3. 对局部变量反复引用
  4. 以步长为1读取数据（因为所有层次上缓存都将数据存储为连续的块，空间局部性）

下面是一个计算矩阵乘积的函数的不同循环顺序（步长）简单对比，假设缓存块大小为32KB，n很大，数组类型为double：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// ijk版本
for(i=0; i<n; i++){
    for(j=0; j<n; j++){
        sum = 0.0;
        for(k=0; k<n; k++)
            sum += A[i][k] * B[k][j];
        C[i][j] += sum;
    }
}

// jki版本
for(j=0; j<n; j++){
    for(k=0; k<n; k++){
        r = B[k][j];
        for(i=0; i<n; i++)
            C[i][j] += A[i][k] * r;
    }
}

// kij版本
for(k=0; k<n; k++){
    for(i=0; i<n; i++){
        r = A[i][k];
        for(j=0; j<n; j++)
            C[i][j] += r * B[k][j];
    }
}
每次迭代 A不命中次数 B不命中次数 C不命中次数 总不命中次数
ijk 0.25 1 0 1.25
jki 1 0 1 2
kij 0 0.25 0.25 0.5

因为double长度是8个字节，所以每次加载4双字到高速缓存块中。然后可以看出kij的每次迭代不命中次数是最小的。