指令级并行的概念.ppt

1／314.1指令级并行的概念¿当指令之间不存在相关时，它们在流水线中是可以当指令之间不存在相关时，它们在流水线中是可以重叠起来并行执行的这种指令序列中存在的潜在重叠起来并行执行的这种指令序列中存在的潜在并行性称为并行性称为指令级并行指令级并行Instruction-Level Parallelism，简记为ILP）¿本章研究：本章研究：如何通过各种可能的技术，获得更多的如何通过各种可能的技术，获得更多的指令级并行性指令级并行性 （硬件技术和软件技术）（硬件技术和软件技术）¿必须要硬件技术和软件技术互相配合，才能够最大必须要硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行限度地挖掘出程序中存在的指令级并行第四章 指令级并行2／311.1.流水线处理器的实际流水线处理器的实际CPICPI¿CPICPI流水线流水线 = = CPICPI理想理想 + + 各类停顿周期数的总和各类停顿周期数的总和 流水线的理想流水线的理想CPICPI是流水线的最大流量是流水线的最大流量 各类停顿包括：各类停顿包括：•结构相关停顿：是由于两条指令使用同一结构相关停顿：是由于两条指令使用同一个功能部件而导致的停顿。

个功能部件而导致的停顿•控制相关停顿：是由于指令流的改变（如控制相关停顿：是由于指令流的改变（如分支指令）而导致的停顿分支指令）而导致的停顿•RAWRAW、、WARWAR和和WAWWAW停顿：由数据相关造成的停顿：由数据相关造成的¿减少其中的任何一种停顿，都可以有效地减少减少其中的任何一种停顿，都可以有效地减少CPICPI，，从而提高流水线的性能从而提高流水线的性能4.1 指令级并行的概念3／312. 2. 本章要研究的技术以及它们所克服的停顿本章要研究的技术以及它们所克服的停顿技术技术主要克服的停顿主要克服的停顿章节章节基本流水线调度基本流水线调度数据先写后读相关停顿数据先写后读相关停顿4.1循环展开循环展开控制相关停顿控制相关停顿4.1寄存器换名寄存器换名数据写后写相关和先读后写数据写后写相关和先读后写相关停顿相关停顿4.1指令动态调度（记分牌和指令动态调度（记分牌和Tomasulo算法）算法）各种数据相关停顿各种数据相关停顿4.2动态分支预测动态分支预测控制相关停顿控制相关停顿4.3前瞻（前瞻（Speculation））所有数据所有数据/控制相关停顿控制相关停顿4.3多指令流出（超标量和超多指令流出（超标量和超长指令字）长指令字）提高理想提高理想CPI4.44.1 指令级并行的概念4／313.3.几个概念几个概念¿基本程序块基本程序块•一段除了入口和出口以外不包含其它分支的线一段除了入口和出口以外不包含其它分支的线性代码段。

性代码段•程序平均每程序平均每6 6～～7 7条指令就会有一个分支条指令就会有一个分支¿循环体中指令之间的并行性称为循环体中指令之间的并行性称为循环级并行性循环级并行性•开发循环体中存在的并行性开发循环体中存在的并行性 最常见、最基本最常见、最基本•是指令级并行研究的重点之一是指令级并行研究的重点之一4.1 指令级并行的概念5／31¿最基本的开发循环级并行的技术最基本的开发循环级并行的技术•指令调度指令调度（（schedulingscheduling））技术技术•循环展开循环展开（（loop unrollingloop unrolling））技术技术•换名换名（（renamingrenaming））技术技术4.1 指令级并行的概念6／314.1.1 循环展开调度的基本方法1. 1. 指令调度指令调度 通过改变指令在程序中的位置，将相关指通过改变指令在程序中的位置，将相关指令之间的距离加大到不小于指令执行延迟，将令之间的距离加大到不小于指令执行延迟，将相关指令转化为无关指令相关指令转化为无关指令 指令调度是循环展开的技术基础。

