第06章 指令级并行-软件方法

1、张晨曦 编著 华中科技大学 计算机学院 2 0 1 3 年 4 月 2 23232 6.1指令调度与循环展开 6.2跨越基本块的静态流水指令调度 6.3静态多指令流出: VLIW 6.4显式并行指令计算EPIC 6.5 开发更多的指令级并行 第六章 指令级并行软件方法 3 33232 6.1.1 循环展开调度的基本方法 1. 1. 指令调度指令调度 通过改变指令在程序中的位置，将相关指通过改变指令在程序中的位置，将相关指 令之间的距离加大到不小于指令执行延迟，将令之间的距离加大到不小于指令执行延迟，将 相关指令转化为无关指令。相关指令转化为无关指令。 指令调度是循环展开的技术基础。指令调度是循

2、环展开的技术基础。 2. 2. 编译器在完成这种指令调度时，受限于以下两编译器在完成这种指令调度时，受限于以下两 个特性：个特性： 程序固有的指令级并行性程序固有的指令级并行性 流水线功能部件的执行延迟流水线功能部件的执行延迟 6.1 指令级并行的概念 4 43232 6.1 指令级并行的概念 表表6.2 6.2 假设的流水线延迟假设的流水线延迟 产生结果指令产生结果指令使用结果指令使用结果指令延迟时钟周期数延迟时钟周期数 浮点计算浮点计算另外的浮点操作另外的浮点操作3 3 浮点计算浮点计算浮点数据存操作浮点数据存操作(SD)(SD)2 2 浮点数据取操作浮点数据取操作(LD)(LD)浮点计算

3、浮点计算1 1 浮点数据取操作浮点数据取操作(LD)(LD)浮点数据存操作浮点数据存操作(SD)(SD)0 0 u 分支指令使用上一条指令的结果作为分支条件分支指令使用上一条指令的结果作为分支条件, , 将要等待一拍将要等待一拍 u 分支指令有一个节拍的延迟槽分支指令有一个节拍的延迟槽 5 53232 例例6.16.1 对于下面的源代码，转换成对于下面的源代码，转换成MIPSMIPS汇编语言，汇编语言， 在在不进行指令调度不进行指令调度和和进行指令调度进行指令调度两种情况下，两种情况下， 分析代码一次循环的执行时间。分析代码一次循环的执行时间。 for (i=1; i=1000; i+)for

4、 (i=1; i=1000; i+) xi = xi + s; xi = xi + s; 6.1 指令级并行的概念 6 63232 解：解：(1)(1) 变量分配寄存器变量分配寄存器 整数寄存器整数寄存器R1R1：循环计数器，初值为：循环计数器，初值为=8000?=8000? 中最高端地址元素的地址。中最高端地址元素的地址。 浮点寄存器浮点寄存器F2F2：保存常数：保存常数S S。 假定最低端元素的地址为假定最低端元素的地址为8 8。 (2)(2) MIPSMIPS汇编语言后的程序汇编语言后的程序 Loop: LD F0,0(R1) Loop: LD F0,0(R1) / /* *0(R1)0

5、(R1)即即x x的地址的地址* */ / ADDD F4,F0,F2 ADDD F4,F0,F2 SD SD 0(R1),F4 0(R1),F4 SUBI R1,R1,#8 SUBI R1,R1,#8/ /* *为什么是为什么是8?8?* */ / BNEZ R1,Loop BNEZ R1,Loop 6.1 指令级并行的概念 7 73232 (3)(3) 程序执行的实际时钟程序执行的实际时钟 根据根据表表6-26-2中给出的的延迟，实际时钟如下：中给出的的延迟，实际时钟如下： 指令流出时钟指令流出时钟 Loop: LD F0, 0(R1) 1Loop: LD F0, 0(R1) 1 ( (空

6、转空转) ) 2 2 ADDD F4, F0 , F2 3 ADDD F4, F0 , F2 3 ( (空转空转) ) 4 4 ( (空转空转) ) 5 5 SD SD 0(R1), F4 0(R1), F4 6 6 SUBI R1, R1, #8 SUBI R1, R1, #8 7 7 ( (空转空转) ) 8 8 BNEZ R1, Loop 9 BNEZ R1, Loop 9 ( (空转空转) 10) 10 每个元素的操作需要每个元素的操作需要1010个时钟周期，其中个时钟周期，其中5 5个个 是空转周期。是空转周期。 6.1 指令级并行的概念 8 83232 (4)(4) 指令调度以后，

