《计算机体系结构》 第四章 指令级并行

篑 第四章指令级并行 41指令级并行的概念 1.流水线的性能受限于流水线中指令之间的相关 性 结构相关 数据相关(写后读RAW读后写WAR写后写 狗 WAW) 控制相关 CP流水线=CP理想+停顿结构相关+停顿写后读+停顿读 后写 +停顿写后写+停顿 控制相关 本章研究的内容:如何消除这些停顿使得进入流水

1. 流水线的性能受限于流水线中指令之间的相关 性： • 结构相关 • 数据相关(写后读RAW,读后写WAR,写后写 WAW) • 控制相关 CPI流水线= CPI理想+停顿结构相关+停顿写后读+停顿读 后写 +停顿写后写+停顿控制相关 本章研究的内容:如何消除这些停顿,使得进入流水 线的指令序列运行时能有更好的并行性 第四章 指令级并行 4.1 指令级并行的概念

篑 2.本章所研究的提高指令级并行的技术 体()循环展开控制相关停顿 条|(态海水词度数塌反 (4)分支预测:控制相关停顿 狗 (5)推断 所有数据/控制相关停顿 (6)多指令流出:提高理想cPI 其他技术:如向量计算机(不在本章讨论) 研究范围:一个基本程序块如一个循环体

2. 本章所研究的提高指令级并行的技术 (1)循环展开: 控制相关停顿 (2)基本流水线调度: 数据写后读停顿 (3)指令动态调度: 各种数据相关停顿 (4)分支预测: 控制相关停顿 (5)推断: 所有数据/控制相关停顿 (6)多指令流出: 提高理想CPI 其他技术: 如向量计算机(不在本章讨论) 研究范围: 一个基本程序块,如一个循环体

3.本章主要针对DLX浮点流水线来进行研究并作如下 的假设: 体 匚产生结果指令使用结果指令停顿周期数 浮点计算 另外的浮点计算3 浮点计算 浮点存操作(SD)_2 浮点取操作①LD)浮点计算 狗 浮点取操作(LD)浮点存操作(SD)|0 而对DLX整型流水线除了分支指令有一个时钟周期 延迟,其余指令没有延迟(为方便起见)

3. 本章主要针对DLX浮点流水线来进行研究,并作如下 的假设: 产生结果指令 使用结果指令 停顿周期数 浮点计算 另外的浮点计算 3 浮点计算 浮点存操作(SD) 2 浮点取操作(LD) 浮点计算 1 浮点取操作(LD) 浮点存操作(SD) 0 而对DLX整型流水线,除了分支指令有一个时钟周期 延迟，其余指令没有延迟（为方便起见）

4.1.1循环展开调度的基本方法 提高指令级并行的最基本方法 (1)指令调度 (2)循环展开 一般由编译器来完成。 指令调度:通过改变指令在程序中的位置,将相关指令 之间的距离加大到不小于指令执行延迟的时 钟数,使相关指令成为实际上的无关指令

4.1.1 循环展开调度的基本方法 提高指令级并行的最基本方法: (1)指令调度 (2)循环展开 一般由编译器来完成。 指令调度：通过改变指令在程序中的位置，将相关指令 之间的距离加大到不小于指令执行延迟的时 钟数，使相关指令成为实际上的无关指令

