《高等计算机系统结构》由会员分享，可在线阅读，更多相关《高等计算机系统结构（52页珍藏版）》请在金锄头文库上搜索。
1、北京大学微处理器研究开发中心计算机系统结构研究所高等计算机系统结构高等计算机系统结构（第四讲）2011年4月2日程 旭现代指令级并行技现代指令级并行技术术北京大学微处理器研究开发中心计算机系统结构研究所流水线的性能流水线的性能通过更加复杂的流水线和动态调度开发隐形（implicit）指令级并行性乱序执行执行，同时保证：=真数据相关(RAW)=精确中断通过寄存器换名，消除WAR和WAW冒险重排序缓冲器（Reorder buffer）保存尚未提交（committing）但已完成的结果，以支持精确中断95%)，可望显著减少转移损失需要硬件支持:预测结构部件: 转移历史表（Branch history
2、 tables）, 转移目标缓冲器（branch target buffers）等错误预测恢复机制： 将结果计算与确认（commit）分离开来 消除流水线中跟随错误预测转移指令的指令 将状态恢复到转移指令之后的正确状态北京大学微处理器研究开发中心计算机系统结构研究所静态转移预测静态转移预测总体而言，一条转移指令发生的概率大约 为60-70%，但是:ISA也可以向转移指令附加上首选转移方向的语义，例如Motorola MC88110bne0 (preferred taken) beq0 (not taken)JZJZbackward90%forward50%北京大学微处理器研究开发中心计算机系统
3、结构研究所动态转移预测动态转移预测learning based on past behaviorlearning based on past behavior时间关联 (Temporal correlation)The way a branch resolves may be a good predictor of the way it will resolve at the next execution空间关联（Spatial correlation） Several branches may resolve in a highly correlated manner (a preferre
4、d path of execution)北京大学微处理器研究开发中心计算机系统结构研究所 假设每条指令2个转移预测位 当连续两次出现转移预测错误时，改变预测方向!takewrongtaken takentakentakentakentakerighttakerighttakewrong taken taken takenBP state:(predict take/take) x (last prediction right/wrong)转移预测位转移预测位Branch Prediction BitsBranch Prediction Bits北京大学微处理器研究开发中心计算机系统结构研究所转
5、移历史表转移历史表Branch History TableBranch History Table4K-entry BHT, 2 bits/entry, 80-90% correct predictions0 0Fetch PCBranch?Target PC+I-CacheOpcodeoffsetInstructionkBHT Index2k-entryBHT,2 bits/entryTaken/Taken?北京大学微处理器研究开发中心计算机系统结构研究所开采转移的空间关联开采转移的空间关联YehYeh and Patt, 1992 and Patt, 1992历史寄存器（History r
6、egister, H,）记录处理器最近执行的N条转移的方向if (xi 7) theny += 1;if (xi 5) thenc -= 4;如果第一转移的条件为“假”，第二个也一定为“假”北京大学微处理器研究开发中心计算机系统结构研究所两级转移预测器两级转移预测器Pentium Pro 通过利用最近两条转移的结果来从四组BHT位中挑选出一组(95% 的正确率)0 0kFetch PCShift in Taken/Taken results of each branch2-bit global branch history shift registerTaken/Taken?北京大学微处理器研
7、究开发中心计算机系统结构研究所BHTBHT局限性局限性仅能预测转移方向，因而，在确定转移目标之前，并不能从转移目标处开始取指令流。UltraSPARC-III fetch pipelineCorrectly predicted taken branch penaltyJump Register penaltyA PC Generation/MuxP Instruction Fetch Stage 1F Instruction Fetch Stage 2B Branch Address Calc/Begin DecodeI Complete DecodeJ Steer Instructions
8、to Functional unitsR Register File ReadE Integer ExecuteRemainder of execute pipeline (+ another 6 stages)北京大学微处理器研究开发中心计算机系统结构研究所转移目标缓冲器转移目标缓冲器（Branch Target BufferBranch Target Buffer）BP bits are stored with the predicted target address.IF stage: If (BP=taken) then nPC=target else nPC=PC+4later: c
9、heck prediction, if wrong then kill the instruction and update BTB & BPb else update BPbIMEMPCBranch Target Buffer (2k entries)kBPbpredictedtargetBP target北京大学微处理器研究开发中心计算机系统结构研究所地址冲突（地址冲突（Address Address CollisionsCollisions）What will be fetched after the instruction at 1028?BTB prediction= Correct
10、 target=Assume a 128-entry BTBBPbtargettake2361028 Add .132 Jump 100InstructionMemory2361032kill PC=236 and fetch PC=1032Is this a common occurrence?Can we avoid these bubbles?北京大学微处理器研究开发中心计算机系统结构研究所BTBBTB仅对控制指令有效仅对控制指令有效BTB仅包含针对转移指令和跳转指令的有用信息 对其他指令，不能改变BTB内部的状态对所有其他指令的下一PC 都是 PC+4 !如何在指令译码之前，就达到上述
11、效果?北京大学微处理器研究开发中心计算机系统结构研究所Branch Target Buffer (BTB)Branch Target Buffer (BTB) Keep both the branch PC and target PC in the BTB PC+4 is fetched if match fails Only taken branches and jumps held in BTB Next PC determined before branch fetched and decoded2k-entry direct-mapped BTB(can also be associa
12、tive)I-CachePCkValidvalidEntry PC=matchpredictedtargettarget PC北京大学微处理器研究开发中心计算机系统结构研究所在译码前查询在译码前查询BTBBTB1028 Add .132 Jump 100BPbtargettake236entry PC132 The match for PC=1028 fails and 1028+4 is fetched eliminates false predictions after ALU instructions BTB contains entries only for control trans
13、fer instructions more room to store branch targets北京大学微处理器研究开发中心计算机系统结构研究所合并合并B BTBTB和和BHTBHT相对BHT而言，BTB的表项的实现成本更高，但是可以在流水线较早的时候就对取指流进行重定向，并能够加速间接转移(JR)BHT可以包含更多的表项，并更加准确A PC Generation/MuxP Instruction Fetch Stage 1F Instruction Fetch Stage 2B Branch Address Calc/Begin DecodeI Complete DecodeJ Stee
14、r Instructions to Functional unitsR Register File ReadE Integer ExecuteBTBBHTBHT in later pipeline stage corrects when BTB misses a predicted taken branchBTB/BHT only updated after branch resolves in E stage北京大学微处理器研究开发中心计算机系统结构研究所跳转寄存器跳转寄存器(JR)(JR)的使用的使用切换状态 (jump to address of matching case)动态过程调用
15、 (jump to run-time function address)子程序返回 (jump to return address)对于上述情况，BTB都可以很好工作吗?BTB works well if same case used repeatedlyBTB works well if same function usually called, (e.g., in C+ programming, when objects have same type in virtual function call)BTB works well if usually return to the same
16、place Often one function called from many distinct call sites!北京大学微处理器研究开发中心计算机系统结构研究所子程序返回栈（子程序返回栈（Subroutine Return StackSubroutine Return Stack）专设一个小的结构来加速针对子程序返回的JR处理，通常比BTBs会更加准确.&fb()&fc()Push call address when function call executedPop return address when subroutine return decoded fa() fb();
17、fb() fc(); fc() fd(); &fd()k entries(typically k=8-16)北京大学微处理器研究开发中心计算机系统结构研究所错误预测的恢复错误预测的恢复按序执行机器：=假设在转移解决之前，没有该转移之后发射的指令会回写结果（write-back）=将错误预测转移之后的所有指令都删除在转移解决之前，转移之后的多条指令（按串行程序序）可能均已完成乱序执行?北京大学微处理器研究开发中心计算机系统结构研究所支持精确中断的按序提交支持精确中断的按序提交 Instructions fetched and decoded into instruction reorder bu
18、ffer in-order Execution is out-of-order ( out-of-order completion) Commit (write-back to architectural state, i.e., regfile & memory, is in-orderTemporary storage needed in ROB to hold results before commitFetchDecodeExecuteCommitReorder BufferIn-orderIn-orderOut-of-orderKillKillKillException?Inject
19、 handler PC北京大学微处理器研究开发中心计算机系统结构研究所流水线中的转移错误预测流水线中的转移错误预测FetchDecodeExecuteCommitReorder BufferKillKillKillBranchResolutionInject correct PCCan have multiple unresolved branches in ROBCan resolve branches out-of-order by killing all the instructions in ROB that follow a mispredicted branchBranchPred
20、ictionPCComplete北京大学微处理器研究开发中心计算机系统结构研究所tvtvtvRecovering ROB/Renaming TableRecovering ROB/Renaming TableRegister FileReorder bufferLoad UnitFUFUFUStore Unitt1t2.tnIns# use exec op p1 src1 p2 src2 pd dest dataCommitRename Tabler1 tvr2Take snapshot of register rename table at each predicted branch, re
21、cover earlier snapshot if branch mispredictedRename SnapshotsPtr2 next to commitPtr1 next availablerollback next available北京大学微处理器研究开发中心计算机系统结构研究所双向推测执行双向推测执行 所需的资源数与并发推测执行的指令流数目成正比与转移预测不同，还可以对转移个两条可能的方向同时进行推测执行 基于转移预测的推测执行比对转移的所有方向都进行推测执行需要更少的资源当同时对一条转移的两条可能指令流进行推测执行时，只有一半的资源真正用于了有用工作当转移预测率很高时，将所有的
22、资源都用于预测的方向是效率很高（cost effective）的方案 北京大学微处理器研究开发中心计算机系统结构研究所“Data in ROB” Design“Data in ROB” Design(HP PA8000, Pentium Pro, Core2Duo)(HP PA8000, Pentium Pro, Core2Duo) On dispatch into ROB, ready sources can be in regfile or in ROB dest (copied into src1/src2 if ready before dispatch) On completion,
23、 write to dest field and broadcast to src fields. On issue, read from ROB src fieldsRegister Fileholds only committed stateReorderbufferLoad UnitFUFUFUStore Unitt1t2.tnIns# use exec op p1 src1 p2 src2 pd dest dataCommit北京大学微处理器研究开发中心计算机系统结构研究所Unified Physical Register FileUnified Physical Register F
24、ile(MIPS R10K, Alpha 21264, Pentium 4)(MIPS R10K, Alpha 21264, Pentium 4) One regfile for both committed and speculative values (no data in ROB) During decode, instruction result allocated new physical register, source regs translated to physical regs through rename table Instruction reads data from
25、 regfile at start of execute (not in decode) Write-back updates reg. busy bits on instructions in ROB (assoc. search) Snapshots of rename table taken at every branch to recover mispredicts On exception, renaming undone in reverse order of issue (MIPS R10000)Rename Tabler1 tir2 tjFUFUStore UnitFULoad
26、 UnitFUt1t2.tnRegFileSnapshots for mispredict recovery(ROB not shown)北京大学微处理器研究开发中心计算机系统结构研究所Pipeline Design with Physical RegfileFetchDecode & RenameReorder BufferPCBranchPredictionUpdate predictorsCommitBranchResolutionBranchUnitALUMEMStore BufferD$ExecuteIn-OrderIn-OrderOut-of-OrderPhysical Reg.
27、Filekillkillkillkill北京大学微处理器研究开发中心计算机系统结构研究所物理寄存器的生命期物理寄存器的生命期ld r1, (r3)add r3, r1, #4sub r6, r7, r9add r3, r3, r6ld r6, (r1)add r6, r6, r3st r6, (r1)ld r6, (r11)ld P1, (Px)add P2, P1, #4sub P3, Py, Pzadd P4, P2, P3ld P5, (P1)add P6, P5, P4st P6, (P1)ld P7, (Pw)RenameWhen can we reuse a physical re
28、gister? When next write of same architectural register commits Physical regfile holds committed and speculative values Physical registers decoupled from ROB entries (no data in ROB)北京大学微处理器研究开发中心计算机系统结构研究所物理寄存器的管理物理寄存器的管理opp1PR1p2PR2exuseRdPRdLPRdP5P6P7P0PnP1P2P3P4R5P5R6P6R7R0P8R1R2P7R3R4ROBRename T
29、ablePhysical RegsFree Listld r1, 0(r3)add r3, r1, #4sub r6, r7, r6add r3, r3, r6ld r6, 0(r1)pppP0P1P3P2P4(LPRd requires third read port on Rename Table for each instruction)P8p北京大学微处理器研究开发中心计算机系统结构研究所物理寄存器的管理物理寄存器的管理opp1PR1p2PR2exuseRdPRdLPRdROBld r1, 0(r3)add r3, r1, #4sub r6, r7, r6add r3, r3, r6l
30、d r6, 0(r1)Free ListP0P1P3P2P4P5P6P7P0PnP1P2P3P4Physical RegspppP8px ld p P7 r1 P0R5P5R6P6R7R0P8R1R2P7R3R4Rename TableP0P8北京大学微处理器研究开发中心计算机系统结构研究所物理寄存器的管理物理寄存器的管理opp1PR1p2PR2exuseRdPRdLPRdROBld r1, 0(r3)add r3, r1, #4sub r6, r7, r6add r3, r3, r6ld r6, 0(r1)Free ListP0P1P3P2P4P5P6P7P0PnP1P2P3P4Physic
31、al RegspppP8px ld p P7 r1 P0R5P5R6P6R7R0P8R1R2P7R3R4Rename TableP0P8P7P1x add P0 r3 P1北京大学微处理器研究开发中心计算机系统结构研究所物理寄存器的管理物理寄存器的管理opp1PR1p2PR2exuseRdPRdLPRdROBld r1, 0(r3)add r3, r1, #4sub r6, r7, r6add r3, r3, r6ld r6, 0(r1)Free ListP0P1P3P2P4P5P6P7P0PnP1P2P3P4Physical RegspppP8px ld p P7 r1 P0R5P5R6P6
32、R7R0P8R1R2P7R3R4Rename TableP0P8P7P1x add P0 r3 P1P5P3x sub p P6 p P5 r6 P3北京大学微处理器研究开发中心计算机系统结构研究所物理寄存器的管理物理寄存器的管理opp1PR1p2PR2exuseRdPRdLPRdROBld r1, 0(r3)add r3, r1, #4sub r6, r7, r6add r3, r3, r6ld r6, 0(r1)Free ListP0P1P3P2P4P5P6P7P0PnP1P2P3P4Physical RegspppP8px ld p P7 r1 P0R5P5R6P6R7R0P8R1R2P
33、7R3R4Rename TableP0P8P7P1x add P0 r3 P1P5P3x sub p P6 p P5 r6 P3P1P2x add P1 P3 r3 P2北京大学微处理器研究开发中心计算机系统结构研究所物理寄存器的管理物理寄存器的管理opp1PR1p2PR2exuseRdPRdLPRdROBld r1, 0(r3)add r3, r1, #4sub r6, r7, r6add r3, r3, r6ld r6, 0(r1)Free ListP0P1P3P2P4P5P6P7P0PnP1P2P3P4Physical RegspppP8px ld p P7 r1 P0R5P5R6P6R
34、7R0P8R1R2P7R3R4Rename TableP0P8P7P1x add P0 r3 P1P5P3x sub p P6 p P5 r6 P3P1P2x add P1 P3 r3 P2x ld P0 r6 P4P3P4北京大学微处理器研究开发中心计算机系统结构研究所opp1PR1p2PR2exuseRdPRdLPRdROBx ld p P7 r1 P0x add P0 r3 P1x sub p P6 p P5 r6 P3x ld p P7 r1 P0物理寄存器的管理物理寄存器的管理ld r1, 0(r3)add r3, r1, #4sub r6, r7, r6add r3, r3, r6
35、ld r6, 0(r1)Free ListP0P1P3P2P4P5P6P7P0PnP1P2P3P4Physical RegspppP8pR5P5R6P6R7R0P8R1R2P7R3R4Rename TableP0P8P7P1P5P3P1P2x add P1 P3 r3 P2x ld P0 r6 P4P3P4Execute & CommitpppP8x北京大学微处理器研究开发中心计算机系统结构研究所opp1PR1p2PR2exuseRdPRdLPRdROBx sub p P6 p P5 r6 P3x add P0 r3 P1x add P0 r3 P1物理寄存器的管理物理寄存器的管理ld r1,
36、 0(r3)add r3, r1, #4sub r6, r7, r6add r3, r3, r6ld r6, 0(r1)Free ListP0P1P3P2P4P5P6P7P0PnP1P2P3P4Physical RegspppP8x x ld p P7 r1 P0R5P5R6P6R7R0P8R1R2P7R3R4Rename TableP0P8P7P1P5P3P1P2x add P1 P3 r3 P2x ld P0 r6 P4P3P4Execute & CommitpppP8xppP7北京大学微处理器研究开发中心计算机系统结构研究所Reorder Buffer HoldsReorder Buff
37、er HoldsActive Instruction WindowActive Instruction Windowld r1, (r3)add r3, r1, r2sub r6, r7, r9add r3, r3, r6ld r6, (r1)add r6, r6, r3st r6, (r1)ld r6, (r1)(Older instructions)(Newer instructions)Cycle tld r1, (r3)add r3, r1, r2sub r6, r7, r9add r3, r3, r6ld r6, (r1)add r6, r6, r3st r6, (r1)ld r6,
38、 (r1)CommitFetchCycle t + 1Execute北京大学微处理器研究开发中心计算机系统结构研究所超标量处理器的寄存器重命名超标量处理器的寄存器重命名在译码阶段，指令被重新分配新的物理目标寄存器在译码阶段，指令被重新分配新的物理目标寄存器源操作数被重命名为具有最新数据的物理寄存器源操作数被重命名为具有最新数据的物理寄存器执行部件仅能看到物理寄存器号执行部件仅能看到物理寄存器号Rename TableOpSrc1 Src2DestOpSrc1 Src2DestRegister Free ListOpPSrc1 PSrc2PDestOpPSrc1 PSrc2PDestUpdate
39、MappingDoes this work?Inst 1Inst 2Read AddressesRead DataWrite Ports北京大学微处理器研究开发中心计算机系统结构研究所超标量处理器的寄存器重命名超标量处理器的寄存器重命名Rename TableOpSrc1 Src2DestOpSrc1 Src2DestRegister Free ListOpPSrc1 PSrc2PDestOpPSrc1 PSrc2PDestUpdateMappingInst 1Inst 2Read AddressesRead DataWrite Ports=?=?Must check for RAW haza
40、rds between instructions issuing in same cycle. Can be done in parallel with rename lookup.MIPS R10K renames 4 serially-RAW-dependent insts/cycle北京大学微处理器研究开发中心计算机系统结构研究所存储器相关存储器相关st r1, (r2)ld r3, (r4)何时能够执行load指令?北京大学微处理器研究开发中心计算机系统结构研究所按序存储队列（按序存储队列（In-Order Memory QueueIn-Order Memory Queue） 在之前的
41、所有存储和装入指令完成之前，Load和store指令不能离开ROB执行希望对Load和Store指令进行推测执行，并与其他指令乱序执行北京大学微处理器研究开发中心计算机系统结构研究所保守的保守的LoadLoad乱序执行乱序执行st r1, (r2)ld r3, (r4) 将Store指令的执行分解为两个阶段：地址计算、数据写入如果地址已知，并可以确认r4 != r2，就可以在Store之前执行load指令 每个load地址都需要与所有之前未确认的STORE之前的地址进行比较(可以使用部分保守比较，例如地址的低12位)如有之前的任何STORE指令有地址尚不确定，就不能执行 load(MIPS R
42、10K, 16 entry address queue)北京大学微处理器研究开发中心计算机系统结构研究所地址推测（地址推测（Address SpeculationAddress Speculation）猜设 r4 != r2在store地址未知情况先，执行load指令需要按程序序保存所有完成但未提交的load/store地址 如果地址猜测不准确，损失可能会很大！st r1, (r2)ld r3, (r4)北京大学微处理器研究开发中心计算机系统结构研究所Memory Dependence PredictionMemory Dependence Prediction(Alpha 21264)(Al
43、pha 21264)st r1, (r2)ld r3, (r4) Guess that r4 != r2 and execute load before storeIf later find r4=r2, squash load and all following instructions, but mark load instruction as store-waitSubsequent executions of the same load instruction will wait for all previous stores to completePeriodically clear
44、 store-wait bits 北京大学微处理器研究开发中心计算机系统结构研究所推测式推测式Loads / StoresLoads / Stores与寄存器的变更相同，在之前的所有指令都提交之后，store指令才能修改存储器需要引进一种新的结构：推测式存储缓冲器（speculative store buffer） 来保存推测式store的数据北京大学微处理器研究开发中心计算机系统结构研究所Speculative Store BufferSpeculative Store BufferOn store execute:=mark entry valid and speculative, and
45、 save data and tag of instruction.On store commit: =clear speculative bit and eventually move data to cacheOn store abort:= clear valid bitDataLoad AddressTagsStore Commit PathSpeculative Store BufferL1 Data CacheLoad DataTagDataSVTagDataSVTagDataSVTagDataSVTagDataSVTagDataSV北京大学微处理器研究开发中心计算机系统结构研究所
46、Speculative Store BufferSpeculative Store BufferIf data in both store buffer and cache, which should we use:Speculative store bufferIf same address in store buffer twice, which should we use:Youngest store older than loadDataLoad AddressTagsStore Commit PathSpeculative Store BufferL1 Data CacheLoad DataTagDataSVTagDataSVTagDataSVTagDataSVTagDataSVTagDataSV北京大学微处理器研究开发中心计算机系统结构研究所FetchDecode & RenameReorder BufferPCBranchPredictionUpdate predictorsCommitDatapath: Branch Predictionand Speculative ExecutionBranchResolutionBranchUnitALUReg. FileMEMStore BufferD$Executekillkillkillkill