7、程序的执行情况指令调度以后，程序的执行情况 SDSD放在分支指令的分支延迟槽中放在分支指令的分支延迟槽中，BNEZBNEZ放在了空转周期！放在了空转周期！ 对存储器地址偏移量进行调整对存储器地址偏移量进行调整 指令流出时钟指令流出时钟 Loop: LD F0, 0(R1) 1Loop: LD F0, 0(R1) 1 SUBI R1, R1 , #SUBI R1, R1 , #8 8 2 2 ADDD F4, F0 , F2 ADDD F4, F0 , F2 3 3 ( (空转空转) ) 4 4 BNEZ R1, LoopBNEZ R1, Loop 5 5 SD SD 8 8(R1), F4(R

8、1), F4 6 6 一个元素的操作时间从一个元素的操作时间从1010个时钟周期减少到个时钟周期减少到6 6个个 5 5个周期是有指令执行的，个周期是有指令执行的，1 1个空转周期。个空转周期。 6.1 指令级并行的概念 9 93232 (5)(5) 例子中的问题及解决方案例子中的问题及解决方案 只有只有LDLD、ADDDADDD和和SDSD这这3 3条指令是有效操作条指令是有效操作. . 占用占用3 3个时钟周期个时钟周期 而而SUBISUBI、空转空转和和BENZBENZ这这3 3个时钟周期都是个时钟周期都是附加附加的的 循环控制开销循环控制开销。 循环展开技术循环展开技术 多次复制循环体

9、并相应调整展开后的指令和循环多次复制循环体并相应调整展开后的指令和循环 结束条件，增加有效操作时间与控制操作时间的结束条件，增加有效操作时间与控制操作时间的 比率。比率。 也给编译器进行指令调度带来了更大的空间。也给编译器进行指令调度带来了更大的空间。 6.1 指令级并行的概念 10103232 例例6.2 6.2 体现循环展开技术的特点体现循环展开技术的特点 将将例例6.16.1中的循环展开成中的循环展开成3 3次次得到得到4 4个个循循 环体，再对展开后的指令序列在不调度和环体，再对展开后的指令序列在不调度和 调度两种情况下，分析代码的性能。调度两种情况下，分析代码的性能。 假定假定R1R

10、1的初值为的初值为3232的倍数，即循环的倍数，即循环 次数为次数为4 4的倍数。的倍数。 6.1 指令级并行的概念 11113232 解：解： 补偿代码问题补偿代码问题 寄存器分配寄存器分配 展开后的循环体内不重复使用寄存器。展开后的循环体内不重复使用寄存器。 F0F0、F4F4：用于展开后的第：用于展开后的第1 1个循环体个循环体 F2F2：保存常数：保存常数 F6F6和和F8F8：用于展开后的第用于展开后的第2 2个循环体个循环体 F10F10和和F12F12：用于第用于第3 3个循环体个循环体 F14F14和和F16F16：用于第用于第4 4个循环体个循环体 6.1 指令级并行的概念

11、12123232 (1)(1) 展开后没有调度的代码展开后没有调度的代码 流出时钟流出时钟 Loop:Loop:LD F0,0(R1)LD F0,0(R1) 1 1 （空转）（空转） 2 2 ADDD F4,F0,F2ADDD F4,F0,F2 3 3 （空转）（空转） 4 4 （空转）（空转） 5 5 SD 0(R1),F4SD 0(R1),F4 6 6 LD F6,LD F6,-8-8(R1)(R1) 7 7 （空转）（空转） 8 8 ADDD F8,F6,F2ADDD F8,F6,F2 9 9 （空转）（空转） 1010 （空转）（空转） 1111 SD SD -8-8(R1),F8 1

