《超标量处理器》笔记

参考书籍：超标量处理器

第一章

1.3.1顺序执行

• 如果将发射的过程放到指令的解码阶段，会严重影响处理器的周期时间，因此将发射的过程单独作为一个流水段
• 因为要保证流水线的写回阶段是顺序执行的，因此所有的FU都需要经历同样周期数的流水线
• ScoreBoard：记录每条指令的执行情况（详见P23）
• 每条指令都可以从旁路网络（bypassing network）获得操作数，不需要等待源寄存器写回

第二章

2.1 Cache的一般设计

例如TLB和Victim Cache多采用全相联结构，而普通的I-cache和D-cache则采用组相联结构

• 强制缺失：预取（prefetching）
• 冲突缺失：可以用Victim Cache来缓解

2.1.1 Cache的组成方式

• 组相连：因为需要从多个Cache line中选择一个匹配的结果，延迟会增大，甚至可能需要流水线，但是其显著地增加了Cache命中，所以得到了广泛的应用
• Cache的访问一般会比较慢，想提高频率，Cache的访问就需要使用流水线，对于指令cache影响不大，但是对于数据cache会增大load指令的延迟。
• 访问方式：
• 串行：对于超标量处理器来说，由于可以调度其他指令，所以就算串行方式增加一个cache阶段的时钟周期，但是也不会引起性能的明显降低
• 全相连：TLB的实现方法

2.1.3 Cache的替换策略

• 伪LRU的一种实现方法：P41
• 需要比较**随机**替换和**伪LRU**所花的时间

2.2 提高Cache的性能

2.2.1 写缓存

• 因为内存一般只有一个读写端口，所以写回脏数据就会需要两次串行的访存，效率低，可以先写道写缓存（write buffer）中，对于写通（write through）的Dcache来说，写缓存尤为必要

2.2.2 流水线

• 读Dcache可以并行读取Tag SRAM和Data SRAM的数据，但是写Dcache只能串行，所以写的时候需要用流水线
• 注意额外的转发

2.2.3 多级结构

• 现代处理器多采用inclusive类型的Cache

2.2.4 Victim Cache

• 防止被踢出的数据马上被利用，而Filter Cache则是防止不会再用的数据一直不被踢出

2.2.5 预取

• 硬件预取：ICache预取的效果要比Dcache要好，可以将预取的指令放到一个单独的缓存中

2.3 多端口Cache

• Multi-banking：需要尽量减少bank的冲突（空间局部性），以及遇到冲突的处理，其它部件也要实现多端口（Tag SRAM和TLB的复制，可以参考Opteron处理器）

2.4 超标量处理器的取指令

• 每周期取更多的指令，多余的放在**指令缓存**中（2路处理器最多可以取4条指令）

第三章

3.4 TLB

• TLB就是页表的Cache

第四章

对**方向**和**目标地址**都需要预测

• 可以将是否是分支指令的信息在指令从L2 cache写入到Icache之前进行**预解码**（pre-decode），然后把这个信息一起写到Icache中
• 分支预测最好时机就是在当前周期得到取指令地址的时候
• 需要根据PC值判断本周期的**指令组**（fetch group）中是否存在跳转指令
• 因为我们是顺序双发，所以本周期的指令组只有两个指令

4.2.1两位饱和计数器的分支预测

• 初始状态一般为 weakly not taken 或 strongly not taken

• 使用格雷码对状态机进行编码，减少出错、降低功耗

• PHT(Pattern History Table) 大小为2KB就有很高的准确率（93%）

• 由于这种方法的正确率有一个极限值，很难达到98%以上的正确率，现代处理器不会直接使用这种方法。

4.2.2局部历史的分支预测

• 当一条分支指令得到结果时，将PHT中对应的计数器读出来，更新好后再写回即可。
• 利用BHT(branch history table)和PHT：将分支此前的跳转情况记录下来，然后索引对应情况的PHT
• 由于容量的限制，PC需要进行hash，然后不可避免的会有两种冲突，如下。解决方法有位拼接或**异或法**
• 两条分支指令对应一个BHR(branch history register)
• 两条分支指令对应两个BHR，但是它们BHR的内容一样，对应PHT中的同一个饱和计数器