指令调度是循环展开的技术基础2. 2. 编译器在完成这种指令调度时，受限于以下两编译器在完成这种指令调度时，受限于以下两 个特性：个特性：• 程序固有的指令级并行性程序固有的指令级并行性• 流水线功能部件的执行延迟流水线功能部件的执行延迟4.1 指令级并行的概念7／313. 3. 本章使用的浮点流水线的延迟本章使用的浮点流水线的延迟产生结果指令使用结果指令延迟时钟周期数浮点计算另外的浮点计算3浮点计算浮点数据存操作（SD）2浮点数据取操作（LD）浮点计算1浮点数据取操作（LD）浮点数据存操作（SD）04.1 指令级并行的概念8／31例例4.14.1 对于下面的源代码，转换成对于下面的源代码，转换成DLXDLX汇编语言，汇编语言，在在不进行指令调度不进行指令调度和和进行指令调度进行指令调度两种情况下，两种情况下，分析代码一次循环的执行时间分析代码一次循环的执行时间 for (i=1; i<=1000; i++)for (i=1; i<=1000; i++) x[i] = x[i] + s; x[i] = x[i] + s;4.1 指令级并行的概念9／31解：解：(1)(1) 变量分配寄存器变量分配寄存器 整数寄存器整数寄存器R1R1：：循环计数器，初值为向量循环计数器，初值为向量 中最高端地址元素的地址。

中最高端地址元素的地址 浮点寄存器浮点寄存器F2F2：：保存常数保存常数S S 假定最低端元素的地址为假定最低端元素的地址为8 8 (2) (2) DLXDLX汇编语言后的程序汇编语言后的程序 Loop:Loop:LDLDF0,0(R1) F0,0(R1) ADDD ADDDF4,F0,F2F4,F0,F2 SD SD0(R1),F40(R1),F4 SUBI SUBIR1,R1,#8R1,R1,#8 BNEZ BNEZR1,LoopR1,Loop4.1 指令级并行的概念10／31(3)(3) 程序执行的实际时钟程序执行的实际时钟¿根据根据表表4-24-2中给出的的延迟，实际时钟如下：中给出的的延迟，实际时钟如下： 指令流出时钟指令流出时钟 Loop: LD F0 , 0(R1) 1 （空转） 2 ADDD F4 , F0 , F2 3 （空转） 4 （空转） 5 SD 0(R1) , F4 6 SUBI R1 , R1 , #8 7 （空转） 8 BNEZ R1 , Loop 9 （空转） 10¿每个元素的操作需要每个元素的操作需要1010个时钟周期，其中个时钟周期，其中5 5个个是空转周期。

是空转周期4.1 指令级并行的概念11／31(4)(4) 指令调度以后，程序的执行情况指令调度以后，程序的执行情况¿SDSD放在分支指令的分支延迟槽中放在分支指令的分支延迟槽中¿对存储器地址偏移量进行调整对存储器地址偏移量进行调整 指令流出时钟指令流出时钟Loop: LD F0 , 0(R1) 1 SUBI R1 , R1 , #8 2 ADDD F4 , F0 , F2 3 （空转） 4 BNEZ R1 , Loop 5 SD 8(R1) , F4 6¿一个元素的操作时间从一个元素的操作时间从1010个时钟周期减少到个时钟周期减少到6 6个个5 5个周期是有指令执行的，个周期是有指令执行的，1 1个空转周期个空转周期4.1 指令级并行的概念12／31(5)(5) 例子中的问题及解决方案例子中的问题及解决方案¿只有只有LDLD、、ADDDADDD和和SDSD这这3 3条指令是有效操作条指令是有效操作. .•占用占用3 3个时钟周期个时钟周期•而而SUBISUBI、、空转空转和和BENZBENZ这这3 3个时钟周期都是附加个时钟周期都是附加的循环控制开销。

