体系结构复习-Part 2-Cache + 指令级并行
体系结构复习-Part 2-Cache + 指令级并行
注：本文中图片截自清华大学汪东升教授体系结构Cache基础部分
1. Cache与存储
1.1 CPU & Memory Gap
Little’s Law
N = λ × T N = \lambda \times T N=λ×T
λ：顾客到达速率（每个单位时间来λ个顾客）T：每个顾客停留时间（每个顾客停留时间T）N：在稳定状态下，商场保持人数为N
假设：每次访存将带来100个时钟延迟、平均每条指令将访存1.2次
分析：
顾客到达速率 => 指令平均访存次数 => λ = 1.2
每个顾客停留时间 => 访存带来的时延 => T = 100
所以，在稳定状态下，系统中正在执行的访存指令有
N
=
λ
×
T
=
1.2
×
100
=
120
N = \lambda \times T = 1.2 \times 100 = 120
N=λ×T=1.2×100=120
1.2 Cache结构
Cache设计的核心思想是局部性，依据拇指法则：
Programs spend 90% of their execution time in only 10% of code
1.2.1 局部性（Locality）
-
时间局部性（Temporal Locality）
-
程序体现
在循环结构的程序中，我们会访问大量相同的指令
-
数据体现
下述程序
int sum = 0; for(int i = 0; i < MAX; i++){ sum += i; }可以看到，在循环体中，数据变量
sum一直被访问
-
-
空间局部性（Spatial Locality）
-
程序体现
当我们执行一个程序的时候，有很大机率是顺序执行，也就是说，我们访问指令i时，很可能会继续访问指令i+1
-
数据体现
例如访问数组，如下：
int a[3]; for(int i = 0; i < 3; i++){ a[i] = func(i); }可见，在循环体中，我们顺序访问了数组
a的空间
-
1.2.2 Cache需要解决的4个关键问题
-
Cache中Block如何布局？（Where can a block be placed in the upper level？）
全相联、组相联、直接相连
-
Cache是如何映射寻找Block？（How is a block found if it is in the upper level？）
不同相联方式寻找不同，以组相联为例：
Tag Array + Data Array
Tag和Data分开的好处在于可以实现并行查找（高功耗、4阶段）：
当然，也可以串行查找，先比对Tag，发现命中再访问Data（低功耗、5阶段）：
-
Cache的Block替换策略？（Which block should be replaced on a miss？）
LRU（Least Recently Used）、Random、LFU（Least Frequency Used）
-
Cache写策略？（What happens on a write？）
-
Write Thru / Whrite Back
Write Thru直接写回Memory，这样可能会慢，为了解决这一问题，引入Write Buffer，Write Buffer一定要快，否则引入可能会带来负面效果
-
Write Allocate / No-Write Allocate
通常来讲，Write Back与Write Allocate结合使用；Write Thru与No-Write Allocate结合使用
-
1.2.3 Cache缺失类型
-
强制缺失（Compulsory）
第一次访问一个块时，该块不在Cache中，需要从下一级存储器中调入Cache，又被称为首次访问不命中
-
容量缺失（Capacity）
程序执行所需的数据块不能全部装入Cache，导致访问缺失，这是因为Cache大小有限
-
冲突缺失（Conflict）
组相联，同一组不断被替换，导致访问缺失；
-
Coherence？？
针对3C问题提出的三种策略：
-
增大Cache大小
- 减小容量缺失
- 增大访问时间（Hit Time）
-
增大组相联度
- 组相联度越高，缺失率越低
- 黄金准则：
- 8路组相联的效率与全相联差不多
- 2：1原则：大小为N的直接映射Cache与大小为N / 2的两路组相联Cache缺失率差不多
- CPU时间是检验Cache性能的唯一准则
- 减少冲突缺失
- 可能增大访问时间（Hit Time）
-
增大Cache Block
- 减少强制缺失
- 增大总线与内存负载开销
- 增大缺失代价（Miss Penalty，因为Block太大了）与冲突缺失（在Cache大小一定的情况下，块数减少，冲突率增大）
1.3 Cache性能（Cache Performance）
核心：
Average Memory Access Time (AMAT) =
HitTime+MissRate*MissPenalty本节主要对
HitTime、MissRate以及MissPenalty进行讨论，从而优化Cache性能
1.3.1 AMAT
推导过程如下：
A
M
A
T
=
H
i
t
R
a
t
e
×
H
i
t
T
i
m
e
+
M
i
s
s
R
a
t
e
∗
(
H
i
t
T
i
m
e
+
M
i
s
s
P
e
n
a
l
t
y
)
=
H
i
t
T
i
m
e
+
M
i
s
s
R
a
t
e
∗
M
i
s
s
P
e
n
a
l
t
y
AMAT = HitRate \times HitTime + MissRate * (HitTime + MissPenalty) = HitTime + MissRate * MissPenalty
AMAT=HitRate×HitTime+MissRate∗(HitTime+MissPenalty)=HitTime+MissRate∗MissPenalty
1.3.2 降低Miss Rate
-
增大Cache Block大小
-
增大Cache大小
-
增大组相联度
-
伪相联Cache
逻辑上分组，采取Way预测方法，未命中（pseudo-hit）则最简单的方法为将MSB取反，再未命中则访存。伪相联Cahe将直接映射的快速访问与2路组相联的少冲突率结合起来；
如果发生太多pseudo-hit，那么就交换逻辑组的内容；
-
编译优化
-
指令级
- 基本块对齐，使程序入口与Cache块起始地址对齐
- Profile对指令进行重排，从而降低指令不命中率
-
数据级
-
内外循环交换（Loop Interchange）
for(j = 0; j < 10; j++){ for(i = 0; i < 10; i++){ M[i][j] += 1; } }TO =>
for(i = 0; i < 10; i++){ for(j = 0; j < 10; j++){ M[i][j] += 1; } }缺失率降低
-
分块（Bloking）
给出下述代码（矩阵乘法）
for(i = 0; i < N; i++){ for(j = 0; j < N; j++){ int sum = 0; for(k = 0; k < N; k++){ sum += (x[i][k] * y[k][j]); } z[i][j] = sum; } }假设Cache容量为N * N + N（单位为int），那么，在N³次访问下，数组y可一直停留在Cache中，不命中次数仅为N * N，剩下数组x和z的不命中次数共为2N³，故总不命中次数为2N³ + N²
若采用分块，假设块大小为B，那么，在N³次访问下，我们同样可读入数组y，因此数组y不命中次数为N²，而对于数组x和数组z，由于我们采用分块策略，因此访问不命中次数有所降低，降为2N³/B，故总不命中为2N³/B + N²
-
数组合并（Merging Arrays）
int val[SIZE]; int key[SIZE];TO =>
typedef struct merger { val, key } MERGER; MERGER mergedArray[SIZE];第一种
val、key访问不连续，第二种连续 -
循环融合（Loop Fusion）
把多个循环合并为一个循环，充分利用了空间局部性与时间局部性原理，因为循环中代码访问连续，且Cache数据块可重用
-
-
1.3.3 降低Miss Penalty
-
多层次Cache（以L1、L2Cache为例）
让我们来重写AMAT公式
A M A T = H i t T i m e L 1 + M i s s R a t e L 1 × M i s s P e n a l t y L 1 M i s s P e n a l t y L 1 = H i t T i m e L 2 + M i s s R a t e L 2 × M i s s P e n a l t y L 2 A M A T = H i t T i m e L 1 + M i s s R a t e L 1 × ( H i t T i m e L 2 + M i s s R a t e L 2 × M i s s P e n a l t y L 2 ) AMAT = HitTime L1 + MissRateL1 \times MissPenaltyL1\\MissPenaltyL1 = HitTimeL2 + MissRateL2 \times MissPenaltyL2\\ AMAT = HitTime L1 + MissRateL1 \times (HitTimeL2 + MissRateL2 \times MissPenaltyL2) AMAT=HitTimeL1+MissRateL1×MissPenaltyL1MissPenaltyL1=HitTimeL2+MissRateL2×MissPenaltyL2AMAT=HitTimeL1+MissRateL1×(HitTimeL2+MissRateL2×MissPenaltyL2)
所以
A M A T = H i t T i m e L 1 + M i s s R a t e L 1 × ( H i t T i m e L 2 + M i s s R a t e L 2 × M i s s P e n a l t y L 2 ) AMAT = HitTime L1 + MissRateL1 \times (HitTimeL2 + MissRateL2 \times MissPenaltyL2) AMAT=HitTimeL1+MissRateL1×(HitTimeL2+MissRateL2×MissPenaltyL2)
根据公式我们可以知道，降低MissPenalty，我们可以通过优化L2 Cache来实现。对L2 Cache的优化同样是优化HitTime、MissRate以及MissPenalty三个参数。其中，MissRate的优化与我们在1.3.2节中讲到的保持一致Cache间的包含关系是应该绝对包含还是应该互斥呢？
-
包含（Inclusion）
优点：一致性
缺点：
-
如果L2的Cache Block大于L1 Cache Block，那么应该如何实施替换策略呢？如果我们将L2的Cache Block替换至L1 Cache中，那么很大可能会换出有用的块，导致L1 Cache的命中率降低；
-
如果L2 Cache大小仅比L1 Cache大一点，那么，L2 Cache是否相当于L1 Cache的一个复制了呢？
-
一致性难以保证
-
-
互斥
保证上述第2点缺陷尽量不出现
-
-
快重启与关键字优先（Early Restart & Critical Word First）
-
Early Restart
只要接收到了CPU请求的字，就立刻发送给CPU，而不必等待整个Cache Block的Loading
-
Critical Word First
先把CPU请求的字送给CPU，再将字所在Block的其他部分送入CPU；
这种方法加快了未命中时CPU的重启速度，降低了CPU等待时间，从而降低了Miss Penalty
-
-
读不命中优先级高于写不命中（Read Priority over Write on Miss）
-
对于Write Thru
我们为Write Thru采用Write Buffer部件来提升Write Thru性能，当发生RAW（Read After Write）时，最简单的方式是等待Write Buffer中的内容全部写回磁盘，但是这样性能会比较差
好的做法是，当Read的时候，我们首先Read Write Buffer中的内容，未命中再读介质（这也就是给予读不命中更高的优先级）
-
对于Write Back
当我们替换回写一个块时，同样可以用到Write Buffer策略
这种做法降低了未命中时读带来的延时，从而降低了Miss Penalty
-
-
写缓冲合并（Merging Write Buffer）
将对相同地址的小小的写入合并为一个大大的写入，如下图所示
这种做法增加了Write Buffer的利用率，减少了因Write Buffer满而等待的时间，从而降低了Miss Penalty
-
受害者Cache（Victim Caches）
Victim Cache其实既可被分类为降低Miss Rate也可被视为降低Miss Penalty，前者将Victim Cache解释为L1 Cache的拓展，在Victim Cache中命中也算命中（因为Victim Cache也很快）；后者解释为：Victim Cache的存在使得L1缺失带来的访问代价比缺失后直接访问L2的代价要低，因此Victim Cache也降低了Miss Penalty
专门用于缓存L1 Cache换出的**”受害块“**
-
*基于硬件的预取
预取技术依靠额外的存储带宽
-
指令预取
-
数据预取
绑定预取：直接将数据加载进寄存器
非绑定预取：将数据加载进Cache
-
1.3.4 降低HitTime
-
小而简的Cache
硬件更快，寻址更方便
-
避免地址转换（Avoiding Address Translation）
在OS中，MMU和TLB（Translation Look-aside Buffer，快表）通常用于虚拟地址（VA）到物理地址（PA）的转换。对于Cache而言，就可能出现基于虚拟地址寻址的Cache和基于物理地址寻址的Cache
最左：物理Cache，通过TLB将VA转化为PA，未命中则访存
中间：虚拟Cache，直接通过VA寻址，若未命中则访存
最右：虚拟Cache，把VA同时送给Cache和TLB，如果Cache未命中，那么找下层存储器，而地址翻译可并行，因此相对物理Cache快许多
总而言之，虚拟Cache避免了地址的转化，能够获得更高的性能，但是多个进程的虚拟地址可能相同，这导致了歧义问题（Ambiguity），可以通过添加PID标识符、清空Cache来解决该问题
另外，不同的进程的虚拟地址可能映射到相同的物理地址，这导致了别名问题（Alias，修改同一份数据），我们需要在虚拟Cache中维护更多的数据拷贝
1.3.5 歧义问题、别名问题详解
这两个问题产生的基础都是引入了虚拟Cache
-
歧义问题
相同的虚拟地址，映射到不同的物理地址，问题描述如下图：
那么，Cache中存在的究竟是哪个PA呢？ -
别名问题
不同虚拟地址，映射到同一物理地址，问题描述如下图：
试想，存在一个当进程1与进程2修改对应Cache中的块，当其中一个需要写回Memory时，很可能会被另一个覆盖，这就出现一致性问题了
-
再谈几种Cache地址转换寻址方法
-
VIVT（Virtual Indexed Virtual Tags）
均采用虚拟地址，那么必然导致歧义问题与别名问题，但速度快
-
PIPT（Physical Indexed Physical Tags）
先将VA转换为PA，不会产生任何问题，但是速度慢
-
VIPT（Virtual Indexed Physical Tags)
速度是VIVT与PIPT的折衷，不会存在歧义问题，因为不同进程的两个相同的虚拟地址的物理页一定不同，那么它们的Tag就不同，于是不会映射到同一Cache的入口上，如下图所示：
但是仍然可能出现别名问题，因为不同虚拟地址还是有可能被翻译为相同的物理地址……（原理是什么？？？暂时还不懂）
-
1.4 并行访问存储器
1.4.1 交叉访问存储器
-
高位交叉访问存储器
连续地址在一个存储体中，并行性不是太好
-
低位交叉访问存储器
连续地址分布在不同存储体中，可并行性好
1.4.2 无冲突访问存储器
-
一维向量无冲突访问存储器
按连续地址访问，没有冲突
-
二维向量无冲突访问存储器
一个n×n的二维数组，按行、列、对角线和反对角线访问，并且在不同的变址位移量情况下，都能实现无冲突访问
解决方案（P · Budnik与D · J · Kuck提出）
并行存储体
m≥n，且为质数。设m满足以下公式：
m = 2 2 p + 1 m = 2^{2p}+1 m=22p+1
则：同一列相邻元素在并行存储器中错开
d1=2^p个存储体；同一行相邻元素在并行存储器中错开
d2=1个存储体；什么叫错开？实际上是错开 = 间隔 + 1，例如错开一个存储体等价于间隔为0，即紧挨着；错开2个存储体等价于间隔为1；
2. 指令级并行及其开发
2.1 基本概念
-
指令级并行（ILP，Instruction Level Parallelism）
指指令间的并行性，利用ILP，计算机可同时执行1条以上的指令
-
ILP开发主要思路
- 资源重复
- 流水线
2.2 相关与指令级并行
-
数据相关
RAW（Read After Write，写后读相关）
LOAD *F0, 0(R1) (Write) ADD F4, *F0, F2 (Read) -
名相关
-
名相关无数据流动
-
如果一条指令中的名改变了，并不会影响另一条指令执行
-
可通过换名技术来消除出名相关（可用编译器亦可用硬件实现）
-
反相关
WAR（Write After Read，读后写相关）
LOAD R5, *R1 (Read) ADD *R1, R2, R3 (Write) -
输出相关
WAW（Write After Write，写后写相关）
LOAD R1, R0 (Write) LOAD R1, R3 (Write)
-
-
数据冲突
-
RAW冲突
本应先写后读，结果先读了
-
WAW冲突
本应先写A再写B，结果先写B再写A了
-
WAR冲突
本应先读后写，结果先写后读了
-
-
控制相关
由分支指令引起的相关
举一例：
if(condition1){ statement1; } statement3; if(condition2){ statement2; }两个限制：
-
条件体中的内容不能移到控制该条件体的
if之前，例如statement1不能移到if(condition1)之前 -
statement3不能移到if条件体内
-
条件体中的内容不能移到控制该条件体的
-
正确执行程序需要保证的两个关键属性
-
数据流
指数据流动，可以简单理解为写后读（RAW）
-
异常行为
无论如何改变指令的执行顺序，都不应该改变程序异常发生的情况
-
2.3 指令的动态调度
静态调度：编译器调度
动态调度：硬件调度代码
注意：在基本流水线中，我们将结构冲突与数据冲突的检测放到了ID段
-
乱序执行
在之前流水线的设计中，ID段一旦检测到冲突将暂停整个流水线的流动，使得后续没有冲突的指令不能执行。因此，乱序执行概念应运而生。为了支持乱序执行，将ID段细分为两个阶段：
-
发射（Issue，IS）
进行指令译码，并检查是否存在结构冲突，如果不存在则允许指令发射；
-
读操作数（Read Operands，RO）
等待数据冲突消失，然后再读操作数；
经典的乱序执行算法有两个：记分牌动态调度算法与Tomasulo算法
-
-
记分牌动态调度算法
上述视频讲得很清楚了。记分牌算法的核心在于三张表：
-
指令状态表
用于记录指令的发射、读操作数、执行或是回写阶段
-
功能部件状态表
用于记录功能部件正在执行什么操作，是否Busy等
-
寄存器状态表
用于记录寄存器的结果来自那个功能部件
记分牌算法保证每个周期只要某指令没有结构冲突以及不存在WAW冲突（即其他正在执行的指令的目的寄存器与当前指令的目的寄存器不同）就能够发射该指令
有一点不一样，教材上对Rj, Rk的修改是若源操作数被读走后也应表述为no
-
-
Tomasulo算法
基本思想为寄存器换名
- 保留站
- Load / Store缓冲区
2.4 动态分支预测技术
分支预测器由两个操作构成，它们分别是分支预测（Predict）与状态更新（Update）
2.4.1 分支历史表（Branch History Table）
适用范围：
判定分支是否成功所需时间大于确定分支目标地址所需的时间
由于前面的流水线判定分支成功与计算分支目标地址都是在ID段完成的，因此BHT方法不会给其带来明显的好处
2-bit BHT状态转换图如下：
2.4.2 高级分支预测技术
-
相关分支预测器
局部历史预测器（LHT）、全局历史预测器（GHT）
用前m个分支行为来预测当前分支行为，每个分支的预测采用n位预测器（表述为（m，n）预测其，原理与我所知道的有些不一样）
按照上图的说法，一个假设一个（m，n）预测其有k个入口，那么其所占比特数为：
N = 2 m ( 从 2 m 个 分 支 历 史 中 选 择 ) × n （ 每 个 历 史 是 一 个 n 位 预 测 器 ） × k （ k 行 ） N = 2^m (从2^m个分支历史中选择)\times n（每个历史是一个n位预测器） \times k（k行） N=2m(从2m个分支历史中选择)×n（每个历史是一个n位预测器）×k（k行） -
锦标赛预测器（Tournament Predictor）
全局历史与局部历史结合
2.4.3 分支目标缓冲器（Branch Target Buffer）
BTB的目标是将分支开销降为0
结构如下：
分析BTB带来的额外延迟：
| 指令在BTB中？ | 预测 | 实际情况 | 额外开销 |
|---|---|---|---|
| 是 | 成功 | 成功 | 0 |
| 是 | 成功 | 失败 | 2 |
| 否 | 失败 | 成功 | 2 |
| 否 | 失败 | 失败 | 0 |
注：BTB的修改将带来额外一个周期的开销，而当预测与实际不符时，我们需要对BTB进行修改，因此预测结果不正确时需要引入额外2个周期开销
2.4.4 多发射
每个周期发射多条指令，CPI < 1
- 超标量处理机
- 超长指令字
MIPS处理机每个时钟周期发射两条指令：1条整数型指令 + 1条浮点操作指令，需要增设浮点寄存器读写端口