指令级并行的概念ppt课件

1、1314.1指令级并行的概念当指令之间不存在相关时，它们在流水线中是可以当指令之间不存在相关时，它们在流水线中是可以重叠起来并行执行的。这种指令序列中存在的潜在重叠起来并行执行的。这种指令序列中存在的潜在并行性称为指令级并行。并行性称为指令级并行。Instruction-Level Parallelism，简记为，简记为ILP本章研讨：如何经过各种能够的技术，获得更多的本章研讨：如何经过各种能够的技术，获得更多的指令级并行性。指令级并行性。 硬件技术和软件技术硬件技术和软件技术必需求硬件技术和软件技术相互配合，才可以最大必需求硬件技术和软件技术相互配合，才可以最大限制地发掘出程序中存在的指令级

2、并行。限制地发掘出程序中存在的指令级并行。第四章 指令级并行2311.1.流水线处置器的实践流水线处置器的实践CPICPICPICPI流水线流水线 = CPI= CPI理想理想 + + 各类停顿周期数的总和各类停顿周期数的总和 流水线的理想流水线的理想CPICPI是流水线的最大流量。是流水线的最大流量。 各类停顿包括：各类停顿包括：构造相关停顿：是由于两条指令运用同一个功能构造相关停顿：是由于两条指令运用同一个功能部件而导致的停顿。部件而导致的停顿。控制相关停顿：是由于指令流的改动如分支指控制相关停顿：是由于指令流的改动如分支指令而导致的停顿。令而导致的停顿。RAWRAW、WARWAR和和WA

3、WWAW停顿：由数据相关呵斥的。停顿：由数据相关呵斥的。减少其中的任何一种停顿，都可以有效地减少减少其中的任何一种停顿，都可以有效地减少CPICPI，从而提高流水线的性能。，从而提高流水线的性能。4.1 指令级并行的概念3312. 2. 本章要研讨的技术以及它们所抑制的停顿本章要研讨的技术以及它们所抑制的停顿技术技术主要克服的停顿主要克服的停顿章节章节基本流水线调度基本流水线调度数据先写后读相关停顿数据先写后读相关停顿4.1循环展开循环展开控制相关停顿控制相关停顿4.1寄存器换名寄存器换名数据写后写相关和先读后写数据写后写相关和先读后写相关停顿相关停顿4.1指令动态调度（记分牌和指令动态调度（

4、记分牌和Tomasulo算法）算法）各种数据相关停顿各种数据相关停顿4.2动态分支预测动态分支预测控制相关停顿控制相关停顿4.3前瞻（前瞻（Speculation）所有数据所有数据/控制相关停顿控制相关停顿4.3多指令流出（超标量和超多指令流出（超标量和超长指令字）长指令字）提高理想提高理想CPI4.44.1 指令级并行的概念4313.3.几个概念几个概念根本程序块根本程序块一段除了入口和出口以外不包含其它分支的线性一段除了入口和出口以外不包含其它分支的线性代码段。代码段。程序平均每程序平均每6 67 7条指令就会有一个分支。条指令就会有一个分支。循环体中指令之间的并行性称为循环级并行性。循环

5、体中指令之间的并行性称为循环级并行性。开发循环体中存在的并行性。开发循环体中存在的并行性。 最常见、最根本最常见、最根本是指令级并行研讨的重点之一。是指令级并行研讨的重点之一。4.1 指令级并行的概念531最根本的开发循环级并行的技术最根本的开发循环级并行的技术指令调度指令调度schedulingscheduling技术技术循环展开循环展开loop unrollingloop unrolling技术技术换名换名renamingrenaming技术技术4.1 指令级并行的概念6314.1.1 循环展开调度的根本方法1. 1. 指令调度指令调度 经过改动指令在程序中的位置，将相关指经过改动指令在程

