指令级并行概念

《指令级并行概念》由会员分享，可在线阅读，更多相关《指令级并行概念（33页珍藏版）》请在金锄头文库上搜索。

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

2、顿。 控制相关停顿：是由于指令流的改变（如分支指令）而导致的停顿。 RAW、WAR和WAW停顿：由数据相关造成的。 减少其中的任何一种停顿，都可以有效地减少CPI，从而提高流水线的性能。,4.1 指令级并行的概念,2. 本章要研究的技术以及它们所克服的停顿,4.1 指令级并行的概念,3.几个概念,基本程序块 一段除了入口和出口以外不包含其它分支的线性代码段。 程序平均每67条指令就会有一个分支。 循环体中指令之间的并行性称为循环级并行性。 开发循环体中存在的并行性。 最常见、最基本 是指令级并行研究的重点之一。,4.1 指令级并行的概念,最基本的开发循环级并行的技术 指令调度（scheduli

3、ng）技术 循环展开（loop unrolling）技术 换名（renaming）技术,4.1 指令级并行的概念,4.1.1 循环展开调度的基本方法,1. 指令调度 通过改变指令在程序中的位置，将相关指 令之间的距离加大到不小于指令执行延迟，将 相关指令转化为无关指令。 指令调度是循环展开的技术基础。 2. 编译器在完成这种指令调度时，受限于以下两 个特性：,程序固有的指令级并行性 流水线功能部件的执行延迟,4.1 指令级并行的概念,3. 本章使用的浮点流水线的延迟,4.1 指令级并行的概念,例4.1 对于下面的源代码，转换成DLX汇编语言，在不进行指令调度和进行指令调度两种情况下，分析代码一

4、次循环的执行时间。 for (i=1; i=1000; i+) xi = xi + s;,4.1 指令级并行的概念,解：(1) 变量分配寄存器 整数寄存器R1：循环计数器，初值为向量 中最高端地址元素的地址。 浮点寄存器F2：保存常数S。 假定最低端元素的地址为8。 (2) DLX汇编语言后的程序 Loop: LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,Loop,4.1 指令级并行的概念,(3) 程序执行的实际时钟,根据表4-2中给出的的延迟，实际时钟如下： 指令流出时钟 Loop: LD F0 , 0(R1) 1 （

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

6、, F4 6 一个元素的操作时间从10个时钟周期减少到6个 5个周期是有指令执行的，1个空转周期。,4.1 指令级并行的概念,(5) 例子中的问题及解决方案,只有LD、ADDD和SD这3条指令是有效操作. 占用3个时钟周期 而SUBI、空转和BENZ这3个时钟周期都是附加的循环控制开销。 循环展开技术 多次复制循环体并相应调整展开后的指令和循环结束条件，增加有效操作时间与控制操作时间的比率。 也给编译器进行指令调度带来了更大的空间。,4.1 指令级并行的概念,例4.2 体现循环展开技术的特点,将例4.1中的循环展开成3次得到4个循环体，再对展开后的指令序列在不调度和调度两种情况下，分析代码的性

7、能。 假定R1的初值为32的倍数，即循环 次数为4的倍数。,4.1 指令级并行的概念,解：,补偿代码问题 寄存器分配 展开后的循环体内不重复使用寄存器。 F0、F4：用于展开后的第1个循环体 F2：保存常数 F6和F8：用于展开后的第2个循环体 F10和F12：用于第3个循环体 F14和F16：用于第4个循环体,4.1 指令级并行的概念,(1) 展开后没有调度的代码,流出时钟 Loop: LD F0,0(R1) 1 （空转） 2 ADDD F4,F0,F2 3 （空转） 4 （空转） 5 SD 0(R1),F4 6 LD F6,-8(R1) 7 （空转） 8 ADDD F8,F6,F2 9 （

8、空转） 10 （空转） 11 SD -8(R1),F8 12 LD F10,-16(R1) 13 （空转） 14,流出时钟 ADDD F12,F10,F2 15 （空转） 16 （空转） 17 SD -16(R1),F12 18 LD F14,-24(R1) 19 （空转） 20 ADDD F16,F14,F2 21 （空转） 22 （空转） 23 SD -24(R1),F16 24 SUBI R1,R1,#32 25 （空转） 26 BNEZ R1,Loop 27 （空转） 28,4.1 指令级并行的概念,结果分析:,这个循环每遍共使用了28个时钟周期 有4个循环体，完成4个元素的操作 平均

