2.1-高等计算机系统结构ppt课件

1、北京大学微处理器研究开发中心1（第五讲）2011年4月16日程 旭VLIW/EPICVLIW/EPIC基于静态调度的基于静态调度的ILPILP北京大学微处理器研究开发中心2复习复习: : 先进超标量技术先进超标量技术简单的转移预测技术也会有不错的效果简单的转移预测技术也会有不错的效果基于路径基于路径Path-basedPath-based的预测器可取得的预测器可取得95%95%的正确的正确率率BTBBTB可以在流水线的前期就改变控制流可以在流水线的前期就改变控制流, BHT, BHT的每个表的每个表项成本小，但需要等到指令译码项成本小，但需要等到指令译码转移错误预测的恢复需要使用流水线的快照转

2、移错误预测的恢复需要使用流水线的快照snapshotssnapshots以减少损失以减少损失统一物理寄存器堆的设计，可以避免从不同地方统一物理寄存器堆的设计，可以避免从不同地方 (ROB+arch regfile)(ROB+arch regfile)读取数据读取数据超标量处理器可以在一个时钟周期对多条相关指令进超标量处理器可以在一个时钟周期对多条相关指令进行重命名行重命名需要采用推测式存储缓冲器需要采用推测式存储缓冲器speculative store speculative store bufferbuffer来避免等待存储操作的确认来避免等待存储操作的确认北京大学微处理器研究开发中心3Fe

3、tchDecode & RenameReorder BufferPCBranchPredictionUpdate predictorsCommitBranchResolutionBranchUnitALUReg. FileMEMStore BufferD$Executekillkillkillkill复习复习: : 转移预测和推测式执行转移预测和推测式执行北京大学微处理器研究开发中心4超标量处理器控制逻辑的可扩展性超标量处理器控制逻辑的可扩展性 每条被发射的指令都必须检查与每条被发射的指令都必须检查与W W* *L L条指令间的关系，即硬件的增长条指令间的关系，即硬件的增长 W W* *(W(

4、W* *L)L) 对于按序机器，对于按序机器，L L与流水线延迟相关与流水线延迟相关 对于乱序机器对于乱序机器, L, L还包括指令缓冲器消耗的时间指令窗口还包括指令缓冲器消耗的时间指令窗口 或或 ROB)ROB) 随着随着W W的增加，需要更大的指令窗口来找都维持机器忙碌所需的指令级并行性的增加，需要更大的指令窗口来找都维持机器忙碌所需的指令级并行性 = L= L变得更大变得更大 = = 乱序控制逻辑的复杂程度增长速度大于乱序控制逻辑的复杂程度增长速度大于 W2 (W3)W2 (W3)Lifetime LIssue GroupPreviously Issued InstructionsIss

