国防科大计算机体系结构公开课_05存储层次

国防科大计算机体系结构公开课学习笔记。

第五章:存储层次。
终于讲到存储惹~这节课也讲得很棒๛ก(ー̀ωー́ก)

2019/5/7 花了整整四天终于啃完了这一章🤪 内容好多

存储器的层次结构

存储层次结构

级别 1 2 3 4
名称 寄存器 缓存 主存储器 磁盘存储
实现技术 具有多个端口的定制存储器、CMOS 片上CMOS SRAM CMOS DRAM 磁盘
管理 编译器 硬件 操作系统 操作系统和用户

Cache 常用 SRAM 来实现,主存常用 DRAM 实现。
Cache 的设计依赖于时空局部性。
两种存储层次:Cache-主存层次 与 主存-辅存层次。

Cache-主存层次 主存-辅存层次
存储管理实现 主要由专用硬件实现 主要由软件实现
CPU 对第二级的访问方式 可直接访问 均通过第一级访问
失效时 CPU 是否切换 不切换 切换到其他进程

存储层次设计面临的四个问题:

  1. 映射规则:当把一个块调入高一级(更靠近 CPU)存储器时,可以放在哪些位置?
  2. 查找算法:当要访问的块在高一层存储器中时,如何找到该块?
  3. 替换算法:发生失效时,应替换哪一块?(侯选位置均被别的块占用)
  4. 写策略:当进行写访问时,应进行哪些操作?

存储层次性能参数:C(平均每位价格),H(命中率),$T_A$(平均访问时间)
假设考虑由 $M_1$ 和 $M_2$ 构成的两级存储层次:
$H = \frac{N_1}{N_1 + N_2}$,失效率 $F = 1 - H$。其中 $N_1, N_2$分别代表访问两个存储器$M_1, M_2$的次数。
$T_A = T_{A1} + (1 - H)T_M = T_{A1} + FT_M$, $T_M = T_{A2} + T_B$。$T_{A1}$表示命中时间,$T_{A2}$是$M_2$的访问时间,$T_M$是失效开销,$T_B$表示把块传送到高一级存储的开销。

Cache 基本知识

映射规则

直接映射、全相联、组相联

规则 特点
全相联 一个块可以放在 Cache 中任一位置 空间利用率最高,冲突概率最低,实现最复杂
直接映射 每一块只能放在 Cache 中唯一位置。对于主存第 i 块,若把它映射到 Cache 第 j 块,j = i mod (M),M 为 Cache 块数。设 $M = 2^m$,则当表示为二进制数时,j 实际上就是 i 的低 m 位。 空间利用率最低,冲突概率最高,实现最简单
组相联 放到组内任意位置。若主存第 i 块映射到第 k 组,那么 k = i mod (G),G 为 Cache 的组数。设 $G = 2^g$,则当表示为二进制数时,k 实际上就是 i 的低 g 位。 n 路组相联指每组中有 n 个块,n = M/G,称为相联度。相联度越高,Cache空间的利用率就越高,块冲突概率就越低,失效率越低

对应关系:

n(路数) G(组数)
全相联 M 1
直接映射 1 M
组相联 1 < n < M 1 < G < M

查找方法

使用目录表来记录 Cache 块调入时存放的位置。
目录表项:| 有效位 | 标识 tag |
访存地址:| tag | index |
并行查找与顺序查找:并行查找需要硬件支持。相联存储器,或,单体多字存储器+比较器。

如何提高查找性能?主侯选位置(MRU 块,Most Recently Used)—> 对于顺序查找来说,把 MRU 块放到最前面,有助于提高查找命中率。

对于 8 个数据块的 cache,其各种映射方式结果如下:

  1. 直接映射访存地址
3 3 2
tag index offset
xxx 000 ·

块数为 $8 = 2^3$,所以低 3 位作为组号。

  1. 2 路组相联访存地址
4 2 2
tag index offset
xxxx 00 ·

组数为 $4 = 2^2$,所以低 2 位作为组号。

  1. 全相联访存地址
6 2
tag offset
xxxxxx 00

替换算法

所要解决的问题:当新调入一块,而该块能占用的 cache 位置已占满时,应当替换哪一块?
思路:替换掉将来最不可能访问的数据块。—> 考虑局部性。

  1. 随机法(实现简单)—> 未考虑局部性
  2. FIFO(实现简单)—> 未考虑局部性
  3. LRU, Least Recently Used(失效率低)
  4. LFU, Least Frequently Used(不常使用)

