【梳理】计算机组成与设计 第4章 处理器 第2节 流水线 流水线冲突（内附文档高清截图）
配套教材：
Computer Organization and Design: The Hardware / Software Interface (5th Edition)
建议先修课程：数字逻辑电路、C / C++、汇编语言。
这是专业必修课《计算机组成原理》的复习指引。建议将本复习指导与博客中的《简明操作系统原理》配合复习。
在本文的最后附有复习指导的高清截图。需要掌握的概念在文档截图中以蓝色标识，并用可读性更好的字体显示 Linux 命令和代码。代码部分语法高亮。
计算机组成原理不是语言课，本复习指导对用到的编程语言的语法的讲解也不会很细致。如果不知道代码中的一些关键字、指令或函数的具体用法，你应该自行查找相关资料。
第二节 流水线 流水线冲突
11、我们回忆一下执行一条指令的大致步骤：
（1）从内存中取指令。
（2）对指令解码（decode），并读寄存器（MIPS指令集允许解码和读写指令中指定的寄存器同时进行）。
（3）开始执行，计算需要访问的地址。
（4）从内存中访问操作数。
（5）把结果写入寄存器。
构建一个5级（stage）流水线（pipeline，也称管线）的CPU，每一级负责上述所说的一步。由于每一级用到的单元是独立的，因此我们可以这样执行：
·解码并读寄存器时，可以同时取下一条指令。
·一条指令开始执行后，下一条指令可以开始解码。
·访问内存时，下一条指令可以开始执行。
·结果写入寄存器时，可以开始根据下一条指令访问内存。
也就是说，一条指令执行到上述5步中非第一步时，下一条指令都开始执行上一步：
（这里每一步的执行时间只是举例；并且，对读写寄存器的指令，假设写在读之前，而且各占一半周期）
由于CPU执行指令的速度是非常快的，也就是说即使是很短的时间，CPU都已经执行了很多指令。所以近似来说，流水线化后的一个CPU与流水线化之前的这个CPU的性能倍数之比就是流水线级数，也就是说一个核心有几级流水线，可以近似把这一个核心看成几个核心（就是上面的对比图中流水线化的指令全部靠在最左边，而不是每个空开一级流水线的位置，执行的指令数越多，这种估计与实际越接近）。当然，流水线结构是有额外开销的，所以实际上的性能提升并没有这么多。
每一级流水线的时钟周期是一样的，而且这个时钟周期必须不短于耗时最长的那一步的执行周期（如果周期再调短的话，就会出现这样的情况：某级流水线对应的步骤虽然执行完毕，但是下一级流水线需要用到的单元还在被占用，所以新的指令无法进入下一级流水线，造成部分单元闲置，所以不如直接把每一步的周期都设成一样的）。
有的指令在整条流水线期间，在某些stage上可能什么都不做。但即便如此，指令还是要通过这些stage的。
12、MIPS的指令集都是定长的（32-bit），所以流水线化比较容易：取指令可以在第一级流水线完成。但是x86指令短则1字节，长则十几字节，流水线化就比较麻烦了。较新的x86 CPU中，指令会被拆分成一系列微操作（micro-op），来降低流水线化的难度。
MIPS的指令格式不多，而且在这些格式中，源寄存器在指令中的位置都是一样的，所以在第二级流水线中可以同时读寄存器堆、确定下一条指令的格式。如果指令格式比较复杂的话，这一级流水线就要拆分成更多级了。
在MIPS中，只允许L / S指令的操作数来自内存。所以第3级流水线可以同时执行并计算内存地址，然后在第4级流水线进行内存访问。x86允许其中一个操作数为内存，这两级流水线在x86中要拆成3级（地址、内存、执行）。
MIPS强制要求内存对齐，所以传输数据到内存时只需要一级流水线就能完成了。
13、假如一个指令在执行的时候需要先等待流水线上前一个指令先执行完毕，那么这两个指令相互之间具有依赖关系。这可能导致流水线冲突（pipeline hazard，也称流水线冒险，流水线风险）的现象发生。流水线冲突分为3种：
结构冲突（structural hazard）：流水线上的一个指令需要使用已经被另一个指令占据的资源（部件数量不够，没法满足指令的重叠执行）。
数据冲突（data hazard）：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。数据冲突又可细分为：
·指令层的数据冲突：指令需要的数据还没有计算出来。
·传输层的数据冲突：指令需要的寄存器内容还没有被存入寄存器。
控制冲突（control hazard，也称分支冲突（branch hazard））：下一条指令流水时，CPU正在执行分支指令，不能在后来的指令的流水开始阶段就判断出先前的指令的分支结果。
这些冲突导致后来的指令必须等候，称为流水线停顿（pipeline stall）。这会在流水线上导致空缺，流水线就不能充分利用，处理速度便开始下降。因此要尽量避免这样的冲突。
14、MIPS属于典型的RISC 5-stage流水线，这样的流水线在纯整数计算时一般没有结构性冲突，所以设计师们比较容易避免结构冲突。多周期单元容易引起结构性冲突，比如在乘法器、触发器、浮点运算单元、寄存器的回写部件上面易出现结构性冲突。
结构性冲突的解决办法主要有：
·拖延新的指令，先待旧指令执行完毕，再执行新指令。
·增加硬件单元。例如，如果两条指令同时需要存储器的某部件，我们可以通过增加另一个该部件的方式避免冲突。
解决数据冲突的办法主要有：
·转发（forwarding），也称旁路（bypassing），即上一条指令的计算结果一旦产生，就立刻将其传给下一条指令，而不要等待上一条指令执行完毕。
如下图，当先被取到的add指令在第3级流水线计算出结果以后，就直接将结果传给下一条sub指令，而不等待add指令执行完毕。
（IF = instruction fetch, ID = instruction decode, EX = execute, MEM = memory access, WB = write back (to registers)）
转发结果之前，有时候需要额外添加流水线停顿，也称气泡（bubble）。气泡是通过插入nop（no operation performed）指令实现的。指令译码时如果控制器发现可能存在冒险，就插入nop指令。这样在有风险的指令进入流水线时，上一条指令已经在流水线中经过了充分多的周期，从而化解了冒险。如果插入的nop数量等于流水线级数，那么CPU就排空了整个流水线。流水线冒泡可以消除任何一种流水线冒险。但插入过多的气泡会严重浪费流水线机制带来的性能提升。
在lw指令以后发生的这种数据冲突是比较特殊的一种，称为load-use数据冲突。
·预测：先假设一个值，如果假设错误，再进行改正。
解决控制冲突的主要办法有：
·等待。在分支指令后插入流水线冒泡，直到分支指令的流水执行完毕。
·分支预测（branch prediction）。猜测分支可能的结果，然后尝试选择被判定为可能性最大的结果执行。如果预测正确，性能就得到提升；如果误预测（misprediction），则要清空这条提前执行的指令的流水线，重新按照实际的分支结果执行。
·延时分支。MIPS架构包含1条指令的分支延迟间隙，亦称分支延时槽（branch delay slot）。分支指令之后，无论分支的判断结果如何，延迟间隙中的指令总是先被执行。这条指令的优先执行与分支无关，不会对分支产生影响。至于将哪条指令放到延迟间隙里，则由MIPS汇编器决定。
分支延迟间隙常见于DSP体系结构与老式的RISC体系结构。MIPS、PA-RISC、ETRAX CRIS、SuperH、SPARC等RISC体系结构在分支后有一个延迟间隙。PowerPC、ARM、DEC Alpha没有采用分支延迟间隙。有的处理器（SHARC DSP与MIPS-X）包含2个分支延迟间隙。
除了分支延迟间隙以外，还有过存储延迟间隙，即在存储内存的指令之后跟一个延迟间隙，现在已经基本不用了。
15、学习了流水线后，我们可以把前面学习的数据通路按流水线的每一级重新绘制（蓝色为传输数据的线路）：
当未发生流水线冲突时，由于每一级流水线用到的单元在接下来都会被其它指令使用，所以有必要用寄存器单独为每条指令保存该指令在流水线上的后续步骤需要用到的内容。例如取指令以后要将取到的内容存入寄存器，这样取指令这一步需要用到的相关单元就可以放心地提供给下一条指令使用。
下图中的蓝色部分是两级流水线之间的流水线寄存器（级间寄存器）。最后一步回写是不需要流水线寄存器的，数据直接写入目标寄存器中。程序计数器（PC）可以视作流水线寄存器。不过当异常发生时，PC的值必须被保存，以便异常处理完毕后返回到该处继续执行；而流水线寄存器中的值可以直接丢弃。流水线寄存器的容量必须足够保存所有在后续可能需要的信息。
流水线寄存器的宽度是有要求的。例如在MIPS架构中，IF / ID两级之间的寄存器必须是64-bit宽，因为需要保存取到的32-bit指令和32-bit的新PC值。
如果要绘制多条指令在流水线上的执行情况，可以画成这样（展示的细节更少）：
16、现在我们来进一步完善之前的图。把数据通路按每一级流水线重绘后，我们把控制信号补上去：
控制信号会被送入相应的流水线寄存器：
将这两个图合并：
17、以下是添加转发单元的流水线化数据通路的示意图：
可以看出，转发器针对两种情况：一种是接下来的指令要用到先来的指令的ALU的计算结果，一种是需要用到先前的指令从内存中取得的数据。探测到后来的指令对前面的指令的结果具有依赖性后，转发单元会输出控制信号控制ALU前的MUX，将转发的结果抢先送入ALU，以便流水线能被充分利用，不至于总是需要等待依赖的结果。两个操作数的是否转发都可以独立控制。
不过，对于有的指令，不能转发其计算结果给后续指令，例如目标寄存器为零寄存器$0的时候。
下图给出了一种需要用到转发来解决数据冲突以便满载流水线的情况，注意sub和add指令之间是没有数据冲突的：
添加了转发单元的数据通路的示意图如下（主要突出转发机制，一些细节没有画出）：
事实上，在ALU与第二操作数的MUX之间还有一个MUX，用于选择将带符号立即数还是将第二操作数传入ALU：
18、在编程中，常常需要进行内存内复制，也就是把内存中的一块数据复制到内存中的另一块。这对应MIPS汇编中在lw指令之后立马跟一条sw指令。所以我们可以添加额外的转发单元来加快这个过程。这里只画出草图：
19、如果在读取一个值到寄存器后，下一条指令立刻就要用到这个值，那么通过转发是不可能解决这个数据冲突的：
由图可知，在第4个周期末尾才能读到内存中的数据，我们不能将它直接转发到下一条指令的第3级流水线之前，也就是第4个周期开头。解决办法是通过冲突检测单元在指令译码期间检测冲突，如果LOAD指令的下一条指令需要立刻用到读取的值，那么就在这两条指令之间插入1个周期的流水线气泡进行停顿。构成气泡的nop指令的全部控制位都是0（具体来说，主要是写入寄存器和写入内存的信号一定要为无效，其余控制信号是否有效都没关系，即可以当作任意项），并且这意味着没有任何寄存器或内存写入，也就是说程序计数器不会增加。另外，IF / ID流水线寄存器的值也被阻止改变。在下一个周期，新指令仍然从同一个内存地址读取，并且指令解码阶段用到的寄存器的值依然从未修改的IF / ID流水线寄存器中读出。
如图，and指令在第2和第3周期分别被取指、解码，但执行延迟至第5周期。
下图是添加冲突探测单元后的数据通路，符号扩展和分支逻辑没有画出来：
由图，冲突探测单元控制PC的和IF / ID流水线寄存器的写入，也控制一个MUX选择将原指令的控制信号保留还是全部输出0（即改成nop指令）。
20、前面我们说过，用分支预测可以避免控制冲突。这里我们举一些具体的例子。
假设无论分支条件是否成立，都一律按不成立的情形处理，即直接顺序执行。如果分支有50%的条件成立，那么我们有50%的概率不必等待分支指令跑完整条流水线。如果程序中的分支语句占比较多，这种办法对性能的提升还是不小的。
如果分支预测错误，则已经进入流水线的那些指令要全部丢弃。在典型的5级流水线MIPS处理器中，具体方法是：将控制信号全部置零，像处理数据冲突时插入气泡一样；不过之后我们不能直接不管取指令（IF）、译码（ID）和执行（EX）这三级的内容，而是必须将其修改，使得与指令匹配。这一步也称为恢复（流水线级间的）寄存器。对于load-use停顿，只需要在译码阶段把控制信号全部置零，然后让剩下的内容自然通过流水线。
21、有时候，分支误预测惩罚（branch misprediction penalty）还是代价太大了，而且处理分支的时间还可以缩短。MIPS支持快的单周期分支，这种支持使得分支误预测惩罚较小。大量事实证明，处理许多分支实际上很简单，比如只用比较符号，或者两数是否相等。实现这种判断不需要完整的ALU，只需要规模更小的逻辑电路。当分支的判定条件比较复杂的时候，再通过规模完整的ALU判定。
为了使得处理分支的速度加快，两个动作被移到更前的阶段：计算分支地址和条件判定。取指令后，我们已经可以利用PC的值和IF / ID流水线寄存器的值来计算分支地址了，也就是说这一步从执行（EX）阶段移到了译码阶段。其实这一步无论执行上面指令都会执行，不过只有在需要的时候才会取用结果。
对分支指令beq，我们通过对相应的位先按位异或后按位或来比较。把分支判定的步骤移到更前的阶段，意味着需要额外的转发和冲突探测硬件，因为必须保证仍在流水线上的依赖结果的分支还能够正确执行。
例如：对beq指令，我们需要将判定结果在译码阶段搞出来，有两个难点：
（1）在译码阶段必须解码指令，决定要不要旁通到比较相等的单元并完成比较，以便需要跳转时重设PC的值。转发是由ALU转发逻辑负责的，但比较相等的单元需要新的转发单元。被旁通的源操作数可以来自EX / MEM的锁存器（latch）和MEM / WB的锁存器。
（锁存器和触发器的区别是：触发器一般为边沿触发，锁存器则是电平触发，对电平敏感，易使信号产生毛刺，但面积比触发器要小很多）
（2）可能发生数据冲突并需要流水线停顿。例如：一个分支前的ALU指令产生了用于分支比较的的一个操作数，就需要一周期的停顿，因为执行阶段完毕后才能给出这个需要的数。如果LOAD后面立刻有一条条件分支指令，而且需要用到读取的数据，则需要两个周期的停顿，因为在内存访问阶段才能给出读到的数据，但译码阶段比内存访问阶段早两个周期。
但即便有这些困难，如此缩短分支的执行时间依然可以提升性能，因为误预测惩罚减小了：只需要清除掉分支指令的下一条指令。由于该指令刚刚取得，仅经过了第一个流水线阶段，因此浪费的周期只有1个。
添加了在分支误预测后刷新流水线的信号的数据通路如下图，只需要清空第一、第二阶段之间的流水线寄存器即可：
22、虽然编译器通常依赖硬件来解决流水线冲突并保证程序的正确执行，但编译器作者应当理解平台的流水线机制，以便发挥最佳性能，否则会出现意料之外的气泡拖慢代码的运行速率。
23、其实刚才说的遇到分支指令后一律按条件不成立并顺序执行处理只是一种很简单的分支预测方式。现代处理器中，多用动态分支预测（dynamic branch prediction）。动态分支预测通常需要编译器配合。在一些CPU中，流水线很深（级数很多），而且一周期可以执行多条指令（超标量（superscalar）或超长指令字（very long instruction word，VLIW）），因此分支误预测惩罚也随之升高（一旦预测错误，就要清空更多的流水线阶段乃至多条流水线）。面向对象的编程语言会产生许多难以预测的间接分支；一些略有不同的流水线停顿会导致分支延迟更高，这些都对分支预测提出了新的要求。
分支预测缓冲（branch prediction buffer），或者说分支历史表（branch history table），保存有地址的低若干位和分支预测的历史结果。如果预测错误，相应的结果会被删除，存入正确的结果。分支预测的结果是根据缓冲区中的历史记录得到的。分支预测缓冲在取指令阶段访问。
简单的1-bit预测策略在一些情况下可能会至少错2次。例如：
设一段循环中，一个条件语句总是每满足条件9次后有1次不满足。由于每次预测错误以后，预测历史都会被修改，于是在每轮循环的最后一次都会预测错误，因为先前的预测结果记录显示分支条件要满足；下一轮循环的第一次分支预测也会出错，因为上一轮循环中的最后一次结果是分支条件不满足。
2-bit策略则在连续预测错误2次以后才修改相应的历史记录。容易看出，在上面的例子中，换用2-bit策略能够将预测错误的概率从1 / 5降低到1 / 10。2-bit策略确保偶然的情形不对预测作出重大影响，在分支条件满足或不满足的概率很高的场合很有用。
分支目标缓冲（branch target buffer，BTB）是一种消除1个周期的误预测惩罚的方式。BTB是定长的哈希表（hash table），将PC的值映射到目标地址，一般至少能存储数千项。这张表记录了最近执行的一些分支指令的目标地址，并且根据PC值进行查找。如果正在执行的指令是最近执行过的分支指令，那么在BTB中会有相应的记录，称为BTB命中（BTB hit）。此时不用再等待判定该指令确为分支指令，也不用重新计算该指令的分支目标地址。于是，可以直接根据BTB中的记录进行分支预测。如果BTB中未找到相应的项，则什么都不做，一切照常进行。
关联预测器（correlated predictor）用于处理分支之间存在关联的情形。例如：
这些分支的结果存在关联，所以可以根据前面执行过的分支来进行分支预测。
竞赛预测器（tournament predictor）使用多种预测器，并追踪哪种预测器对哪一条分支的预测效果最好。一种典型的竞赛预测器为每一条分支使用两种分支预测器：一种基于分支本身的相关信息，通过PC的值来访问这些信息；一种是关联预测器，通过基于最后执行的一定数量的分支的全局历史来进行预测。
24、MIPS和ARM指令集中，都有自己的减少分支数量的方式。例如MIPS有专门的movn和movz指令，分别在指定的寄存器的值为非零和零时才执行移动操作，否则不进行任何操作。ARMv7的绝大多数指令都有专门的区域控制执行的条件，只有这些条件满足时，该指令才执行。使用这些满足一定条件才执行的指令，就不用通过专门的分支指令来实现相同的功能了。
25、流水线越长，意味着同一条指令能被拆成更多的步骤，于是每个步骤的时间理论上更短，因此CPU的频率也越高。但是流水线的长度是有限制的：一条指令不能细分成无限个步骤，而且长的流水线在预测失败时惩罚也会变高（需要清除更多的指令、恢复更多的级间寄存器，注意被清除的指令是徒增功耗），旁通数据解决流水线冲突也比较难做。当流水线的级数过长时，流水线寄存器的速度反而成了瓶颈，这时候再提升流水线级数，带来的性能提升就没有多少了。
越长的流水线意味着越复杂的内部结构，生产的良品率越发难以保证，越多的功耗将会被浪费在信号传递上，发热得不到控制的结果不言而喻。
Load-use型冒险也会在长流水线上有更长的停顿。