5、ue Width W北京大学微处理器研究开发中心5乱序控制的复杂度乱序控制的复杂度:MIPS R10000:MIPS R10000Control Logic SGI/MIPS Technologies Inc., 2019 北京大学微处理器研究开发中心6Check instruction dependenciesSuperscalar processor串行串行ISAISA的瓶颈的瓶颈a = foo(b);for (i=0, i no x-operation RAW Parallelism within an instruction = no x-operation RAW checkchec

6、k No data use before data ready = no data interlocksNo data use before data ready = no data interlocksTwo Integer Units,Single Cycle LatencyTwo Load/Store Units,Three Cycle LatencyTwo Floating-Point Units,Four Cycle LatencyInt Op 2Mem Op 1Mem Op 2FP Op 1FP Op 2Int Op 1北京大学微处理器研究开发中心8VLIW VLIW 编译编译器的

7、器的职责职责编译编译器器: : 调调度成最大度成最大并并行行执执行行确保指令确保指令内内的的并并行性行性避免避免数数据冒据冒险险( (无互无互锁锁) )通常用通常用显显式的式的NOPNOP指令指令来来分隔分隔实际实际操作操作北京大学微处理器研究开发中心9早期早期VLIWVLIW机器机器 FPS AP120B (1976)FPS AP120B (1976) scientific attached array processorscientific attached array processor first commercial wide instruction machinefirst com

8、mercial wide instruction machine hand-coded vector math libraries using software hand-coded vector math libraries using software pipelining and loop unrollingpipelining and loop unrolling Multiflow Trace (1987)Multiflow Trace (1987) commercialization of ideas from Fishers Yale group commercializatio

9、n of ideas from Fishers Yale group including “trace scheduling”including “trace scheduling” available in configurations with 7, 14, or 28 available in configurations with 7, 14, or 28 operations/instructionoperations/instruction 28 operations packed into a 1024-bit instruction word28 operations pack

10、ed into a 1024-bit instruction word Cydrome Cydra-5 (1987)Cydrome Cydra-5 (1987) 7 operations encoded in 256-bit instruction word7 operations encoded in 256-bit instruction word rotating register filerotating register file北京大学微处理器研究开发中心10循环的执行循环的执行for (i=0; iN; i+) Bi = Ai + C;Int1Int 2M1M2FP+FPxloo

11、p:How many FP ops/cycle?How many FP ops/cycle?ld add r1fadd sd add r2 bne 1 fadd / 8 cycles = 0.125loop: ld f1, 0(r1) add r1, 8 fadd f2, f0, f1 sd f2, 0(r2) add r2, 8 bne r1, r3, loopCompileSchedule北京大学微处理器研究开发中心11循环展开循环展开Loop UnrollingLoop Unrolling）for (i=0; iN; i+) Bi = Ai + C;for (i=0; iN; i+=4)

12、 Bi = Ai + C; Bi+1 = Ai+1 + C; Bi+2 = Ai+2 + C; Bi+3 = Ai+3 + C;Unroll inner loop to perform 4 iterations at onceNeed to handle values of N that are not multiples of unrolling factor with final cleanup loop北京大学微处理器研究开发中心12循环展开后代码的调度循环展开后代码的调度loop: ld f1, 0(r1) ld f2, 8(r1) ld f3, 16(r1) ld f4, 24(r1

13、) add r1, 32 fadd f5, f0, f1 fadd f6, f0, f2 fadd f7, f0, f3 fadd f8, f0, f4 sd f5, 0(r2) sd f6, 8(r2) sd f7, 16(r2) sd f8, 24(r2)add r2, 32 bne r1, r3, loopScheduleInt1Int 2M1M2FP+FPxloop:Unroll 4 waysld f1ld f2ld f3ld f4add r1fadd f5fadd f6fadd f7fadd f8sd f5sd f6sd f7sd f8add r2bneHow many FLOPS/

14、cycle?4 fadds / 11 cycles = 0.36北京大学微处理器研究开发中心13软件流水软件流水Software PipeliningSoftware Pipelining）loop: ld f1, 0(r1) ld f2, 8(r1) ld f3, 16(r1) ld f4, 24(r1) add r1, 32 fadd f5, f0, f1 fadd f6, f0, f2 fadd f7, f0, f3 fadd f8, f0, f4 sd f5, 0(r2) sd f6, 8(r2) sd f7, 16(r2) add r2, 32 sd f8, -8(r2) bne r

15、1, r3, loopInt1Int 2M1M2FP+FPxUnroll 4 ways firstld f1ld f2ld f3ld f4fadd f5fadd f6fadd f7fadd f8sd f5sd f6sd f7sd f8add r1add r2bneld f1ld f2ld f3ld f4fadd f5fadd f6fadd f7fadd f8sd f5sd f6sd f7sd f8add r1add r2bneld f1ld f2ld f3ld f4fadd f5fadd f6fadd f7fadd f8sd f5add r1loop:iterateprologepilogHo

16、w many FLOPS/cycle?How many FLOPS/cycle?4 fadds / 4 cycles = 1北京大学微处理器研究开发中心14软件流水与循环展开软件流水与循环展开timeperformancetimeperformanceLoop UnrolledSoftware PipelinedStartup overheadWind-down overheadLoop IterationLoop IterationSoftware pipelining pays startup/wind-down costs only once per loop, not once per

17、 iteration北京大学微处理器研究开发中心15如果没有循环，怎么办如果没有循环，怎么办? ?转移指令限制了控制流敏感的非转移指令限制了控制流敏感的非规则代码中基本块的大小规则代码中基本块的大小很难从单独的基本块中发现很难从单独的基本块中发现ILP ILP Basic block北京大学微处理器研究开发中心16踪迹调度踪迹调度Trace SchedulingTrace Scheduling） Fisher,Ellis Fisher,Ellis Pick string of basic blocks, a Pick string of basic blocks, a trace, that

18、represents most frequent trace, that represents most frequent branch pathbranch path Use profiling feedback or compiler Use profiling feedback or compiler heuristics to find common branch heuristics to find common branch paths paths Schedule whole “trace” at onceSchedule whole “trace” at once Add fi

19、xup code to cope with branches Add fixup code to cope with branches jumping out of tracejumping out of trace北京大学微处理器研究开发中心17“典型典型” ” VLIWVLIW的的问题问题目标代码的兼容性目标代码的兼容性需要针对每种机器重新编译所有代码，甚至对于同一代中的两种需要针对每种机器重新编译所有代码，甚至对于同一代中的两种不同机器也需要如此不同机器也需要如此目标代码的大小目标代码的大小 指令填充浪费指令存取空间存储器指令填充浪费指令存取空间存储器/cache/cache）循环展开循

20、环展开/ /软件流水将复制代码软件流水将复制代码需要调度访存延迟可变的操作需要调度访存延迟可变的操作caches caches 和和/ /或或 主存块的冲突可能产生静态时刻不可预知的变化主存块的冲突可能产生静态时刻不可预知的变化确认转移发生概率确认转移发生概率动态剖视动态剖视ProfilingProfiling需要增加巨大的一步来进行静态转移预需要增加巨大的一步来进行静态转移预测测对于静态时刻不可预测的转移进行调度对于静态时刻不可预测的转移进行调度根据转移路径的不同，最佳调度策略也不同根据转移路径的不同，最佳调度策略也不同北京大学微处理器研究开发中心18VLIWVLIW指令的指令的编码编码Sc

21、hemes to reduce effect of unused fieldsSchemes to reduce effect of unused fieldsCompressed format in memory, expand on I-cache Compressed format in memory, expand on I-cache refillrefillused in Multiflow Traceused in Multiflow Traceintroduces instruction addressing challengeintroduces instruction ad

22、dressing challengeMark parallel groupsMark parallel groupsused in TMS320C6x DSPs, Intel IA-64used in TMS320C6x DSPs, Intel IA-64Provide a single-op VLIW instructionProvide a single-op VLIW instruction Cydra-5 UniOp instructions Cydra-5 UniOp instructionsGroup 1Group 2Group 3北京大学微处理器研究开发中心19Rotating

23、Register FilesRotating Register FilesProblems: Scheduled loops require lots of registers, Lots of duplicated code in prolog, epilogSolution: Allocate new set of registers for each loop iterationld r1, ()add r2, r1, #1st r2, ()ld r1, ()add r2, r1, #1st r2, ()ld r1, ()add r2, r1, #1st r2, ()ld r1, ()a

24、dd r2, r1, #1st r2, ()ld r1, ()add r2, r1, #1st r2, ()ld r1, ()add r2, r1, #1st r2, ()PrologEpilogLoop北京大学微处理器研究开发中心20Rotating Register FileRotating Register FileP0P1P2P3P4P5P6P7RRB=3+R1Rotating Register Base (RRB) register points to base of current register set. Value added on to logical register s

25、pecifier to give physical register number. Usually, split into rotating and non-rotating registers.dec RRBbloopdec RRBdec RRBdec RRBld r1, ()add r3, r2, #1st r4, ()ld r1, ()add r3, r2, #1st r4, ()ld r1, ()add r2, r1, #1st r4, ()PrologEpilogLoopLoop closing branch decrements RRB北京大学微处理器研究开发中心21Rotati

26、ng Register FileRotating Register File(Previous Loop Example)(Previous Loop Example)bloopsd f9, ()fadd f5, f4, .ld f1, ()Three cycle load latency encoded as difference of 3 in register specifier number (f4 - f1 = 3)Four cycle fadd latency encoded as difference of 4 in register specifier number (f9 f

27、5 = 4)bloopsd P17, ()fadd P13, P12,ld P9, ()RRB=8bloopsd P16, ()fadd P12, P11,ld P8, ()RRB=7bloopsd P15, ()fadd P11, P10,ld P7, ()RRB=6bloopsd P14, ()fadd P10, P9,ld P6, ()RRB=5bloopsd P13, ()fadd P9, P8,ld P5, ()RRB=4bloopsd P12, ()fadd P8, P7,ld P4, ()RRB=3bloopsd P11, ()fadd P7, P6,ld P3, ()RRB=2

28、bloopsd P10, ()fadd P6, P5,ld P2, ()RRB=1北京大学微处理器研究开发中心22Cydra-5:Cydra-5:存存储储延延迟迟寄存器寄存器Memory Latency RegisterMemory Latency Register：MLR)MLR)问题问题: : 装入操作可能出现时延变化装入操作可能出现时延变化解决方案：让软件选择所需时延解决方案：让软件选择所需时延编译对代码进行调度以满足最大装入编译对代码进行调度以满足最大装入- -使用使用load-useload-use间隔间隔软件将软件将MLRMLR设置为机器代码调度的延迟设置为机器代码调度的延迟 硬件