12、2(R1),F8 12 LD F10,-16(R1) 13LD F10,-16(R1) 13 （空转）（空转） 1414 流出时钟流出时钟 ADDDADDDF12,F10,F2F12,F10,F2 15 15 （空转）（空转） 16 16 （空转）（空转） 1717 SDSD-16(R1),F12-16(R1),F12 18 18 LDLDF14,-24(R1) 19F14,-24(R1) 19 （空转）（空转） 2020 ADDDADDDF16,F14,F2F16,F14,F2 21 21 （空转）（空转） 2222 （空转）（空转） 2323 SDSD-24(R1),F16 24-24(R

13、1),F16 24 SUBISUBIR1,R1,#R1,R1,#3232 25 25 （空转）（空转） 2626 BNEZBNEZR1,Loop 27R1,Loop 27 （空转）（空转） 2828 6.1 指令级并行的概念 13133232 结果分析结果分析: : 这个循环每遍共使用了这个循环每遍共使用了2828个时钟周期个时钟周期 有有4 4个个循环体，完成循环体，完成4 4个个元素的操作元素的操作 平均每个元素使用平均每个元素使用28/4=728/4=7个时钟周期个时钟周期 原始循环的每个元素需要原始循环的每个元素需要1010个时钟周期个时钟周期 节省的时间节省的时间: :从从减少循环控

14、制减少循环控制的开销中获得的的开销中获得的 在整个展开后的循环中，实际指令只有在整个展开后的循环中，实际指令只有1414条，条， 其它其它1313个周期都是空转。个周期都是空转。 效率并不高效率并不高 6.1 指令级并行的概念 14143232 (2)(2) 对指令序列进行优化调度对指令序列进行优化调度 Loop:Loop:LDLDF0F0,0(R1),0(R1)1 1 LD LDF6F6,-8(R1),-8(R1)2 2 LD LDF10F10,-16(R1),-16(R1) 3 3 LD LDF14F14,-24(R1),-24(R1) 4 4 ADDD ADDDF4,F0,F2F4,F0

15、,F25 5 ADDD ADDDF8,F6,F2F8,F6,F26 6 ADDD ADDDF12,F10,F2F12,F10,F2 7 7 ADDD ADDDF16,F14,F2F16,F14,F2 8 8 SD SD0(R1),F40(R1),F49 9 SD SD-8(R1),F8-8(R1),F81010 SUBI SUBIR1,R1,#32R1,R1,#32 12 12 SD SD16(R1),F1216(R1),F12 11 11 / /* *16-32=-1616-32=-16* */ / BNEZ BNEZR1,LoopR1,Loop 13 13 SD SD8(R1),F168(

16、R1),F16 14 14 / /* *8-32=-248-32=-24* */ / 6.1 指令级并行的概念 指令流出时钟指令流出时钟 15153232 结果分析：结果分析： 没有数据相关引起的空转等待没有数据相关引起的空转等待 整个循环仅仅使用了整个循环仅仅使用了1414个时钟周期个时钟周期 平均每个元素的操作使用平均每个元素的操作使用14/4=3.514/4=3.5个时钟周期个时钟周期 循环展开循环展开和和指令调度指令调度可以有效地提高循环级并可以有效地提高循环级并 行性。行性。 这种循环级并行性的提高实际是通过实现指令级这种循环级并行性的提高实际是通过实现指令级 并行来达到的。并行来达

17、到的。寄存器开销增大！寄存器开销增大！ 可以使用编译器来完成，也可以通过硬件来可以使用编译器来完成，也可以通过硬件来 完成。完成。 6.1 指令级并行的概念 16163232 4. 4. 循环展开和指令调度时要注意的问题循环展开和指令调度时要注意的问题 (1) (1) 保证正确性保证正确性 (2) (2) 注意有效性注意有效性 (3) (3) 使用不同的寄存器使用不同的寄存器 (4) (4) 尽可能减少循环控制中的测试指令和分支指令尽可能减少循环控制中的测试指令和分支指令 (5) (5) 注意对存储器数据的相关性分析注意对存储器数据的相关性分析 (6) (6) 注意新的相关性注意新的相关性 5

18、. 5. 实现循环展开的关键实现循环展开的关键 分析清楚代码中指令的相关性，然后通过分析清楚代码中指令的相关性，然后通过 指令调度来消除相关指令调度来消除相关. . 6.1 指令级并行的概念 17173232 6.5.1 相关性 开发指令级并行的开发指令级并行的关键关键 存在相关的两条指令，不能改变它们的顺序。存在相关的两条指令，不能改变它们的顺序。 相关是否导致流水线的空转，还与流水线的相关是否导致流水线的空转，还与流水线的 组织与结构有关。组织与结构有关。 程序中程序中的相关主要有以下三种的相关主要有以下三种 数据相关数据相关 名相关名相关 控制相关控制相关 6.5 开发更多的指令级并行

