这次回顾深入理解计算机系统第6章 ，这一章介绍了存储器层次结构。

电子书地址：

http://eol.bnuz.edu.cn/meol/common/script/preview/download_preview.jsp?fileid=2169600&resid=242120&lid=28605

备注：图片和总结内容均来自于电子书。

第6章：存储器层次结构

重要概念提要

  • 局部性：
    • 时间局部性；
    • 空间局部性；
    • 指令局部性；
  • 缓存不命中（读）：
    • 强制性不命中（冷不命中）；
    • 冲突不命中；
    • 容量不命中；
  • 缓存不命中（写）：
    • 直写；
    • 写回；
    • 写分配；
    • 非写分配；
  • 高速缓存：
    • 直接映射高速缓存；
    • $E$路组相连高速缓存；
    • 全相连高速缓存；
  • 冲突不命中相关概念：
    • 抖动；
    • 选择中间位做索引的原因；

6.1 存储技术

略过。

6.2 局部性

基本概念

  • 编写良好的计算机程序具有良好的局部性（locality）：
    • 计算机程序倾向于引用临近于其他最近引用过的数据项；
    • 或者最近引用过的数据项本身；
  • 这种倾向性称为局部性原理。
  • 有良好局部性的程序比局部性差的程序运行的更快。

两种不同的局部性

  • 时间局部性
    • 被引用过一次的内存位置可能在不远的将来再被引用；
  • 空间局部性
    • 被引用过一次的内存位置的附近可能在不远的将来再被引用；

局部性的例子

  • 硬件层
    • 引入高速缓存存储器来保存最近被引用的指令和数据项；
  • 操作系统
    • 使用主存作为虚拟地址空间来作为最近被引用块的高速缓存块；
  • web浏览器
    • 将最近被引用的文档放在本地磁盘；

数据局部性

例1

int sumvec(int v[N]) 
{  	
    int i, sum = 0; 

    for (i = 0; i < N; i++)
	sum += v[i];
    return sum;	
}

分析：

  • 由于sum每次循环都会被引用，所以有好的时间局部性；
  • 由于sum是标量，所以没有空间局部性；
  • v有很好的空间局部性；

小结：

  • 对于数组，每隔$k$个元素进行访问，就称为步长为$k$的引用模式；
    • 空间局部性随着$k$增大而降低；
  • 步长为$1$的引用模式为顺序引用模式，例如此处的数组v；

例2

代码1：

int sumarrayrows(int a[M][N]) 
{  	
    int i, j, sum = 0;

    for (i = 0; i < M; i++) 
	for (j = 0; j < N; j++)
	    sum += a[i][j];
    return sum;	
}

该程序空间局部性较好，因为引用模式的步长为$1$。

代码2：

int sumarraycols(int a[M][N]) 
{  	
    int i, j, sum = 0;

    for (j = 0; j < N; j++)
	for (i = 0; i < M; i++) 
	    sum += a[i][j];
    return sum;	
}

该程序时间局部性较差，因为引用模式的步长为$N$。

指令局部性

由于指令存放在内存中，所以也可以评价程序关于取指的局部性，考虑之前的例1：

  • for中循环体是按顺序执行的，所以循环指令有和好的空间局部性；
  • 循环体会被执行多次，所以有很好的时间局部性；

小结

评价局部性的简单原则：

  • 重复引用相同变量的程序有良好的时间局部性。
  • 对于具有步长为$k$的引用模式的程序，步长越小，空间局部性越好。具有步长为$1$的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局部性会很差。
  • 对于取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多，局部性越好。

6.3 存储器层次结构

不同存储技术的访问时间差异很大。速度较快的技术每字节的成本要比速度较慢的技术高，而且容量较小。为了能够用较低的价格得到更好的存储性能，有人提出了存储器层次结构，整体如下：

中心思想是，对于每个$k$，位于$k$层的更快更小的存储设备作为位于$k+1$层的更大更慢的存储设备的缓存。

存储器层次结构中的缓存

