第6章指令级并行的开发软件方法

1/89▲第6章指令级并行的开发——软件方法沈立▲6.1基本指令调度及循环展开6.2跨越基本块的静态指令调度6.3静态多指令流出：VLIW技术6.4显式并行指令计算EPIC6.5开发更多的指令级并行6.6实例：IA-64体系结构3/89▲1.指令调度：找出不相关的指令序列，让它们在流水线上重叠并行执行。2.制约编译器指令调度的因素程序固有的指令级并行流水线功能部件的延迟6.1基本指令调度及循环展开6.1.1指令调度的基本方法4/89▲表6.1本节使用的浮点流水线的延迟6.1基本指令调度及循环展开产生结果的指令使用结果的指令延迟(cycles)浮点计算另一个浮点计算3浮点计算浮点store(S.D)2浮点Load(L.D)浮点计算1浮点Load(L.D)浮点store(S.D)05/89▲例6.1对于下面的源代码，转换成MIPS汇编语言，在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。for(i=1000;i0;i--)x[i]=x[i]+s;解：先把该程序翻译成MIPS汇编语言代码Loop：L.DF0,0(R1)ADD.DF4,F0,F2S.DF4,0(R1)DADDIUR1,R1,#-8BNER1,R2,Loop6/89▲6.1基本指令调度及循环展开在不进行指令调度的情况下，根据表中给出的浮点流水线中指令执行的延迟，程序的实际执行情况如下：指令流出时钟Loop：L.DF0,0(R1)1(空转)2ADD.DF4,F0,F23(空转)4(空转)5S.DF4,0(R1)6DADDIUR1,R1,#-87(空转)8BNER1,R2,Loop9(空转)107/89▲6.1基本指令调度及循环展开在用编译器对上述程序进行指令调度以后，程序的执行情况如下：指令流出时钟Loop：L.DF0,0(R1)1DADDIUR1,R1,#-82ADD.DF4,F0,F23(空转)4BNER1,R2,Loop5S.DF4,8(R1)68/89▲6.1基本指令调度及循环展开进一步分析：编译时指令调度是怎样减少整个指令序列在流水线上的执行时间的？指令调度能否跨越分支边界？怎样提高整个执行过程中有效操作的比率？9/89▲1.循环展开把循环体的代码复制多次并按顺序排放，然后相应调整循环的结束条件。开发循环级并行的有效方法例6.2将例6.1中的循环展开3次得到4个循环体，然后对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。假定R1的初值为32的倍数，即循环次数为4的倍数。消除冗余的指令，并且不要重复使用寄存器。6.1.2循环展开6.1基本指令调度及循环展开展开后没有调度的代码如下(需要分配寄存器)指令流出时钟Loop:L.DF0,0(R1)1（空转）2ADD.DF4,F0,F23（空转）4（空转）5S.DF4,0(R1)6L.DF6,-8(R1)7（空转）8ADD.DF8,F6,F29（空转）10（空转）11S.DF8,-8(R1)12L.DF10,-16(R1)13（空转）14指令流出时钟ADD.DF12,F10,F215（空转）16（空转）17S.DF12,-16（R1）18L.DF14,-24（R1）19（空转）20ADD.DF16,F14,F221（空转）22（空转）23S.DF16,-24（R1）24DADDIUR1,R1,#-3225（空转）26BNER1,R2,Loop27（空转）2850%是空转周期！调度后的代码如下：指令流出时钟Loop:L.DF0,0（R1）1L.DF6,-8（R1）2L.DF10,-16（R1）3L.DF14,-24（R1）4ADD.DF4,F0,F25ADD.DF8,F6,F26ADD.DF12,F10,F27ADD.DF16,F14,F28S.DF4,0（R1）9S.DF8,-8（R1）10DADDIUR1,R1,#-3212S.DF12,16（R1）11BNER1,R2,Loop13S.DF16,8（R1）14没有空转周期！结论：通过循环展开、寄存器重命名和指令调度，可以有效开发出指令级并行。12/89▲6.1基本指令调度及循环展开2.循环展开和指令调度的注意事项保证正确性注意有效性使用不同的寄存器删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。注意对存储器数据的相关性分析注意新的相关性13/89▲1.概述目标：在保持原有数据相关和控制相关不变的前提下，尽可能地缩短包含分支结构的代码段的总执行时间。单流出处理器——减少指令数多流出处理器——缩短关键路径长度基本思想：在循环体内的多个基本块间移动指令，扩大那些执行频率较高的基本块的体积。6.2跨越基本块的静态指令调度6.2.1全局指令调度14/89▲6.2跨越基本块的静态指令调度2.实例分析由于分支条件为true(转移)的概率大，全局指令调度时会将语句1、2、3、5合并为一个更大的基本块。1:A[i]=A[i]+B[i]2:A[i]=0?3:B[i]=5:C[i]=4:XTrueFalseelse部分Then部分一个分支结构的代码段如何保证分支条件为false时结果依然正确？如何将语句3和5调度到语句2之前？15/89▲6.2跨越基本块的静态指令调度将上图中的代码转换为下面的MIPS汇编指令LDR4，0(R1)//取ALDR5，0(R2)//取BDADDUR4，R4，R5//A=A+BSD0(R1)，R4//存ABNEZR4，elsepart//A=0则转移X//代码段X，基本块elsepartJjointhenpart：//基本块thenpartSD…，0(R2)//指令I1，对应语句3join：SD…，0(R3)//指令I2，对应语句516/89▲6.2跨越基本块的静态指令调度调度指令I1直接将I1移到BEQZ前是否会产生错误结果？向基本块elsepart中增加补偿代码补偿代码有可能带来额外时间开销调度指令I2将I2移动到基本块thenpart中，同时复制到elsepart中。若不影响执行结果，将I2调度到BEQZ前，同时删除elsepart中的副本。17/89▲6.2跨越基本块的静态指令调度3.全局指令调度是一个很复杂的问题以I1的调度为例：需要确定分支中基本块thenpart和elsepart的执行频率各是多少？在分支语句前完成I1所需的开销是多大？调度I1是否能够缩短thenpart块的执行时间？I1是否是最佳的被调度对象？是否需要向elsepart块中增加补偿代码，补偿代码开销如何？怎样生成补偿代码？18/89▲1.概述踪迹（trace）：程序执行的指令序列，通常由一个或多个基本块组成，trace内可以有分支，但一定不能包含循环。踪迹调度（tracescheduling）会优化执行频率高的trace，减少其执行开销。由于需要添加补偿代码以确保正确性，那些执行频率较低的trace的开销反而会有所增加。踪迹调度非常适合多流出处理器。6.2.2踪迹调度6.2跨越基本块的静态指令调度19/89▲2.踪迹调度的步骤分为两步：踪迹选择和踪迹压缩踪迹选择从程序的控制流图中选择执行频率较高的路径，每条路径就是一条trace。处理转移成功与失败概率相差较大的情况循环结构：循环展开分支结构：根据典型输入集下的运行统计信息6.2跨越基本块的静态指令调度20/89▲踪迹选择——实例分析6.2跨越基本块的静态指令调度1:A[i]=A[i]+B[i]2:A[i]=0?3:B[i]=5:C[i]=4:Xtruefalsethen部部else部部A[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=truefalsetrace部部A[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=truefalsetrace部部trace部部A[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=truefalsetrace部部trace部部A[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=truefalsetrace部部trace部部将左边的循环展开4次并把阴影部分(执行频率高)拼接在一起就可以得到一条trace；一条trace可以有多个入口和多个出口。21/89▲踪迹压缩对已生成的trace进行指令调度和优化，尽可能地缩短其执行时间；跨越trace内部的入口或出口调度指令时必须非常小心，有时还需要增加补偿代码。6.2跨越基本块的静态指令调度B1B3B4B5B2B6B7NNNYYYB1:x=x+1y=x–yifx5gotoB3B2:z=x*zy=y+1gotoB5B3:y=2*yx=x-2(a)部部部部B1:x=x+1ifx5gotoB3B2:y=x–yz=x*zy=y+1gotoB5B3:y=x–yy=2*yx=x-2(b)部部部部部部部部部部B1部B2部B3部部部部部部三条trace：B1-B3、B4以及B5-B7指令“y=x-y”被从B1调度到B3中，跨越了trace的一个出口；需要向块B2中增加补偿代码，即将指令“y=x-y”复制到B2的第一条指令之前。22/89▲3.踪迹调度的性能特点踪迹调度能够提升性能的最根本原因在于选出的trace都是执行频率很高的路径，减少它们的执行开销有助于缩短程序的总执行时间。对于某些应用，补偿代码引起的开销很有可能降低踪迹调度的优化效果。踪迹调度会大大增加编译器的实现复杂度。6.2跨越基本块的静态指令调度23/89▲1.概述在踪迹调度中，如果trace入口或出口位于trace内部，编译器生成补偿代码的难度将大大增加，而且编译器很难评估这些补偿代码究竟会带来多少性能损失。超块（superblock）是只能拥有一个入口，但可以拥有多个出口的结构超块的构造过程与trace相似，但怎样确保只有一个入口？6.2.3超块调度6.2跨越基本块的静态指令调度24/89▲2.超块构造——尾复制技术6.2跨越基本块的静态指令调度1:A[i]=A[i]+B[i]2:A[i]=0?3:B[i]=5:C[i]=4:Xtruefalsethen部部else部部将左边的循环展开4次并把阴影部分(执行频率高)拼接在一起就可以得到一个超块；超块有1个入口和5个出口(n=4/3/2/1/0)。除了n=0外，从其他4个出口退出超块后，还需要继续完成余下的n次叠代(黄色部分)。A[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=truefalseA[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=truefalseA[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=truefalseA[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=truefalseA[i]=A[i]+B[i]A[i]=0?B[i]=C[i]=XTrueFalse部部4-n部n=4部部部部部n=3部部部部部n=2部部部部部n=1部部部部部n=0部部部部部25/89▲3.超块调度的性能特点尾复制技术简化了补偿代码的生成过程，并降低了指令调度的复杂度。超块结构目标代码的体积也大大增加。补偿代码的生成使得编译过程更加复杂，而且由于无法准确评估由补偿代码引起的时间开销，这限制方法超块调度的应用范围。6.2跨越基本块的静态指令调度26/89▲1.VLIWvs.超标量在动态调度的超标量处理器中，相关检测和指令调度基本都由硬件完成。在静态调度的超标量处理器中，部分相关检测和指令调度工作交由编译器完成。在VLIW处理器中，相关检测和指令调度工作全部由编译器完成，它需要更“智能”的编译器。6.3静态多指令流出：VLIW技术slotslotslotslot32bit32bit32bit32bit128bitVLIW指令27/89▲2.实例分析6.3静态多指令流出——VLIW技术例6.3假设某VLIW处理器每个时钟周期可以同时流出