写策略

写操作必须在确认是否命中后才可进行。
写访问可能导致 cache 和主存内容不一致。
两种写策略:

  1. 写直达法:执行写操作时,不仅写入 cache,而且写入下一级存储器 —> 一致性好;
  2. 写回法:只写入 cache。仅当 cache 中相应的块被替换时,才写回主存(设置“污染位”) —> 速度快,占用存储器频带低。

另:写缓冲器:CPU 写入下一级存储器时,写到写缓冲器即可,由写缓冲器写入下一级存储器。
按写分配(写时取):写失效时,先把所写单元所在的块调入 Cache,再行写入;
不按写分配(绕写法):写失效时,直接写入下一级。
读命中、写命中、读失效、写失效需要再查查
混合 cache 和分离 cache:指令和数据是否存储在一起。混合 cache 会导致结构相关。另:指令的局部性更好。

提高整体访存性能

平均访问时间 = 命中时间 + 失效率 × 失效开销
CPU 执行时间 = (CPU 时钟周期数 + 存储器停顿周期数)x 时钟周期时间

  • 存储器停顿周期数指处理器在等待存储器访问而停顿时的周期数目。此公式假定处理器在发生缓存缺失时停顿。
  • $存储器停顿周期数 = 缺失数 × 缺失代价 = IC × \frac{缺失}{指令} × 缺失代价 = IC × \frac{存储器访问}{指令} × 缺失率 × 缺失代价$
    • “每条指令的缺失数”的好处在于它与硬件实现无关,缺点在于每条指令的缺失数与体系结构相关,因此对于仅使用单一计算机系列的架构,最常使用的是每条指令的缺失数。
    • IC: 指令数
    • $缺失率=\frac{未找到目标的访问数}{总访问数}$,可以使用缓存模拟器测量,原理是取得指令与数据引用的地址跟踪。缺失率是缓存设计中最重要的度量之一。
  • 由于读写的缺失率和缺失代价往往不同:

$存储器停顿周期数 = IC × 每条指令的读取操作 × 读取缺失率 × 读取缺失代价 + IC × 每条指令的写入操作 × 写入缺失率 × 写入缺失代价$
$CPU 时间 = IC × (CPI + \frac{访存次数}{指令数} × 失效率 × 失效开销) × 时钟周期时间$

平均访存时间 = 命中时间 + 失效率 × 失效开销,故可以从三个方面改进Cache的性能

  1. 降低失效率
  2. 减少失效开销
  3. 减少Cache命中时间

需要注意一点:体系结构牵一发而动全身,一定要清楚改变了 A 后,整体会受到什么样的影响。(单纯去降低失效率之类的是不可取的!要从全局视角做 tradeoff)

降低 Cache 失效率

三种失效 (3C)

  1. 强制性失效 (Compulsory miss):当第一次访问一个块时,该块不在 Cache 中,需从下一级存储器中调入 Cache,这就是强制性失效 (冷启动失效,首次访问失效)
  2. 容量失效 (Capacity miss):如果程序执行时所需的块不能全部调入 Cache 中,则当某些块被替换后,若又重新被访问,就会发生失效。这种失效称为容量失效。—> 如何测试系统容量失效是多少?用全相联映射模拟(因为全相联映射中不存在冲突失效)。
  3. 冲突失效 (Conflict miss):在组相联或直接映射 Cache 中,若太多的块映射到同一组(块)中,则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置),然后又被重新访问的情况。这就是发生了冲突失效(碰撞失效,干扰失效)。如何测量呢?

特征:

  1. 相联度越高,冲突失效就越少;
  2. 强制性失效不受 Cache 容量的影响,但容量失效却随着容量的增加而减少;强制性失效和容量失效不受相联度的影响。
  3. 表中的数据符合 2:1 的 Cache 经验规则,即大小为 N 的直接映射 Cache的失效率约等于大小为N/2 的两路组相联Cache的失效率。

减少三种失效的方法

  • 强制性失效:增加块大小;预取(利用 CPU 空闲时间预取)——不过强制性失效本身概率很低,所以要注意不要造成别的开销
  • 容量失效:增加容量——防止出现抖动现象
  • 冲突失效:提高相联度——理想情况:全相联

许多降低失效率的方法会增加命中时间或失效开销。