19、18183232 1. 1. 数据相关数据相关（Data dependenceData dependence） 对于对于指令指令i i和和指令指令j j，如果，如果 (1) (1) 指令指令j j使用使用指令指令i i产生的结果，或者产生的结果，或者 (2) (2) 指令指令j j与与指令指令k k数据相关，数据相关，指令指令k k与与指令指令i i数据相数据相 关，则关，则指令指令j j与与指令指令i i数据相关。数据相关。 数据相关具有传递性。数据相关具有传递性。 数据相关是两条指令之间存在一个先写后读相关链。数据相关是两条指令之间存在一个先写后读相关链。 相关链贯穿整个程序，是程序的内在

20、特征。相关链贯穿整个程序，是程序的内在特征。 这种相关链是导致流水线停顿的原因之一。这种相关链是导致流水线停顿的原因之一。 6.5 开发更多的指令级并行 19193232 指令的相关指令的相关( (依赖依赖) )距离（距离（DistanceDistance） 两条指令之间的指令条数。两条指令之间的指令条数。 分析数据相关的主要工作分析数据相关的主要工作: : (1) (1) 确定指令的相关性，找到所有可能产生停确定指令的相关性，找到所有可能产生停 顿的地方。顿的地方。 (2) (2) 确定必须严格遵守的数据的计算顺序。确定必须严格遵守的数据的计算顺序。 (3) (3) 确定指令的最大相关距离，

21、确定程序中可确定指令的最大相关距离，确定程序中可 能的最大并行性。能的最大并行性。 6.5 开发更多的指令级并行 20203232 2. 2. 名相关（名相关（Name dependenceName dependence） 指令使用的寄存器或存储器称为指令使用的寄存器或存储器称为名名。 如果两条指令使用相同的名，但是它们之间并如果两条指令使用相同的名，但是它们之间并 没有数据流，则称之为没有数据流，则称之为名相关名相关。 指令指令j j与与指令指令i i之间名相关有以下两种：之间名相关有以下两种： (1) (1) 反相关反相关（anti-dependenceanti-dependence） (

22、2) (2) 输出相关输出相关（output dependenceoutput dependence） 6.5 开发更多的指令级并行 21213232 消除名相关消除名相关 名相关的指令之间没有数据交换。名相关的指令之间没有数据交换。 如果一条指令中的名改变了，并不影响另外一如果一条指令中的名改变了，并不影响另外一 条指令的执行。条指令的执行。 通过改变指令中操作数的名来消除名相关，这通过改变指令中操作数的名来消除名相关，这 就是就是换名（换名（renamingrenaming）技术）技术。 对于寄存器操作数进行换名称为对于寄存器操作数进行换名称为寄存器换名寄存器换名。 (register r

23、enaming)(register renaming) 可以用编译器静态完成或硬件动态完成。可以用编译器静态完成或硬件动态完成。 6.5 开发更多的指令级并行 22223232 例：例：我们对我们对例例6.26.2编译过程进行分析，来仔细考察编译过程进行分析，来仔细考察 换名的过程。换名的过程。 (1) (1) 首先，仅仅去除首先，仅仅去除4 4遍循环体中的分支指令，遍循环体中的分支指令， 得到以下由得到以下由1717条指令构成的指令序列：条指令构成的指令序列： 6.5 开发更多的指令级并行 23233232 Loop: LD F0, 0(R1)Loop: LD F0, 0(R1) ADDD

24、F4, F0, F2 ADDD F4, F0, F2 SD 0(R1), F4 SD 0(R1), F4 SUBI SUBI R1R1, R1, #8, R1, #8 LD F0, 0( LD F0, 0(R1R1) ) ADDD F4, F0, F2 ADDD F4, F0, F2 SD 0( SD 0(R1R1), F4), F4 SUBI R1, SUBI R1, R1R1, #8, #8 LD LD F0, 0(R1)F0, 0(R1) ADDDADDDF4, F0, F2F4, F0, F2 SDSD 0(R1), F4 0(R1), F4 SUBISUBIR1, R1, #8R1,

