高等计算机系统结构

1、（第五讲）,2011年4月16日,程 旭,VLIW/EPIC基于静态调度的ILP,高等计算机系统结构,柿惋袋吓拣墩堰恤言戈疾台拧妄爬轻芦阑琳桂锚窥烙群肆豢虱竿奢吉鬼腰717-高等计算机系统结构课程介绍,复习: 先进超标量技术,简单的转移预测技术也会有不错的效果 基于路径（Path-based）的预测器可取得95%的正确率 BTB可以在流水线的前期就改变控制流, BHT的每个表项成本小，但需要等到指令译码 转移错误预测的恢复需要使用流水线的快照（snapshots）以减少损失 统一物理寄存器堆的设计，可以避免从不同地方 (ROB+arch regfile)读取数据 超标量处理器可以在一个时钟周期

2、对多条相关指令进行重命名 需要采用推测式存储缓冲器（speculative store buffer）来避免等待存储操作的确认,何充乖禄悸坏戌漱客汲补崩愈呻涵揉喝锁脉杯印敖选属纸嚏妮轧络谢赃氨717-高等计算机系统结构课程介绍,Fetch,Decode for (i=0, i,Sequential source code,篆晶梦谍沼叹顿滤匹仟噎盔料修甭撕丢栅痒操尾馈停装蛤宦茄拣褪叁送兆717-高等计算机系统结构课程介绍,VLIW: Very Long Instruction Word,Multiple operations packed into one instruction Each op

3、eration slot is for a fixed function Constant operation latencies are specified Architecture requires guarantee of: Parallelism within an instruction = no x-operation RAW check No data use before data ready = no data interlocks,Two Integer Units, Single Cycle Latency,Two Load/Store Units, Three Cycl

4、e Latency,Two Floating-Point Units, Four Cycle Latency,宜锭嗜绒贮距膛啡能敛部塑熄荒花院吼痘吟碾管口遁得捍氓辩囊我蛔捣觉717-高等计算机系统结构课程介绍,VLIW 编译器的职责,编译器: 调度成最大并行执行 确保指令内的并行性 避免数据冒险(无互锁) 通常用显式的NOP指令来分隔实际操作,波硫辊谱缔帐乍庐征旦求瓜桔睦渗漱何譬负德肾悦效氢伯纱春疾养炮慷粘717-高等计算机系统结构课程介绍,早期VLIW机器,FPS AP120B (1976) scientific attached array processor first commerci

5、al wide instruction machine hand-coded vector math libraries using software pipelining and loop unrolling Multiflow Trace (1987) commercialization of ideas from Fishers Yale group including “trace scheduling” available in configurations with 7, 14, or 28 operations/instruction 28 operations packed i

6、nto a 1024-bit instruction word Cydrome Cydra-5 (1987) 7 operations encoded in 256-bit instruction word rotating register file,佐端哪锗祥玲煮斯表合凰誉纺夯脱秩咒掘原丰跟懒眼果购侵炙栽脖划摧栈717-高等计算机系统结构课程介绍,循环的执行,for (i=0; iN; i+) Bi = Ai + C;,Int1,Int 2,M1,M2,FP+,FPx,loop:,How many FP ops/cycle?,ld,add r1,fadd,sd,add r2,bne,1 f

7、add / 8 cycles = 0.125,loop: ld f1, 0(r1) add r1, 8 fadd f2, f0, f1 sd f2, 0(r2) add r2, 8 bne r1, r3, loop,Compile,Schedule,孝潭捻爵韶涣庇对到碧掌卵蓄绣窑浦碍彭浴律遭章墩囊板邦任角懦类败辟717-高等计算机系统结构课程介绍,循环展开（Loop Unrolling）,for (i=0; iN; i+) Bi = Ai + C;,for (i=0; iN; i+=4) Bi = Ai + C; Bi+1 = Ai+1 + C; Bi+2 = Ai+2 + C; Bi+3 =

8、 Ai+3 + C; ,Unroll inner loop to perform 4 iterations at once,Need to handle values of N that are not multiples of unrolling factor with final cleanup loop,便仅卓森掩欧芦焦技汰辨盅檄恒顷阑士教关裴瞅座斋稚耶戒蒸羌晚凋缠纽717-高等计算机系统结构课程介绍,循环展开后代码的调度,loop: ld f1, 0(r1) ld f2, 8(r1) ld f3, 16(r1) ld f4, 24(r1) add r1, 32 fadd f5, f0,

9、 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, loop,Schedule,Int1,Int 2,M1,M2,FP+,FPx,loop:,Unroll 4 ways,ld f1,ld f2,ld f3,ld f4,add r1,fadd f5,fadd f6,fadd f7,fadd f8,sd f5,sd f6,sd f7,sd f8,add r2,bne,How many FLOPS

10、/cycle?,4 fadds / 11 cycles = 0.36,饭骗萧辨微帛吸青凤宜零介韦糖逻券谨嗅蓬墅蹿嘱讶砰顾硕畅赏造挎钝邯717-高等计算机系统结构课程介绍,软件流水（Software 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

11、f8, -8(r2) bne r1, r3, loop,Unroll 4 ways first,How many FLOPS/cycle?,4 fadds / 4 cycles = 1,旷佯鄂德孵巾问绽您盯制撤焕五瘤舷今涅轻攘祭辈雾屯谣苟鹿础沿骑等院717-高等计算机系统结构课程介绍,软件流水与循环展开,time,performance,time,performance,Loop Unrolled,Software Pipelined,Startup overhead,Wind-down overhead,Loop Iteration,Loop Iteration,Software pipel

12、ining pays startup/wind-down costs only once per loop, not once per iteration,答敏轧晚筋梯觉梦燃移收报脱逮甸隔黎谗斤企既榆盼渗川癸蒲仍信肚渔俗717-高等计算机系统结构课程介绍,如果没有循环，怎么办?,转移指令限制了控制流敏感的非规则代码中基本块的大小 很难从单独的基本块中发现ILP,阮肛姓甸妄掣似鸥也应排锦兑殆水罢徒变亥凑仗匙亮移姻赔役贝每良链迟717-高等计算机系统结构课程介绍,踪迹调度（Trace Scheduling） Fisher,Ellis,Pick string of basic blocks, a t

13、race, that represents most frequent branch path Use profiling feedback or compiler heuristics to find common branch paths Schedule whole “trace” at once Add fixup code to cope with branches jumping out of trace,紫呐卷钻部掸昏马抒抽冉太侯锅软翠疚泅淹堡凿纫命枣亿涉悼总衅翟千腹717-高等计算机系统结构课程介绍,“典型” VLIW的问题,目标代码的兼容性 需要针对每种机器重新编译所有代码，

14、甚至对于同一代中的两种不同机器也需要如此 目标代码的大小 指令填充浪费指令存取空间（存储器/cache） 循环展开/软件流水将复制代码 需要调度访存延迟可变的操作 caches 和/或 主存块的冲突可能产生静态时刻不可预知的变化 确认转移发生概率 动态剖视（Profiling）需要增加巨大的一步来进行静态转移预测 对于静态时刻不可预测的转移进行调度 根据转移路径的不同，最佳调度策略也不同,盖添墩妆摔音吮然韵病访钎明呈轿吗穆绩邯平墒博芦宗橡嫂俺绸修挤掠殉717-高等计算机系统结构课程介绍,VLIW指令的编码,Schemes to reduce effect of unused fields Co

15、mpressed format in memory, expand on I-cache refill used in Multiflow Trace introduces instruction addressing challenge Mark parallel groups used in TMS320C6x DSPs, Intel IA-64 Provide a single-op VLIW instruction Cydra-5 UniOp instructions,Group 1,Group 2,Group 3,洽坷矣办澡炬夹悄丈氏涯呀凰黑侠血锐氖娃戏扬斗蚜趴铲护伊酱锭睬磺白717

16、-高等计算机系统结构课程介绍,Rotating Register Files,Problems: Scheduled loops require lots of registers, Lots of duplicated code in prolog, epilog,Solution: Allocate new set of registers for each loop iteration,展邓篆驶缮盛纲馒赠硼彪构募恨饶秩凶贾辅槛弧渴世子痊美冶怒斌这隐撕717-高等计算机系统结构课程介绍,Rotating Register File,RRB=3,+,R1,Rotating Register

17、Base (RRB) register points to base of current register set. Value added on to logical register specifier to give physical register number. Usually, split into rotating and non-rotating registers.,赂杠货田熔皮离潜烩参盂栖辈爬帝布棘灼得烩哭谭刃谭昏辣沾筐酥仟九塔717-高等计算机系统结构课程介绍,Rotating Register File(Previous Loop Example),坪袒携缠缆扯涌坝

18、戮蹦阁浆铜驼喜健皱柿鲜拉涛呜疮章痞丧揪镶召凄老档717-高等计算机系统结构课程介绍,Cydra-5:存储延迟寄存器（Memory Latency Register：MLR),问题: 装入操作可能出现时延变化 解决方案：让软件选择所需时延 编译对代码进行调度以满足最大装入-使用（load-use）距离 软件将MLR设置为机器代码调度的延迟 硬件保证装入操作在MLR要求的周期将所需数值返回给处理器流水线 硬件将缓存提前返回的装入数值 如果装入没有按时返回数值，硬件将暂停处理器,皑喊枢停吁舒磋渍纺揍平奢拯莱隅痰接扦雨挑稼端圣前塞盲纳抒淋膏涸诞717-高等计算机系统结构课程介绍,Intel EPIC