以第$k$层和第$k+1$层为例：

  • 第$k,k+1$层的存储器被划分成连续的数据对象组块（chunk），称为块（block），每块都有唯一的地址或名字，第$ k+1$层的块数更多；
  • 任何时刻，第$k$层的缓存包含第$k+1$层的子集副本；
    • 例如上图中第$k$层包含$4,9,14,3$；
  • 数据总是以块大小为传送单元在第$k$层和第$k+1$层之间来回复制；
    • 对于不同的$k$，传送单元大小不同，一般来说，$k$越大，传送单元越大；

缓存命中和不命中

假设要从第$k$层读取$d$，那么会有如下两种情况：

  • 缓存命中
    • 如果第$k$层中包含数据$d$，那么就称为缓存命中；
  • 缓存不命中
    • 如果第$k$层中没有缓存数据$d$，那么就称为缓存不命中；此时会从第$k+1$层取出包含$d$的块，然后缓存到第$k$层中；
    • 如果第$k$层的缓存已满，那么会覆盖现存的某个块，这称为替换或驱逐，被驱逐的块称为牺牲块，该块由替换策略来控制。

缓存不命中的种类：

  • 强制性不命中（冷不命中）：
    • 第$k$层的缓存是空的（此时所有对数据的访问都会不命中），空缓存也被称为冷缓存；
    • 通常是短暂的；
  • 冲突不命中：
    • 产生不命中后需要执行某个放置策略来确定第$k+1$层中取出的块放在哪，这种情形产生的不命中称为冲突不命中；
  • 容量不命中：
    • 程序每个阶段访问的缓存块的相对稳定集合，称为这个阶段的工作集，当工作集的大小超过缓存的大小时，缓存会经历容量不命中；

6.4 高速缓存存储器

这部分假设CPU和主存之间只有一个L1高速缓存，忽略L2，L3高速缓存。

通用的高速缓存存储器组织结构

考虑满足如下条件的计算机系统：

  • 每个存储器地址有$m$位，形成$M=2^m$个不同地址；

该机器的高速缓存块信息如下：

  • 有$S=2^s$个高速缓存组；
  • 每个组包含$E$个高速缓存行；
  • 每个行由$B=2^b$字节的数据块组成；
    • 有一个有效位指明该行是否包含有意义的信息；
    • 有$t=m-(b+s)$个标记位唯一标识行；
  • 高速缓存结构用$(S,E,B,m)$描述；
  • 高速缓存的容量大小定义为$C=S\times E\times B$；

图示：

上图为高速缓存$(S,E,B,m)$的通用组织：

  • (a) 高速缓存是一个高速缓存组的数据；每组包含一行或多行，每行包含一个有效位，一些标记位和一个数据块；
  • (b) 高速缓存的结构将$m$个地址位划分成了$t$个标记位，$s$个组索引和$b$个块偏移位；

参数总结：

基本参数：

参数 描述
$S=2^s$ 组数
$E$ 每个组的行数
$B=2^b$ 块大小（字节）
$m=\log_2 M$ （主存）物理地址位数

衍生参数：

参数 描述
$M=2^m$ 内存地址的最大数量
$s=\log_2 (S)$ 组索引位数量
$b=\log_2(B)$ 块偏移位数量
$t=m-(s+b)$ 标记位数量
$C=B\times E\times S$ 不包括像有效位和标记位这样开销的高速缓存大小（字节）

高速缓存的作用方式

当一条加载指令指示CPU从主存地址$A$中读一个字时，它将$A$的地址发送到高速缓存，然后进行如下操作：

  • 解析$A$的标记，组索引，块偏移；
  • （组选择）通过组索引定位到对应的组；
  • （行匹配）通过标记位判断组中的哪一行包含$A$处的字；
    • 如果存在这样的行且设置了有效位（字抽取），则说明高速缓存中缓存了$A$的字；
      • 块偏移给出了$B$个字节的数据块中的起始字偏移；
    • 否则说明高速缓存中没有缓存$A$的字；

几种不同的高速缓存

根据高速缓存行数$E$，高速缓存可以分为三类：

  • $E=1$：直接映射高速缓存；
    • 每组只有一行；
  • $1<E<C/B$：$E$路组相连高速缓存；
  • $E=C/B$：全相连高速缓存；
    • 只有一个组，包含所有的行；