29、保证装入操作在硬件保证装入操作在MLRMLR要求的周期将所需数值返回给处理器流要求的周期将所需数值返回给处理器流水线水线硬件将缓存提前返回的装入数值硬件将缓存提前返回的装入数值如果装入没有按时返回数值，硬件将暂停处理器如果装入没有按时返回数值，硬件将暂停处理器北京大学微处理器研究开发中心23Intel EPIC IA-64Intel EPIC IA-64 与传统与传统CISCCISC和和RISCRISC相比，相比，EPICEPIC是一种新型的体系结是一种新型的体系结构构 Explicitly Parallel Instruction ComputingExplicitly Parallel I

30、nstruction Computing IA-64IA-64是是IntelIntel最新采用的一种最新采用的一种ISAISA IA-64 = Intel Architecture 64-bitIA-64 = Intel Architecture 64-bit 一种目标代码兼容的一种目标代码兼容的VLIWVLIW Itanium (Itanium (最早称为最早称为Merced)Merced)是采用是采用IA-64IA-64的第一种的第一种处理器处理器 20192019年预计第一种产品在年预计第一种产品在20192019问世问世 ( (实际上为实际上为2019)2019) McKinleyMc

31、Kinley是是20192019年推出的第二类产品年推出的第二类产品北京大学微处理器研究开发中心24IA-64 IA-64 的指令格式的指令格式Template bits describe grouping of these Template bits describe grouping of these instructions with others in adjacent bundlesinstructions with others in adjacent bundlesEach group contains instructions that can Each group conta

