指令级并行指令级并行的概念2

指令级并行指令级并行的概念第一页，共32页。1.流水线处理器的实际CPICPI流水线=CPI理想+各类停顿周期数的总和流水线的理想CPI是流水线的最大流量。各类停顿包括：结构相关停顿：是由于两条指令使用同一个功能部件而导致的停顿。控制相关停顿：是由于指令流的改变（如分支指令）而导致的停顿。RAW、WAR和WAW停顿：由数据相关造成的。减少其中的任何一种停顿，都可以有效地减少CPI，从而提高流水线的性能。4.1指令级并行的概念虚拟存储器的特点第二页，共32页。2.本章要研究的技术以及它们所克服的停顿技术主要克服的停顿章节基本流水线调度数据先写后读相关停顿4.1循环展开控制相关停顿4.1寄存器换名数据写后写相关和先读后写相关停顿4.1指令动态调度（记分牌和Tomasulo算法）各种数据相关停顿 4.2动态分支预测控制相关停顿4.3前瞻（Speculation）所有数据/控制相关停顿4.3多指令流出（超标量和超长指令字）提高理想CPI4.44.1指令级并行的概念虚拟存储器的特点第三页，共32页。3.几个概念基本程序块一段除了入口和出口以外不包含其它分支的线性代码段。程序平均每6～7条指令就会有一个分支。循环体中指令之间的并行性称为循环级并行性。开发循环体中存在的并行性。最常见、最基本是指令级并行研究的重点之一。4.1指令级并行的概念虚拟存储器的特点第四页，共32页。最基本的开发循环级并行的技术指令调度（scheduling）技术循环展开（loopunrolling）技术换名（renaming）技术4.1指令级并行的概念虚拟存储器的特点第五页，共32页。循环展开调度的基本方法1.指令调度通过改变指令在程序中的位置，将相关指令之间的距离加大到不小于指令执行延迟，将相关指令转化为无关指令。指令调度是循环展开的技术基础。2.编译器在完成这种指令调度时，受限于以下两个特性：

程序固有的指令级并行性流水线功能部件的执行延迟4.1指令级并行的概念虚拟存储器的特点第六页，共32页。3.本章使用的浮点流水线的延迟产生结果指令使用结果指令延迟时钟周期数浮点计算另外的浮点计算3浮点计算浮点数据存操作（SD）2浮点数据取操作（LD）浮点计算1浮点数据取操作（LD）浮点数据存操作（SD）04.1指令级并行的概念虚拟存储器的特点第七页，共32页。例4.1

对于下面的源代码，转换成DLX汇编语言，在不进行指令调度和进行指令调度两种情况下，分析代码一次循环的执行时间。