9、每个元素使用28/4=7个时钟周期 原始循环的每个元素需要10个时钟周期 节省的时间:从减少循环控制的开销中获得的 在整个展开后的循环中，实际指令只有14条，其它13个周期都是空转。 效率并不高,4.1 指令级并行的概念,(2) 对指令序列进行优化调度,指令流出时钟 Loop: LD F0,0(R1) 1 LD F6,-8(R1) 2 LD F10,-16(R1) 3 LD F14,-24(R1) 4 ADDD F4,F0,F2 5 ADDD F8,F6,F2 6 ADDD F12,F10,F2 7 ADDD F16,F14,F2 8 SD 0(R1),F4 9 SD -8(R1),F8 10

10、 SUBI R1,R1,#32 12 SD 16(R1),F12 11 BNEZ R1,Loop 13 SD 8(R1),F16 14,4.1 指令级并行的概念,结果分析：,没有数据相关引起的空转等待 整个循环仅仅使用了14个时钟周期 平均每个元素的操作使用14/4=3.5个时钟周期 循环展开和指令调度可以有效地提高循环级并行性。 这种循环级并行性的提高实际是通过实现指令级并行来达到的。 可以使用编译器来完成，也可以通过硬件来完成。,4.1 指令级并行的概念,4. 循环展开和指令调度时要注意的问题,(1) 保证正确性 (2) 注意有效性 (3) 使用不同的寄存器 (4) 尽可能减少循环控制中的

11、测试指令和分支指令 (5) 注意对存储器数据的相关性分析 (6) 注意新的相关性,5. 实现循环展开的关键 分析清楚代码中指令的相关性，然后通过 指令调度来消除相关.,4.1 指令级并行的概念,4.1.2 相关性,开发指令级并行的关键 存在相关的两条指令，不能改变它们的顺序。 相关是否导致流水线的空转，还与流水线的组织与结构有关。 程序中的相关主要有以下三种,数据相关 名相关 控制相关,4.1 指令级并行的概念,1. 数据相关（data dependence）,对于指令i和指令j，如果 (1) 指令j使用指令i产生的结果，或者 (2) 指令j与指令k数据相关，指令k与指令i数据相 关，则指令j

12、与指令i数据相关。 数据相关具有传递性。 数据相关是两条指令之间存在一个先写后读相关链。 相关链贯穿整个程序，是程序的内在特征。 这种相关链是导致流水线停顿的原因之一。,4.1 指令级并行的概念,指令的相关距离（distance） 两条指令之间的指令条数。 分析数据相关的主要工作: (1) 确定指令的相关性，找到所有可能产生停 顿的地方。 (2) 确定必须严格遵守的数据的计算顺序。 (3) 确定指令的最大相关距离，确定程序中可 能的最大并行性。,4.1 指令级并行的概念,2. 名相关（name dependence）,指令使用的寄存器或存储器称为名。 如果两条指令使用相同的名，但是它们之间并没

13、有数据流，则称之为名相关。 指令j与指令i之间名相关有以下两种： (1) 反相关（anti-dependence） (2) 输出相关（output dependence）,4.1 指令级并行的概念,消除名相关,名相关的指令之间没有数据交换。 如果一条指令中的名改变了，并不影响另外一条指令的执行。 通过改变指令中操作数的名来消除名相关，这就是换名（renaming）技术。 对于寄存器操作数进行换名称为寄存器换名。 （register renaming） 可以用编译器静态完成或硬件动态完成。,4.1 指令级并行的概念,例：我们对例4.2编译过程进行分析，来仔细考察 换名的过程。 (1) 首先，仅仅

14、去除4遍循环体中的分支指令， 得到以下由17条指令构成的指令序列：,4.1 指令级并行的概念,Loop: 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,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 ,

15、 R1 , #8 BNEZ R1 , Loop,4.1 指令级并行的概念,(2) 编译器可以通过对相关链上存储器访问偏移 量的直接调整，将前3条SUBI指令消除掉，从而得到下面一个14条指令构成的指令序列：,4.1 指令级并行的概念,Loop: 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

16、 SD -24(R1) , F4 SUBI R1 , R1 , #32 BNEZ R1 , Loop,4.1 指令级并行的概念,(3) 通过寄存器换名，消除名相关。 得到右边的指令序列：,Loop: LD F0 , 0(R1) ADDD F4 , F0 , F2 SD 0(R1) , F4 LD F6 , -8(R1) ADDD F8 , F6 , F2 SD -8(R1) , F8 LD F10 , -16(R1) ADDD F12 , F10 , F2 SD -16(R1) , F12 LD F14 , -24(R1) ADDD F16 , F14 , F2 SD -24(R1) , F16 SUBI R