32、ins instructions that can execute in parallelexecute in parallelInstruction 2Instruction 1Instruction 0Template128-bit instruction bundlegroup igroup i+1group i+2group i-1bundle jbundle j+1 bundle j+2bundle j-1北京大学微处理器研究开发中心25IA-64IA-64中的寄存器中的寄存器128128个个通用通用6464位定点寄存器位定点寄存器128128个个通用通用64/8064/80位浮点寄

33、存器位浮点寄存器6464个个1 1位位预测预测寄存器寄存器GPRGPR可以旋可以旋转转rotaterotate以以减减小小软软件流水化循件流水化循环环的代的代码码大小大小北京大学微处理器研究开发中心26IA-64 Predicated ExecutionIA-64 Predicated ExecutionProblem: Mispredicted branches limit ILPProblem: Mispredicted branches limit ILPSolution: Eliminate hard to predict branches with predicated execut

34、ionSolution: Eliminate hard to predict branches with predicated executionAlmost all IA-64 instructions can be executed conditionally under Almost all IA-64 instructions can be executed conditionally under predicatepredicateInstruction becomes NOP if predicate register falseInstruction becomes NOP if

35、 predicate register falseInst 1Inst 2br a=b, b2Inst 3Inst 4br b3Inst 5Inst 6Inst 7Inst 8b0:b1:b2:b3:ifelsethenFour basic blocksInst 1Inst 2p1,p2 50% branches removed北京大学微处理器研究开发中心27Predicate Software Pipeline StagesPredicate Software Pipeline StagesSingle VLIW InstructionSoftware pipeline stages tur

36、ned on by rotating predicate registers Much denser encoding of loops(p1) bloop(p3) st r4(p2) add r3(p1) ld r1Dynamic Execution(p1) ld r1(p1) ld r1(p1) ld r1(p1) ld r1(p1) ld r1(p2) add r3(p2) add r3(p2) add r3(p2) add r3(p2) add r3(p3) st r4(p3) st r4(p3) st r4(p3) st r4(p3) st r4(p1) bloop(p1) bloo

37、p(p1) bloop(p1) bloop(p1) bloop(p1) bloop(p1) bloop北京大学微处理器研究开发中心28IA-64 Speculative ExecutionIA-64 Speculative ExecutionProblem: Branches restrict compiler code motionProblem: Branches restrict compiler code motionInst 1Inst 2br a=b, b2Load r1Use r1Inst 3Cant move load above branch because might ca

38、use spurious exceptionLoad.s r1Inst 1Inst 2br a=b, b2Chk.s r1Use r1Inst 3Speculative load never causes exception, but sets “poison” bit on destination registerCheck for exception in original home block jumps to fixup code if exception detectedParticularly useful for scheduling long latency loads earlySolution: Speculative operations that dont cause Solution: Speculative operations that dont cause exceptionsexceptions北京大学微处理器研究