for(i=1;i<=1000;i++) x[i]=x[i]+s;4.1指令级并行的概念虚拟存储器的特点第八页，共32页。解：(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指令级并行的概念虚拟存储器的特点第九页，共32页。(3)程序执行的实际时钟根据表4-2中给出的的延迟，实际时钟如下：

指令流出时钟

Loop:LD F0,0(R1) 1

（空转） 2 ADDDF4,F0,F2 3

（空转） 4

（空转） 5 SD 0(R1),F4 6 SUBI R1,R1,#8 7

（空转） 8 BNEZR1,Loop 9

（空转） 10每个元素的操作需要10个时钟周期，其中5个是空转周期。4.1指令级并行的概念第十页，共32页。(4)指令调度以后，程序的执行情况SD放在分支指令的分支延迟槽中对存储器地址偏移量进行调整

指令流出时钟Loop:LDF0,0(R1) 1 SUBIR1,R1,#8 2 ADDDF4,F0,F2 3

（空转） 4 BNEZR1,Loop 5 SD 8(R1),F4 6一个元素的操作时间从10个时钟周期减少到6个5个周期是有指令执行的，1个空转周期。4.1指令级并行的概念虚拟存储器的特点第十一页，共32页。(5)例子中的问题及解决方案只有LD、ADDD和SD这3条指令是有效操作.占用3个时钟周期而SUBI、空转和BENZ这3个时钟周期都是附加的循环控制开销。循环展开技术多次复制循环体并相应调整展开后的指令和循环结束条件，增加有效操作时间与控制操作时间的比率。也给编译器进行指令调度带来了更大的空间。4.1指令级并行的概念虚拟存储器的特点第十二页，共32页。例4.2体现循环展开技术的特点

将例4.1中的循环展开成3次得到4个循环体，再对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。假定R1的初值为32的倍数，即循环次数为4的倍数。4.1指令级并行的概念虚拟存储器的特点第十三页，共32页。解：补偿代码问题寄存器分配展开后的循环体内不重复使用寄存器。F0、F4：用于展开后的第1个循环体F2：保存常数F6和F8：用于展开后的第2个循环体F10和F12：用于第3个循环体F14和F16：用于第4个循环体4.1指令级并行的概念虚拟存储器的特点第十四页，共32页。(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),F1624 SUBI R1,R1,#32 25

（空转） 26 BNEZ R1,Loop 27

（空转） 284.1指令级并行的概念虚拟存储器的特点第十五页，共32页。结果分析:这个循环每遍共使用了28个时钟周期有4个循环体，完成4个元素的操作平均每个元素使用28/4=7个时钟周期原始循环的每个元素需要10个时钟周期节省的时间:从减少循环控制的开销中获得的在整个展开后的循环中，实际指令只有14条，其它13个周期都是空转。效率并不高4.1指令级并行的概念虚拟存储器的特点第十六页，共32页。(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 144.1指令级并行的概念第十七页，共32页。结果分析：没有数据相关引起的空转等待整个循环仅仅使用了14个时钟周期平均每个元素的操作使用14/4=3.5个时钟周期循环展开和指令调度可以有效地提高循环级并行性。这种循环级并行性的提高实际是通过实现指令级并行来达到的。可以使用编译器来完成，也可以通过硬件来完成。4.1指令级并行的概念第十八页，共32页。4.循环展开和指令调度时要注意的问题(1)保证正确性(2)注意有效性(3)使用不同的寄存器(4)尽可能减少循环控制中的测试指令和分支指令(5)注意对存储器数据的相关性分析(6)注意新的相关性5.实现循环展开的关键

分析清楚代码中指令的相关性，然后通过指令调度来消除相关.4.1指令级并行的概念第十九页，共32页。相关性开发指令级并行的关键存在相关的两条指令，不能改变它们的顺序。相关是否导致流水线的空转，还与流水线的组织与结构有关。程序中的相关主要有以下三种

数据相关名相关控制相关4.1指令级并行的概念第二十页，共32页。1.数据相关（datadependence）对于指令i和指令j，如果

(1)指令j使用指令i产生的结果，或者

(2)指令j与指令k数据相关，指令k与指令i数据相关，则指令j与指令i数据相关。数据相关具有传递性。数据相关是两条指令之间存在一个先写后读相关链。相关链贯穿整个程序，是程序的内在特征。这种相关链是导致流水线停顿的原因之一。4.1指令级并行的概念第二十一页，共32页。指令的相关距离（distance）两条指令之间的指令条数。分析数据相关的主要工作:(1)确定指令的相关性，找到所有可能产生停顿的地方。

(2)确定必须严格遵守的数据的计算顺序。

(3)确定指令的最大相关距离，确定程序中可

能的最大并行性。4.1指令级并行的概念第二十二页，共32页。2.名相关（namedependence）指令使用的寄存器或存储器称为名。如果两条指令使用相同的名，但是它们之间并没有数据流，则称之为名相关。指令j与指令i之间名相关有以下两种：

(1)反相关（anti-dependence）

(2)输出相关（outputdependence）4.1指令级并行的概念第二十三页，共32页。

消除名相关名相关的指令之间没有数据交换。如果一条指令中的名改变了，并不影响另外一条指令的执行。通过改变指令中操作数的名来消除名相关，这就是换名（renaming）技术。对于寄存器操作数进行换名称为寄存器换名。

（registerrenaming）可以用编译器静态完成或硬件动态完成。4.1指令级并行的概念第二十四页，共32页。例：我们对例4.2编译过程进行分析，来仔细考察

换名的过程。

(1)首先，仅仅去除4遍循环体中的分支指令，

得到以下由17条指令构成的指令序列：4.1指令级并行的概念第二十五页，共32页。Loop:LDF0,0(R1) ADDDF4,F0,F2 SD 0(R1),F4 SUBIR1,R1,#8 LD F0,0(R1) ADDDF4,F0,F2 SD 0(R1),F4 SUBIR1,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,Loop4.1指令级并行的概念第二十六页，共32页。(2)编译器可以通过对相关链上存储器访问偏移量的直接调整，将前3条SUBI指令消除掉，从而得到下面一个14条指令构成的指令序列：

4.1指令级并行的概念第二十七页，共32页。Loop: LD F0,0(R1) ADDDF4,F0,F2

SD 0(R1),F4 LD F0,-8(R1) ADDDF4,F0,F2 SD -8(R1),F4

LD F0,-16(R1) ADDDF4,F0,F2

SD -16(R1),F4 LD F0,-24(R1) ADDD F4,F0,F2 SD -24(R1),F4 SUBIR1,R1,#32 BNEZR1,Loop4.1指令级并行的概念第二十八页，共32页。(3)通过寄存器换名，消除名相关。得到右边的指令序列：Loop: LD F0,0(R1) ADDD F4,F0,F2

SD 0(R1),F4 LD F6,-8(R1) ADDD F8