计算机原理与嵌入式系统笔记：第十篇
MIPS流水线结构
必考的牢弟
流水线组成与加速比估算
MIPS的流水线由5级组成，每级完成指令执行的一个步骤：
- IF：从存储器中取指令
- ID：指令解码和读寄存器
- EX：指令执行操作或地址计算
- MEM：存取存储器操作数
- WB：将结果写回寄存器
一般假设寄存器堆的读或写为100ps，其他操作为200ps。则：
- lw指令既要读又要写寄存器堆，并且要访问数据存储器，因此耗时800ps；
- sw指令不需要写入寄存器堆，因此耗时700ps；
- R-type指令不需要访问数据存储器，因此耗时600ps；
- branch指令不需要访问数据存储器，也不需要写入寄存器堆，因此耗时500ps。
则执行3条lw指令的加速比应该是1.71，执行3条R-type指令的加速比应该是1.28。
有关流水线的更多内容请参阅：ARM第四话：流水线！
流水线各级延时不均衡会降低加速比，进/出流水线的延时也会降低加速比。
面向流水线的指令集设计
设计适应流水线的MIPS指令集，应当遵循“4+1”原则：
- 所有的指令长度都相同（32-bit）
- 简化了流水线第一级取指和第二级译码
- 而x86指令的长度：1~15 bytes
- 指令格式少且规则，寄存器字段位置相同
- 可以在1个周期内完成指令译码和读寄存器堆
- 存储器操作数仅出现在存取指令中
- 类似于ARM指令集的Load-Store结构
- 可以在流水线第三级计算访存地址，在流水线第四级访问存储器
- 所有操作数必须在存储器中对齐
- 访存操作只需要1个cycle，一个数据传输指令不需要访问两次存储器
- 减化旁路设计的原则
- 每条指令在流水线的最后一级最多只写回一个结果
流水线冒险
冒险（hazard）：在下一个时钟周期中，下一条指令不能被执行的情况。冒险分为三种：结构冒险、数据冒险和控制冒险。
结构冒险
结构冒险（structural hazard） 是由于资源不足导致的冲突。
不妨假设MIPS流水线仅使用一个存储器的情况，因其为冯·诺依曼结构，数据与指令共享一个存储器，Load/Store都需要访问存储器，第一条指令在访问存储器中数据的同时，第四条指令将会在同一存储器中读取指令，造成访存冲突；这会导致第四条指令的取指令操作不得不被阻塞（stall），也称为流水线气泡（bubble）。因此，在MIPS的流水线数据通路中使用分立的指令存储器和数据存储器。
数据冒险
数据冒险（data hazard） 是由于一条指令的数据依赖于更早的一条还在流水线中的指令的计算结果造成的冲突。如下面的代码：
add $s0, $t0, $t1 |
前推或旁路
一种解决数据冒险的方法：前推（forwarding），也称为旁路（bypassing），可以从处理器的数据通路内部资源中提前取出数据。这样子当add指令结果在ALU计算后就可以被sub指令使用，不需要等结果存到寄存器堆，但需要在数据通路上增加额外的连线与控制信号。
但旁路技术并不能避免所有流水线阻塞的发生。考虑发生 取数-使用型数据冒险（load-use data hazard） 的情况：
lw $s0, 20($t1) |
应该如何避免阻塞？
调度代码避免阻塞
可以重新排列数据加载指令在代码中的顺序，以避免发生取数-使用型数据冒险。
如：对于a=b+e;c=b+f;：
然而，调度后的代码依旧存在执行-存储型数据冒险，如每两条相邻的add-sw。
控制冒险
由于Branch指令的结果决定程序的控制，因此流水线无法总是正确的取得下一条指令。
add $4, $5, $6 |
beq和or之间存在冒险。在流水线取下一条指令之前，需要等待Branch指令的结果确定，即阻塞流水线直到跳转地址确定之后。因此，即使分支不执行，也会阻塞1个时钟周期。
更多分支预测方法包含静态分支预测和动态分支：
- 静态分支预测基于分支的行为进行预测，例如loop底部的分支，预测目标地址向后的分支总不发生或是总是发生；
- 动态分支预测取决于每一条分支的行为，可能会动态改变预测结果，如记录每条分支发生的历史纪录，来进行预测。
延迟分支（ delayed branch ） 要求分支指令后面的n条指令总是执行，无论分支是否执行。这样，在分支指令执行期间CPU能够让流水线满负载运行，改善流水线效率。但是，分支指令后面可能是空操作（NOP）。因为处于延迟分支窗口中的指令对于两条执行路径都要有效，如果没有足够的有效指令填充，就需要使用NOP。
MIPS流水线数据通路与竞争冒险的消除
流水线寄存器
MIPS处理器中，指令与数据从左到右依次通过5级流水线IF·ID·EX·MEM·WB，这其中有两个从右到左的回路：
- 写回阶段，把结果写回数据通路中的寄存器堆中。
- 选择PC的下一个值时，需要在自增的PC和MEM级的分支地址之间进行选择。
这两个从右向左的回路不会影响当前指令，只有当前指令以后的指令才会受到这种数据反向活动的影响。第一个会导致数据冒险；第二个会导致控制冒险。
不考虑控制信号，算一下各级流水线寄存器的位宽？
答案
-
IF/ID：
PC的位宽为32位，指令为32位，因此IF/ID级位宽为64；
-
ID/EX：
PC的位宽为32位，data1与data2的位宽均为32位，同时经过符号扩展单元后的数也为32位，因此ID/EX级位宽为128；
-
EX/MEM：
PC的位宽为32位，data1与data2的位宽均为32位，因此运算后结果的ALU_Result也为32位，Zero为1位，因此EX/MEM级位宽为97；
-
MEM/WB：
data位宽为32位，ALU_Result为32位，因此MEM/WB级位宽为64。
指令在流水线的执行
在WB的存储步骤中，这一级流水线不做任何操作，但是之后的指令已经进入流水线中进行处理，所以无法加速当前sw指令。
注意Load指令的最后一级流水线，会将数据写回当前的寄存器地址，即此时处于IF/ID级的寄存器。因此会发生错误！如何避免？
必须将传递的全部信息放入流水线寄存器中，逐级进行传递，直到该信息被使用为止；否则，后续指令进入流水线时会冲掉之前的信息（如：Write register）。
流水线控制
有关控制信号的更多内容，请参阅 MIPS第一话：比较烦的指令集和控制信号
根据流水线的5级，我们将控制信号分成5组：
- IF：总是要读指令存储器和写PC操作，因此不需要控制。
- ID：在每个时钟周期内，本阶段所作的操作都是相同的，因此不需要设置控制信号。
- EX：控制信号有RegDst、ALUop和ALUSrc，根据这些信号的选择结果寄存器、ALU操作、为ALU选择输入数据。
- MEM：控制信号有Branch、MemRead和MemWrite，这些控制信号分别由相等则分支、装载指令和存储指令设置。
- WB：控制信号包括MemtoReg和RegWrite，用于决定是否将ALU结果或存储器数据写入到寄存器堆。
如果考虑控制信号，算一下各级流水线寄存器的位宽？
计算可能有误，网上也未找到相关内容，仅供参考。
答案
-
IF/ID：
64位（因为没有控制信号存入）
-
ID/EX：
需要额外存储rt与rd，以及9位的控制信号，总位宽为：
128+9+5+5=147位
-
EX/MEM：
需要额外存储多路选择器的结果，以及5位的控制信号，总位宽为：
97+5+10=112位
-
MEM/WB：
需要额外存储2位的控制信号，总位宽为：64+2=66位
流水线的数据冒险
对于下面的MIPS指令，分析数据相关性：
sub $2, $1, $3 |
显然，后四条指令都依赖于第一条指令得到的寄存器$2的结果， 这些导致指令执行时间后推的数据依赖，就是流水线的数据冒险。 可以采用旁路技术解决冒险，关键是何时检测数据冒险并将结果前推?
流水线冒险的分类
在流水线中传递寄存器序号（Rs、Rt、Rd），使用流水线寄存器字段精确地表示数据相关性：
- ID/EX.RegisterRs和ID/EX.RegisterRt：表示在ID/EX级流水线寄存器中保存的Rs/Rt寄存器序号，也是EX级流水线中的ALU模块的两个源操作数寄存器序号。
- EX/MEM.RegisterRd和MEM/WB.RegisterRd：表示在EX/MEM级、MEM/WB级流水线寄存器中保存的目标寄存器序号。
要检测数据冒险，条件还需要满足：
- 仅发生在指令将数据写回寄存器堆，可以通过检测RegWrite信号来判断这种情况，如EX/MEM.RegWrite和MEM/WB.RegWrite，已经存在于流水线寄存器缓存的控制信号中。
- 指令的目标寄存器Rd不是$0，因为MIPS的$0寄存器是常量0，即EX/MEM.RegisterRd≠0或者MEM/WB.RegisterRd≠0。
EX冒险
sub指令处于EX级，而add指令处于MEM级时：
若EX/MEM.RegisterRd == ID/EX.RegisterRs = $2，代码中$2出现了1a类冒险：
add $2, $1, $3 |
若EX/MEM.RegisterRd == ID/EX.RegisterRt = $2，代码中$2出现了1b类冒险：
add $2, $1, $3 |
MEM冒险
or指令处于EX级，而add指令处于WB级时：
若MEM/WB.RegisterRd == ID/EX.RegisterRs = $2，代码中$2出现了2a类冒险：
add $2, $1, $3 |
若MEM/WB.RegisterRd == ID/EX.RegisterRt = $2，代码中$2出现了2b类冒险：
add $2, $1, $3 |
答案
- 1b
- 2a
- 无冒险
带旁路的流水线数据通路
为了实现旁路，需要在流水线的EX级增加两个多路选择器，为ALU的两个操作数选择数据来源。
EX冒险的条件及控制：
如果前一条指令要写寄存器堆且要写的寄存器号与ALU要读的寄存器号一致（只要不是寄存器0），那么就控制多路选择器从流水线寄存器EX/MEM中读取数值，旁路到ALU的输入。
MEM冒险的条件及控制：
当不是EX冒险且满足MEM冒险的条件时，从流水线寄存器MEM/WB中读取数值，旁路到ALU的输入。
由于MEM级的结果是最新的，因此结果由MEM级旁路得到，因为旁路的存在，这种情况下第1和第3条指令间没有2a型冒险。
检测取数-使用型冒险
当发生取数-使用型数据冒险（load-use data hazard）时，无法使用旁路技术完全消除冒险，需要阻塞流水线。
插入气泡阻塞流水线的操作：
- 清除ID/EX流水线寄存器中的9-bit控制信号（置为0）
- 阻止更新PC寄存器和IF/ID流水线寄存器
- 正在使用的指令又被再次解码
- 后续的指令又从指令存储器中再次取出
阻塞降低了系统性能，但是保证了结果的正确性。编译器可以基于流水线结构，通过调度安排代码，避免冒险和阻塞。
处理控制冒险
解决办法一：假定分支不发生
采用阻塞直到分支判断完毕（MEM级）来处理控制冒险实在太慢。可以假定分支不发生，继续顺序执行指令，如果分支不发生的可能性是50%，就可以将控制冒险的代价减半。
当分支发生时，为了丢弃指令，需要将最初的控制信号置0，即将流水线的IF、ID和EX级的指令全部清除（flush）。
解决办法二：减少分支的延迟
MEM级才能确定分支要执行的下一条指令的地址，许多分支仅仅需要简单的判断（如相等或正负），不需要完整的ALU操作而仅使用简单的一些逻辑门就够了。因此可以将分支决策提前：
- 计算分支目标地址（从EX级前移到ID级）
- 级间寄存器比较以判断分支条件（在ID级用XOR实现，同时需要额外的旁路和冒险检测硬件，因为分支条件的判断可能依赖于还在流水线中的结果）
如下面的代码：
36: sub $10, $4, $8 |
在第三个时钟周期ID级确定分支发生，因此地址72被选为下一个PC地址，同时为下一个时钟周期预取的指令置为0，后果是流水线中产生了一个气泡或者一条空指令。
分支中的数据冒险
如果分支指令中待比较的寄存器是前2nd或3rd R-type指令的目的寄存器（在ID级进行比较），则可以通过旁路技术解决数据冒险。
如果比较寄存器是前1条ALU指令的目的寄存器或前2条load指令的目的寄存器，则需要1个时钟周期的阻塞：
lw $1, addr |
如果比较寄存器是前1条指令的Load指令的目的寄存器，则需要2个时钟周期的阻塞：
lw $1, addr |
解决办法三：动态分支预测
通过查找指令的地址观察上一次执行分支指令时是否发生跳转，如果上次发生跳转，就从上次分支发生的地址取新的指令。
- 分支预测缓存BPB（Branch Prediction Buffer）：
- 一小块按照分支指令的低位地址索引的存储器，其中包括一位或多位数据用以说明最近是否发生过分支。
- 分支目标缓存BTB（Branch Target Buffer）：
- 一种用于缓存分支目标地址的cache存储结构
动态分支预测需要提前计算分支目标地址，否则当分支发生时，会带来1个时钟周期阻塞。
动态分支预测只是对正确分支方向的一种假设，在这个基础上，沿着预测的方向取指。如果假设的分支方向错误，预测错误的指令将被删除，预测位将取反，并返回原来的位置，继续按照正确的方向取指并执行。
使用1-bit预测位的简单预测方法具有性能上的缺陷：即使一个分支几乎总是发生，但它一旦未发生就将导致两次预测错误。使用1-bit预测位会在第一次和最后一次的循环迭代时预测错误。
为了弥补1-bit预测位的缺陷，使用2-bit预测位方案，发生两次连续的预测错误时才改变预测方向。
下一章开始讲总线！