6、序中的位置，将相关指令之间的间隔加大到不小于指令执行延迟，将令之间的间隔加大到不小于指令执行延迟，将相关指令转化为无关指令。相关指令转化为无关指令。 指令调度是循环展开的技术根底。指令调度是循环展开的技术根底。2. 2. 编译器在完成这种指令调度时，受限于以下两编译器在完成这种指令调度时，受限于以下两 个特性：个特性： 程序固有的指令级并行性程序固有的指令级并行性 流水线功能部件的执行延迟流水线功能部件的执行延迟4.1 指令级并行的概念7313. 3. 本章运用的浮点流水线的延迟本章运用的浮点流水线的延迟产生结果指令使用结果指令延迟时钟周期数浮点计算另外的浮点计算3浮点计算浮点数据存操作（SD

7、）2浮点数据取操作（LD）浮点计算1浮点数据取操作（LD）浮点数据存操作（SD）04.1 指令级并行的概念831例例4.14.1 对于下面的源代码，转换成对于下面的源代码，转换成DLXDLX汇编言语，汇编言语，在不进展指令调度和进展指令调度两种情况下，在不进展指令调度和进展指令调度两种情况下，分析代码一次循环的执行时间。分析代码一次循环的执行时间。 for (i=1; i=1000; i+)for (i=1; i=1000; i+) xi = xi + s; xi = xi + s;4.1 指令级并行的概念931解：解：(1) (1) 变量分配存放器变量分配存放器 整数存放器整数存放器R1R1

8、：循环计数器，初值为向量：循环计数器，初值为向量 中最高端地址元素的地址。中最高端地址元素的地址。 浮点存放器浮点存放器F2F2：保管常数：保管常数S S。 假定最低端元素的地址为假定最低端元素的地址为8 8。 (2) DLX(2) DLX汇编言语后的程序汇编言语后的程序 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 指令级并行的概念1031(3) (3) 程序执行的实践时钟程

9、序执行的实践时钟根据表根据表4-24-2中给出的的延迟，实践时钟如下：中给出的的延迟，实践时钟如下： 指令流出时指令流出时钟钟 Loop: LDLoop: LD F0 , 0(R1) F0 , 0(R1) 1 1 空转空转 2 2 ADDD F4 , F0 , F2 ADDD F4 , F0 , F2 3 3 空转空转 4 4 空转空转 5 5 SD SD 0(R1) , F4 0(R1) , F4 6 6 SUBI SUBI R1 , R1 , #8 R1 , R1 , #8 7 7 空转空转 8 8 BNEZ R1 , Loop BNEZ R1 , Loop 9 9 空转空转 1010每个

10、元素的操作需求每个元素的操作需求1010个时钟周期，其中个时钟周期，其中5 5个个是空转周期。是空转周期。4.1 指令级并行的概念1131(4) (4) 指令调度以后，程序的执行情况指令调度以后，程序的执行情况SDSD放在分支指令的分支延迟槽中放在分支指令的分支延迟槽中对存储器地址偏移量进展调整对存储器地址偏移量进展调整 指令流出时钟指令流出时钟Loop: LD F0 , 0(R1)Loop: LD F0 , 0(R1) 1 1 SUBI R1 , R1 , #8 SUBI R1 , R1 , #8 2 2 ADDD F4 , F0 , F2 ADDD F4 , F0 , F2 3 3 空转空

11、转 4 4 BNEZ R1 , Loop BNEZ R1 , Loop 5 5 SD SD 8(R1) , F4 8(R1) , F4 6 6一个元素的操作时间从一个元素的操作时间从1010个时钟周期减少到个时钟周期减少到6 6个个5 5个周期是有指令执行的，个周期是有指令执行的，1 1个空转周期。个空转周期。4.1 指令级并行的概念1231(5) (5) 例子中的问题及处理方案例子中的问题及处理方案只需只需LDLD、ADDDADDD和和SDSD这这3 3条指令是有效操作条指令是有效操作. .占用占用3 3个时钟周期个时钟周期而而SUBISUBI、空转和、空转和BENZBENZ这这3 3个时钟