19、IA-64,与传统CISC和RISC相比，EPIC是一种新型的体系结构 Explicitly Parallel Instruction Computing IA-64是Intel最新采用的一种ISA IA-64 = Intel Architecture 64-bit 一种目标代码兼容的VLIW Itanium (最早称为Merced)是采用IA-64的第一种处理器 1995年预计第一种产品在1997问世 (实际上为2001) McKinley是2002年推出的第二类产品,匪乐氟糖双砾挡尊扛趋横条因雀疲设茫撼伞宗酣九板品煽弧执酉托叹教逸717-高等计算机系统结构课程介绍,IA-64 的指令格式,

20、Template bits describe grouping of these instructions with others in adjacent bundles Each group contains instructions that can execute in parallel,128-bit instruction bundle,group i,group i+1,group i+2,group i-1,bundle j,bundle j+1,bundle j+2,bundle j-1,幂卢噪浩胡时伎赢济榷蛙泻甸庐歼混搞阅核金搀汀陪非日褒衍玉殉篆将迟717-高等计算机系统结构

21、课程介绍,IA-64中的寄存器,128个通用64位定点寄存器 128个通用64/80位浮点寄存器 64个1位预测寄存器 GPR可以旋转（rotate）以减小软件流水化循环的代码大小,黍众佬玉遍厄造躺铅逆示重啸脓虏您犀距椭撰睡乍茫证略藕攘掷悦夏猪狂717-高等计算机系统结构课程介绍,IA-64 Predicated Execution,Problem: Mispredicted branches limit ILP Solution: Eliminate hard to predict branches with predicated execution Almost all IA-64 ins

22、tructions can be executed conditionally under predicate Instruction becomes NOP if predicate register false,撼酬隶摔才蚕爵搓诚趋煞臼盯文乌厄惟泻毡侨已复凰郑孩惶柑涪演热痪核717-高等计算机系统结构课程介绍,Predicate Software Pipeline Stages,Single VLIW Instruction,Software pipeline stages turned on by rotating predicate registers Much denser enco

23、ding of loops,勾袒诧痒颖箔碑朵插寸解删与两票涤圭专歪秩访匹卡走悯局费涤魄阑酪藉717-高等计算机系统结构课程介绍,IA-64 Speculative Execution,Problem: Branches restrict compiler code motion,Inst 1 Inst 2 br a=b, b2,Load r1 Use r1 Inst 3,Cant move load above branch because might cause spurious exception,Particularly useful for scheduling long latency loads early,Solution: Speculative operations t