有可能有多个功能部件挂起在这一步。 解决写后读相关。
(3)执行(EX)：对浮点运算来讲，这一步可能要化 多个时钟周期，由于功能部件独立，不会发生冲突。 (4)写结果(WR)：记分牌知道功能部件执行完成后， 检查目标寄存器，如果前面没有指令读该寄存器或 已完成对该寄存器的读操作，则完成这一步骤，否 则将该功能部件挂起在这一步。
水线的指令序列运行时能有更好的并行性
2. 本章所研究的提高指令级并行的技术
(1)循环展开: (2)基本流水线调度: (3)指令动态调度: (4)分支预测: (5)推断: (6)多指令流出: 其他技术: 研究范围: 控制相关停顿 数据写后读停顿 各种数据相关停顿 控制相关停顿 所有数据/控制相关停顿 提高理想CPI
(9) (10) (11) (12) (13) (14)
SD SD SD
0(R1),F4 -8(R1),F8 -16(R1),F12
SUBI R1,R1,#32 BNEZ R1,LOOP SD 8(R1),F16
一共 14 个时钟周期，平均每次循环使用14/43.5个 周期。所有“空转”消失，即数据相关和控制相关被消 除，达到完全指令级并行。 结论：由编译器所完成的循环展开和指令调度(静态调 度)，能有效提高指令级并行。
4.2.2 动态算法之一：记分牌
1. 命名(Scoreboard)起源于CDC 6600 2. 将管理由指令移向功能部件 3. 采用尽可能多的功能部件
CDC 6600采用16个功能部件：4个浮点部件，5个存 储器访问部件，7个整数操作部件。
在DLX中，用于浮点部件：一个浮点乘法器，一个浮 点加法器，一个浮点除法器，一个整数部件。
指令调度：
(1) (2) (3) (4) (5) (6) LOOP: LD F0,0(R1) (空转) ADDD F4,F0,F2 SUBI R1,R1,#8 BNEZ R1,LOOP SD 8(R1),F4
一共 6 个时钟周期，其中有 1 个空转周期。
这种指令调度由编译器完成的，其基本思想是将指令序 列中的“无关”指令调入空转周期。
4.2 指令的动态调度
1. 基本流水线的数据相关解决方法：
• • 采用定向技术（相关隐藏） 停顿
2. 解决停顿的方法：
•
静态调度方法（编译器） 产生于60年代，目前比较流行。
动态调度方法（处理器） 产生于更早时期，目前在一些RISC机中仍 在采用。
•
3. 动态调度的优点： • • • 能处理某些在编译时无法知道的相关情况 能简化编译器的设计 使代码适合移植
循环展开+指令调度要注意这几方面问题： (1)正确性(主要是循环控制和操作数偏移量修改) (2)有效性(主要是不同循环次之间的无关性) (3)使用不同的寄存器(避免冲突) (4)尽可能减少循环控制中的测试和分支 (5)注意对存储器数据的相关性分析 (6)注意新的相关性
关键：要分析清指令之间存在怎样的相关性以及在这种 相关性下指令应该如何被修改和调度。
4. 动态调度的主要缺点： • • 硬件复杂度大 调度的范围比较小
4.2.1 动态调度的原理
1. 基本流水线的最大问题是指令必须顺序流出: 例如： DIVD F0,F2,F4 ADDD F10,F0,F8 SUBD F12,F8,F14
SUBD指令并不与前面指令数据相关，但仍需等待。 2.动态调度的解决方法： (1)结构相关：设置多个功能部件或功能部件 流水化 (2)数据相关：挂起
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 ......
名相关不能改变指令顺序，但由于没有数据流，但可以 通过改变操作数名来消除名相关，称为重命名 (renaming)技术： LOOP: LD F0,0(R1) ADDD F4,F0,F2 SD 0(R1),F4 LD F8,-8(R1) ADDD F12,F8,F2 SD -8(R1),F12 ......
例： for (i=1; i<=1000; i++) x[i]=x[i] + s; 考虑对应的DLX汇编语言实现. 约定：x[0] 的内存地址为 0 （为简单起见） R1的初值为x[1000]的地址 F2中存放的值为常量 s LOOP: LD ADDD SD SUBI BNEZ F0,0(R1) F4,F0,F2 0(R1),F4 R1,R1,#8 R1,LOOP
4. 指令运行过程
(1)指令流出(IS)：如果指令所需的功能部件空闲， 并且其他正在运行的指令与它不发生目的寄存器冲 突，则记分牌将向该功能部件流出指令，功能部件 被置成准备运行该指令状态(纪录于记分牌)
解决了结构相关和写后写相关。
(2)读操作数(RO)：如果前面已流出的正在运行的 指令不对本指令的源操作数进行写操作，或者一个 正在工作的功能部件已完成对该寄存器的写操作， 则进行读操作数，并完成该步骤(离开挂起状态)。
一共 27 个时钟周期，平均每次循环使用27/46.7个 周期。 循环展开+指令调度(循环展开调度)： (1) (2) (3) (4) (5) (6) (7) (8) LOOP: LD LD LD LD ADDD ADDD ADDD ADDD F0,0(R1) F6,-8(R1) F10,-16(R1) F14,-24(R1) F4,F0,F2 F8,F6,F2 F12,F10,F2 F16,F14,F2
有可能有多个功能部件挂起在这一步。 解决读后写相关。
5. 例子：
LD LD MULD SUBD DIVD ADDD
F6,34(R2) F2,45(R3) F0,F2,F4 F8,F6,F2 F10,F0,F6 F6,F8,F2
(1)指令状态表：表示正在执行的各指令处于四步中的 哪一步。 (2)功能状态表：表示各功能部件的状态，每个功能部 件一共有九个域： Busy: 该功能部件是否在工作(被分配) Op: 该功能部件当前操作
4.1.2 相关性 相关性指的是一条指令的运行如何依赖于另一条指令的 运行。 研究相关性，不但可作为是否可指令调度的依据，而且 可了解程序固有的并行性以及可以获得的并行性。
相关
意味指令的运行、结果产生的顺序有要求， 意味指令的并行运行和改变顺序可能会产生问题， 不意味指令的流水线运行一定会产生停顿。
Fi: 目的寄存器编号 Fj,Fk:源寄存器编号 Qj,Qk:向源寄存器写结果的功能部件 Rj,Rk:源寄存器是否就绪并且还未被使用
Yes: No:
就绪并且还没有被使用过 (后面指令不可改写它) (1)未就绪 (前面指令可改写它) (2)已被使用过 (后面指令可改写它)
(3)结果寄存器状态表：表示每个寄存器是当前哪一个 功能部件的目的寄存器 (不是则为零)。
而对DLX整型流水线,除了分支指令有一个时钟周期 延迟，其余指令没有延迟（为方便起见）。
4.1.1 循环展开调度的基本方法 提高指令级并行的最基本方法:
(1)指令调度 (2)循环展开
一般由编译器来完成。 指令调度：通过改变指令在程序中的位置，将相关指令 之间的距离加大到不小于指令执行延迟的时 钟数，使相关指令成为实际上的无关指令。
实际运行：
(1) (2) (3) (4) (5) (6) (7) (8) (9) LOOP: LD F0,0(R1) (空转) ADDD F4,F0,F2 (空转) (空转) SD 0(R1),F4 SUBI R1,R1,#8 BNEZ R1,LOOP (空转)
一共 9 个时钟周期，其中有 4 个空转周期。
如向量计算机(不在本章讨论) 一个基本程序块,如一个循环体
3. 本章主要针对 DLX浮点流水线来进行研究 ,并作如下 的假设:
产生结果指令 浮点计算 浮点计算 浮点取操作(LD) 浮点取操作(LD) 使用结果指令 另外的浮点计算 浮点存操作(SD) 浮点计算 浮点存操作(SD) 停顿周期数 3 2 1 0
(13) (14) (15) (16) (17) (18)
LD F0,-16(R1) (空转) ADDD F4,F0,F2 (空转) (空转) SD -16(R1),F4
(19) (20) (21) (22) (23) (24) (25) (26) (27)
LD F0,-24(R1) (空转) ADDD F4,F0,F2 (空转) (空转) SD -24(R1),F4 SUBI R1,R1,#32 BNEZ R1,LOOP (空转)
分析数据相关的主要工作： (1)确定指令的相关性 (2)确定数据的计算顺序 (3)确定最大并行性
数据相关是程序相关性中最本质的相关性之一。
2.名相关 两条指令使用相同的寄存器或内存单元(称为名)， 但它们之间没有数据流。
指令j和指令i之间的名相关有以下两种： (1)反相关： 指令i先执行，指令j写的名是指令i读 的名(读后写相关)。 (2)输出相关：指令i和指令j写的是同一个寄存器或内 存单元(写后写相关)。
相关类型 数据相关(data dependence) 名相关(name dependence) 控制相关(control dependence)
1. 数据相关 对指令i和j，如果 (1)指令j使用指令i产生的结果，或 (2)指令j与指令k数据相关，指令k与指令i数据相 关(传递性)
例 LOOP:
停顿：后续指令全部被停顿 挂起：后续指令仍可执行，被流出(如果没有数据相 关)或也被挂起(如果有数据相关) 处理器中： • 可以有多条指令同时被执行(多个功能部件) • 可以有多条指令被挂起(一旦解除数据相关则运行) • 指令运行乱序
乱序带来的问题：异常处理比较复杂，难以确定和恢复 现场。
3.指令译码阶段分成两个阶段： • 流出(Issue,IS):指令译码，检查结构相关(停顿) • 读操作数(Read Operands,RO):检查数据相关(挂起)