动态调度(Cont)-推断执行和ILP.ppt

计算机体系结构 Chapter4_3.1动态调度动态调度(Cont),Cont),推断执行推断执行和和ILPILP计算机体系结构 Chapter4_3.2Review TomasuloTomasulo引入动态调度的动机引入动态调度的动机在没有专用编译器的情况下，提高系统性能解决编译时无法判定的部分相关问题Scoreboard 和TomasulaTomasula 主要贡献主要贡献Dynamic schedulingRegister renaming-消除了WAW，WAR相关Load/store disambiguation算法的主要缺陷算法的主要缺陷复杂要求高速CDB性能受限于Common Data Bus动态硬件方案可以用硬件进行循环展开如何处理分支?我们可以用硬件做循环展开必须可以解决分支指令问题如何处理精确中断?Out-of-order execution out-of-order completion!计算机体系结构 Chapter4_3.3为什么顺序发射为什么顺序发射?顺序发射使我们可以进行程序的数据流分析我们可以知道某条指令的结果会流向哪些指令如果我们乱序发射，可能会混淆RAW和WAR相关每一周期发射多条指令也使用该原则将会正确地工作:需要多端口的“rename table”,以便同时对一组指令所用的寄存器重命名需要在单周期内发射到多个RS中.寄存器文件需要有2x 个读端口和x个写端口.计算机体系结构 Chapter4_3.4关于异常处理关于异常处理?乱序完成加大了实现精确中断的难度在前面指令还没有完成时，寄存器文件中可能会有后面指令的运行结果.如果这些前面的指令执行时有中断产生，怎么办？例如：DIVD F10,F0,F2SUBD F4,F6,F8ADDD F12,F14,F16需要“rollback”寄存器文件到原来的状态:精确中断的含义是其返回地址为：-该地址之前的所有指令都已完成-其后的指令还都没有完成实现精确中断的技术：顺序完成（或提交）即提交指令完成的顺序必须与指令发射的顺序相同计算机体系结构 Chapter4_3.5进行循环重叠执行需要尽快解决分支问题进行循环重叠执行需要尽快解决分支问题!在循环展开的例子中，我们假设整数部件可以快速解决分支问题，以便进行循环重叠执行!Loop:LDF00R1MULTDF4F0F2SDF40R1SUBIR1R1#8BNEZR1Loop如果分支依赖于multd,怎么办?需要能预测分支方向如果分支成功，我们就可以重叠执行循环对于superscalar机器这一问题更加突出计算机体系结构 Chapter4_3.6控制相关的动态解决技术控制相关的动态解决技术控制相关：由条件转移或程序中断引起的相关，也称全局相关。控制相关对流水线的吞吐率和效率影响相对于数据相关要大得多条件指令在一般程序中所占的比例相当大中断虽然在程序中所占的比例不大，但中断发生在程序中的哪一条指令，发生在一条指令执行过程中的哪一个功能段都是不确定的处理好条件转移和中断引起的控制相关是很重要的。关键问题：要确保流水线能够正常工作减少因断流引起的吞吐率和效率的下降计算机体系结构 Chapter4_3.7分支对性能的影响分支对性能的影响假设在一条有K段的流水线中，在最后一段才能确定目标地址i-1ii+1i+2i+k-3p+1p+2p+k-3i+k-2p+k-2OutputOutput当分支方向预测错误时，不仅流水线中有多个功能段要浪费，更严重的是可能造成程序执行结果发生错误，因此当程序沿着错误方向运行后，作废这些程序时，一定不能破坏通用寄存器和主存储器的内容。计算机体系结构 Chapter4_3.8条件转移指令对流水线性能的影响条件转移指令对流水线性能的影响假设对于一条有K段的流水线，由于条件分支的影响，在最坏情况下，每次条件转移将造成k-1个时钟周期的断流。假设条件分支在一般程序中所占的比例为p,条件成功的概率为q。试分析分支对流水线的影响。结论：条件转移指令对流水线的影响很大，必须采取相关措施来减少这种影响。预测可以是静态预测“Static”(at compile time)或动态预测“Dynamic”(at runtime)动态分支预测 vs.静态分支预测，哪个好？计算机体系结构 Chapter4_3.9Dynamic Branch Prediction动态分支预测：预测分支的方向在程序运行时刻动态确定需解决的关键问题是：如何记录转移历史信息如何根据所记录的转移历史信息，预测转移的方向主要方法基于BPB(Branch Prediction Buffer)或BHT(Branch History Table)的方法-1-bit BHT和2-bit BHT-Correlating Branch Predictors-Tournament Predictors:Adaptively Combining Local and Global PredictorsHigh Performance Instruction Delivery-BTB-Integrated Instruction Fetch Units-Return Address PredictorsPerformance=(accuracy,cost of misprediction)Misprediction Flush Reorder Buffer计算机体系结构 Chapter4_3.101-bit BHTBranch History Table:分支指令的PC的低位索引1-bit BHT该表记录上一次转移是否成功不做地址检查例题：一个循环供循环10次，它将分支成功9次，1次不成功，假设此分支的预测位始终在缓冲区中，那么分支预测的准确性是多少？静态预测 vs.动态预测问题:在一个循环中,1-bit BHT 将导致2次分支预测错误(avg is 9 iteratios before exit):最后一次循环,前面都是预测成功，而这次需要退出循环第一次循环，由于前面预测为失败，而这次实际上为成功计算机体系结构 Chapter4_3.11解决办法解决办法:2位记录分支历史位记录分支历史Red:stop,not takenGreen:go,taken2-bit BHTNTTTNTPredict TakenPredict Not TakenPredict TakenPredict Not TakenTNTTNT计算机体系结构 Chapter4_3.12计算机体系结构 Chapter4_3.13计算机体系结构 Chapter4_3.14BHT Accuracy分支预测错误的原因:预测错误由于使用PC的低位查找BHT表，可能得到错误的分支历史记录BHT表的大小问题4096 项的表分支预测错误的比例为1%(nasa7,tomcatv)to 18%(eqntott),spice at 9%and gcc at 12%再增加项数，对提高预测准确率几乎没有效果(in Alpha 21164)计算机体系结构 Chapter4_3.15Correlating Branch Predicator 例如：if(aa=2)aa=0;if(bb=2)bb=0;if(aa!=bb)翻译为DLX SUBI R3,R1,#2 BNEZ R3,L1 ;branch b1(aa!=2)ADDI R1,R0,R0 ;aa=0 L1:SUBI R3,R2,#2 BNEZ R3,L2 ;branch b2(bb!=2)ADDI R2,R0,R0 ;bb=0 L2:SUBI R3,R1,R2 ;R3=aa-bb BEQZ R3,L3 ;branch b3(aa=bb)计算机体系结构 Chapter4_3.16Correlating Branches观察结果：b3 与分支b2 和b1相关。如果b1和b2都分支失败，则b3一定成功。Correlating predictors 或 两级预测器：分支预测器根据其他分支的行为来进行预测。工作原理：根据一个简单的例子我们来看其基本原理 if(d=0)d=1;if(d=1)d=0;翻译为DLX BNEZ R1,L1 ;branch b1(d!=0)ADDI R1,R0,#1 ;d=0,so d=1 L1:ADDI R3,R1,#-1 BNEZ R3,L2 ;branch b2(d!=1).L2:计算机体系结构 Chapter4_3.17两级预测器基本工作原理两级预测器基本工作原理假设d的初始值序列为0，1，2b1 如果分支失败，b2一定也分支失败。前面的两位标准的预测方案就没法利用这一点，而两级预测方案就可以。计算机体系结构 Chapter4_3.18假设d的初始值在2和0之间切换。用1-bit预测器，初始设置为预测失败，T表示预测成功，NT表示预测失败。结论：这样的序列每次预测都错，预测错误率100计算机体系结构 Chapter4_3.19Correlating Branches基本思想：用1位作为correlation位。即每个分支都有两个相互独立的预测位：一个预测位假设最近一次执行的分支失败时的预测位，另一个预测位是假设最近一次执行的分支成功时的预测位。最近一次执行的分支通常与要预测的分支不是同一条指令记为（1，1）前一位表示最近一次分支失败时的预测位，后一位表示最近一次分支成功时的预测位计算机体系结构 Chapter4_3.20Correlating 预测器的预测和执行情况，显然只有在第一次d=2时，预测错误，其他都预测正确记为（1，1）预测器，即根据最近一次分支的行为来选择一对1-bit预测器中的一个。更一般的表示为（m,n)，即根据最近的m个分支，从2m个分支预测器中选择预测器，每个预测器的位数为n计算机体系结构 Chapter4_3.21Correlating Branches(2,2)predictor:2-bit global,2-bit localBranch address(4 bits)2-bits per branch local predictorsPrediction2-bit recent global branch history(01=not taken then taken)计算机体系结构 Chapter4_3.22计算机体系结构 Chapter4_3.23Tournament PredictorsTournament predictors:使用两个预测器一个基于全局信息一个基于局部信息再加一个选择器Use the predictor that tends to guess correctlyaddrhistoryPredictor APredictor B计算机体系结构 Chapter4_3.24Tournament Predictor in Alpha 21264Selector：4K 2-bit 计数器用来选择全局预测器还是局部预测器Global predictor：使用4K项，根据最近的12个分支的执行情况来索引，每项为标准的2-bit预测器12-bit pattern:ith bit 0=ith prior branch not taken;ith bit 1=ith prior branch taken;Local predictor：两级预测器Top level：1024个10-bit 项构成，每个10-bit项对应最近10次分支的转移方向Next level：由Top level所选项中的10-bit索引找到1K 项中的对应项，每项由3-bit saturating counter 作为局部预测器Total size:4K*2+4K*2+1K*10+1K*3=29K bits!(180,000 transistors)计算机体系结构 Chapter4_3.25%of predictions from local predictor in Tournament Scheme计算机体系结构 Chapter4_3.26Accuracy of Branch PredictionProfile:branch profile from last execution(static in that in encoded in instruction,but profile)fig 3.40计算机体系结构 Chapter4_3.27Accuracy v.Size(SPEC89)计算机体系结构 Chapter4_3.28分支指令的地址作为BTB的索引，以得到分支预测地址必须检测分支指令的地址是否匹配，以免用错误的分支地址从表中得到预测地址分支方向确定后，更新预测的PCSimple dynamic prediction:Branch Target Buffer(BTB)Branch PCPredicted PC=?PC of instructionFETCHExtra prediction statebitsYes:instruction is branch and use predicted PC as next PCNo:branch not predicted,proceed normally(Next PC=PC+4)计算机体系结构 Chapter4_3.29计算机体系结构 Chapter4_3.30 Determine the total branch penalty for a branch-target buffer assuming the penalty cycles for individual mispredictions from figure 2.24.Make the following assumptions about the prediction accuracy and hit rate:Prediction accuracy is 90%(for instructions in the butter)Hit rate in the buffer is 90%(for branches predicted taken)Ans.P1=90%*10%P2=10%BP=(0.09+0.1)*2 =0.38计算机体系结构 Chapter4_3.31Review 控制相关的动态解决技术控制相关的动态解决技术 动态分支预测：预测分支的方向在程序运行时刻动态确定需解决的关键问题：如何记录转移历史信息如何根据所记录的转移历史信息，预测转移的方向主要方法1-bit BHT和2-bit BHTCorrelating Branch PredictorsTournament Predictors:Adaptively Combining Local and Global PredictorsHigh Performance Instruction Delivery-BTB-Integrated Instruction Fetch Units-Return Address PredictorsPerformance=(accuracy,cost of misprediction)Misprediction Flush Reorder Buffer计算机体系结构 Chapter4_3.32Accuracy of Different Schemes4096 Entries 2-bit BHTUnlimited Entries 2-bit BHT1024 Entries(2,2)BHT0%18%Frequency of Mispredictions计算机体系结构 Chapter4_3.33HW support for More ILP避免分支预测：将分支预测转换为有条件的执行指令:if(x)then A=B op C else NOP如果条件不成立，即不写结果，也不引起异常扩展ISA,Alpha,MIPS,PowerPC,SPARC 的ISA,存在条件传送指令;PA-RISC 的“取消”分支指令EPIC:64 1-bit 条件位选择有条件的执行带条件的指令（conditional instructions）的缺陷：如果取消该指令执行，仍然需要花费时间如果检测条件较晚，仍然要Stall复杂条件将降低其有效性，条件是否成立要在流水线较后段才能知道计算机体系结构 Chapter4_3.34需要硬件缓存没有提交的指令结果:reorder buffer（ROB）3 个域:指令类型,目的地址,值Reorder buffer 可以作为操作数源=就像有更多的寄存器（与RS类似）当程序执行阶段完成后，用ROB的编号代替RS中的值增加指令提交阶段ROB提供执行完成阶段和提交阶段的操作数一旦操作数提交，结果就写入寄存器这样，在预测失败时，容易恢复推断执行的指令，或发生异常时，容易恢复状态ReorderBufferFPOpQueueFP AdderFP AdderRes StationsRes StationsFP Regs硬件支持精确中断硬件支持精确中断计算机体系结构 Chapter4_3.351.Issueget instruction from FP Op Queue如果RS和ROB有空闲单元就发射指令。如果寄存器或ROB中源操作数可用，就将其发送到RS，目的地址的ROB编号也发送给RS(this stage sometimes called“dispatch”)2.Executionoperate on operands(EX)当操作数就绪后，开始执行。如果没有就绪，监测CDB，检查RAW相关3.Write resultfinish execution(WB)将运算结果通过CDB传送给所有等待结果的FU以及ROB单元，标识RS可用4.Commitupdate register with reorder result按ROB表中顺序，如果结果已有，就更新寄存器（或存储器），并将该指令从ROB表中删除预测失败或有中断时，刷新ROB支持推断执行的支持推断执行的 Tomasulo 算法的四阶段算法的四阶段计算机体系结构 Chapter4_3.36LD F6,34(R2)LD F2,45(R3)MULT F0,F2,F4SUBD F8,F6,F2DIVD F10,F0,F6ADDD F6,F8,F2计算机体系结构 Chapter4_3.37计算机体系结构 Chapter4_3.38计算机体系结构 Chapter4_3.39计算机体系结构 Chapter4_3.40计算机体系结构 Chapter4_3.41v计算机体系结构 Chapter4_3.42计算机体系结构 Chapter4_3.43计算机体系结构 Chapter4_3.44计算机体系结构 Chapter4_3.45计算机体系结构 Chapter4_3.46计算机体系结构 Chapter4_3.47计算机体系结构 Chapter4_3.48计算机体系结构 Chapter4_3.49计算机体系结构 Chapter4_3.50计算机体系结构 Chapter4_3.51计算机体系结构 Chapter4_3.52计算机体系结构 Chapter4_3.53计算机体系结构 Chapter4_3.54计算机体系结构 Chapter4_3.55计算机体系结构 Chapter4_3.56计算机体系结构 Chapter4_3.57消除存储器的二义性消除存储器的二义性:处理对存储器引用的处理对存储器引用的RAW相关相关Question:给定一个指令序列，store，load 这两个操作是否有关？即下列代码是否有相关问题?Eg:st0(R2),R5 ldR6,0(R3)我们是否可以较早启动ld?Store的地址可能会延迟很长时间才能得到.我们也许想在同一个周期开始这两个操作的执行.两种方法:No Speculation:不进行load操作，直到我们确信地址 0(R2)0(R3)Speculation:我们可以假设他们相关还是不相关(called“dependence speculation”)，如果推测错误通过ROB来修正计算机体系结构 Chapter4_3.58需要缓冲区以程序序保存所有对存储器的写操作保存地址（地址可用时）和值（值可用时）FIFO ordering:以程序序确认和删除store当发射一个load操作时，记录当前store队列的头指针.当load的地址可用时，检查store队列:如果在load前存在正等待该地址的store操作，则stall该load操作如果load地址与前面的store地址匹配，则有 memory-induced RAW hazard:-存储的值可用 返回值-存储的值还没有准备好 返回该store指令的ROB编号否则发出存储器请求由于实际的store操作顺序提交，所以不会有WAW 相关.Hardware Support for Memory Disambiguation计算机体系结构 Chapter4_3.59-LD F4,10(R3)NMemory Disambiguation:ToMemoryFP addersFP multipliersReservation StationsFP OpQueueROB7ROB6ROB5ROB4ROB3ROB2ROB1F2F0-ST 10(R3),F5 LD F0,32(R2)ST 0(R3),F4NNYDone?DestDestOldestNewestfrom Memory2 32+R24 ROB3DestReorder BufferRegisters计算机体系结构 Chapter4_3.60Relationship between precise interrupts and speculation:推断是猜测的一种形式Branch prediction,data predictionIf we speculate and are wrong,need to back up and restart execution to point at which we predicted incorrectlyThis is exactly same as precise exceptions!分支预测非常重要Need to“take our best shot”at predicting branch direction.If we issue multiple instructions per cycle,lose lots of potential instructions otherwise:-Consider 4 instructions per cycle-If take single cycle to decide on branch,waste from 4-7 instruction slots!支持精确中断和推断执行的技术:in-order completion or commitThis is why reorder buffers in all new processors计算机体系结构 Chapter4_3.61计算机体系结构 Chapter4_3.62小结小结#1/2Reservations stations:寄存器重命名，缓冲源操作数避免寄存器成为瓶颈避免了Scoreboard中无法解决的 WAR,WAW 相关允许硬件做循环展开不限于基本块(IU先行，解决控制相关)贡献Dynamic schedulingRegister renamingLoad/store disambiguation360/91 后 Pentium II;PowerPC 604;MIPS R10000;HP-PA 8000;Alpha 21264使用这种技术计算机体系结构 Chapter4_3.63动态调度方案可以用硬件动态完成循环展开通过重命名机制来消除WAR和 WAW 相关Reorder Buffer:提供了撤销指令运行的机制指令以发射序存放在ROB中指令顺序提交分支预测对提高性能是非常重要的推断执行是利用了ROB撤销指令执行的机制Superscalar 和VLIW:CPI 1)小结小结#2/2