的循环控制开销¿循环展开技术循环展开技术•多次复制循环体并相应调整展开后的指令和循多次复制循环体并相应调整展开后的指令和循环结束条件，增加有效操作时间与控制操作时环结束条件，增加有效操作时间与控制操作时间的比率间的比率•也给编译器进行指令调度带来了更大的空间也给编译器进行指令调度带来了更大的空间4.1 指令级并行的概念13／31例例4.4.2 2 体现循环展开技术的特点体现循环展开技术的特点 将将例例4.14.1中的循环展开成中的循环展开成3 3次次得到得到4 4个个循循环体，再对展开后的指令序列在不调度和调环体，再对展开后的指令序列在不调度和调度两种情况下，分析代码的性能度两种情况下，分析代码的性能 假定假定R1R1的初值为的初值为3232的倍数，即循环的倍数，即循环次数为次数为4 4的倍数4.1 指令级并行的概念14／31解：解：¿补偿代码问题补偿代码问题¿寄存器分配寄存器分配展开后的循环体内不重复使用寄存器展开后的循环体内不重复使用寄存器F0F0、、F4F4：：用于展开后的第用于展开后的第1 1个循环体个循环体F2F2：：保存常数保存常数F6F6和和F8F8：：用于展开后的第用于展开后的第2 2个循环体个循环体F10F10和和F12F12：：用于第用于第3 3个循环体个循环体F14F14和和F16F16：：用于第用于第4 4个循环体个循环体4.1 指令级并行的概念15／31(1)(1) 展开后没有调度的代码展开后没有调度的代码流出时钟流出时钟Loop:LDF0,0(R1) 1（空转） 2ADDDF4,F0,F2 3（空转） 4（空转） 5SD0(R1),F4 6LDF6,-8(R1) 7（空转） 8ADDDF8,F6,F2 9（空转） 10（空转） 11SD-8(R1),F8 12LDF10,-16(R1) 13（空转） 14流出时钟流出时钟ADDDF12,F10,F2 15（空转） 16 （空转） 17SD-16(R1),F12 18LDF14,-24(R1) 19（空转） 20ADDDF16,F14,F2 21（空转） 22（空转） 23SD-24(R1),F16 24SUBIR1,R1,#32 25（空转） 26BNEZR1,Loop 27（空转） 284.1 指令级并行的概念16／31结果分析结果分析: :¿这个循环每遍共使用了这个循环每遍共使用了2828个时钟周期个时钟周期¿有有4 4个个循环体，完成循环体，完成4 4个个元素的操作元素的操作平均每个元素使用平均每个元素使用28/4=728/4=7个时钟周期个时钟周期¿原始循环的每个元素需要原始循环的每个元素需要1010个时钟周期个时钟周期节省的时间节省的时间: :从减少循环控制的开销中获得的从减少循环控制的开销中获得的¿在整个展开后的循环中，实际指令只有在整个展开后的循环中，实际指令只有1414条，条，其它其它1313个周期都是空转。

个周期都是空转 效率并不高效率并不高4.1 指令级并行的概念17／31(2)(2) 对指令序列进行优化调度对指令序列进行优化调度指令流出时钟指令流出时钟Loop:LDF0,0(R1)1 LDF6,-8(R1)2 LDF10,-16(R1)3 LDF14,-24(R1)4 ADDDF4,F0,F25 ADDDF8,F6,F26 ADDDF12,F10,F27 ADDDF16,F14,F28 SD0(R1),F49 SD-8(R1),F810 SUBIR1,R1,#3212 SD16(R1),F1211 BNEZR1,Loop13 SD8(R1),F16144.1 指令级并行的概念18／31结果分析：结果分析：¿没有数据相关引起的空转等待没有数据相关引起的空转等待¿整个循环仅仅使用整个循环仅仅使用了了1414个时钟周期个时钟周期•平均每个元素的操作使用平均每个元素的操作使用14/4=3.514/4=3.5个时钟周期个时钟周期•循环展开循环展开和和指令调度指令调度可以有效地提高循环级并可以有效地提高循环级并行性。