4.2.3全局历史的分支预测

• 用GHR(global history register)记录所有的分支跳转情况
• 两条PC的GHR相同，因为它们的PC值不同，同样应对冲突可以用：位拼接或**异或法**

4.2.4竞争的分支预测

参考图4.25

• 利用CPHT(Choice PHT)来判断选择GHR还是BHR
• 同样的，为了减少冲突，可以把GHR的值和PC的值异或后对CPHT进行索引

4.2.5分支预测的更新

• commit阶段再更新会导致后续跟的比较紧的其他跳转指令获取不了最新的GHR，不至于形同虚设（书上的说会“形同虚设”，但是我觉得不至于），但是会有一定影响

• 综合来看，在**取指令阶段用分支预测的结果对GHR进行更新**是不错的做法，就算当前预测错了，那么之后的分支指令也会因为当前分支预测失败而被冲刷掉，不会有负面影响。不过由于GHR写入了一个错误值，需要进行修复

• 用FIFO的Checkpoint GHR来依次保存GHR的值

当预测错误时用

• 更新BHR的时候可以在退休的再更新，这样可以简化设置，也不会有太大的负面影响；而饱和计数器由于一般会处于饱和状态，也可以指令在退休的时候再更新

4.3分支指令的目标地址预测

4.3.1直接跳转（PC-relative）

取值阶段需要n+1级流水线（若ICache 需要n个周期返回指令）

• BTB(branch target buffer)：存储跳转指令对应的PC值，与cache类似。
• 减少tag位数（可以位截取，或者**异或运算**，yyds）不仅节省BTB的存储空间，也不会引起分支预测争取率的降低。
• 一般只将**预测发生跳转**的分支指令对应的地址放到BTB中
• BTB缺失的处理
• 停止执行：需要加入气泡，尤其是间接跳转指令
• 继续执行：预测跳转的地址可能不跳转，继续执行可能会是对的，但是功耗大

4.3.2 间接跳转（absolute）

大部分间接跳转都是CALL/Return指令，它们是有迹可循的

• RAS(Return Address Stack)：保存每次CALL指令的下一条指令
• 在BTB中保存指令的类型（CALL、Return或其它），因此在分支预测阶段（第一个取值阶段）就可以知道当前指令是哪一个指令，进而得到下一个指令的地址
• 用带**计数器**的RAS来解决重复的递归函数
• 使用Target Cache预测其它类型的分支指令的跳转地址（与预测是否跳转类似）

4.3.3小结

参考图4.49

• 使用BHR、GHR和饱和计数器来预测分支指令的方向；使用BTB、RAS和Target Cache预测分支指令的目标地址；它们都是基于取值阶段的PC值来预测的

4.4分支预测失败的恢复

详见书：非乱序流水线应该不用这么麻烦

4.5超标量处理器的分支预测

• 对于目标地址的预测可能并不需要这么复杂

**MIPS**中，程序绝大部分出现的分支指令都是直接跳转（PC-relative），它们的目标地址可以很快算出来，不必进行目标地址的预测，而是在取值阶段算出目标地址；当然对于非Return的间接跳转就不行了。

• 使用**交叠方式**（interleaving）实现多端口设计，在超标量处理器中很常用，如重排序缓存（ROB）、发射队列（Issue Queue）和指令缓存（Instruction Buffer）等

第五章

• 乘法/乘累加指令在MIPS指令集中保存在特殊寄存器Hi和Lo中，但是在超标量寄存器里被认为是33和34个通用寄存器，对它们可以进行正常的寄存器重命名

• 类似的指令可以进行指令更改，比如MULT：

31:26	25:21	20:16	15:6	5:0
Special 000000	rs	rt	0 0000000000	MULT 011000

我们发现其中[15:6]位是没有意义的, 正好可以编码两个寄存器, 所以将指令改成如下

31:26	25:21	20:16	15:11	10:6	5:0
Special 000000	rs	rt	RdHi	RdLo	MULT 011000

第六章

6.1 指令缓存

每周期的取指数和解码数不匹配

