流水线(Pipeline)介绍.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,1,处理器流水线相关技术,报告人：,Hardy,2,流水线技术,1.,流水线的概念,2.,流水线的冒险和冒险的解决办法,3.,多发射处理器,3,1.,流水线的概念,流水线技术,：,把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。将多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他子过程并行进行。,流水线的描述,：最常用的方法是时间,-,空间图,横坐标,：表示,时间,，即各个任务在流水线中所经过的时间,纵坐标,：表示,空间,，即流水线的各个子过程，也称为,级、流水线深度,(Stage),4,流水线时间空间图,5,流水线技术应用到处理器中就是采用流水线方式执行指令。一个,MIPS,指令包包含五个处理步骤：,1.,取指,令周期（,IF,）,2.,指令,译码,/,读寄存器周期（,ID,）,3.,执行,操作,/,计算地址（,EX,）,4.,从数据存储器中,读取,操作数（,MEM,）,5.,将结果,写回,寄存器堆（,WB,）,6,采用相同的功能模块，指令顺序执行和按照流水线技术执行，在时间上可以看出流水线指令的执行速度提高了,4,倍。,7,流水线的基本作用,流水线增大了,CPU,的指令吞吐量,即单位时间执行指令的条数，但是它未减少指令各自的执行时间。实际上流水线技术要对流水线附加一些控制，因而了增加开销，使单条指令执行时间略有增加。,吞吐量的增大意味着程序运行的更快，总的执行时间变短，尽管没有一条指令的执行变快。,8,2.,流水线的冒险,尽管流水线可以带来处理器性能上的提高，但是不是所有的指令就直接可以进行流水线操作，在指令执行中的下一个周期中的下一条指令不能执行，这种情况叫做,冒险,。,有三类冒险：,1.,结构冒险,2.,数据冒险,3.,控制冒险,流水线中的冒险会引起流水线停顿，部分指令就要延期执行。,9,2.1,结构冒险,结构冲突（资源冲突）：,流水线中多条指令在同一时钟周期,内争用同一功能部件,的现象。即因硬件资源满足不了指令重叠执行的要求而发生的冲突。,常见的导致结构相关的原因：,功能部件不是完全流水或者资源不够用。,例如访存冲突,10,结构冒险,11,2.2,结构冒险的解决办法,MIPS,指令集是为流水线设计的，在设计流水线过程中能够很容易的避免结构冒险。,但是流水结构中只有一个存储器时，两条指令同时在一个存储器中预取指令就会发生结构冒险。,12,为消除资源冲突而插入的流水线,气泡,（,Bubble,）,13,解决办法二,设置相互独立的,指令存储器和数据存储器,或设置相互独立的,指令,Cache,和数据,Cache,。,14,2.3,数据冒险,一条指令必须等到另一条指令的完成而造成的流水线暂停的情况叫做,数据冒险,。形如：,adds0,$t0,$t0,sub$t2,$s0$t3,加法指令需要到,WB,阶段后才写回结果，减法指令此时才可以继续执行。在不任何干预的情况下，流水线白白浪费了三个时钟周期。,15,AND,OR,操作不会暂停，但是,DSUB,XOR,指令需要等待,DADD,在,WB,阶段写回数据后才可以执行。,16,2.4,数据冒险的解决办法,根据指令中读写访问的顺序，可以将数据冒险分为三类。分别是,:,写后读（,RAW,）,写后写,(WAW),读后写,(WAR),17,写后读冒险（,RAW:Read After Write,）,在,i,写入之前，,j,先去读。,j,会错误的获取旧值。,这对应“,真数据相关,”为了确保,j,可以得到正确的,i,值，必须保持程序的顺序。,i:DSUB,R1,R2,R3,j:DADD R4,R1,R3,18,写后写冲突（,WAW:Write After Write,）,在,i,写入之前，,j,先写。最后写入的结果,i,是错误的。,这对应“,输出相关,”，寄存器换名技术可以消除,i:DSUB,R1,R4,R3,j:DADD,R1,R2,R3,k:DMUL R6,R1,R7,Cant happen in MIPS 5 stage pipeline because:,-All instructions take 5 stages,and,-Writes are always in stage 5,19,读后写冲突（,WAR:Write After Read,）,在,i,读之前，,j,先写。,i,读出的内容是错误的！,这对应“,反相关,”，寄存器换名技术可以消除,i:DSUB R4,R1,R3,j:DADD,R1,R2,R3,k:DMUL R6,R1,R7,Cant 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,，减法指令要等到加法指令写回寄存器堆时才可以执行指令，浪费了时间。转发技术：在加法指令在,ALU,运算一结束就将结果送给减法指令的输入项。,这样从内部资源中直接提前得到缺少的运算项的过程叫做转发,。,21,在原始的数据通路中用,流水线寄存器,将流水线各部分分开，这些寄存器可以存储所有穿过它的数据，寄存器的宽度都足够大。目前流行的有,128,位，,97,位，,64,位。,有了流水线寄存器后，转发就变的简单了。在指令执行的五个阶段中间各加了个寄存器记录流过的数据。,22,如图所示，加法指令后面的取字指令没有等到加法指令写回,R1,后再执行，而是提前就获得了,R1,的数据，减少了等待时间。,23,转发技术不能解决所有的数据冒险,当一条指令试图读取一个由前一条装载指令读入的寄存器时，就无法使用转发解决数据冒险问题了。,24,对于装载指令的存在，我们采用了,插入阻塞（气泡，）,方法解决问题。增加一个,冒险检测单元，,一旦发现装载指令后就在其他需要这个结果的指令前插入阻塞。直到可以使用转发技术或指令可以得到结果为止。,25,编译器调度（静态调度）,插入阻塞对于流水线来说仍然是暂停了流水线的执行。既然转发技术无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？,实际上，编译器的确可以通过,重新组织代码顺序,来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技术为,指令调度,（,instruction scheduling,）。,原理：,相关不一定引起阻塞，只要隔开足够远,在一个流水线上引起阻塞，在另一个流水线上不一定引起阻塞,，编译优化与机器有关,26,例,1,请为下列表达式生成没有暂停的流水线,指令序列：,a,b,c,；,d,e,f,；,假设载入延迟为,1,个时钟周期。,两条,ALU,指令（,ADD Ra,，,Rb,，,Rc,和,SUB Rd,，,Re,，,Rf,）分别和两条,Load,指令（,LW Rc,，,c,和,LW Rf,，,f,）之间存在数据相关。为了保证流水线正确执行调度前的指令序列，必须在指令执行过程中插入两个时钟周期的暂停。但是考察调度后的指令序列不难发现，,由于流水线允许转发，就不必在指令执行过程中插入任何暂停周期。,27,LD Rb,，,B,IF,ID,EX,MEM,WB,LD Rc,，,C,IF,ID,EX,MEM,WB,ADD Ra,，,Rb,，,Rc,IF,ID,停,EX,MEM,WB,SD Ra,，,A,IF,停,ID,EX,MEM,WB,LD Re,，,E,IF,ID,EX,MEM,WB,LD Rf,，,F,IF,ID,EX,MEM,WB,SUB Rd,，,Re,，,Rf,IF,ID,停,EX,MEM,WB,SD Rd,，,D,IF,停,ID,EX,MEM,WB,调度前执行情况（采用了转发技术）,28,LD Rb,，,B,IF,ID,EX,MEM,WB,LD Rc,，,C,IF,ID,EX,MEM,WB,LD Re,，,E,IF,ID,EX,MEM,WB,ADD Ra,，,Rb,，,Rc,IF,ID,EX,MEM,WB,LD Rf,，,F,IF,ID,EX,MEM,WB,SD Ra,，,A,IF,ID,EX,MEM,WB,SUB Rd,，,Re,，,Rf,IF,ID,EX,MEM,WB,SD Rd,，,D,IF,ID,EX,MEM,WB,调度后执行情况（采用了转发技术）,29,动态调度,有些信息在译码时难以确定，如是否发生异常、访存操作需要多少周期等，静态调度就不能完成。,动态调度：硬件会重新安排指令的执行顺序以减少停顿并同时保持数据流和异常行为。,优点：有些相关编译无法检测、编译器更加简单、程序性能对机器依赖少,30,动态调度的思想,基本思想：,把相关的解决尽量延迟到马上就会出错的时候,前面指令的,stall,不影响后面指令继续前进,把译码分成两个阶段：发射和读操作数,发射：指令译码，检查结构相关,读操作数：检查操作数是否准备好，准备好就,读数，否则等待，当一条指令在读操作数阶段,等待时，后面指令的发射可以继续进行,乱序执行：,指令进入是有序的,执行可以乱序，只要没有相关就可执行，多条,指令同时执行,结束可以乱序，也可以有序（主要是精确例外,的需要），乱序结束会导致,WAR,相关（静态,流水线中只有,RAW,和,WAW,相关）,31,Tomasulo,算法,IBM 360/91,中首次使用，由,Robert Tomasulo,提出的一种支持乱序执行的高级方案。它会跟踪指令的操作数何时可用，将,RAW,冒险降至最低，并在硬件中引入寄存器重命名功能，将,WAW,和,WAR,冒险降至最低。,现代处理器使用了该算法的各种变体，但是核心都是：,1.,跟踪指令相关以允许在操作数可用时立即执行指令。,2.,重命名寄存器以避免,WAR,和,WAW,冒险32,33,Tomasulo,算法的流水阶段,1.,发射：把操作队列的指令根据操作类型送到保留站（如果保留站有空），发射过程中读寄存器的值和结果状态域,2.,执行：如果所需的操作数都准备好，则执行，否则侦听结果总线并接收结果总线的值。,3.,写回：把结果送到结果总线，释放保留站,34,35,36,37,38,39,Tomasulo,算法小结,通过动态调度缓解流水线阻塞：例如减少,CACHE,失效对性能的影响,保留站：重命名寄存器,+,缓存源操作数,避免寄存器成为瓶颈,避免,WAW,和,WAR,阻塞,缺点：,硬件复杂性,结果总线成为瓶颈，多条结果总线增加硬件复杂度,40,流水线技术一直是提高处理器速度的最有效技术之一。但目前的在相关处插入阻塞，转发技术，编译器调度都是尽量,分离相关问题的指令,，使他们不会导致冲突，从而减少暂停的影响。虽然都会相应的显著减少数据相关的次数提高流水效率，但也会不可避免的增加硬件复杂度和编译器的复杂性。,而动态调度则可以,以硬件的方式,调整指令执行顺序，,使不相关的后续指令得以不受暂停,的影响而继续执行，可以在降低编译器复杂度的同时处理一些编译阶段无法知道的相关，在出现数据冒险是尽量避免出现流水暂停。,41,2.5,控制冒险,也叫分支冒险，,指因为程序的执行方向可能被改变而引起的流水线暂停,叫做,控制冒险,。,执行分支指令，程序计数器,PC,值两种情况PC,值改变为目标地址（转移,成功,）,PC,值保持正常（转移,失败,，顺序执行），,PC+4,。,PC,值不定，所以流水线需要暂停，直到确定了新的,PC,值为止,42,由于分支指令在,MEM,阶段才确定是否执行分支，分支后面的三个指令都要被取回并执行。,43,2.6,控制冒险的解决办法,1.,处理分支指令最简单的方法,:,一旦检测到分支指令,(,在,ID,段,),，就暂停执行其后的指令，直到分支指令到达,MEM,段，确定出新的,PC,值为止。,特点：简单但是速度非常慢。,44,2.,缩短分支延迟,确定分支目标地址越早，需要清除的指令就越少。,将分支执行提前到,ID,级,。,首先计算分支目标地址：在,IF/ID,流水线寄存器中就有了,PC,值和立即数，增加一个加法器就可以得到目标地址。,分支判断：判断从,ID,级取到的两个寄存器的值是否相等，对应的位进行异或操作即可。,45,3.,延迟分支：,把分支开销为,n,的分支指令看成是延迟长度为,n,的分支指令，其后紧跟有,n,个延迟槽。流水线遇到分支指令时，按正常方式处理，,顺带执行延迟槽中的指令（不影响分支的一条指令），,从而减少分支开销。,特点：对于每个时钟周期发射一条指令的五级流水线处理器而言，延迟分支简单有效。但是随着处理器向着更深流水线发展和单周期多指令方向发展。延迟分支作用不大。,46,4.,预测分支不发生,假设分式不发生继续执行顺序的指令流。如果分支发生了，就丢弃已经读取并译码的指令，按照分支目标继续执行。,特点：如果分支发生的可能性较大，并且丢弃指令的代价很小的话，这种优化方法可以减小控制冒险的损失。,47,5.,预测分支成功,假设分支转移成功，并开始从分支目标地址处取指令执行。,起作用的前题：先知道分支目标地址，后知道分支是否成功。,特点：,因为在,5,段流水线中总是先得到转移的结果，后得到目标的地址，所以不适用于,5,段流水。适合那些隐含条件码和更强功能转移条件的机器中，转移的目标地址比其结果更早产生，这时采用预测转移被选中的方法比较合适,。,48,6.,动态分支预测：假设分支是否发生是一种粗略的预测分支方法。一种策略是通过查找指令的地址观察上一次执行该指令时分支是否发生，,如果上次执行时分支发生就从上次分支发生的地方开始取新的指令,，这种技术叫做,动态分支预测,。,实现方式：使用,分支预测缓存,或,分支历史记录表。,缓存是一小块按照分支指令的地址地位索引的存储器区，包括了一位或多位数据用以说明最近是否发生过分支。,特点：开销大但是灵活高效。,49,最新的分支预测方法,竞赛预测器：,竞赛预测器对每个分支使用多个预测器，并记录哪个预测器效果最好。这样可以为特定的分支选择正确的预测器。,典型的竞赛预测器对每个分支地址有两个预测：一个是基于局部信息，一个是基于全局分支的行为。用一个选择器来选择由那个预测器来预测结果。,50,多发射处理器,为了进一步提高处理器性能，前面的技术让,CPI,接近理想值,1,了，不能再小了。产生了多,发射处理器：允许一个始终周期发送多条指令。,主要由以下几类多发射处理器：,VLIW,（超长指令字）处理器（将多个操作包装在一个非常长的指令里）,超标量处理器（每个周期发送多条指令）,51,Thank You,！,