降低失效率的方法

  1. 增加块大小 —> 会增大失效开销
  2. 提高相联度 —> 是以增加命中时间为代价的
  3. Victim Cache
    在 Cache 和它从下一级存储器调数据的通路之间设置一个全相联的小 Cache,用于存放被替换出去的块(称为 Victim),以备重用。Victim Cache 对于减小冲突失效很有效,特别是对于小容量的直接映射数据 Cache,作用尤其明显。
  4. 伪相联 Cache
    在逻辑上把直接映射 Cache 的空间上下平分为两个区。对于任何一次访问,伪相联 Cache 先按直接映射 Cache 的方式去处理。若命中,则其访问过程与直接映射 Cache 的情况一样;若不命中,则再到另一区相应的位置去查找。若找到,则发生了伪命中(慢命中),否则就只好访问下一级存储器。
    缺点:多种命中时间会使 CPU 流水线的设计复杂化
  5. 硬件预取
    指令和数据都可以预取。预取内容既可放入 Cache,也可放在外缓冲器中。—> 硬件开销
  6. 编译器控制的预取
    由编译器加入预取指令,在数据被用到之前发出预取请求。
    (1) 寄存器预取:把数据取到寄存器中
    (2) Cache 预取: 只将数据取到 Cache 中
    两种工作方法:
    (1) 故障性预取:预取时,若出现虚地址故障或违反访问权限,就会发生异常。
    (2) 非故障性预取:预取时,若出现虚地址故障或违反访问权限,并不会导致异常,只是转变为“不预取”。
    要求使用的是非阻塞 Cache(非锁定 Cache),可以同时接收和处理多个请求(预取数据时,处理器应该能继续执行)
    数组一般是按行位寻址存放 —> 局部性问题。如果按行取用元素,则受益于空间局部性。
    关于编译器控制预取的一个例题:
    对于下面的程序,判断哪些访问可能会导致数据 Cache 失效。然后,加入预取指令以减少失效。最后,计算所执行的预取指令的条数以及通过预取避免的失效次数。假定:
    (1) 我们用的是一个容量为 8KB、块大小为 16B 的直接映象 Cache,它采用写回法并且按写分配;
    (2) a、b 分别为 3×100 (3 行 100 列) 和 101×3 的双精度浮点数组,每个元素都是 8 个字节。当程序开始执行时,这些数据都不在 Cache 内。
    1
    2
    3
    for (i=0 ; i < 3 ; i=i+1 )
    for(j=0 ; j < 100 ; j=j+1 )
    a[i][j]=b[j][0]×b[j+1][0];

解:





优化:

1
2
3
4
5
6
7
8
9
10
for (j=0,j<100;j=j+1) {
prefetch (b[j+7][0]); /*取预7次循 后所需的环b(j,0) */
prefetch (a[0][j+7]); /*取预7次循 后所需的环a(0,j) */
a[0][j]=b[j ][0] * b [j+1][0];
}
for (i=1; i < 3; i=i+1) {
for (j=0; j < 100; j=j+1)
prefetch(a[i][j+7]);/*取预7次循 后所需的环a(i,j) */
a[i][j]=b[j][0] * b[j+1][0];
}

  1. 用编译器技术减少 Cache 失效
    在编译时,对程序中的指令和数据进行重新组织,以降低 Cache 失效率。核心思想:使一块数据被从 Cache 替换出去之前,能最大限度利用其中的数据(访问次数最多)。

常见手段:(我觉得这部分内容对平时写高级语言代码做优化也很有帮助~~~)
(1)数组合并

1
2
3
4
5
6
7
8
9
10
/* 修改前 */
int val [SIZE];
int key [SIZE];

/* 修改后 */
struct merge {
int val ;
int key ;
};
struct merge merged_array[size];

(2)内外循环交换(考虑局部性问题)

1
2
3
4
5
6
7
8
9
/*修改前 */
for (j=0 ;j<100 ;j=j+1)
for (i=0 ;i<5000 ;i=i+1)
x[i][j]=2*x[i][j];

/*修改后 */
for (i=0 ;i<100 ;i=i+1)
for (j=0 ;j<5000 ;j=j+1)
x[i][j]=2*x[i][j];

(3)循环融合(把多个循环融合成一个循环,避免频繁访存)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/*修改前 */
for (i=0 ; i<N ;i=i+1)
for (j=0 ; j<N ; j=j+1)
a[i][j]=1/b[i][j]*c[i][j];
for (i=0 ;i<N ;i=i+1)
for (j=0 ; j<N ;j=j+1)
d[i][j]=a[i][j]+c[i][j];

