流水线(Pipeline)介绍

1、1处理器流水线相关技术报告人：Hardy2流水线技术v1.流水线的概念v2.流水线的冒险和冒险的解决办法v3.多发射处理器31.流水线的概念v流水线技术：把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。将多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他子过程并行进行。v流水线的描述：最常用的方法是时间-空间图横坐标：表示时间，即各个任务在流水线中所经过的时间纵坐标：表示空间，即流水线的各个子过程，也称为级、流水线深度(Stage)4流水线时间空间图5v流水线技术应用到处理器中就是采用流水线方式执行指令。一个MIPS指令包包含五个处理步骤： 1.取指

2、令周期（IF）2.指令译码/读寄存器周期（ID）3.执行操作/计算地址（EX）4.从数据存储器中读取操作数（MEM）5.将结果写回寄存器堆（WB）6采用相同的功能模块，指令顺序执行和按照流水线技术执行，在时间上可以看出流水线指令的执行速度提高了4倍。7流水线的基本作用 流水线增大了CPU的指令吞吐量即单位时间执行指令的条数，但是它未减少指令各自的执行时间。实际上流水线技术要对流水线附加一些控制，因而了增加开销，使单条指令执行时间略有增加。吞吐量的增大意味着程序运行的更快，总的执行时间变短，尽管没有一条指令的执行变快。82.流水线的冒险v尽管流水线可以带来处理器性能上的提高，但是不是所有的指令就

3、直接可以进行流水线操作，在指令执行中的下一个周期中的下一条指令不能执行，这种情况叫做冒险。有三类冒险：1.结构冒险2.数据冒险3.控制冒险流水线中的冒险会引起流水线停顿，部分指令就要延期执行。92.1 结构冒险v结构冲突（资源冲突）：流水线中多条指令在同一时钟周期内争用同一功能部件的现象。即因硬件资源满足不了指令重叠执行的要求而发生的冲突。v常见的导致结构相关的原因：功能部件不是完全流水或者资源不够用。功能部件不是完全流水或者资源不够用。 例如访存冲突例如访存冲突10结构冒险112.2 结构冒险的解决办法vMIPS指令集是为流水线设计的，在设计流水线过程中能够很容易的避免结构冒险。v但是流水结

4、构中只有一个存储器时，两条指令同时在一个存储器中预取指令就会发生结构冒险。12为消除资源冲突而插入的流水线气泡（Bubble） 时时间间（时时钟钟周周期期） 1 2 3 4 5 6 M Reg ALU M Reg M Reg ALU M Reg M Reg ALU M Reg 7 8 load 指指令令 i+1 指指令令 i+2 暂暂 停停 M Reg ALU M 指指令令 i+3 气气泡泡 气气泡泡 气气泡泡 气气泡泡 气气泡泡 13解决办法二v设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。 IM Reg ALU DM Reg IF 段段 ID 段段 E

5、X段段 MEM 段段 WB 段段 流水线寄存器流水线寄存器 142.3 数据冒险v一条指令必须等到另一条指令的完成而造成的流水线暂停的情况叫做数据冒险。形如： add $s0, $t0, $t0 sub $t2, $s0 $t3 加法指令需要到WB阶段后才写回结果，减法指令此时才可以继续执行。在不任何干预的情况下，流水线白白浪费了三个时钟周期。15 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1， R2， R3 DSUB R4，R1，R5 XOR R6，R1，R7

6、 AND R8，R1，R9 IM Reg OR R10，R1，R11 AND,OR操作不会暂停，但是DSUB,XOR指令需要等待DADD在WB阶段写回数据后才可以执行。162.4 数据冒险的解决办法v根据指令中读写访问的顺序，可以将数据冒险分为三类。分别是:v写后读（RAW）v写后写 (WAW)v读后写 (WAR) 17写后读冒险（RAW: Read After Write）v在 i 写入之前，j 先去读。j 会错误的获取旧值。v这对应“真数据相关”，为了确保j可以得到正确的i值，必须保持程序的顺序。i: DSUB R1,R2,R3j: DADD R4,R1,R318写后写冲突（WAW: Wr

7、ite After Write）v在 i 写入之前，j 先写。最后写入的结果 i 是错误的。v这对应“输出相关”，寄存器换名技术可以消除i: DSUB R1,R4,R3 j: DADD R1,R2,R3k: DMUL R6,R1,R7Cant happen in MIPS 5 stage pipeline because: - All instructions take 5 stages, and - Writes are always in stage 519读后写冲突（WAR: Write After Read）v在 i 读之前，j 先写。i 读出的内容是错误的！v这对应“反相关” ，寄存