后续会分别介绍这三种情形，从如下基本步骤介绍：

  • 组选择；
  • 行匹配和字选择；
  • 缓存不命中时的行替换规则；

直接映射高速缓存

此时$E=1$，表示每组只有$1$行：

组选择：

行匹配和字选择：

说明：

  • 这里行数为$1$，不需要选择；
  • $w_0$表示低位。

缓存不命中时的行替换规则：

  • 由于行数为$1$，所以如果不命中时替换当前行即可；
例子

考虑计算向量点积的函数：

float dotprod(float x[8], float y[8])
{
	float sum = 0.0;
    int i;
    
    for (i = 0; i < 8; i++)
        sum += x[i] * y[i];
   	return sum;
}

对于$x,y$来说，该函数有良好的空间局部性，所以理论上命中率较高，但实际上并非如此，原因如下：

假设浮点数是$4$个字节，数组$x$被加载到地址$0$，数组$y$被加载到地址$32$，sum存放在CPU寄存器中（不需要内存引用），假设$x[i],y[i]$的高速缓存映射关系如下：

循环过程中的缓存情况如下：

  • 引用$x[0]$，缓存不命中，加载$x[0]\sim x[3]$；
  • 引用$y[0]$，缓存不命中，加载$y[0]\sim y[3]$；
  • …

每次引用均会导致冲突不命中，这种现象称为抖动，解决方法在数组的结尾放一些填充位，对于此例可以定义：

float x[12]

那么$x[i],y[i]$的高速缓存映射关系如下：

选择中间位做索引的原因

选择中间位做索引的原因：高位做索引会使得一些连续的内存块映射到相同的高速缓存块。

图示：

$E$路组相连高速缓存

此时$1<E<C/B$。

组选择：

行匹配和字选择：

缓存不命中时的行替换规则：

  • 最不常使用（LFU）
  • 最近最少使用（LRU）

全相连高速缓存

此时$E=C/B$，只有一个组，包含所有的行：

组选择：

注意此时没有组索引位。

行匹配和字选择：

说明：

  • 因为高速缓存电路必须并行地搜索许多相匹配的标记，构造一个又大又快的相联高速缓存很困难，而且很昂贵。
  • 因此，全相联高速缓存只适合做小的高速缓存，例如虚拟内存系统中的翻译备用缓冲器(TLB)。

有关写的问题

假设要写一个已经缓存了的字$w$，在高速缓存更新了它的副本后，如何在低一层的高速缓存中更新，有如下几种方式：

  • 直写：立即将$w$的高速缓存块写回到低一层中；
  • 写回：尽可能地推迟更新，只有当替换算法要驱逐当前层的缓存块之，才更新低一层；
    • 写回能减少总线流量；
    • 但是增加了复杂性，需要增加额外的修改位表明是否被修改过；

处理写不命中的方法：

  • 写分配：加载相应低一层中的块到高速缓存中，然后更新当前高速缓存块；
    • 写回中通常使用；
  • 非写分配：避开高速缓存，直接把这个字写到低一层中；
    • 直写中通常使用；

课本建议：

  • 使用写回和写分配的高速缓存模型。

高速缓存参数的性能指标

常见指标：

  • 不命中率：不命中数量/引用数量；
  • 命中率：1-不命中率；
  • 命中时间：高速缓存传送一个字到CPU所需的时间，包括组选择，行确认和字选择的时间；
  • 不命中处罚：由不命中所引起的额外时间；

其他度量：

  • 高速缓存的大小；
  • 块大小；
  • 相连度（$E$）；
  • 写策略；

6.5~6.7 小结

编写高效代码的技巧：

  • 将注意力集中在内循环上，大部分计算和内存访问都发生在这里。
  • 通过按照数据对象存储在内存中的顺序、以步长为1的来读数据，从而使得你程序中的空间局部性最大。
  • 一旦从存储器中读入了一个数据对象，就尽可能多地使用它，从而使得程序中的时间局部性最大。