行性¿这种循环级并行性的提高实际是通过实现指令级这种循环级并行性的提高实际是通过实现指令级并行来达到的并行来达到的¿可以使用编译器来完成，也可以通过硬件来可以使用编译器来完成，也可以通过硬件来完成4.1 指令级并行的概念19／314. 4. 循环展开和指令调度时要注意的问题循环展开和指令调度时要注意的问题(1) (1) 保证正确性保证正确性(2) (2) 注意有效性注意有效性(3) (3) 使用不同的寄存器使用不同的寄存器(4) (4) 尽可能减少循环控制中的测试指令和分支指令尽可能减少循环控制中的测试指令和分支指令(5) (5) 注意对存储器数据的相关性分析注意对存储器数据的相关性分析(6) (6) 注意新的相关性注意新的相关性5. 5. 实现循环展开的关键实现循环展开的关键 分析清楚代码中指令的相关性，然后通过分析清楚代码中指令的相关性，然后通过 指令调度来消除相关指令调度来消除相关. .4.1 指令级并行的概念20／314.1.2 相关性¿开发指令级并行的开发指令级并行的关键关键•存在相关的两条指令，不能改变它们的顺序存在相关的两条指令，不能改变它们的顺序。

•相关是否导致流水线的空转，还与流水线的相关是否导致流水线的空转，还与流水线的组织与结构有关组织与结构有关¿程序中的相关主要有以下三种程序中的相关主要有以下三种• 数据相关数据相关• 名相关名相关• 控制相关控制相关4.1 指令级并行的概念21／311. 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数据相关数据相关 数据相关具有传递性数据相关具有传递性¿数据相关是两条指令之间存在一个先写后读相关链数据相关是两条指令之间存在一个先写后读相关链•相关链贯穿整个程序，是程序的内在特征相关链贯穿整个程序，是程序的内在特征•这种相关链是导致流水线停顿的原因之一这种相关链是导致流水线停顿的原因之一。

4.1 指令级并行的概念22／31¿指令的相关距离指令的相关距离（（distancedistance）） 两条指令之间的指令条数两条指令之间的指令条数¿分析数据相关的主要工作分析数据相关的主要工作: : (1) (1) 确定指令的相关性，找到所有可能产生停确定指令的相关性，找到所有可能产生停 顿的地方顿的地方 (2) (2) 确定必须严格遵守的数据的计算顺序确定必须严格遵守的数据的计算顺序 (3) (3) 确定指令的最大相关距离，确定程序中可确定指令的最大相关距离，确定程序中可 能的最大并行性能的最大并行性4.1 指令级并行的概念23／312. 2. 名相关（名相关（name dependencename dependence））¿指令使用的寄存器或存储器称为指令使用的寄存器或存储器称为名名¿如果两条指令使用相同的名，但是它们之间并如果两条指令使用相同的名，但是它们之间并没有数据流，则称之为没有数据流，则称之为名相关名相关¿指令指令j j与与指令指令i i之间名相关有以下两种：之间名相关有以下两种： (1) (1) 反相关反相关（（anti-dependenceanti-dependence）） (2) (2) 输出相关输出相关（（output dependenceoutput dependence））4.1 指令级并行的概念24／31¿ 消除名相关消除名相关•名相关的指令之间没有数据交换。