12、周期都是附加的个时钟周期都是附加的循环控制开销。循环控制开销。循环展开技术循环展开技术多次复制循环体并相应调整展开后的指令和循环多次复制循环体并相应调整展开后的指令和循环终了条件，添加有效操作时间与控制操作时间的终了条件，添加有效操作时间与控制操作时间的比率。比率。也给编译器进展指令调度带来了更大的空间。也给编译器进展指令调度带来了更大的空间。4.1 指令级并行的概念1331例例4.2 4.2 表达循环展开技术的特点表达循环展开技术的特点 将例将例4.14.1中的循环展开成中的循环展开成3 3次得到次得到4 4个循个循环体，再对展开后的指令序列在不调度和环体，再对展开后的指令序列在不调度和调度

13、两种情况下，分析代码的性能。调度两种情况下，分析代码的性能。 假定假定R1R1的初值为的初值为3232的倍数，即循环的倍数，即循环次数为次数为4 4的倍数。的倍数。4.1 指令级并行的概念1431解：解：补偿代码问题补偿代码问题存放器分配存放器分配展开后的循环体内不反复运用存放器。展开后的循环体内不反复运用存放器。F0F0、F4F4：用于展开后的第：用于展开后的第1 1个循环体个循环体F2F2：保管常数：保管常数F6F6和和F8F8：用于展开后的第：用于展开后的第2 2个循环体个循环体F10F10和和F12F12：用于第：用于第3 3个循环体个循环体F14F14和和F16F16：用于第：用于第

