课程主页：http://www.cs.cmu.edu/afs/cs/academic/class/15213-f15/www/schedule.html

课程资料：https://github.com/EugeneLiu/translationCSAPP

课程视频：https://www.bilibili.com/video/av31289365/

这一讲介绍了高速缓存存储器。

高速缓存存储器的组织和操作

高速缓存存储器

  • 高速缓存存储器是小型，基于SRAM的快速存储器，可在硬件中自动管理

    • 保留经常访问的主内存块

  • CPU首先在缓存中查找数据

  • 典型系统结构：

高速缓存$(S,E,B)$的通用组织

高速缓存读取

利用上图的结构进行高速缓存读取，索引组判断属于哪个组，块偏移确定了$B$个字节的数据块中的字偏移，标记位确定标记。

例子

考虑$E=2$的情形：

首先通过$0…01$确定是第二个缓存，然后比较tag：

最后$100$确定偏移：

再来看一个具体例子：

如果读取的缓存中没有内容或者有效位为0，则记为miss，否则为hit。

写

  • 存在多个数据副本：
    • L1，L2，L3，主存，磁盘
  • write-hit怎么办？
    • Write-through（立即写入内存）
    • Write-back（将写操作推迟到内存中，直到替换行为止）
      • 需要一个dirty bit（行是否与内存不同）
  • 发生写缺失该怎么办？
    • write-miss（加载到缓存中，更新行在缓存中）
      • 如果有更多写入该位置的信息，则很好
    • No-write-allocate（直接写入内存，不加载到缓存中）
  • 典型
    • Write-through + No-write-allocate
    • Write-back + Write-allocate

高速缓存性能指标

  • 不命中率
    • 在缓存中找不到的内存引用的比例（丢失/访问）$\text{= 1 – hit rate}$
    • 典型数字（百分比）：
      • L1为3-10％
      • 对于L2来说可能很小（例如<1％），具体取决于大小等。
  • 命中时间
    • 从高速缓存传送一个字到CPU所需时间
      • 包括确定行是否在缓存中的时间
    • 典型数字：
      • L1需要4个时钟周期
      • L2需要10个时钟周期
  • 不命中处罚
    • 因为错过而需要额外的时间
    • 主存通常需要50-200个周期（趋势：正在增加！）
例子

比较99%命中率和97%命中率的平均读取时间：

  • 97%：$1+0.03\times 100=4$
  • 99%：$1+0.01\times 100=2$

这说明99%的命中率比97%命中率好两倍，所以我们关注不命中率。

编写高速缓存友好的代码

  • 使最常见的情形快速运行
    • 专注于核心功能的内循环
  • 最小化内部循环中的不命中数量
    • 重复引用变量是好的（时间局部性）
    • 步长为$1$的引用模式很好（空间局部性）

缓存的性能影响

存储器山

  • 读吞吐量（读带宽）
    • 每秒从内存读取的字节数（MB / s）
  • 存储器山：测量读吞吐量与空间和时间局部性的关系
    • 表示储器系统性能的紧凑方法。

存储器山测试函数
long data[MAXELEMS];  /* Global array to traverse */

/* test - Iterate over first "elems" elements of
 *        array “data” with stride of "stride", using 
 *        using 4x4 loop unrolling.                                                            
 */ 
int test(int elems, int stride) {
    long i, sx2=stride*2, sx3=stride*3, sx4=stride*4;
    long acc0 = 0, acc1 = 0, acc2 = 0, acc3 = 0;
    long length = elems, limit = length - sx4;

    /* Combine 4 elements at a time */
    for (i = 0; i < limit; i += sx4) {
        acc0 = acc0 + data[i];
        acc1 = acc1 + data[i+stride];
        acc2 = acc2 + data[i+sx2];
        acc3 = acc3 + data[i+sx3];
    }

    /* Finish any remaining elements */
    for (; i < length; i++) {
        acc0 = acc0 + data[i];
    }
    return ((acc0 + acc1) + (acc2 + acc3));
}

重新排列循环以改善空间局部性

矩阵乘法
/* 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;
  }
}

注意按这个方法写效率较低，从内存布局即可看出：

更换循环次序，一共可以得到6种循环，效率如下：

这里解释下为什么kij的效率较高，首先看代码：

/* 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];   
  }
}

接着看示意图：

说明该代码的空间局部性较好。

使用分块以改善时间局部性

高速缓存未命中的分析
  • 假设：
    • 矩阵元素是双精度
    • 高速缓存块 = 8 doubles
    • 缓存大小$C << n$（比$n$小得多）
  • 第一次迭代：
    • $n / 8 + n = 9n / 8$次未命中
  • 总未命中次数：
    • $9n / 8 n^2 =(9/8) n^3$

分块矩阵乘法
c = (double *) calloc(sizeof(double), n*n);

/* Multiply n x n matrices a and b  */
void mmm(double *a, double *b, double *c, int n) {
    int i, j, k;
    for (i = 0; i < n; i+=B)
		for (j = 0; j < n; j+=B)
             for (k = 0; k < n; k+=B)
		 /* B x B mini matrix multiplications */
                  for (i1 = i; i1 < i+B; i++)
                      for (j1 = j; j1 < j+B; j++)
                          for (k1 = k; k1 < k+B; k++)
	                      	c[i1*n+j1] += a[i1*n + k1]*b[k1*n + j1];
}

图示如下：

未命中的分析
  • 假设：
    • 高速缓存块 = 8 doubles
    • 缓存大小$C << n$（比$n$小得多）
    • 三个分块可以放入缓存，$3B^2<C$
  • 第一次（块）迭代：
    • 每个方块$B\times B/ 8=B^2/8$次未命中
    • 总共：$2n / B * B^2 / 8$ = $nB/4$（忽略矩阵c）
  • 总共未命中：
    • $nB/4 * (n/B)^2 = n^3/(4B)$

在缓存中的示意图：

分块总结

  • 无分块：$(9 / 8)^{*} n^{3}$
  • 分块：$1 /(4 B)^{*} n^{3}$
  • 建议选择最大的$B$，使得$3B^2<C$
  • 产生巨大差异的原因：
    • 矩阵乘法具有固有的时间局部性：
      • 输入数据：$3n^2$，计算$2n^3$
      • 每个数组元素使用$O(n)$次！
    • 但是程序必须正确编写

总结

  • 缓存可能会对性能产生重大影响
  • 您可以编写程序来利用它！
    • 着眼于内部循环，其中发生大量的计算和内存访问。
    • 尝试通过依次跨步读取数据对象来最大化空间局部性。
    • 从内存中读取数据对象后，请尽可能多地使用它，以尽量提高时间局部性。