• 在取指阶段和解码阶段之间的缓存
• 有效指令的个数，告诉缓存哪些指令是有效的
• 为了减少对寄存器重命名阶段的影响，一般会将特殊指令（累乘加：madd）拆分成两条普通的指令，每条指令只有**一个**目的寄存器
• 用**交叠**的方式，使用多个单端口的SRAM来实现指令内存这个多端口FIFO

6.2一般情况

• 从指令缓存中读取的四条指令未必是四字对齐的，需要按顺序排列好

6.3特殊情况

6.3.1 分支指令的处理

• 每周期最多只有一条分支指令（MIPS指令集有延迟槽，所以顺序双发不可能需要处理两条）
• 解码阶段对分支指令的预测的检查

6.3.2乘累加/乘法指令的处理

• 在处理器内部，被拆分的乘累加在流水线的执行阶段，仍然以一个完整的乘累加指令完成；拆分只是更有利于进行寄存器重命名和便于在ROB中的存放；在写发射队列的时候，将两条指令进行了融合，最终变成一条完整的乘累加或乘法指令
• 一个周期多个复杂指令：拆分完后只进行部分解码

第七章

7.1概述

• 有限个数的寄存器导致了上述的假相关性

假的相关性制约了原始程序获得的并行性

第八章

• 采用集中式发射队列（Centralized Issue Queue，CIQ）
• 采用非数据捕捉（MIPS R10000和Alpha 21264）
• 旁路网络

第九章

• 退休的时候才真正更新寄存器状态

• 用cluster实现多端口

• CLZ指令的一种实现方式（在MIPS中允许所有的位为0）

• AGU（Address Generate Unit）用来计算地址，在超标量处理器中由于并行处理的需要以及访存对处理器的性能的影响，单独用了一个FU来计算地址，同时进行分支检查

• BRU（Branch Unit）负责计算分支指令的目的地址，并根据这些条件来决定是否

9.3旁路网络

• 从寄存器中读出的数据需要一周期的时间（Source Drive）才能进入FU的输入端；同理FU计算出结果也需要一个阶段（Result Drive）才能到达所有的FU的输入端

• 从一个输出到另一个输入如果时间很长会让execute的时间变少，可以用（Cluster）来解决这个问题

• 两条指令同时想要占有旁路网络去转发数据，会产生冲突

• 不需要在所有的FU之间都设置旁路网络
• AGU进行地址计算时，一般都会用到ALU的结果，尤其是间接跳转（寄存器跳转）
• load/store单元中store单元也不需要旁路

9.4 操作数的选择

• 寄存器的信息需要保存在一个表格中（ScoreBoard）
• 将ScoreBoard的读取放到流水线的RF Read阶段可以减少对周期时间的影响，但是需要额外的比较电路，此外，ScoreBoard的电路本身就比较复杂
• 有些时候**简单的就是好的**，每条FU计算出结果的时候都进行广播（类似单指令流水线的转发）

9.5 Cluster

和交叠（interleaving）类似

• 发射队列的Cluster结构：分布式发射队列（多端口会耗费大量资源，同时会降低速度）

9.5.1 Cluster IQ

• 不同的分布式发射队列处理不同的指令，对应少数的仲裁电路和FU

9.5.2 Cluster Bypass

• 旁路网络只分布在每个Cluster内部，进而减少大量的旁路电路
• 对于乱序处理器来说，不同Cluster中的相邻指令之间可以调度其它指令填补空白；但是对于顺序处理器，无法调度只能bubble的情况难以接受，一般会尽量采用完全的旁路网络（Intel的Atom处理器），

9.6 存储器指令的加速

9.6.1 Memory Disambiguation

• 为了降低设计难度和处理器中存储器的正确性，大部分处理器的store指令是顺序执行（in-order），而load指令主要有三种实现方法，这里只介绍完全的顺序执行
• 完全的顺序执行：最保守，性能低，超标量处理器中基本不会采用这个方法（。。。我们应该是采用这个方法）

9.6.2 非阻塞Cache

• 非阻塞（Non-blocking）Cache：在发生D-Cache缺失的时候，处理器可以继续执行后面的load/store指令

