流水线(Pipeline)介绍

1处理器流水线相关技术报告人：Hardy2流水线技术1.流水线的概念2.流水线的冒险和冒险的解决办法3.多发射处理器31.流水线的概念流水线技术：把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。将多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他子过程并行进行。流水线的描述：最常用的方法是时间-空间图横坐标：表示时间，即各个任务在流水线中所经过的时间纵坐标：表示空间，即流水线的各个子过程，也称为级、流水线深度(Stage)4流水线时间空间图5流水线技术应用到处理器中就是采用流水线方式执行指令。一个MIPS指令包包含五个处理步骤：1.取指令周期（IF）2.指令译码/读寄存器周期（ID）3.执行操作/计算地址（EX）4.从数据存储器中读取操作数（MEM）5.将结果写回寄存器堆（WB）6采用相同的功能模块，指令顺序执行和按照流水线技术执行，在时间上可以看出流水线指令的执行速度提高了4倍。7流水线的基本作用流水线增大了CPU的指令吞吐量—即单位时间执行指令的条数，但是它未减少指令各自的执行时间。实际上流水线技术要对流水线附加一些控制，因而了增加开销，使单条指令执行时间略有增加。吞吐量的增大意味着程序运行的更快，总的执行时间变短，尽管没有一条指令的执行变快。82.流水线的冒险尽管流水线可以带来处理器性能上的提高，但是不是所有的指令就直接可以进行流水线操作，在指令执行中的下一个周期中的下一条指令不能执行，这种情况叫做冒险。有三类冒险：1.结构冒险2.数据冒险3.控制冒险流水线中的冒险会引起流水线停顿，部分指令就要延期执行。92.1结构冒险结构冲突（资源冲突）：流水线中多条指令在同一时钟周期内争用同一功能部件的现象。即因硬件资源满足不了指令重叠执行的要求而发生的冲突。常见的导致结构相关的原因：功能部件不是完全流水或者资源不够用。例如访存冲突10结构冒险112.2结构冒险的解决办法MIPS指令集是为流水线设计的，在设计流水线过程中能够很容易的避免结构冒险。但是流水结构中只有一个存储器时，两条指令同时在一个存储器中预取指令就会发生结构冒险。12为消除资源冲突而插入的流水线气泡（Bubble）时间（时钟周期）123456MRegALUMRegMRegALUMRegMRegALUMReg78load指令i+1指令i+2暂停MRegALUM指令i+3气泡气泡气泡气泡气泡13解决办法二设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。IMRegALUDMRegIF段ID段EX段MEM段WB段流水线寄存器142.3数据冒险一条指令必须等到另一条指令的完成而造成的流水线暂停的情况叫做数据冒险。形如：add$s0,$t0,$t0sub$t2,$s0$t3加法指令需要到WB阶段后才写回结果，减法指令此时才可以继续执行。在不任何干预的情况下，流水线白白浪费了三个时钟周期。15时间（时钟周期）123456IMRegALUDMRegIMRegALUDMRegIMRegALUDMIMRegALUDADDR1，R2，R3DSUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9IMRegORR10，R1，R11AND,OR操作不会暂停，但是DSUB,XOR指令需要等待DADD在WB阶段写回数据后才可以执行。162.4数据冒险的解决办法根据指令中读写访问的顺序，可以将数据冒险分为三类。分别是:写后读（RAW）写后写(WAW)读后写(WAR)17写后读冒险（RAW:ReadAfterWrite）在i写入之前，j先去读。j会错误的获取旧值。这对应“真数据相关”，为了确保j可以得到正确的i值，必须保持程序的顺序。i:DSUBR1,R2,R3j:DADDR4,R1,R318写后写冲突（WAW:WriteAfterWrite）在i写入之前，j先写。最后写入的结果i是错误的。这对应“输出相关”，寄存器换名技术可以消除i:DSUBR1,R4,R3j:DADDR1,R2,R3k:DMULR6,R1,R7Can’thappeninMIPS5stagepipelinebecause:-Allinstructionstake5stages,and-Writesarealwaysinstage519读后写冲突（WAR:WriteAfterRead）在i读之前，j先写。i读出的内容是错误的！这对应“反相关”，寄存器换名技术可以消除i:DSUBR4,R1,R3j:DADDR1,R2,R3k:DMULR6,R1,R7Can’thappeninMIPS5stagepipelinebecause:-Allinstructionstake5stages,and-Readsarealwaysinstage2,and-Writesarealwaysinstage5读后读RAR不是数据冒险，读操作不改变值20转发（旁路）方式解决数据冒险形如：add$s0,$t0,$t0sub$t2,$s0$t3，减法指令要等到加法指令写回寄存器堆时才可以执行指令，浪费了时间。转发技术：在加法指令在ALU运算一结束就将结果送给减法指令的输入项。这样从内部资源中直接提前得到缺少的运算项的过程叫做转发。21在原始的数据通路中用流水线寄存器将流水线各部分分开，这些寄存器可以存储所有穿过它的数据，寄存器的宽度都足够大。目前流行的有128位，97位，64位。有了流水线寄存器后，转发就变的简单了。在指令执行的五个阶段中间各加了个寄存器记录流过的数据。22如图所示，加法指令后面的取字指令没有等到加法指令写回R1后再执行，而是提前就获得了R1的数据，减少了等待时间。时间（时钟周期）123456IMRegALUDMRegIMRegALUDMRegIMRegALUDMIMRegALUADDR1，R2，R3SUBR4，R1，R5XORR6，R1，R7ANDR8，R1，R9IMRegORR10，R1，R1123转发技术不能解决所有的数据冒险当一条指令试图读取一个由前一条装载指令读入的寄存器时，就无法使用转发解决数据冒险问题了。24对于装载指令的存在，我们采用了插入阻塞（气泡，）方法解决问题。增加一个冒险检测单元，一旦发现装载指令后就在其他需要这个结果的指令前插入阻塞。直到可以使用转发技术或指令可以得到结果为止。25编译器调度（静态调度）插入阻塞对于流水线来说仍然是暂停了流水线的执行。既然转发技术无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？实际上，编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技术为指令调度（instructionscheduling）。原理：相关不一定引起阻塞，只要隔开足够远•在一个流水线上引起阻塞，在另一个流水线上不一定引起阻塞，编译优化与机器有关26例1请为下列表达式生成没有暂停的流水线指令序列：a＝b＋c；d＝e－f；假设载入延迟为1个时钟周期。两条ALU指令（ADDRa，Rb，Rc和SUBRd，Re，Rf）分别和两条Load指令（LWRc，c和LWRf，f）之间存在数据相关。为了保证流水线正确执行调度前的指令序列，必须在指令执行过程中插入两个时钟周期的暂停。但是考察调度后的指令序列不难发现，由于流水线允许转发，就不必在指令执行过程中插入任何暂停周期。27LDRb，BIFIDEXMEMWBLDRc，CIFIDEXMEMWBADDRa，Rb，RcIFID停EXMEMWBSDRa，AIF停IDEXMEMWBLDRe，EIFIDEXMEMWBLDRf，FIFIDEXMEMWBSUBRd，Re，RfIFID停EXMEMWBSDRd，DIF停IDEXMEMWB调度前执行情况（采用了转发技术）28LDRb，BIFIDEXMEMWBLDRc，CIFIDEXMEMWBLDRe，EIFIDEXMEMWBADDRa，Rb，RcIFIDEXMEMWBLDRf，FIFIDEXMEMWBSDRa，AIFIDEXMEMWBSUBRd，Re，RfIFIDEXMEMWBSDRd，DIFIDEXMEMWB调度后执行情况（采用了转发技术）29动态调度有些信息在译码时难以确定，如是否发生异常、访存操作需要多少周期等，静态调度就不能完成。动态调度：硬件会重新安排指令的执行顺序以减少停顿并同时保持数据流和异常行为。优点：有些相关编译无法检测、编译器更加简单、程序性能对机器依赖少30动态调度的思想基本思想：•把相关的解决尽量延迟到马上就会出错的时候•前面指令的stall不影响后面指令继续前进把译码分成两个阶段：发射和读操作数•发射：指令译码，检查结构相关•读操作数：检查操作数是否准备好，准备好就读数，否则等待，当一条指令在读操作数阶段等待时，后面指令的发射可以继续进行•乱序执行：•指令进入是有序的•执行可以乱序，只要没有相关就可执行，多条指令同时执行•结束可以乱序，也可以有序（主要是精确例外的需要），乱序结束会导致WAR相关（静态流水线中只有RAW和WAW相关）31Tomasulo算法IBM360/91中首次使用，由RobertTomasulo提出的一种支持乱序执行的高级方案。它会跟踪指令的操作数何时可用，将RAW冒险降至最低，并在硬件中引入寄存器重命名功能，将WAW和WAR冒险降至最低。现代处理器使用了该算法的各种变体，但是核心都是：1.跟踪指令相关以允许在操作数可用时立即执行指令。2.重命名寄存器以避免WAR和WAW冒险。3233Tomasulo算法的流水阶段1.发射：把操作队列的指令根据操作类型送到保留站（如果保留站有空），发射过程中读寄存器的值和结果状态域2.执行：如果所需的操作数都准备好，则执行，否则侦听结果总线并接收结果总线的值。3.写回：把结果送到结果总线，释放保留站343536373839Tomasulo算法小结通过动态调度缓解流水线阻塞：例如减少CACHE失效对性能的影响保留站：重命名寄存器+缓存源操作数•避免寄存器成为瓶颈•避免WAW和WAR阻塞•缺点：•硬件复杂性•结果总线成为瓶颈，多条结果总线增加硬件复杂度40流水线技术一直是提高处理器速度的最有效技术之一。但目前的在相关处插入阻塞，转发技术，编译器调度都是尽量分离相关问题的指令，使他们不会导致冲突，从而减少暂停的影响。虽然都会相应的显著减少数据相关的次数提高流水效率，但也会不可避免的增加硬件复杂度和编译器的复杂性。而动态调度则可以以硬件的方式调整指令执行顺序，使不相关的后续指令得以不受暂停的影响而继续执行，可以在降低编译器复杂度的同时处理一些编译阶段无法知道的相关，在出现数据冒险是尽量避免出现流水暂停。412.5控制冒险也叫分支冒险，指因为程序的执行方向可能被改变而引起的流水线暂停叫做控制冒险。执行分支指令，程序计数器PC值两种情况：PC值改变为目标地址（转移成功）PC值保持正常（转移失败，顺序执行），PC+4。PC值不定，所以流水线需要暂停，直到确定了新的PC值为止42由于分支指令在MEM阶段才确定是否执行分支，分支后面的三个指令都要被取回并执行。432.6控制冒险的解决办法1.处理分支指令最简单的方法:一旦检测到分支指令(在ID段)，就暂停执行其后的指令，直到分支指令到达MEM段，确定出新的PC值为止。特点：简单但是速度非常慢。442.缩短分支延迟确定分支目标地址越早，需要清除的指令就越少。将分支执行提前到ID级。首先计算分支目标地址：在IF/ID流水线寄存器中就有了PC值和立即数，增加一个加法器就可以得到目标地址。分支判断：判断从ID级取到的两个寄存器的值是否相等，对应的位进行异或操作即可。453.延迟分支：把分支开销为n的分支指令看成是延迟长度为n的分支指令，其后紧跟有n个延迟槽。流水线遇到分支指令时，按正常方式处理，顺带执行延迟槽中的指令（不影响分支的一条指令），从而减少分支开销。特点