25、 R1, #8 LDLD F0, 0(R1) F0, 0(R1) ADDDADDDF4, F0, F2F4, F0, F2 SDSD 0(R1), F4 0(R1), F4 SUBISUBIR1, R1, #8R1, R1, #8 BNEZBNEZR1, LoopR1, Loop 6.5 开发更多的指令级并行 24243232 (2) (2) 编译器可以通过对相关链上存储器访问偏移量的编译器可以通过对相关链上存储器访问偏移量的 直接调整，将前直接调整，将前3 3条条SUBISUBI指令消除掉，从而得到下面指令消除掉，从而得到下面 一个一个1414条指令构成的指令序列：条指令构成的指令序列： 6

26、.5 开发更多的指令级并行 25253232 Loop: LDLoop: LD F0, 0(R1) F0, 0(R1) ADDD F4, F0, F2 ADDD F4, F0, F2 SD SD 0(R1), F4 0(R1), F4 LD LD F0, -8(R1) F0, -8(R1) ADDD F4, F0, F2 ADDD F4, F0, F2 SD SD -8(R1), F4 -8(R1), F4 LD LD F0, -16(R1) F0, -16(R1) ADDD F4, F0, F2 ADDD F4, F0, F2 SD SD -16(R1), F4 -16(R1), F4 LD

27、 LD F0, -24(R1) F0, -24(R1) ADDD ADDD F4, F0, F2 F4, F0, F2 SD SD -24(R1), F4 -24(R1), F4 SUBI R1, R1, SUBI R1, R1, #32#32 BNEZ R1, Loop BNEZ R1, Loop 6.5 开发更多的指令级并行 26263232 (3)(3)通过寄存器换名，通过寄存器换名， 消除名相关。得到消除名相关。得到 右边的指令序列：右边的指令序列： Loop:Loop:LDLDF0, 0(R1)F0, 0(R1) ADDDADDDF4, F0, F2F4, F0, F2 SDSD0(

28、R1), F40(R1), F4 LDLDF6F6, -8(R1), -8(R1) ADDDADDDF8, F6, F2F8, F6, F2 SDSD-8(R1), F8-8(R1), F8 LDLDF10F10, -16(R1), -16(R1) ADDDADDDF12, F10, F2F12, F10, F2 SDSD-16(R1), F12-16(R1), F12 LDLDF14F14, -24(R1), -24(R1) ADDDADDDF16, F14, F2F16, F14, F2 SDSD-24(R1), F16-24(R1), F16 SUBISUBIR1, R1, #32R1,

29、 R1, #32 BNEZBNEZR1, LoopR1, Loop 换名操作需要较大换名操作需要较大 的寄存器开销。的寄存器开销。 6.5 开发更多的指令级并行 27273232 3 3控制相关（控制相关（control dependencecontrol dependence） 控制相关控制相关是指由分支指令引起的相关。是指由分支指令引起的相关。 典型的程序结构是典型的程序结构是“if-thenif-then”结构。结构。 看下面一个示例：看下面一个示例： if p1if p1 S1; S1; S; S; if p2 if p2 S2; S2; 6.5 开发更多的指令级并行 28283232

30、 处理控制相关的处理控制相关的两个原则两个原则： (1) (1) 与控制相关的指令不能移到分支指令之与控制相关的指令不能移到分支指令之 前，即控制有关的指令不能调度到分支前，即控制有关的指令不能调度到分支 指令控制范围以外；指令控制范围以外； (2) (2) 与控制无关的指令不能移到分支指令之与控制无关的指令不能移到分支指令之 后，即控制无关的指令不能调度到分支后，即控制无关的指令不能调度到分支 指令控制范围以内。指令控制范围以内。 6.5 开发更多的指令级并行 29293232 再考察再考察例例6.26.2： 假设循环展开时，循环控制分支指令没有去除，假设循环展开时，循环控制分支指令没有去除， 则指令序列如下：则指令序列如下： 6.5 开发更多的指令级并行 30303232 Loop: LDLoop: LDF0, 0(R1)F0, 0(R1) ADDDADDDF4, F0, F2F4, F0, F2 SDSD0(R1), F40(R1), F4 SUBISUBIR1, R1, #8R1, R1, #8 BEQZBEQZR1, ExitR1, Exit LDLDF0, 0(R1)F0, 0(R1) ADDDADDDF4, F0, F2F4, F0, F2 SDSD0