14、4 4个循环体个循环体4.1 指令级并行的概念1531(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

15、24SUBIR1,R1,#32 25空转 26BNEZR1,Loop 27空转 284.1 指令级并行的概念1631结果分析结果分析: :这个循环每遍共运用了这个循环每遍共运用了2828个时钟周期个时钟周期有有4 4个循环体，完成个循环体，完成4 4个元素的操作个元素的操作平均每个元素运用平均每个元素运用28/4=728/4=7个时钟周期个时钟周期原始循环的每个元素需求原始循环的每个元素需求1010个时钟周期个时钟周期节省的时间节省的时间: :从减少循环控制的开销中获得的从减少循环控制的开销中获得的在整个展开后的循环中，实践指令只需在整个展开后的循环中，实践指令只需1414条，条，其它其它13

16、13个周期都是空转。个周期都是空转。 效率并不高效率并不高4.1 指令级并行的概念1731(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 指令级并行的概念183

17、1结果分析：结果分析：没有数据相关引起的空转等待没有数据相关引起的空转等待整个循环仅仅运用了整个循环仅仅运用了1414个时钟周期个时钟周期平均每个元素的操作运用平均每个元素的操作运用14/4=3.514/4=3.5个时钟周期个时钟周期循环展开和指令调度可以有效地提高循环级并行循环展开和指令调度可以有效地提高循环级并行性。性。这种循环级并行性的提高实践是经过实现指令级这种循环级并行性的提高实践是经过实现指令级并行来到达的。并行来到达的。可以运用编译器来完成，也可以经过硬件来完成。可以运用编译器来完成，也可以经过硬件来完成。4.1 指令级并行的概念19314. 4. 循环展开和指令调度时要留意的问

18、题循环展开和指令调度时要留意的问题(1) (1) 保证正确性保证正确性(2) (2) 留意有效性留意有效性(3) (3) 运用不同的存放器运用不同的存放器(4) (4) 尽能够减少循环控制中的测试指令和分支指令尽能够减少循环控制中的测试指令和分支指令(5) (5) 留意对存储器数据的相关性分析留意对存储器数据的相关性分析(6) (6) 留意新的相关性留意新的相关性5. 5. 实现循环展开的关键实现循环展开的关键 分析清楚代码中指令的相关性，然后经过分析清楚代码中指令的相关性，然后经过 指令调度来消除相关指令调度来消除相关. .4.1 指令级并行的概念20314.1.2 相关性开发指令级并行的关

19、键开发指令级并行的关键存在相关的两条指令，不能改动它们的顺序。存在相关的两条指令，不能改动它们的顺序。相关能否导致流水线的空转，还与流水线的组相关能否导致流水线的空转，还与流水线的组织与构造有关。织与构造有关。程序中的相关主要有以下三种程序中的相关主要有以下三种 数据相关数据相关 名相关名相关 控制相关控制相关4.1 指令级并行的概念21311. 1. 数据相关数据相关data dependencedata dependence对于指令对于指令i i和指令和指令j j，假设，假设 (1) (1) 指令指令j j运用指令运用指令i i产生的结果，或者产生的结果，或者 (2) (2) 指令指令j

20、j与指令与指令k k数据相关，指令数据相关，指令k k与指令与指令i i数据数据相相 关，那么指令关，那么指令j j与指令与指令i i数据相关。数据相关。 数据相关具有传送性。数据相关具有传送性。数据相关是两条指令之间存在一个先写后读相关链。数据相关是两条指令之间存在一个先写后读相关链。相关链贯穿整个程序，是程序的内在特征。相关链贯穿整个程序，是程序的内在特征。这种相关链是导致流水线停顿的缘由之一。这种相关链是导致流水线停顿的缘由之一。4.1 指令级并行的概念2231指令的相关间隔指令的相关间隔distancedistance 两条指令之间的指令条数。两条指令之间的指令条数。分析数据相关的主要

21、任务分析数据相关的主要任务: : (1) (1) 确定指令的相关性，找到一切能够产生确定指令的相关性，找到一切能够产生停停 顿的地方。顿的地方。 (2) (2) 确定必需严厉遵守的数据的计算顺序。确定必需严厉遵守的数据的计算顺序。 (3) (3) 确定指令的最大相关间隔，确定程序中确定指令的最大相关间隔，确定程序中可可 能的最大并行性。能的最大并行性。4.1 指令级并行的概念23312. 2. 名相关名相关name dependencename dependence指令运用的存放器或存储器称为名。指令运用的存放器或存储器称为名。假设两条指令运用一样的名，但是它们之间并假设两条指令运用一样的名，

22、但是它们之间并没有数据流，那么称之为名相关。没有数据流，那么称之为名相关。指令指令j j与指令与指令i i之间名相关有以下两种：之间名相关有以下两种： (1) (1) 反相关反相关anti-dependenceanti-dependence (2) (2) 输出相关输出相关output dependenceoutput dependence4.1 指令级并行的概念2431 消除名相关消除名相关名相关的指令之间没有数据交换。名相关的指令之间没有数据交换。假设一条指令中的名改动了，并不影响另外一假设一条指令中的名改动了，并不影响另外一条指令的执行。条指令的执行。经过改动指令中操作数的名来消除名相关

23、，这经过改动指令中操作数的名来消除名相关，这就是换名就是换名renamingrenaming技术。技术。对于存放器操作数进展换称号为存放器换名。对于存放器操作数进展换称号为存放器换名。 register renamingregister renaming可以用编译器静态完成或硬件动态完成。可以用编译器静态完成或硬件动态完成。4.1 指令级并行的概念2531例：我们对例例：我们对例4.24.2编译过程进展分析，来仔细调查编译过程进展分析，来仔细调查 换名的过程。换名的过程。 (1) (1) 首先，仅仅去除首先，仅仅去除4 4遍循环体中的分支指令，遍循环体中的分支指令， 得到以下由得到以下由171

24、7条指令构成的指令序列：条指令构成的指令序列：4.1 指令级并行的概念2631Loop: 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 , Loo

25、p4.1 指令级并行的概念2731(2) (2) 编译器可以经过对相关链上存储器访问偏移编译器可以经过对相关链上存储器访问偏移 量量的直接调整，将前的直接调整，将前3 3条条SUBISUBI指令消除掉，从而得到下指令消除掉，从而得到下面一个面一个1414条指令构成的指令序列：条指令构成的指令序列： 4.1 指令级并行的概念2831Loop: 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

26、SD -16(R1) , F4 LD F0 , -24(R1) ADDD F4 , F0 , F2 SD -24(R1) , F4 SUBI R1 , R1 , #32 BNEZ R1 , Loop4.1 指令级并行的概念2931(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换名操作需求较大的存