/*修改后 */
for (i=0 ;i < N ;i=i+1)
for (j=0 ;j < N ;j=j+1){
a[i][j]=1/b[i][j]*c[i][j];
d[i][j]=a[i][j]+c[i][j];
}

(4)分块访问:把对数组的整行或整列访问改为按块进行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*修改前*/
for (i=0; i < N; i=i+1)
for (j=0; j < N; j=j+1) {
r=0;
for (k=0; k < N; k=k+1) {
r=r+y[i][k]*z[k][j];
}
x[i][j]=r;
}
//计算过程失效次数:2N^3+N^2

/*修改后 */
for (jj=0; jj < N; jj=jj+B)
for (kk=0; kk < N; kk=kk+B)
for (i=0; i < N; i=i+1)
for (j=jj; j < min(jj+B-1,N); j=j+1) {
r=0;
for (k=kk; k < min(kk+B-1,N); k=k+1) {
r=r+y[i][k]*z[k][j];
}
x[i][j]=x[i][j]+r;
}
//计算过程失效次数:(N/B)×(N/B)×N×(2B)+N^2 = 2N^3/B+N^2

减少 Cache 失效开销

  1. 写缓冲与写合并
    写直达 Cache 中,因为所有的写请求都必须发送到下级存储层次中,所以经常使用一个写缓冲来降低失效开销。如何提高写缓冲的效率和利用率?写合并。在写回法 Cache 中,也可采用写缓冲器
  2. 使读失效优先于写
    Cache 中的写缓冲器导致对存储器访问的复杂化。
    解决方法(读失效的处理):
    (1)推迟对读失效的处理直到写缓冲排空(缺点:读失效的开销增加)
    (2)检查写缓冲器中的内容:增加硬件
  3. 子块放置技术
    把 Cache 块进一步划分为更小的块(子块),并给每个子块赋予一位有效位,用于指明该子块中的数据是否有效。Cache 与下一级存储器之间以子块为单位传送数据。但标识仍以块为单位。
  4. 请求字处理技术
    请求字:从下一级存储器调入 Cache 的块中,只有一个字是立即需要的。这个字称为请求字。应尽早把请求字发送给 CPU。怎么做?
    (1) 尽早重启动:调块时,从块的起始位置开始读起。一旦请求字到达,就立即发送给 CPU,让 CPU 继续执行。
    (2) 请求字优先:调块时,从请求字所在的位置读起。这样,第一个读出的字便是请求字。将之立即发送给 CPU。
    这种技术在以下情况下效果不大:
    (3) Cache 块较小
    (4) 下一条指令正好访问同一 Cache 块的另一部分。
  5. 非阻塞 Cache
    非阻塞 Cache:Cache 失效时仍允许 CPU 进行其它的命中访问。即允许“失效下命中”。
  6. 第二级 Cache(多级 Cache)
    应把 Cache 做得更快?还是更大?答案:二者兼顾,再增加一级 Cache:第一级 Cache (L1) 小而快,第二级 Cache (L2) 容量大。
    性能分析:
    平均访问时间 = L1 命中时间 + L1 失效率 × L1 失效开销 = L1 命中时间 + L1 失效率 × (L2 命中时间 + L2 失效率 × L2 失效开销)
    局部失效率与全局失效率:
    局部失效率 = 该级 Cache 的失效次数/到达该级 Cache 的访问次数
    全局失效率 = L1 失效率 × L2 失效率
    评价多级 Cache 时,应使用全局失效率这个指标。
    第二级 Cache 不会影响 CPU 的时钟频率,因此其设计有更大的考虑空间。
    设计时两个需要权衡的问题:
    (1) 能否降低 CPI 中的平均访存时间部分?
    (2) 成本是多少?(节约成本)
    L2 Cache 参数选择:
    (1) 容量
    第二级 Cache 的容量一般比第一级的大许多,如 512KB。
    (2) 相联度
    第二级 Cache 可采用较高的相联度或伪相联方法。
    (3)大小块
    为减少平均访存时间,可以让 L1 Cache 采用较小的块,而 L2 Cache 采用较大的块。

减少命中时间

