《计算机系统结构》电子教案(课6).ppt

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