指令级并行的概念.ppt

33,／31,4.1 指令级并行的概念,当指令之间不存在相关时，它们在流水线中是可以重叠起来并行执行的这种指令序列中存在的潜在并行性称为,指令级并行,Instruction-Level Parallelism，,简记为,ILP）,,本章研究：,如何通过各种可能的技术，获得更多的指令级并行性硬件技术和软件技术）,,必须要硬件技术和软件技术互相配合，才能够最大限度地挖掘出程序中存在的指令级并行第四章 指令级并行,1.流水线处理器的实际,CPI,CPI,流水线,=,CPI,理想,+,各类停顿周期数的总和,,流水线的理想,CPI,是流水线的最大流量各类停顿包括：,,结构相关停顿：是由于两条指令使用同一个功能部件而导致的停顿控制相关停顿：是由于指令流的改变（如分支指令）而导致的停顿RAW,、,WAR,和,WAW,停顿：由数据相关造成的减少其中的任何一种停顿，都可以有效地减少,CPI,，,从而提高流水线的性能4.1 指令级并行的概念,2. 本章要研究的技术以及它们所克服的停顿,技术,主要克服的停顿,章节,基本流水线调度,数据先写后读相关停顿,4.1,循环展开,控制相关停顿,4.1,寄存器换名,数据写后写相关和先读后写相关停顿,4.1,指令动态调度（记分牌和Tomasulo算法）,各种数据相关停顿,4.2,动态分支预测,控制相关停顿,4.3,前瞻（Speculation）,所有数据/控制相关停顿,4.3,多指令流出（超标量和超长指令字）,提高理想CPI,4.4,4.1 指令级并行的概念,3.几个概念,基本程序块,,一段除了入口和出口以外不包含其它分支的线性代码段。

程序平均每,6～7,条指令就会有一个分支循环体中指令之间的并行性称为,循环级并行性,开发循环体中存在的并行性最常见、最基本,,是指令级并行研究的重点之一4.1 指令级并行的概念,最基本的开发循环级并行的技术,,指令调度,（,scheduling）,技术,,循环展开,（,loop unrolling）,技术,,换名,（,renaming）,技术,,4.1 指令级并行的概念,4.1.1 循环展开调度的基本方法,1.,指令调度,,通过改变指令在程序中的位置，将相关指,,令之间的距离加大到不小于指令执行延迟，将,,相关指令转化为无关指令指令调度是循环展开的技术基础2. 编译器在完成这种指令调度时，受限于以下两,,个特性：,,程序固有的指令级并行性,,流水线功能部件的执行延迟,4.1 指令级并行的概念,3. 本章使用的浮点流水线的延迟,产生结果指令,使用结果指令,延迟时钟周期数,浮点计算,另外的浮点计算,3,浮点计算,浮点数据存操作（SD）,2,浮点数据取操作（LD）,浮点计算,1,浮点数据取操作（LD）,浮点数据存操作（SD）,0,4.1 指令级并行的概念,例4.1,,,对于下面的源代码，转换成,DLX,汇编语言，在,不进行指令调度,和,进行指令调度,两种情况下，分析代码一次循环的执行时间。

for (i=1; i<=1000; i++),,x[i] = x[i] + s;,4.1 指令级并行的概念,解：,(1),,变量分配寄存器,,整数寄存器,R1,：循环计数器，初值为向量,,中最高端地址元素的地址浮点寄存器,F2,：保存常数,S,假定最低端元素的地址为,82),,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,,（,空转） 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) , 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个,循环体，再对展开后的指令序列在不调度和调度两种情况下，分析代码的性能假定,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,,（空转） 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,个,元素的操作,,平均每个元素使用,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,,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) 尽可能减少循环控制中的测试指令和分支指令,,(5) 注意对存储器数据的相关性分析,,(6) 注意新的相关性,,5.,实现循环展开的关键,,,分析清楚代码中指令的相关性，然后通过,,指令调度来消除相关.,4.1 指令级并行的概念,4.1.2 相关性,开发指令级并行的,关键,,存在相关的两条指令，不能改变它们的顺序。

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

指令,j,与,指令,i,之间名相关有以下两种：,,(1),反相关,（,anti-dependence）,,(2),输出相关,（,output dependence）,4.1 指令级并行的概念,消除名相关,名相关的指令之间没有数据交换如果一条指令中的名改变了，并不影响另外一条指令的执行通过改变指令中操作数的名来消除名相关，这就是,换名（,renaming,）,技术,对于寄存器操作数进行换名称为,寄存器换名,register renaming）,,可以用编译器静态完成或硬件动态完成4.1 指令级并行的概念,例：,我们对,例4.2,编译过程进行分析，来仔细考察 换名的过程1) 首先，仅仅去除,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 , 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,,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 R1 , R1 , #32,,BNEZ R1 , Loop,,换名操作需要较大的寄存器开销4.1 指令级并行的概念,3．控制相关（,control dependence）,,控制相关,是指由分支指令引起的相关典型的程序结构是“,if-then,”,结构看下面一个示例：,,,if p1{,,S1;,,,,};,,S;,,,,if p2{,,,,S2;,,,,};,,4.1 指令级并行的概念,处理控制相关的,两个原则,：,,(1) 与控制相关的指令不能移到分支指令之,,前，即控制有关的指令不能调度到分支,,指令控制范围以外；,,(2) 与控制无关的指令不能移到分支指令之,,后，即控制无关的指令不能调度到分支,,指令控制范围以内。

4.1 指令级并行的概念,再考察,例4.2,：,,假设循环展开时，循环控制分支指令没有去除，,,则指令序列如下：,4.1 指令级并行的概念,Loop: LD F0 , 0(R1),,ADDD F4 , F0 , F2,,,SD 0(R1) , F4,,SUBI R1 , R1 , #8,,BEQZ R1 , Exit,,LD F0 , 0(R1),,ADDD F4 , F0 , F2,,SD 0(R1) , F4,,,SUBI R1 , R1 , #8,,BEQZ R1 , Exit,,LD F0 , 0(R1),,ADDD F4 , F0 , F2,,,SD 0(R1) , F4,,SUBI R1 , R1 , #8,,BEQZ R1 , Exit,,LD F0 , 0(R1),,ADDD F4 , F0 , F2,,SD 0(R1) , F4,,,SUBI R1 , R1 , #8,,BNEZ R1 , Loop,,Exit:,,4.1 指令级并行的概念,。