例:for(i=1;i<=1000;i++) x[]=x[+s; 考虑对应的DLX汇编语言实现 约定:x[0]的内存地址为0(为简单起见) R1的初值为X[1000]的地址 F2中存放的值为常量s LOOP. LD FO,O(RI) ADDD F4 F0-F2 SD0(R1),F4 SUBI RI, R1#8 BNEZ RI LOOP

例： for (i=1; i<=1000; i++) x[i]=x[i] + s; 考虑对应的DLX汇编语言实现. 约定：x[0] 的内存地址为 0 （为简单起见） R1的初值为x[1000]的地址 F2中存放的值为常量 s LOOP: LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,LOOP

实际运行: LOOP. LDF0,0(R1) (2) (空转 (3) ADDD F4,F0.F2 (4) (空转) (5) (空转) (6) sD0(R1),F4 SUBI RIRI#8 (8) BNEZ RILOOP (9) (空转) 一共9个时钟周期,其中有4个空转周期

实际运行： (1) LOOP: LD F0,0(R1) (2) (空转) (3) ADDD F4,F0,F2 (4) (空转) (5) (空转) (6) SD 0(R1),F4 (7) SUBI R1,R1,#8 (8) BNEZ R1,LOOP (9) (空转) 一共 9 个时钟周期，其中有 4 个空转周期

指令调度: LOOP. LDF0,0(R1) (2) (空转 (3) ADDD F4 F0 F2 (4) SUBI RIRI#8 (5) BNEZ RI LOOP (6) sD8(R1),F4 一共6个时钟周期,其中有1个空转周期。 这种指令调度由编译完成的,其基本思想是将指令序 列中的“无关”指令调入空转周期

指令调度： (1) LOOP: LD F0,0(R1) (2) (空转) (3) ADDD F4,F0,F2 (4) SUBI R1,R1,#8 (5) BNEZ R1,LOOP (6) SD 8(R1),F4 一共 6 个时钟周期，其中有 1 个空转周期。 这种指令调度由编译器完成的，其基本思想是将指令序 列中的“无关”指令调入空转周期

操作意义分析 每次循环一共使用了五个操作 三个操作为实际操作(LD, ADDD, SD) 两个操作为循环控制( SUBI BENZ) 事实上,循环控制所需要的指令数-般是恒定的,不会 因每次循环所含的操作个数的多少而变化,但它所花 的时间显然与循环次数有关--通过增加每次循环完成 的操作来降低循环次数,从而降低循环控制所花费的时 间 循环展开:通过多次复制循环体(并改变循环结束条件) 来减少循环控制对性能的影响(循环控制指令以及控制 相关引起的停顿)

操作意义分析： 每次循环一共使用了五个操作 三个操作为实际操作( LD, ADDD, SD ) 两个操作为循环控制( SUBI, BENZ ) 事实上，循环控制所需要的指令数一般是恒定的，不会 因每次循环所含的操作个数的多少而变化，但它所花费 的时间显然与循环次数有关---通过增加每次循环完成 的操作来降低循环次数，从而降低循环控制所花费的时 间。 循环展开：通过多次复制循环体(并改变循环结束条件) 来减少循环控制对性能的影响(循环控制指令以及控制 相关引起的停顿)

循环展开(4次): LOOP. LDF0,0(R1) 2) (空转) (3) ADDD F4 F0F2 (4) (空转) (5) (空转) (6) sD0(R1),F4 LDF0,-8(R1) (8) 空转 (9) ADDD F4,F0.F2 10) (空转) (11) (空转) (12) SD-8(R1),F4

循环展开(4次)： (1) LOOP: LD F0,0(R1) (2) (空转) (3) ADDD F4,F0,F2 (4) (空转) (5) (空转) (6) SD 0(R1),F4 (7) LD F0,-8(R1) (8) (空转) (9) ADDD F4,F0,F2 (10) (空转) (11) (空转) (12) SD -8(R1),F4

(13) LDF0,-16(R1) 14) (空转) (15) ADDD F4 F0 F2 16) (空转) 7) (空转) (18) SD-16(R1),F4 (19) LDF0,-24(R1) (20) (空转) (21) ADDD F4,F0,F2 22 (空转) (23) (空转) (24) SD-24(R1),F4 (25) SUBI RI.R1#32 26) BNEZ RI LOOP (27) (空转)

(13) LD F0, -16(R1) (14) (空转 ) (15) ADDD F4,F0,F2 (16) (空转 ) (17) (空转 ) (18) SD -16(R1),F4 (19) LD F0, -24(R1) (20) (空转 ) (21) ADDD F4,F0,F2 (22) (空转 ) (23) (空转 ) (24) SD -24(R1),F4 (25) SUBI R1,R1,#32 (26) BNEZ R1,LOOP (27) (空转 )