这次回顾深入理解计算机系统第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的来读数据,从而使得你程序中的空间局部性最大。
  • 一旦从存储器中读入了一个数据对象,就尽可能多地使用它,从而使得程序中的时间局部性最大。