命中时间直接影响到处理器的时钟频率。在当今的许多计算机中,往往是 Cache 的访问时间限制了处理器的时钟频率。

  1. 容量小且结构简单的 Cache
    可以将 CPU 与 Cache 集成在同一个芯片内,这样片内访存会更快。
  2. 虚拟 Cache
    访问 Cache 的索引或 Cache 中的标识 (tag)。存在的问题:
    (1)虚拟 Cache 的清空问题。不同程序的虚拟 Cache 都是重叠的,上一程序用完后若未清空虚拟 Cache,下一个程序在调用的时候就可能会出现问题。解决办法:在地址标识中增加 PID 字段。
    (2)同义/别名问题:多个虚拟地址对应同一个物理地址。解决办法:反别名法、页着色。
    另:虚拟索引+物理标识:利用虚拟地址找到索引读 cache,同时进行虚实地址转换。前提:虚拟索引 = 物理索引。优点:兼得虚拟 cache 和物理 cache 的好处。缺点:要保证索引在页里面,cache 容量受限,<= 页大小 × 相联度。
  3. 流水化写
    写操作一定要判断标识命中后方可写 —> 设置一个写 buffer。

总结


主存

主存的主要性能指标:延迟和带宽。
以往 Cache 主要关心延迟(失效开销),I/O 主要关心带宽,现在 Cache 也关心两者。

增加带宽

  1. 增加存储器的宽度

    缺点:CPU 一次只需要访问一个块,所以在存储器和 CPU 之间需要使用一个多路选择器过滤,这样会影响时钟周期;
  2. 多体交叉存储器

    存储系统中采用多个 DRAM,利用它们潜在的并行性。
    多体交叉存储器内部地址是怎么分配、怎么寻址的呢?
    在多体交叉存储器中,每个存储单元的地址是以体地址和体内地址来确定的。
    分两种:低位交叉编址和高位交叉编址。
    低位交叉编址:

    相邻地址数据分布在不同体中,从而可以并行工作。
    高位交叉编址:

    相邻地址往往在同一个体中,并行性不能得到很好的挖掘。
    对低位交叉编址,如何充分挖掘并行性?
    (1)同时启动

    几个体同时读偏移地址,不过输出时要传四次。
    (2)分时启动

    可以流水处理。
    另:独立存储体。设置多个存储控制器,使多个体能独立操作,以便能同时进行多个独立的访存。—> 要求每个体有独立的地址线,非阻塞 Cache。

存储芯片技术

DRAM 芯片优化技术:芯片内部优化技术是提高主存系统性能的一个重要方面。

  • 快页模式:内部缓冲一行的数据以便进行列访问。
  • SDRAM:Synchronous DRAM —— DRAM接口增加一个时钟信号,可使 DRAM 能针对一个请求连续同步地传输多个数据而不需同步开销。
  • DDR(double data rate):在DRAM时钟的上沿和下沿都进行数据传输,可把数据传输率提高一倍(以前只在单沿传输)。

存储器优化技术都是通过增加少量逻辑来开发 DRAM 内部潜在的高带宽,这种优化代价很小,却能使带宽显著提高。

虚拟存储器

虚存管理方式

分两类:页式和段式。

  • 页式虚存把空间划分为大小相同的块,称为页面。常用页大小为 4KB~64KB。
  • 段式虚存把空间划分为可变长的块,称为段。
  • 页面是对空间的机械划分,而段则往往是按程序的逻辑意义进行划分。
  • 另:段页式

有关虚拟存储器的四个问题

  1. 映象规则
    全相联。以降低失效率为主要目标。
  2. 查找算法
    页表,段表,TLB。
  • 页表和段表:索引页号或段号的数据结构,含有所要查找的块的物理地址。
    • 段式系统:段内位移加上段的物理地址就是最终的物理地址。
    • 页式系统:只需简单地将页内位移拼接在相应页面的物理地址之后。
  • TLB(Table Look-aside buffer)是一个专用的高速缓冲器,用于存放近期经常使用的页表项
  1. 替换算法
    LRU。尽可能减少页故障,OS 为每个页面设置“使用位”。
  2. 写策略
    写回法

进程保护

  1. 界地址寄存器
    基地址、上界地址
    检测条件:(基地址+地址)< 上界地址
  2. 虚拟存储器
    给每个页面增加访问权限标志
  3. 环形保护
  4. 加锁和解锁

实例

Alpha 机器中虚地址变换过程:

L1 L2 L3 存储的都是下一级存储的索引。