8、器换名技术可以消除i: DSUB R4,R1,R3 j: DADD R1,R2,R3k: DMUL R6,R1,R7Cant happen in MIPS 5 stage pipeline because:- All instructions take 5 stages, and- Reads are always in stage 2, and - Writes are always in stage 5读后读RAR不是数据冒险，读操作不改变值20转发（旁路）方式解决数据冒险 形如：add $s0, $t0, $t0 sub $t2, $s0 $t3，减法指令要等到加法指令写回寄存器堆时才可

9、以执行指令，浪费了时间。转发技术：在加法指令在ALU运算一结束就将结果送给减法指令的输入项。这样从内部资源中直接提前得到缺少的运算项的过程叫做转发。21 在原始的数据通路中用流水线寄存器将流水线各部分分开，这些寄存器可以存储所有穿过它的数据，寄存器的宽度都足够大。目前流行的有128位，97位，64位。 有了流水线寄存器后，转发就变的简单了。在指令执行的五个阶段中间各加了个寄存器记录流过的数据。22如图所示，加法指令后面的取字指令没有等到加法指令写回R1后再执行，而是提前就获得了R1的数据，减少了等待时间。 时 间 （ 时 钟 周 期 ） 1 2 3 4 5 6 IM Reg ALU DM Re

10、g IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU ADD R1， R2， R3 SUB R4， R1， R5 XOR R6， R1， R7 AND R8，R1，R9 IM Reg OR R10， R1， R11 23转发技术不能解决所有的数据冒险当一条指令试图读取一个由前一条装载指令读入的寄存器时，就无法使用转发解决数据冒险问题了。24v对于装载指令的存在，我们采用了插入阻塞（气泡，）方法解决问题。增加一个冒险检测单元，一旦发现装载指令后就在其他需要这个结果的指令前插入阻塞。直到可以使用转发技术或指令可以得到结果为止。25编译器调度（静态调度）v插入阻塞

11、对于流水线来说仍然是暂停了流水线的执行。既然转发技术无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？ v实际上，编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技术为 指令调度（instruction scheduling）。v原理：相关不一定引起阻塞，只要隔开足够远在一个流水线上引起阻塞，在另一个流水线上不一定引起阻塞，编译优化与机器有关26 例例1 请为下列表达式生成没有暂停的流水线请为下列表达式生成没有暂停的流水线v 指令序列：指令序列：v abc ；v def ；v 假设载入延迟为假设载入延迟为1个时钟周

12、期。个时钟周期。两条ALU指令（ADD Ra，Rb，Rc 和 SUB Rd，Re，Rf）分别和两条Load指令（LW Rc，c和LW Rf，f）之间存在数据相关。为了保证流水线正确执行调度前的指令序列，必须在指令执行过程中插入两个时钟周期的暂停。但是考察调度后的指令序列不难发现，由于流水线允许转发，就不必在指令执行过程中插入任何暂停周期。 27LD RbLD Rb，B BIFIFIDIDEXEXMEMEM MWBWBLD RcLD Rc，C CIFIFIDIDEXEX MEMMEM WBWBADD RaADD Ra，RbRb，RcRc IFIFIDID 停停EXEX MEMMEM WBWBSD

13、 RaSD Ra，A AIFIF 停停IDIDEXEX MEMMEM WBWBLD ReLD Re，E EIFIFIDIDEXEX MEMMEM WBWBLD RfLD Rf，F FIFIFIDIDEXEX MEMMEM WBWBSUB RdSUB Rd，ReRe，RfRfIFIFIDID停停EXEX MEMMEM WBWBSD RdSD Rd，D D IFIF停停IDIDEXEX MEMMEM WBWB调度前执行情况（采用了转发技术）28LD RbLD Rb，B BIFIFIDIDEXEX MEMMEM WBWBLD RcLD Rc，C CIFIFIDIDEXEX MEMMEM WBWBLD

14、 ReLD Re，E EIFIFIDIDEXEX MEMMEM WBWBADD RaADD Ra，RbRb，RcRcIFIFIDIDEXEX MEMMEM WBWBLD RfLD Rf，F FIFIFIDIDEXEX MEMMEM WBWBSD RaSD Ra，A AIFIFIDIDEXEX MEMMEM WBWBSUB RdSUB Rd，ReRe，RfRfIFIFIDIDEXEX MEMMEM WBWBSD RdSD Rd，D D IFIFIDIDEXEX MEMMEM WBWB调度后执行情况（采用了转发技术）29动态调度v有些信息在译码时难以确定，如是否发生异常、访存操作需要多少周期等，静

