资源描述
单击此处编辑母版标题样式,2014.2.17,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第5章 指令级并行硬件方法（,P111）,（,指令级，多发射或乱序执行，动态调度）,本章学习由硬件（即流水线控制器）实现的指令级并行方法，主要内容是流水线的多指令控制技术，目的是让处理机中同时流动更多的指令，减少各种原因造成的停顿，以缩短程序执行时间。,5.1 指令级并行的概念（重点）,5.2 相关与指令级并行,5.3 指令的动态调度,5.4 动态分支预测技术（重点）,5.5 多指令流出技术（重点）,从执行程序的角度来看，并行性等级从低到高可分为：,指令内部并行：单条指令中各微操作之间的并行。,指令级并行：并行执行两条或两条以上的指令。,线程级并行：并行执行两个或两个以上的线程。通常是以一个进程内派生的多个线程为调度单位。,任务级或过程级并行：并行执行两个或两个以上的过程或任务（程序段）。以子程序或进程为调度单元。,作业或程序级并行：并行执行两个或两个以上的作业或程序。,并行性等级的划分（,P23，1.5.1,节）,指令级并行的英文缩写是,ILP,（,Instruction-Level Parallelism）,开发,ILP,的途径有两种：,资源重复，重复设置多个处理部件，让它们同时执行相邻或相近的多条指令；,采用流水线技术，使指令重叠并行执行。,(1)狭义指令级并行 超标量,SuperScalar,（,设备重复） 超长指令字,Very Long Instruction Word（,简称,VLIW）,(2)广义指令级并行 流水线,Pipeline,（,设备细分） 超级流水线,Super Pipeline,(3)线程级并行 超线程,Hyper-Threading（,简称,HT）,(4)任务线程 多核处理机,Multicore,5.1 指令级并行的概念,静态调度（软件方法）：在程序执行前，在编译过程中对目标指令序列进行优化，避免将来由于相关和冲突造成的停顿。主要手段是将冲突指令错开启动时间、变量换名等。,动态调度（硬件方法）：在程序执行中，由专门硬件预测将要发生的冲突、控制指令在流水线中的流动，避免停顿。,2. 流水线处理机的实际,CPI =,理想流水线的,CPI,加上各类停顿的时钟周期数：,CPI,流水线,=,CPI,理想,+ 停顿,结构冲突,+ 停顿,数据冲突,+ 停顿,控制冲突,CPI,理想,是衡量流水线最高性能的一个指标。本式表明降低实际,CPI,有许多途径。,换一个角度，有时从,CPI,的倒数看问题会有新思路，,IPC（Instructions Per Cycle）,是每个时钟周期完成的指令条数。,在不能缩短单条指令周期数的情况下，在每个时钟周期里启动更多的指令（提高,IPC），,同样可以提高处理机的性能。这就是,ILP,的基本思想。,1. 开发,ILP,的方法分类,基本程序块：一串连续的代码除了入口和出口以外，没有其他的分支指令和转入点 。,程序平均每47条指令就会有一个分支。,4. 循环级并行：使一个循环中的不同循环体并行执行。,开发循环的不同叠代之间存在的并行性（最常见、最基本思路）,这是指令级并行研究的重点之一,5. 最基本的开发循环级并行的技术,循环展开（,loop unrolling）,技术,采用向量指令和向量数据表示,3. 基本程序块,多发射技术（,Multiple Issue）：,同时启动多条指令。,为什么要多发射？在传统流水线上，要减少,CPU,时间，可以减少,CPI,或者,Cycle。CPI,的下限是1，减少,Cycle,碰到了“4,G,墙”（指,Intel,公司开发4,GHz P4,计划失败，因为功耗正比于主频3次方），工程师们无奈又回头来打,CPI,的主意，想使,CPI,低于1，即在一个时钟周期内流出多条指令。,狭义的多指令流出技术（同时启动）包括超标量(,Superscalar),和超长指令字(,VLIW)，,广义的多指令流出技术（分时启动）还包括超流水线(,Superpipeline),等。,超标量采用多条流水线的多发射技术，每个时钟周期流出的指令数不定，既可以使用编译器静态调度，也可以使用硬件动态调度。 由于管理乱序流动中指令相关问题的硬件复杂度非常大，所以目前超标量,CPU,的,ILP,没有超过8的。,采用单发射技术的传统处理机又被称为“标量处理机”。,5.5 多指令流出技术（又称多发射技术，,P141）,超长指令字,CPU,采用长指令单发射，多个执行部件同时执行小指令的方法，每个时钟周期流出的小指令数是限定的。在编译过程中，由编译程序来判断实际指令之间的相关关系，进行静态调度，把抽取,ILP,的复杂工作转移给编译器，而执行指令的硬件则大大简化，也比较规则，有利于低功耗设计。,超流水线则是将每个功能部件进一步流水化，使得一个功能部件在一拍中可以分时处理多条指令。,5.5 多指令流出技术（续,）,5.5.0 超标量技术：一个时钟节拍内,同时,发射多条指令（,P,142,第1段）。,时空图,“超标量”的前身是“多操作部件技术”。,它是通过“设备并联”技术扩充的单流水线，被扩充的部件通常是运算部件、访存部件等“瓶颈”部件。,5.5.3 超长指令字技术,VLIW,（,P147,，P163,）,把多条无相关关系的常规指令打包在一个超长的指令字中，让它们同时被处理，分别控制多个功能部件并行工作的技术。,每个操作放在一个槽（,slot）,内。,这种技术的实质，是把超标量技术中的相关性识别任务，由,CPU,硬件转移给程序员或编译程序去实现。,5.5.5 超流水技术：一个时钟节拍内,分时,发射多条指令（,P149）,时空图,附：超线程技术,HT,通俗的理解就是将一颗具有超线程功能的“实体”处理器虚拟成两个“逻辑”处理器，让多个应用程序或单一应用程序的多个线程，能够同时在同一颗处理器上执行。,超线程运行模式下，,CPU,中核心资源的利用率可提高3040%，也就是说在同样时间里可多执行3040%的指令，其性能可以与含双处理器的系统相媲美，但具有低得多的价格。,为了同时执行多个线程，使用超线程技术的新一代,P4 HT,处理器需要增加一个逻辑处理器单元。因此面积比以往的,P4,增大了5%。而其余部分如,ALU（,整数运算单元）、,FPU（,浮点运算单元）、,L2 Cache（,二级缓存）则保持不变，这些部分是被分享的。,虽然采用超线程技术能同时执行两个线程，但是当两个线程争夺同一资源时，其中一个要被阻塞，这时性能就不如两个真正的,CPU。,含有超线程技术的,CPU,需要主板（包括芯片组和,BIOS）、,软件（包括操作系统和应用软件，如,XP,）,支持，才能比较理想地发挥该项技术的优势。,超线程是一种过渡技术，不久就被多核心技术取代。,对于多指令流出的处理机，分支等待造成的性能下降比单流出机器更为显著每停一拍要减少几条指令，所以需要采取更复杂的解决办法。,第3章介绍了避免在分支（包括无条件跳转）指令后面空等待的几种方法。,其中“在,ID,周期完成判断并计算目标地址”的方法把分支等待周期由3个减少到1个，但是再要消除这1个等待周期就很难了。有的处理机做这两件事需要的周期数还不止1个。,从上文调换不相关指令到“延迟槽”执行的办法固然可以避免这段时间的空等待，但是找不到不相关指令就不能用。,为了利用这种等待周期，还有一个办法是“猜测”，不等“判跳”完成就开始取下条指令，取完之后“判跳”结果也出来了，如果证明“猜对”就继续执行这条指令，“猜错”就报废它。,为了容易实现，一个,CPU,在设计时就把“猜”的方向设定了，即总是猜分支失败（或者总是猜分支成功），这种猜法的“猜对率”没有保障。,5.4 动态分支预测技术（,P133）,现在讨论的“动态分支预测技术”就是对每条分支指令完成之后的真实方向进行记录，下次再回到这条指令时就往上次的同一方向猜，猜对的可能性就增大了。万一有的指令是一会儿总是分支失败，一会儿又总是分支成功（动态变化），那也可以在猜错后及时修改记录，以后就按新的方向猜。,“分支开销”指“猜对”、“猜错”两种情况下流水线分别等待的时间（周期数）。显然，“猜错”时的开销更大，否则“猜”就没有意义了。,5.4 动态分支预测技术（续）,分支历史表的英文缩写是,BHT（Branch History Table）,(1) 1,位,BHT,方法,表中给最近遇到的每条分支指令分配1个,bit,的记录单元，0表示上次分支不成功，1表示上次分支成功。,BHT,表可以设在指令,Cache,中，也可以用一个专门的,RAM,来实现。查表方法是相联比较。表的容量决定了能为多少个“最近用到”的分支指令记录历史信息。装满之后可以按“先进先出”或“最近最少使用”策略进行替换。,5.4.1 分支历史表,BHT,方法（,P134）,(2) 2位,BHT,方法,有的分支指令会有“临时性换向”，比如一段循环程序末尾的“返回指令”可能在,n-1,次分支成功后跟1次分支失败，但是下一次再执行这段循环程序，“返回指令”又应该按分支成功猜测。为了避免“1位,BHT,方法”被这种偶然变化所“欺骗”，可以使用2,bit,信息记录，只有连续2次“猜错”才会“改口”猜另一方向。具体算法见下图。,5.4.1 分支历史表,BHT,方法（续）,分支目标缓冲器,的英文缩写是,BTB（Branch-Target Buffer），,也称分支目标,Cache（ranch-Target Cache）。,上面介绍的,BHT,表只保存了分支指令地址和成功转移的方向，没有保存成功转移的目标地址，即只猜“是否转移”，不猜“转到哪里”，在转移成功情况下即使“猜对了”也需要另花时间计算目标地址，这对于判断分支方向和计算目标地址同时进行的机器来说起不到节省时间的作用。,分支目标缓冲器,BTB,表里面增加了成功转移的目标地址，如果“猜”本次转移成功就可以立即用它取指，不等待目标地址的计算结果，而“猜”本次分支失败则不需要使用目标地址。所以,BTB,表只保存成功的分支指令地址及其目标地址，不保存失败的分支指令。遇到分支指令要“猜”时，采用并行比较来搜索，搜到匹配项猜“分支成功” ，没有匹配项猜“分支失败” ，而后者不需要,BTB,提供目标地址。,5.4.2 分支目标缓冲器,BTB,方法,BTB,表的结构：,分支目标缓冲器,BTB,方法（续1）,下条指令地址,（送,PC,去）,匹配成功,信号,比较器,当前指令地址,（从,PC,来）,比较器,比较器,BTB,预测方法逻辑分支图：,分支目标缓冲器,BTB,方法（续2）,否,（预测错误）,是,（预测错误）,ID,周期：,IF,周期：,是,（预测“转移”）,否,（预测“不转移”）,启动,BTB,表查找成功,（命中）？,取当前指令；查找,BTB,表,当前指令译码；取下条指令,ID,周期：,当前指令译码；取下条指令,BTB,表添加一条记录，需若干拍；,重取下条指令，又需1拍,当前指令转移成功？,当前指令转移成功？,否,（预测正确）,是,（预测正确）,延迟0拍,延迟若干拍+1,延迟0拍,BTB,表删减一条记录，需若干拍；,重取下条指令，又需1拍,延迟若干拍+1,BTB,预测机构加入到流水线中：,分支目标缓冲器,BTB,方法（续3）,相对跳转距离,IF/ID,BTB,命中？,指令,存储器,MUX,MUX,ADD,PC,4,NPC,IR,ADD,判跳成功？,寄存器组,符号位扩展,IF,段,ID,段,现在,分析采用,BTB,预测方法的加速效果，,以,第3章末尾（,P90）,的改进后的,MIPS,流水线为例,。,在采用,BTB,预测方法之前，该流水线在,ID,周期进行分支判断与计算目标地址，到,EX,周期才能取下一条指令，所以每条转移指令之后有1个周期的固定延迟。,采用,BTB,预测方法之后，不同情况下的延迟周期数是不同的，下面分4种情形讨论。,分支目标缓冲器,BTB,方法（续4）,情形1：,BTB,命中，指令,K,转移 延迟=0,分支目标缓冲器,BTB,方法（续5）,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令,K,指令,L,1.指令,K,取指，,PC+4；,2.使用指令,K,的地址，检索,BTB,表，命中，表明指令,K,上次转移成功，猜此次仍转移，,PC,指令,L,的地址,1.指令,K,译码、判断转移、计算转移目标地址；,2.判断结果是：转移。所以“试取指令,L”,有效；,3.不改,BTB,表，猜指令,K,下次仍转移到指令,L,使用,PC,值，试取指令,L（,有效）,情形2：,BTB,命中，指令,K,不转移 延迟=2,分支目标缓冲器,BTB,方法（续6）,IF,ID,EX,Mem,WB,ID,EX,Mem,WB,指令,K,指令,L,1.指令,K,取指，,PC+4；,2.使用指令,K,的地址，检索,BTB,表，命中，表明指令,K,上次转移成功，猜此次仍转移，,PC,指令,L,的地址,1.指令,K,译码、判断转移、计算转移目标地址；,2.判断结果是：不转移。所以“试取指令,L”,无效，须报废；,3.,PC,指令,L,的地址+4,使用,PC,值，试取指令,L（,无效）,Str,IF,指令,K+1,使用新,PC,值,，,改取指令,K+1,删除,BTB,表该项，猜指令,K,下次不转移,IF,情形3：,BTB,不命中，指令,K,转移 延迟=2,分支目标缓冲器,BTB,方法（续7）,IF,ID,EX,Mem,WB,ID,EX,Mem,WB,指令,K,指令,K+1,1.指令,K,取指，,PC+4；,2.使用指令,K,的地址，检索,BTB,表，不命中，表明指令,K,上次没有转移，猜此次仍不转移，不改,PC,1.指令,K,译码、判断转移、计算转移目标地址；,2.判断结果是：转移。所以“试取指令,K+1”,无效，须报废；,3.,PC,指令,L,的地址,使用,PC,值，试取指令,K+1（,无效）,Str,IF,指令,L,使用新,PC,值,，,改取指令,L,BTB,表增添一项，猜指令,K,下次转移到指令,L,IF,情形4：,BTB,不命中，指令,K,不转移 延迟=0,分支目标缓冲器,BTB,方法（续8）,IF,ID,EX,Mem,WB,IF,ID,EX,Mem,WB,指令,K,指令,K+1,1.指令,K,取指，,PC+4；,2.使用指令,K,的地址，检索,BTB,表，不命中，表明指令,K,上次没有转移，猜此次仍不转移，不改,PC,1.指令,K,译码、判断转移、计算转移目标地址；,2.判断结果是：不转移。所以“试取指令,K+1”,有效；,3.不改,BTB,表，猜指令,K,下次仍不转移,使用,PC,值，试取指令,K+1（,有效）,注意：该情形包括当前指令是转移指令但不成功、当前指令不是转移指令两种情况。,小结：,可见，与不用,BTB,的时序相比，情形1、4减少了延迟，而情形2、3增加了延迟。,我们可以这样计算：,平均转移延迟=情形1概率0+情形2概率2+情形3概率2+情形1概率0,如果平均值小于1，则新方法加快了转移指令执行速度，反之则减慢了速度。,分支目标缓冲器,BTB,方法（续9）,采用,BTB,预测方法后的,CPI,计算公式：,平均,CPI =,理想,CPI +,平均延迟周期数,由于平均,CPI,针对所有指令，所以还要把非转移指令也考虑进去，如下图,分支目标缓冲器,BTB,方法（续10）,所有指令,转移指令,非转移指令（,BTB,必不命中，本次必不转移）,BTB,命中,BTB,不命中,本次不转移,BTB,不命中，不转移：,0拍,本次转移 ,BTB,命中，转移：,0拍,本次不转移 ,BTB,命中，不转移：,若干拍+1,本次转移 ,BTB,不命中，转移：,若干拍+1,例5.6 设程序中转移指令占20%，50%可以在,BTB,命中，命中的指令本次转移概率为90%，未命中的指令本次转移概率为60%，判断转移并计算地址的开销是2，修改,BTB,的开销是1，非转移指令的,CPI=1。,求平均,CPI。,解：,分支目标缓冲器,BTB,方法（续11）,所有指令,转移指令,非转移指令（,BTB,必不命中，本次必不转移）,BTB,命中,BTB,不命中,本次不转移,BTB,不命中，不转移：,0拍,本次转移 ,BTB,命中，转移：,0拍,本次不转移 ,BTB,命中，不转移：,2+1拍,本次转移 ,BTB,不命中，转移：,2+1拍,20%,80%,50%,50%,90%,10%,60%,40%,平均,CPI = 1 + 20% 50%(90%0 + 10%3) +,+ 50%(60%3 + 40%0) ,= 1.21,如果不采用,BTB,预测方法，每条转移指令无论是否成功，都有2个周期的固定延迟。,平均,CPI = 1 + 20%2 = 1.40,可见，采用,BTB,预测方法有可能缩短平均,CPI。,分支目标缓冲器,BTB,方法（续12）,5.8题假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本,CPI,为1。,(1)求程序执行的,CPI。,(2),相对于采用固定的2个时钟周期延迟的分支处理，采用哪种方法能使程序执行速度更快？,分析：,分支目标缓冲器,BTB,方法（续13）,所有指令,转移指令,非转移指令（,BTB,必不命中，本次必不转移）,BTB,命中,BTB,不命中,本次不转移 ,0拍,本次转移 ,BTB,命中，转移：,0拍,本次不转移 ,BTB,命中，不转移：,4拍,本次转移 ,15%,85%,90%,10%,90%,10%,平均：,3拍,5.9题假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比例为5%，没有无条件转移指令的程序,CPI,值为1。假设分支目标缓冲中包含分支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的,CPI,值为多少？假设原来的,CPI=1.1。,分析：本题只考虑无条件转移指令，所以取指后100%会转移，,BTB,命中开销=0拍，所缺的条件是不命中开销。再看，“原来的,CPI,”指使用,BTB,方法前的平均,CPI，,是1.1，理想,CPI=1，,由此可以解出原来的转移开销。使用,BTB,方法后的不命中开销比它多1拍。,分支目标缓冲器,BTB,方法（续14）,所有指令,转移指令,非转移指令（,BTB,必不命中，必不转移） ,0拍,BTB,命中（100%必转移） ,0拍,BTB,不命中（100%必转移） ,?拍,5%,95%,90%,10%,思考题：,5.8题：,BTB“,命中率为90%”意味着什么？实际上有没有可能达到？,参考观点：,BTB,表中存放最近一次执行中转移成功的转移指令地址，它的命中率指程序中包含的全部转移指令有百分之多少已经存入。显然，“条件转移指令命中率为90%”的情形只能是90%以上条件转移指令被执行过后才可能出现，即程序运行的后期。我们要计算程序运行全程的平均,CPI，,应该引用,BTB,的平均命中率，通常应该在50%左右。,一些特殊程序中，,BTB,平均命中率也可能达到90%，比如高次数循环。,该题的设计者为了证明“,BTB,方法能使程序执行速度更快”，设定了特殊情况下的已知条件。,5.9题：根据,BTB,方法原理，,BTB,不命中开销 = 指令本身的转移开销 +,BTB,表修改开销（1拍），但是习题指导书中的题解没有加这1拍。,参考观点：该题解应该修正。,分支目标缓冲器,BTB,方法（续15）,各次作业应交的内容,作业6（第6次课）,5.11，5.8，5.9,
展开阅读全文