名相关的指令之间没有数据交换•如果一条指令中的名改变了，并不影响另外一如果一条指令中的名改变了，并不影响另外一条指令的执行条指令的执行•通过改变指令中操作数的名来消除名相关，这通过改变指令中操作数的名来消除名相关，这就是就是换名（换名（renamingrenaming））技术技术•对于寄存器操作数进行换名称为对于寄存器操作数进行换名称为寄存器换名寄存器换名 （（register renamingregister renaming））可以用编译器静态完成或硬件动态完成可以用编译器静态完成或硬件动态完成4.1 指令级并行的概念25／31例：例：我们对我们对例例4.24.2编译过程进行分析，来仔细考察编译过程进行分析，来仔细考察 换名的过程换名的过程 (1) (1) 首先，仅仅去除首先，仅仅去除4 4遍循环体中的分支指令，遍循环体中的分支指令， 得到以下由得到以下由1717条指令构成的指令序列：条指令构成的指令序列：4.1 指令级并行的概念26／31Loop: LD F0 , 0(R1) ADDD F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 LD F0 , 0(R1) ADDD F4 , F0 , F2 SD 0(R1) , F4 SUBI R1 , R1 , #8 LDF0 , 0(R1)ADDDF4 , F0 , F2 SD0(R1) , F4SUBIR1 , R1 , #8 LDF0 , 0(R1)ADDDF4 , F0 , F2 SD0(R1) , F4SUBIR1 , R1 , #8BNEZR1 , Loop4.1 指令级并行的概念27／31(2) (2) 编译器可以通过对相关链上存储器访问偏移编译器可以通过对相关链上存储器访问偏移 量量的直接调整，将前的直接调整，将前3 3条条SUBISUBI指令消除掉，从而得到下指令消除掉，从而得到下面一个面一个1414条指令构成的指令序列：条指令构成的指令序列： 4.1 指令级并行的概念28／31Loop: LD F0 , 0(R1) ADDD F4 , F0 , F2 SD 0(R1) , F4 LD F0 , -8(R1) ADDD F4 , F0 , F2 SD -8(R1) , F4 LD F0 , -16(R1) ADDD F4 , F0 , F2 SD -16(R1) , F4 LD F0 , -24(R1) ADDD F4 , F0 , F2 SD -24(R1) , F4 SUBI R1 , R1 , #32 BNEZ R1 , Loop4.1 指令级并行的概念29／31(3) (3) 通通过过寄寄存存器器换换名名，，消消除除名名相关。

相关 得到右边得到右边的指令序列：的指令序列： Loop:LDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4LDF6 , -8(R1)ADDD F8 , F6 , F2SD-8(R1) , F8LDF10 , -16(R1)ADDD F12 , F10 , F2SD-16(R1) , F12LDF14 , -24(R1)ADDD F16 , F14 , F2SD-24(R1) , F16SUBIR1 , R1 , #32BNEZR1 , Loop换名操作需要较大的寄存器开销换名操作需要较大的寄存器开销 4.1 指令级并行的概念30／313 3．控制相关（．控制相关（control dependencecontrol dependence））¿ 控制相关控制相关是指由分支指令引起的相关是指由分支指令引起的相关¿ 典型的程序结构是典型的程序结构是““if-thenif-then””结构¿ 看下面一个示例：看下面一个示例： if p1{ S1; }; S; if p2{ S2; };4.1 指令级并行的概念31／31¿ 处理控制相关的处理控制相关的两个原则两个原则：： (1) (1) 与控制相关的指令不能移到分支指令之与控制相关的指令不能移到分支指令之 前，即控制有关的指令不能调度到分支前，即控制有关的指令不能调度到分支 指令控制范围以外；指令控制范围以外； (2) (2) 与控制无关的指令不能移到分支指令之与控制无关的指令不能移到分支指令之 后，即控制无关的指令不能调度到分支后，即控制无关的指令不能调度到分支 指令控制范围以内。

指令控制范围以内4.1 指令级并行的概念32／31再考察再考察例例4.24.2：： 假设循环展开时，循环控制分支指令没有去除，假设循环展开时，循环控制分支指令没有去除，则指令序列如下：则指令序列如下： 4.1 指令级并行的概念33／31Loop: LDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4SUBIR1 , R1 , #8BEQZR1 , ExitLDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4SUBIR1 , R1 , #8BEQZR1 , Exit LDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4SUBIR1 , R1 , #8BEQZR1 , ExitLDF0 , 0(R1)ADDD F4 , F0 , F2SD0(R1) , F4SUBIR1 , R1 , #8BNEZR1 , Loop Exit: 4.1 指令级并行的概念。