15、态调度就不能完成。v动态调度：硬件会重新安排指令的执行顺序以减少停顿并同时保持数据流和异常行为。v优点：有些相关编译无法检测、编译器更加简单、程序性能对机器依赖少30动态调度的思想v基本思想 ：把相关的解决尽量延迟到马上就会出错的时候 前面指令的stall不影响后面指令继续前进v把译码分成两个阶段：发射和读操作数 发射：指令译码，检查结构相关 读操作数：检查操作数是否准备好，准备好就 读数，否则等待，当一条指令在读操作数阶段 等待时，后面指令的发射可以继续进行v乱序执行： 指令进入是有序的 执行可以乱序，只要没有相关就可执行，多条 指令同时执行 结束可以乱序，也可以有序（主要是精确例外 的需要

16、），乱序结束会导致WAR相关（静态 流水线中只有RAW和WAW相关）31Tomasulo算法vIBM 360/91中首次使用，由Robert Tomasulo提出的一种支持乱序执行的高级方案。它会跟踪指令的操作数何时可用，将RAW冒险降至最低，并在硬件中引入寄存器重命名功能，将WAW和WAR冒险降至最低。v现代处理器使用了该算法的各种变体，但是核心都是： 1.跟踪指令相关以允许在操作数可用时立即执行指令。 2.重命名寄存器以避免WAR和WAW冒险。3233Tomasulo算法的流水阶段 1.发射：把操作队列的指令根据操作类型送到保留站（如果保留站有空），发射过程中读寄存器的值和结果状态域 2.

17、执行：如果所需的操作数都准备好，则执行，否则侦听结果总线并接收结果总线的值。 3.写回：把结果送到结果总线，释放保留站343536373839Tomasulo算法小结v通过动态调度缓解流水线阻塞：例如减少CACHE失效对性能的影响v保留站：重命名寄存器+缓存源操作数 避免寄存器成为瓶颈 避免WAW和WAR阻塞v缺点： 硬件复杂性 结果总线成为瓶颈，多条结果总线增加硬件复杂度40 流水线技术一直是提高处理器速度的最有效技术之一。但目前的在相关处插入阻塞，转发技术，编译器调度都是尽量分离相关问题的指令，使他们不会导致冲突，从而减少暂停的影响。虽然都会相应的显著减少数据相关的次数提高流水效率，但也会

18、不可避免的增加硬件复杂度和编译器的复杂性。 而动态调度则可以以硬件的方式调整指令执行顺序，使不相关的后续指令得以不受暂停的影响而继续执行，可以在降低编译器复杂度的同时处理一些编译阶段无法知道的相关，在出现数据冒险是尽量避免出现流水暂停。412.5 控制冒险v也叫分支冒险，指因为程序的执行方向可能被改变而引起的流水线暂停叫做控制冒险。 v执行分支指令，程序计数器PC值两种情况：PC值改变为目标地址（转移成功）PC值保持正常（转移失败，顺序执行），PC+4。vPC值不定，所以流水线需要暂停，直到确定了新的PC值为止42由于分支指令在MEM阶段才确定是否执行分支，分支后面的三个指令都要被取回并执行。

19、432.6 控制冒险的解决办法v1. 处理分支指令最简单的方法:v一旦检测到分支指令(在ID段)，就暂停执行其后的指令，直到分支指令到达MEM段，确定出新的PC值为止。v特点：简单但是速度非常慢。44v2.缩短分支延迟v确定分支目标地址越早，需要清除的指令就越少。将分支执行提前到ID级。v首先计算分支目标地址：在IF/ID流水线寄存器中就有了PC值和立即数，增加一个加法器就可以得到目标地址。v分支判断：判断从ID级取到的两个寄存器的值是否相等，对应的位进行异或操作即可。45v3.延迟分支：把分支开销为n 的分支指令看成是延迟长度为n 的分支指令，其后紧跟有n 个延迟槽。流水线遇到分支指令时，按正常方式处理，顺带执行延迟槽中的指令（不影响分支的一条指令），从而减少分支开销。v特点：对于每个时钟周期发射一条指令的五级流水线处理器而言，延迟分支简单有效。但是随着处理器向着更深流水线发展和单周期多指令方向发展。延迟分支作用不大。46v4.预测分支不发生v假设分式不发生，继续执行顺序的指令流。如果分支发生了，就丢弃已经读取并译码的指令，按照分支目标继续执行。v特点：如果分支发生的可能性较大，并且丢弃指令的代价很小的话，这种优化方法可以减小