9.6.3 关键字优先

• 从下级流水线读取数据的时候，可以先读指令所需要的数据到cache line中，这样CPU就得到了想要的数据，而D-cache会继续完成其它数据的填充。但需要在存储器系统中添加额外的硬件才能实现
• 关键词优先和提前开始都可以应用于I-Cache，但是要保证原始顺序

第十章

10.1 概述

• 从外部来看，处理器总时按照程序指定的顺序执行；从内部来看，超标量处理器，尤其是乱序的，在分发阶段（Dispatch）打乱指令，然后在提交阶段（Commit）拉回到顺序执行，从这个角度来说，超标量处理器堪称一个伪装高手。

10.4 特殊情况的处理

• 由于store指令改变程序员可见状态（architecture state），必须保证其在执行阶段（尤其是写DCache的时候的）的正确性，因为有可能架构在设计的时候存在在提交阶段才检测到分支预测错误的可能性，那么此前的所有指令都不该被执行，这点需要注意。
• 分支预测使得原本流水线中指令的状态变为三种（正常、异常、不执行），增加了异常处理的复杂。
• store指令的处理：因为store指令退休的时候才能写回，此时或出现缓存缺失，堵塞了之后的指令会导致处理器性能的降低。解决方法为在Store Buffer中增加一个状态位。
• RISC处理器的一个设计思想：不为不经常出现的情况浪费硬件资源

第十一章

11.2 取指令和分支预测

• Alpha 21264采用两级流水线来访问ICache，第一级得到ICache中的指令和Tag，第二级进行Tag比较，同时把指令送到解码器等相关部件中
• 两种分支预测方法：第一种简单，第二种复杂需两个周期，如果两种方法复测结果不一样，则bubble掉简单预测的指令，采用复杂方式预测的指令。

11.2.1 line/way的预测

• 本质上就是把BTB放到了ICache中，因为21264处理器每周期取出的四条指令在四字对齐的边界之内，所以每四条指令用一个line/way预测
• 预测信息包含三个内容：（1）successor way：下个周期取出的fetch group在ICache中的way，（2）successor index：下个周期要取出的一组指令中在Cache line中的位置，需要先找到Cache line，然后再找其在Cache line中的位置。（3）branch position：本周期取出的指令组中，若存在预测跳转的分支指令，存储该指令下一条指令的位置，不存储分支指令的位置是因为：一、更容易找到本周期中哪些指令不该进入流水线；二、用00就可以表示出“本周期取出的指令都需要进入流水线”这个信息。

• 可以用两位饱和计数器的方式来管理line/way的预测值
• 同时也有三个问题：（1）很多Cache line没有分支指令，浪费分支指令的信息，而独立的BTB只会把预测结果是跳转的指令放在BTB中（2）Cache占用更多的资源（3）每当Cache line被替换，它包含的预测信息就消失了，而独立的BTB不会有这样的问题。
• 配合使用virtually-indexed，virtually-tagged结构的Cache更合理

11.2.2 分支预测

• 21264处理器的复杂分支预测与简单分支预测的冲突

• 基于全局历史的预测和局部历史的预测的冲突

• 对于基于局部历史的分支预测方法，使用非推测（non-speculative）的方式更新；对于基于全局历史的分支预测方法，使用了推测的分式更新，所以GHR的状态可能不正确，所以需要用类似于Checkpoint的方法进行更新。

11.4 发射

• 将寄存器堆复制的方法是Cluster结构中常用的方法之一，减少了寄存器对的读端口，访问寄存器退的速度会提高，总的面积也不会显著增多。

11.5 执行单元

11.5.1 整数的执行单元

• Cluster结构中，若两条相邻的相关指令是在同一Cluster内执行的，就可以背靠背执行；若在不同的Cluster，则需要跨越Cluster，需要单独的一个周期来传递
• 寄存器堆有专门供load指令使用的写端口，以此来提高load指令的执行效率

11.5.2 浮点数的执行单元

• 浮点数有专门的处理单元，包括加法、乘法、除法等

11.8 结论

• Alpha 21264 处理器在很多方面做出了有益的尝试