1,流水线的性能受限于流水线中指令之间的相关性：
结构相关
数据相关 (写后读 RAW,读后写 WAR,写后写 WAW)
控制相关
CPI流水线 = CPI理想 +停顿 结构相关 +停顿 写后读 +停顿 读后写
+停顿 写后写 +停顿 控制相关本章研究的内容,如何消除这些停顿,使得进入流水线的指令序列运行时能有更好的 并行性第四章 指令级并行
4.1 指令级并行的概念
2,本章所研究的提高指令级并行的技术
(1)循环展开,控制相关停顿
(2)基本流水线调度,数据写后读停顿
(3)指令动态调度,各种数据相关停顿
(4)分支预测,控制相关停顿
(5)推断,所有数据 /控制相关停顿
(6)多指令流出,提高理想 CPI
其他技术,如向量计算机 (不在本章讨论 )
研究范围,一个基本程序块,如一个循环体
3,本章主要针对 DLX浮点流水线来进行研究,并作如下的假设,
产生结果指令 使用结果指令 停顿周期数浮点计算 另外的浮点计算 3
浮点计算 浮点存操作 ( SD ) 2
浮点取操作 ( L D) 浮点计算 1
浮点取操作 ( L D) 浮点存操作 ( SD ) 0
而对 DLX整型流水线,除了分支指令有一个时钟周期延迟,其余指令没有延迟 （ 为方便起见 ） 。
4.1.1 循环展开调度的基本方法提高指令级并行的最基本方法,
(1)指令调度
(2)循环展开一般由编译器来完成。
指令调度,通过改变指令在程序中的位置，将相关指令之间的距离加大到不小于指令执行延迟的时钟数，使相关指令成为实际上的无关指令。
例,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
实际运行：
(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 个空转周期。
指令调度：
(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 )
事实上，循环控制所需要的指令数一般是恒定的，不会因每次循环所含的操作个数的多少而变化，但它所花费的时间显然与循环次数有关 ---通过增加每次循环完成的操作来降低循环次数，从而降低循环控制所花费的时间。
循环展开,通过多次复制循环体 (并改变循环结束条件 )
来减少循环控制对性能的影响 (循环控制指令以及控制相关引起的停顿 )。
循环展开 (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) 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) (空转 )
一共 27 个时钟周期，平均每次循环使用 27/4?6.7个周期。
循环展开 +指令调度 (循环展开调度 )：
(1) LOOP,LD F0,0(R1)
(2) LD F6,-8(R1)
(3) LD F10,-16(R1)
(4) LD F14,-24(R1)
(5) ADDD F4,F0,F2
(6) ADDD F8,F6,F2
(7) ADDD F12,F10,F2
(8) ADDD F16,F14,F2
(9) SD 0(R1),F4
(10) SD -8(R1),F8
(11) SD -16(R1),F12
(12) SUBI R1,R1,#32
(13) BNEZ R1,LOOP
(14) SD 8(R1),F16
一共 14 个时钟周期，平均每次循环使用 14/4?3.5个周期。所有“空转”消失，即数据相关和控制相关被消除，达到完全指令级并行。
结论,由编译器所完成的循环展开和指令调度 (静态调度 )，能有效提高指令级并行。
循环展开 +指令调度 要注意这几方面问题：
(1)正确性 (主要是循环控制和操作数偏移量修改 )
(2)有效性 (主要是不同循环次之间的无关性 )
(3)使用不同的寄存器 (避免冲突 )
(4)尽可能减少循环控制中的测试和分支
(5)注意对存储器数据的相关性分析
(6)注意新的相关性关键,要分析清指令之间存在怎样的相关性以及在这种相关性下指令应该如何被修改和调度。
4.1.2 相关性相关性指的是一条指令的运行如何依赖于另一条指令的运行 。
研究相关性,不但可作为是否可指令调度的依据,而且可了解程序固有的并行性以及可以获得的并行性 。
相关意味指令的运行,结果产生的顺序有要求,
意味指令的并行运行和改变顺序可能会产生问题,
不意味指令的流水线运行一定会产生停顿 。
相关类型数据相关 (data dependence)
名相关 (name dependence)
控制相关 (control dependence)
1,数据相关对指令 i和 j，如果
(1)指令 j使用指令 i产生的结果，或
(2)指令 j与指令 k数据相关，指令 k与指令 i数据相关 (传递性 )
例
LOOP,LD F0,0(R1) (1)
ADDD F4,F0,F2 (2)
SD 0(R1),F4 (3)
结论指令 (1)和指令 (2)数据相关，指令 (2)和指令 (3)
数据相关 =〉 指令 (1)和指令 (3)数据相关例
SUBI R1,R1,8 (4)
BNEZ R1,LOOP (5)
结论指令 (4)和指令 (5)数据相关 。
分析数据相关的主要工作：
(1)确定指令的相关性
(2)确定数据的计算顺序
(3)确定最大并行性数据相关是程序相关性中最本质的相关性之一。
2.名相关两条指令使用相同的寄存器或内存单元 (称为名 )，
但它们之间没有数据流。
指令 j和指令 i之间的名相关有以下两种：
(1)反相关,指令 i先执行，指令 j写的名是指令 i读的名 (读后写相关 )。
(2)输出相关,指令 i和指令 j写的是同一个寄存器或内存单元 (写后写相关 )。
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
......
3,控制相关分支指令引起的相关，如果一条指令是否执行的情况依赖于一条分支指令，则称它与该分支指令控制相关。
例
if p1 {
s1
};
if p2 {
s2
};
=>
s1控制相关于 p1,s2控制相关于 p2
s1与 p2,s2与 p1控制无关 。
基本处理原则
(1)与控制相关的指令不能移到分支指令之前；
(2)与控制无关的指令不能移到分支指令之后；
减少或消除控制相关的方法是减少或消除分支指令。
1,基本流水线的数据相关解决方法：
采用定向技术 （ 相关隐藏 ）
停顿
2,解决停顿的方法：
静态调度方法（编译器）
产生于 60年代，目前比较流行。
动态调度方法（处理器）
产生于更早时期,目前在一些 RISC机中仍在采用 。
4.2 指令的动态调度
3,动态调度的优点：
能处理某些在编译时无法知道的相关情况
能简化编译器的设计
使代码适合移植
4,动态调度的主要缺点：
硬件复杂度大
调度的范围比较小
4.2.1 动态调度的原理
1,基本流水线的最大问题是指令必须顺序流出,
例如：
DIVD F0,F2,F4
ADDD F10,F0,F8
SUBD F12,F8,F14
SUBD指令并不与前面指令数据相关，但仍需等待。
2.动态调度的解决方法：
(1)结构相关：设置多个功能部件或功能部件流水化
(2)数据相关：挂起停顿,后续指令全部被停顿挂起,后续指令仍可执行，被流出 (如果没有数据相关 )或也被挂起 (如果有数据相关 )
处理器中：
可以有多条指令同时被执行 (多个功能部件 )
可以有多条指令被挂起 (一旦解除数据相关则运行 )
指令运行乱序乱序带来的问题：异常处理比较复杂，难以确定和恢复现场。
3.指令译码阶段分成两个阶段：
流出 (Issue,IS):指令译码，检查结构相关 (停顿 )
读操作数 (Read Operands,RO):检查数据相关 (挂起 )
4.2.2 动态算法之一：记分牌
1,命名 (Scoreboard)起源于 CDC 6600
2,将管理由指令移向功能部件
3,采用尽可能多的功能部件
CDC 6600采用 16个功能部件,4个浮点部件,5个存储器访问部件,7个整数操作部件。
在 DLX中，用于浮点部件：一个浮点乘法器，一个浮点加法器，一个浮点除法器，一个整数部件。
4,指令运行过程
(1)指令流出 (IS),如果指令所需的功能部件空闲，
并且其他正在运行的指令与它不发生目的寄存器冲突，则记分牌将向该功能部件流出指令，功能部件被置成准备运行该指令状态 (纪录于记分牌 )
解决了结构相关和写后写相关。
(2)读操作数 (RO),如果前面已流出的正在运行的指令不对本指令的源操作数进行写操作，或者一个正在工作的功能部件已完成对该寄存器的写操作，
则进行读操作数，并完成该步骤 (离开挂起状态 )。
有可能有多个功能部件挂起在这一步。
解决写后读相关。
(3)执行 (EX),对浮点运算来讲，这一步可能要化多个时钟周期，由于功能部件独立，不会发生冲突。
(4)写结果 (WR),记分牌知道功能部件执行完成后，
检查目标寄存器，如果前面没有指令读该寄存器或已完成对该寄存器的读操作，则完成这一步骤，否则将该功能部件挂起在这一步。
有可能有多个功能部件挂起在这一步。
解决读后写相关。
5,例子：
LD F6,34(R2)
LD F2,45(R3)
MULD F0,F2,F4
SUBD F8,F6,F2
DIVD F10,F0,F6
ADDD F6,F8,F2
(1)指令状态表,表示正在执行的各指令处于四步中的哪一步。
(2)功能状态表,表示各功能部件的状态，每个功能部件一共有九个域：
Busy,该功能部件是否在工作 (被分配 )
Op,该功能部件当前操作
Fi,目的寄存器编号
Fj,Fk:源寄存器编号
Qj,Qk:向源寄存器写结果的功能部件
Rj,Rk:源寄存器是否 就绪并且还未被使用
Yes,就绪并且还没有被使用过
(后面指令不可改写它 )
No,(1)未就绪
(前面指令可改写它 )
(2)已被使用过
(后面指令可改写它 )
(3)结果寄存器状态表,表示每个寄存器是当前哪一个功能部件的目的寄存器 (不是则为零 )。
指令状态表指令
IS RO EX WR
L D F 6,34 ( R 2)
L D F 2,45 ( R 3)
M U L D F 0,F 2,F 4?
S U B D F 8,F 6,F 2?
D I V D F 10,F 0,F 6?
A D D D F 6,F 8,F 2
功能部件状态表部件
Busy Op Fi Fj Fk Qj Qk Rj Rk
整数 Y es LD F2 R3 No
乘法 Y es M U L D F0 F2 F4 整数 No Y es
加法 Y es SU B D F8 F6 F2 整数 Y es No
除法 y es D I V D F 10 F0 F6 乘法 No Y es
结果寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
部件 乘法 整数 加法 除法
5,例子,假设流水线延迟如下：加法 2 个时钟周期,
乘法十个时钟周期,除法四十时钟周期,起始状态如上表,分别给出 MULD和 DIVD准备写结果之前的记分牌 。
指令状态表指令
IS RO EX WR
L D F 6,34( R2)
L D F 2,45( R3)
MUL D F 0,F 2,F 4
SU B D F 8,F 6,F 2
D I V D F 10,F 0,F 6?
A D D D F 6,F 8,F 2
功能部件状态表部件
B us y Op Fi Fj Fk Qj Qk Rj Rk
整数 NO
乘法 Y es M U L D F0 F2 F4 No No
加法 Y es A D D D F6 F8 F2 No No
除法 y es D I V D F 10 F0 F6 乘法 No Y es
结果寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
部件 乘法 加法 除法指令状态表指令
IS RO EX WR
L D F 6,34(R2)
L D F 2,45(R3)
MUL D F 0,F 2,F 4
SU B D F 8,F 6,F 2
D I V D F 10,F 0,F 6
A D D D F 6,F 8,F 2
功能部件状态表部件
B usy Op Fi Fj Fk Qj Qk Rj Rk
整数 NO
乘法 No
加法 No
除法 y es D I V D F 10 F0 F6 No No
结果寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
部件 除法
6,执行过程：
FU,指令使用的功能部件
D,目的寄存器
S1,S2,源寄存器
Op,要进行的操作
Fj(FU),功能部件 FU的数据项 Fj
result(?D?),结果寄存器中对应于 D的内容 (
产生结果 D的功能部件名 )
Fj(FU)S1?,将寄存器 S1的名送入 Fj(FU)
(1)指令流出 IS
进入条件：
not Busy(FU) and not result(?D?);
not result(?D?)表示结果寄存器状态表中 D 的内容为空。
记分牌纪录操作：
Busy(FU)? yes
Op(FU)? Op
Fi(FU)D?
Fj(FU)S1?
Fk(FU)S2?
Qj? result(?S1?)
Qk? result(?S2?)
Rj? not Qj
Rk? not Qk
result(?D?)? FU
not Qj表示 Qj为零则 yes,反之则 no 。
(2)读操作数 RO
进入条件：
Rj? Rk
记分牌纪录操作：
Rj? no
Rk? no
Qj? 0
Qk? 0
(3)执行 EX
结束条件：
功能部件操作结束
(4)写结果 WR
进入条件：
f( ( Fj(f)? Fi(FU) or Rj(f) = no )
and ( Fk(f)? Fi(FU) or Rk(f) = no ) )
f的两种情况前面指令,Rj(f) = no 表示操作数已取走后面指令,Rj(f) = no 一定成立记分牌纪录操作：
f( if Qj(f) = FU then Rj(f)? yes );
f( if Qk(f) = FU then Rk(f)? yes );
result(Fi(FU)) = 0
busy(FU) = no
性能 （ CDC 6600测试结果）
对 FORTRAN程序性能提高 1.7倍对汇编程序性能提高 2.5倍硬件并不太复杂，记分牌电路只相当于一个功能部件。
性能受限原因：
(1) 程序中可开发的并行性
(2) 记分牌容量
(3) 功能部件的数量和种类
(4) 反相关 (读后写 )和输出相关 (写后写 )
记分牌 (复习 )
记分牌信息分为三部分：
(1)指令状态表：表示正在执行的各指令处于四步中的哪一步。
(2)功能状态表：表示各功能部件的状态，每个功能部件一共有九个域：
Busy,该功能部件是否在工作 (被分配 )
Op,该功能部件当前操作
Fi,目的寄存器编号
Fj,Fk:源寄存器编号
Qj,Qk:向源寄存器写结果的功能部件
（没有则零）
Rj,Rk:源寄存器是否 就绪并且还没有被使用过
Yes,就绪并且还没有被使用过
(后面指令不可改写它 )
No,(1)未就绪
(前面指令可改写它 )
(2)已被使用过
(后面指令可改写它 )
(3)结果寄存器状态表：表示每个寄存器是当前哪一个功能部件的目的寄存器 (否则为零 )。
(1)指令流出 IS
进入条件：
not Busy(FU) and not result(?D?);
not result(?D?)表示结果寄存器状态表中 D 的内容为零。
记分牌纪录操作：
Busy(FU)? yes
Op(FU)? Op
Fi(FU)D?
Fj(FU)S1?
Fk(FU)S2?
Qj? result(?S1?)
Qk? result(?S2?)
Rj? not Qj
Rk? not Qk
result(?D?)? FU
not Qj表示 Qj为零则 yes,Qj为非零则 no
(2)读操作数 RO
进入条件：
Rj? Rk ( Rj 和 Rk 同时为 Yes )
记分牌纪录操作：
Rj? no
Rk? no
Qj? 0
Qk? 0
(3)执行 EX
结束条件：
功能部件操作结束
(4)写结果 WR
进入条件：
f( ( Fj(f)? Fi(FU) or Rj(f) = no )
and ( Fk(f)? Fi(FU) or Rk(f) = no ) )
记分牌纪录操作：
f( if Qj(f) = FU then Rj(f)? yes );
f( if Qk(f) = FU then Rk(f)? yes );
result(Fi(FU)) = no
busy = no
性能 （ CDC 6600测试结果）
对 FORTRAN程序性能提高 1.7倍对汇编程序性能提高 2.5倍硬件并不太复杂，记分牌电路只相当于一个功能部件。
性能受限原因：
(1) 程序中可开发的并行性 （ 写后读 ）
(2) 记分牌容量
(3) 功能部件的数量和种类
(4) 反相关 (读后写 )和输出相关 (写后写 )
4.2.2 动态算法之二,Tomasulo算法
1,采用于 IBM 360/91浮点部件 (1967年 )；
2,将记分牌技术和寄存器重命名技术结合起来，更有效地解决 写后写,读后写 相关；
3,寄存器重命名技术使得在不改变指令系统前提下 实际寄存器数量得到增加。
开发这种技术的原因：
IBM 360/91一方面需要获得很高的浮点性能，一方面又希望整个 360系列只用一个指令系统和编译器
只能有四个浮点寄存器，指令和指令之间较易产生读后写、写后写相关
通过寄存器重命名技术增加实际的寄存器数量保留站
一旦浮点运算指令流出，进入保留站
保留站记录指令的操作，如果任何一个操作数就绪，
则将其值立即取入保留站，使得指令执行时无需再访问相应的寄存器 (解决了读后写 )
保留站中相关指令之间的数据传递直接进行 (不通过浮点寄存器 )，使得保留站中某些指令可以没有目的寄存器（ 减少了寄存器使用量? 增加了寄存器数量 ）
如果保留站中有两条指令的目的寄存器相同，则前面指令的目的寄存器会被删除 (解决了写后写 )
基本结构 (DLX)
三个 FP加法保留站可记录三条浮点加减法指令
两个 FP乘法保留站可记录两条浮点乘除法指令
六个取缓冲可记录六条读存储器指令
三个存缓冲可记录三条写存储器指令
（ 149页 图 4.5）
浮点运算指令留在保留站的原因是等待操作数的形成 (写后读 )或等待运算操作的完成访存指令留在存取缓冲的原因是等待访存操作的完成或等待存操作数的形成指令运行过程
(1)指令流出 (IS)：取一条浮点指令，如果有相应的空闲保留站就流出，如果操作数就绪 (在寄存器中 )就将值送入保留站；如果是访存指令，有空的缓冲则流出。否则等待。
解决了 结构相关 。
(2)执行 (EX)：如果操作数未就绪，监视公共数据总线等待结果 (某个操作完成后会以广播方式通知所有等待该结果的保留站 )，当两个操作数都就绪则开始运行。
解决了 写后读 相关。
(3)写结果 (WB)：结果计算完，写入公共数据总线，广播至所有等待该结果的保留站和目的寄存器 (如果存在 )。
数据结构
(1)指令状态表,表示正在执行的各指令处于三步中的哪一步。
(2)寄存器状态表,表示各寄存器分别是哪一个保留站的目的寄存器。
(3)保留站,一共有六个域
Busy,该保留站是否空闲
Op,对操作数 S1,S2的操作
Vj,Vk,操作数值
Qj,Qk,将产生操作数值的保留站号，为零表示操作数值已在 Vj,Vk中或不需要。
(4)取缓冲,一共有两个域
Busy,该保留站是否空闲
Address,地址值
(5)存缓冲,一共有四个域
Busy,该保留站是否空闲
Address,地址值
Vj,操作数值
Qj,将产生操作数值的保留站号，为零表示操作数值已在 Vj中。
例子：
LD F6,34(R2)
LD F2,45(R3)
MULD F0,F2,F4
SUBD F8,F6,F2
DIVD F10,F0,F6
ADDD F6,F8,F2
指令状态表指令
IS EX WB
L D F 6,3 4 ( R 2 )
L D F 2,4 5 ( R 3 )
MU L D F 0,F 2,F 4?
S U B D F 8,F 6,F 2?
D I V D F 1 0,F 0,F 6?
A D D D F 6,F 8,F 2? 功能部件状态表名称
B u s y Op Vi Vk Qj Qk
A D D 1 Y e s S U B D M E M [3 4 + R E G S [R 2 ]] L O A D 2
A D D 2 Y e s A D D D A D D 1 L O A D 2
A D D 3 No
M U L T 1 Y e s M U L T D R E G [ F 4 ] L O A D 2
M U L T 2 Y e s D I V D M E M [3 4 + R E G S [R 2 ]] M U L T 1
寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
Qi M U L T 1 L O A D 2 A D D 2 A D D 1 M U L T 2
取缓冲,取缓冲域 L O A D 1 L O A D 2 L O A D 3
A dd r es s R eg s [ R 3 ] + 34
bu s y No y es No
存缓冲：
存缓冲域 S T O R E 1 S T O R E 2 S T O R E 3
Vj
Qj
A dd r es s
bu s y No No No
例子,假设流水线延迟如下：加法 2 个时钟周期，乘法十个时钟周期，除法四十时钟周期，起始状态如上表，给出 MULD准备写结果之前的记分牌。
指令状态表指令
IS EX WB
L D F 6,3 4 ( R 2 )
L D F 2,4 5 ( R 3 )
MU L D F 0,F 2,F 4
S U B D F 8,F 6,F 2
D I V D F 1 0,F 0,F 6?
A D D D F 6,F 8,F 2
功能部件状态表名称
B u s y Op Vi Vk Qj Qk
A D D 1 No
A D D 2 No
A D D 3 No
M U L T 1 Y e s M U L T D M E M [4 5 + R E G S [R 3 ]] R E G [ F 4 ]
M U L T 2 Y e s D I V D M E M [3 4 + R E G S [R 2 ]] M U L T 1
寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
Qi M U L T 1 M U L T 2
(1)指令流出 IS
进入条件：
保留站或缓冲器有空闲记录内容：
if (reg[?S1?].Qi? 0)
{ RS[R].Qj? reg[?S1?].Qi }
else
{ RS[R].Vj? S1; RS[R].Qj? 0 } ;
if (reg[?S2?].Qi? 0)
{ RS[R].Qk? reg[?S2?].Qi }
else
{ RS[R].Vk? S2; RS[R].Qk? 0 } ;
RS[R].Busy? yes ;
reg[?D?].Qi? R ;
RS[R].Op? Op ;
(2)执行 EX
进入条件：
(RS[R].Qj = 0) and (RS[R].Qk = 0)
记录内容：
无 (操作数在 Vj和 Vk中 )
(3)写结果 WR
进入条件：
保留站 R执行结束，且公共数据总线可用记录内容：
x( if (reg[x].Qi = R )
{ Fx? result; reg[x].Qi? 0 } );
x( if (RS[x].Qj = R )
{ RS[x].Vj? result; RS[x].Qj? 0 } );
x( if (RS[x].Qk = R )
{ RS[x].Vk? result; RS[x].Qk? 0 } );
x( if (store[x].Qj = R )
{ store[x].V? result;
store[x].Qi? 0 } );
RS[R].Busy = no;
例子：
LOOP,LD F0,0(R1)
MULTD F4,F0,F2
SD 0(R1),F4
SUBI R1,R1,#8
BNEZ R1,LOOP
设连续两个循环的所有指令全都流出，但所有的浮点存取及浮点运算都没完成，给出状态表信息。
指令状态表指令 循环层数
IS EX WR
L D F 0,0( R 1) 1
MU L T D F 4,F 0,F 2 1?
SD 0( R 1),F 4 1?
L D F 0,0( R 1) 2
MU L T D F 4,F 0,F 2 2?
SD 0( R 1),F 4 2?
功能部件状态表名称
B u s y Op Vj Vk Qj Qk
A D D 1 No
A D D 2 No
A D D 3 No
M U L T 1 Y e s M U L T R E G S [ F 2] L O A D 1
M U L T 2 Y e s M U L T R E G S [ F 2] L O A D 2
寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
Qi L O A D 2 M U L T 2
取缓冲域 L O A D 1 L O A D 2 L O A D 3
A dd r es s R eg s [ R 1] R eg s [ R 1 ] - 8
bu s y y es y es No
存缓冲域 S T O R E 1 S T O R E 2 S T O R E 3
Vj
Qj M U L T 1 M U L T 2
A dd r es s R eg s [ R 1] R eg s [ R 1 ] - 8
bu s y y es y es No
注,这里 Regs[R1] 表示第一次循环前寄存器 R1
的值。
4.3 控制相关的动态解决技术上一章解决控制相关：
(1)“冻结,或,排空,流水线的方法
(2)“预测分支失败,的方法
(3)“预测分支成功,的方法
(4)“延迟分支,的方法
a)从前调度
b)从目标处调度
c)从失败处调度除了,延迟分支,方法的,从前调度,以外，性能的获得都是以预测成功为前提。
如果预测在编译时进行 （ 或固定 ）
----控制相关的静态解决技术执行时进行动态进行
----控制相关的动态解决技术
上一章的方法都是 静态解决技术。
4.3.1 减少分支延迟：分支预测缓冲技术基本思想,基于该分支指令的历史记录 ----根据该分支指令在最近一次或几次的运行情况 (分支成功或失败 )，
来预测该分支指令的本次运行情况 (分支成功或失败 )。
实现方法,建立一片缓冲区，记录各运行过的分支指令的运行情况 (分支成功或失败 )。
缓冲区如何寻址 ----根据分支指令地址的低位，究竟多少位取决于缓冲区大小。
缓冲区的内容 ----预测位，其长度 (多少位 )决定能记录该指令前多少次运行情况。
分支指令的执行过程：
(1)现场保留。
(2)按预测方向取后继指令。
(3)得到分支结果后如果预测成功，继续运行；
如果预测失败，恢复保留的现场，从分支处重新执行；
(4)修改预测位。
i - 1
分支指令
i
i + 1 i + 2
p + 2p + 1
得到分支结果
(1)预测位长度为 1
预测位内容,记录该指令最近一次分支是否成功,
如,1”表示分支成功,,0”表示分支失败。
预测方法,如果该指令最近一次分支成功则预测分支成功，反之则预测分支失败。
预测位修改,如果实际运行该指令发现分支成功，则置预测位为,1”，反之为,0”。
1 0
分支不成功分支成功分支不成功分支成功
(2)预测位长度为 n
预测位内容：为 0 到 2n-1 计数器，每次分支结果出来后，如 分支成功则加 1，分支失则减 1，计数器值增加到 2n-1 后不再增加，减小到 0 后不再减小。
预测方法,如果计数器值大于或等于最大值的一半 2n-1,预测分支成功，反之预测分支失败。
11 10
分支不成功分支成功分支不成功分支成功
01 00
分支不成功分支成功分支不成功分支成功分支预测成功分支预测不成功
N 为 2 时的预测位：
实际试验：
(1)预测位为 2 和预测位为 n 的预测性能差别不大。
(2)预测缓冲区大小增加到 4096 个记录项后预测性能不再明显增加 (只用取指令地址的低 12 位 )
(3)在预测位为 2,预测缓冲区为 4096 个记录项情况下，预测准确率为 82％?99％，即 预测失败率为
1％?18％。
起作用的前提：目标地址的计算要快于分支结果计算。
4.3.2 进一步减少分支延迟：分支目标缓冲分支指令无延迟的前提：
(1)分支预测成功
(2)分支预测和目标地址计算都在 IF 阶段就能完成。
基本思想,设立一个缓冲区 (称为 分支目标缓冲区,或
BTB )，其中存放最近一次运行时分支成功的分支指令的信息 (指令地址、分支目标 PC )，如果当前指令属于分支目标缓冲 (与其中某一条指令的地址相同 )，则确定该指令是分支指令，并预测分支成功，从分支目标缓冲直接获得目标 PC ；反之，则顺序取指令 (普通指令或预测分支失败的分支指令 )。
地址标示 分支目标 PC
当前 PC
查找、比较分支目标缓冲命中？ 认为本指令是分支指令并且分支成功，
以分支目标 PC 作为下一条指令地址
Y
N
认为本指令不是分支成功的分支指令，
按普通指令处理当前 PC 值访问指令存储器和查询 B T B
预测错误，清除取来的指令并从分支的另外一个目标取指令，删除
B T B 中对应项
Y e s No
B T B 中存在？
以 分支目标 PC 值 送 PC
成功分支指令？
当前分支成功？
预测成功，后继指令无延迟执行以当前 指令 PC
值 和 分支目标
PC 送入 B T B 中作为一个新项普通指令
No Y e s
No Y e s
取指令指令译码指令执行作为 下一条指令地址例,根据下面的假设计算分支目标缓冲的性能。
(1) 预测准确率 90％
(2) 缓冲区命中率 90％
(3) 假设分支转移成功的比例为 60％
指令在 B T B 中？ 预测结果 实际动作 延迟周期是 成功 成功 0
是 成功 不成功 2
不是 成功 2
解：一共分四种情况，
分支指令在 BTB 中？ 为成功分支指令？ 延迟周期是 (90 % ) 0
是 (90 % )
不是 (1 0%) 2
是 (60 % ) 2
不是 (1 0%)
不是 (4 0%) 0
分支延迟 =90％?10％?2 + 10％?60％?2
=0.18 + 0.12
=0.30 时钟周期地址标示 分支目标 PC
当前 PC
查找、比较分支目标缓冲命中？ 认为本指令是分支指令并且分支成功，
以分支目标 PC 作为下一条指令地址
Y
N
认为本指令不是分支成功的分支指令，
按普通指令处理分支目标指令优点,(1)可以有更多时间访问缓冲区 (使用更大缓冲区 )
(2)可以进行分支目的指令缓冲优化 ---实现无条件分支指令（甚至某些情况下的条件分支指令）的零周期。
如果分支指令的目的地址会变化,
如过程指针,CASE语句,RETURN语句等应采用预测非直接分支技术 (不在这里讨论 )。
4.3.3 基于硬件的推断执行分支预测方法进一步提高并行性的障碍：错误预测造成的状态改变。
保留站方法中，指令运行分 取指令、执行、写结果 三个阶段。写结果改变浮点寄存器的值 ----改变处理机状态。
推断执行,将写结果分成两步,写结果 和 确认 。
写结果：将结果写在一个缓冲器中，后继指令可以通过访问缓冲器使用该结果。
仅到达这一步的指令可任意删除而不会影响 机器的状态 (寄存器的值 )
确认,在延迟一定时间，按照指令的流出顺序对指令是否应该运行进行逐个确认，
指令得到确认后，才将结果从缓冲器写到寄存器。
这样，分支指令后流出的指令 (预测运行的指令 )只有等到分支指令被确认后才能被确认，如果分支指令确认时发现预测错误，后继指令可删除而不影响 机器的状态 (寄存器的值 )
异常处理变得容易。 虽然各指令的执行为并行和乱序进行的，但各指令的确认顺序严格按照指令的流出顺序进行，这使得机器的状态 (寄存器的值 )可以确定。
再定序缓冲器：存放推断执行过程中未被确认的指令的结果，有三个域，
(1)指令类型,分支指令、存存储器指令 (改变内存 )或寄存器指令 (改变寄存器 )
(2)目的地址,确认后将结果写到哪里
(3)值域,指令的结果
---对保留站结构的扩充，同时可取代保留站结构中的存、取缓冲。
---环形 FIFO结构。
执行步骤：
(1)指令流出,如果 有空的保留站 和 再定序缓冲,则从浮点指令队列中取一条指令。如果操作数在寄存器或再定序缓冲中，则送入保留站；更新缓冲器的控制域 (BUSY)
表示正在使用；该再定序缓冲的编号也要送入对应的保留站，以便保留站获得结果后知道写入哪个再定序缓冲中。
(2)执行,如果全部操作数有效，则开始执行，否则等待并检测 CDB。
(3)写结果,结果获得后写到 CDB,到达对应的 再定序缓冲 和 等待该结果的其他保留站 。也可以不使用 CDB，
等待该结果的其他保留站总是到再定序缓冲中获得结果。
(4)确认,当一条指令到达再定序缓冲出口时，
如果它不是分支指令,并且结果已获得 (否则等待 )，将结果写入目的地址 (寄存器或存储器 )，指令运行结束，
从再定序缓冲中清除；
如果该指令是分支指令,并且分支结果已获得 (否则等待 )，则根据分支结果决定从再定序缓冲中只清除该指令 (预测正确 )或所有指令 (预测错误，从正确入口重新运行 )。
例,设浮点功能单元的延迟为加法 2 个时钟周期，乘法 10 个时钟周期，除法 40 个时钟周期，给出下面的代码段当指令 MULTD要确认时的状态。
LD F6,34(R2)
LD F2,45(R3)
MULTD F0,F2,F4
SUBD F8,F6,F2
DIVD F10,F0,F6
ADDD F6,F8,F2
寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
Qi #3 #6 #4 #5
忙 y e s N o N o y e s y e s y e s No
再定序缓冲编号
B u s y 指令 状态 目的 值
1 No LD F 6,3 4 ( R 2 ) 确认 F6 M e m [ 3 4 + R e g s [ R 2 ] ]
2 No LD F 2,4 5 ( R 3 ) 确认 F2 M e m [ 4 5 + R e g s [ R 3 ] ]
3 Y e s M U L T D F 0,F 2,F 4 写结果 F0 #2? R e g s [ F 4 ]
4 Y e s S U B D F 8,F 6,F 2 写结果 F8 #1 - #2
5 Y e s D I V D F 1 0,F 0,F 6 执行 F 1 0
6 Y e s A D D D F 6,F 8,F 2 写结果 F6 # 4 + # 2
保留站状态名称
B us y Op Vi Vk Qj Qk 目的
A D D 1 No
A D D 2 No
A D D 3 No
M U L T 1 No M U L T D M E M [4 5 + R E G S [R 2] ] R E G [ F 4] #3
M U L T 2 Y e s D I V D M E M [3 4 + R E G S [R 2] ] #3 #5
技术的核心,动态预测 + 推断性执行 + 保留站技术优点,在不改变指令系统 (不改变编译器 )情况下大幅度提高流水线性能。
缺点,实现技术非常复杂。
应用,PowerPC 620,MIPS R10000,Intel P6,PII、
AMD K5,K6等。
结构相关
数据相关 (写后读 RAW,读后写 WAR,写后写 WAW)
控制相关
CPI流水线 = CPI理想 +停顿 结构相关 +停顿 写后读 +停顿 读后写
+停顿 写后写 +停顿 控制相关本章研究的内容,如何消除这些停顿,使得进入流水线的指令序列运行时能有更好的 并行性第四章 指令级并行
4.1 指令级并行的概念
2,本章所研究的提高指令级并行的技术
(1)循环展开,控制相关停顿
(2)基本流水线调度,数据写后读停顿
(3)指令动态调度,各种数据相关停顿
(4)分支预测,控制相关停顿
(5)推断,所有数据 /控制相关停顿
(6)多指令流出,提高理想 CPI
其他技术,如向量计算机 (不在本章讨论 )
研究范围,一个基本程序块,如一个循环体
3,本章主要针对 DLX浮点流水线来进行研究,并作如下的假设,
产生结果指令 使用结果指令 停顿周期数浮点计算 另外的浮点计算 3
浮点计算 浮点存操作 ( SD ) 2
浮点取操作 ( L D) 浮点计算 1
浮点取操作 ( L D) 浮点存操作 ( SD ) 0
而对 DLX整型流水线,除了分支指令有一个时钟周期延迟,其余指令没有延迟 （ 为方便起见 ） 。
4.1.1 循环展开调度的基本方法提高指令级并行的最基本方法,
(1)指令调度
(2)循环展开一般由编译器来完成。
指令调度,通过改变指令在程序中的位置，将相关指令之间的距离加大到不小于指令执行延迟的时钟数，使相关指令成为实际上的无关指令。
例,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
实际运行：
(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 个空转周期。
指令调度：
(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 )
事实上，循环控制所需要的指令数一般是恒定的，不会因每次循环所含的操作个数的多少而变化，但它所花费的时间显然与循环次数有关 ---通过增加每次循环完成的操作来降低循环次数，从而降低循环控制所花费的时间。
循环展开,通过多次复制循环体 (并改变循环结束条件 )
来减少循环控制对性能的影响 (循环控制指令以及控制相关引起的停顿 )。
循环展开 (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) 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) (空转 )
一共 27 个时钟周期，平均每次循环使用 27/4?6.7个周期。
循环展开 +指令调度 (循环展开调度 )：
(1) LOOP,LD F0,0(R1)
(2) LD F6,-8(R1)
(3) LD F10,-16(R1)
(4) LD F14,-24(R1)
(5) ADDD F4,F0,F2
(6) ADDD F8,F6,F2
(7) ADDD F12,F10,F2
(8) ADDD F16,F14,F2
(9) SD 0(R1),F4
(10) SD -8(R1),F8
(11) SD -16(R1),F12
(12) SUBI R1,R1,#32
(13) BNEZ R1,LOOP
(14) SD 8(R1),F16
一共 14 个时钟周期，平均每次循环使用 14/4?3.5个周期。所有“空转”消失，即数据相关和控制相关被消除，达到完全指令级并行。
结论,由编译器所完成的循环展开和指令调度 (静态调度 )，能有效提高指令级并行。
循环展开 +指令调度 要注意这几方面问题：
(1)正确性 (主要是循环控制和操作数偏移量修改 )
(2)有效性 (主要是不同循环次之间的无关性 )
(3)使用不同的寄存器 (避免冲突 )
(4)尽可能减少循环控制中的测试和分支
(5)注意对存储器数据的相关性分析
(6)注意新的相关性关键,要分析清指令之间存在怎样的相关性以及在这种相关性下指令应该如何被修改和调度。
4.1.2 相关性相关性指的是一条指令的运行如何依赖于另一条指令的运行 。
研究相关性,不但可作为是否可指令调度的依据,而且可了解程序固有的并行性以及可以获得的并行性 。
相关意味指令的运行,结果产生的顺序有要求,
意味指令的并行运行和改变顺序可能会产生问题,
不意味指令的流水线运行一定会产生停顿 。
相关类型数据相关 (data dependence)
名相关 (name dependence)
控制相关 (control dependence)
1,数据相关对指令 i和 j，如果
(1)指令 j使用指令 i产生的结果，或
(2)指令 j与指令 k数据相关，指令 k与指令 i数据相关 (传递性 )
例
LOOP,LD F0,0(R1) (1)
ADDD F4,F0,F2 (2)
SD 0(R1),F4 (3)
结论指令 (1)和指令 (2)数据相关，指令 (2)和指令 (3)
数据相关 =〉 指令 (1)和指令 (3)数据相关例
SUBI R1,R1,8 (4)
BNEZ R1,LOOP (5)
结论指令 (4)和指令 (5)数据相关 。
分析数据相关的主要工作：
(1)确定指令的相关性
(2)确定数据的计算顺序
(3)确定最大并行性数据相关是程序相关性中最本质的相关性之一。
2.名相关两条指令使用相同的寄存器或内存单元 (称为名 )，
但它们之间没有数据流。
指令 j和指令 i之间的名相关有以下两种：
(1)反相关,指令 i先执行，指令 j写的名是指令 i读的名 (读后写相关 )。
(2)输出相关,指令 i和指令 j写的是同一个寄存器或内存单元 (写后写相关 )。
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
......
3,控制相关分支指令引起的相关，如果一条指令是否执行的情况依赖于一条分支指令，则称它与该分支指令控制相关。
例
if p1 {
s1
};
if p2 {
s2
};
=>
s1控制相关于 p1,s2控制相关于 p2
s1与 p2,s2与 p1控制无关 。
基本处理原则
(1)与控制相关的指令不能移到分支指令之前；
(2)与控制无关的指令不能移到分支指令之后；
减少或消除控制相关的方法是减少或消除分支指令。
1,基本流水线的数据相关解决方法：
采用定向技术 （ 相关隐藏 ）
停顿
2,解决停顿的方法：
静态调度方法（编译器）
产生于 60年代，目前比较流行。
动态调度方法（处理器）
产生于更早时期,目前在一些 RISC机中仍在采用 。
4.2 指令的动态调度
3,动态调度的优点：
能处理某些在编译时无法知道的相关情况
能简化编译器的设计
使代码适合移植
4,动态调度的主要缺点：
硬件复杂度大
调度的范围比较小
4.2.1 动态调度的原理
1,基本流水线的最大问题是指令必须顺序流出,
例如：
DIVD F0,F2,F4
ADDD F10,F0,F8
SUBD F12,F8,F14
SUBD指令并不与前面指令数据相关，但仍需等待。
2.动态调度的解决方法：
(1)结构相关：设置多个功能部件或功能部件流水化
(2)数据相关：挂起停顿,后续指令全部被停顿挂起,后续指令仍可执行，被流出 (如果没有数据相关 )或也被挂起 (如果有数据相关 )
处理器中：
可以有多条指令同时被执行 (多个功能部件 )
可以有多条指令被挂起 (一旦解除数据相关则运行 )
指令运行乱序乱序带来的问题：异常处理比较复杂，难以确定和恢复现场。
3.指令译码阶段分成两个阶段：
流出 (Issue,IS):指令译码，检查结构相关 (停顿 )
读操作数 (Read Operands,RO):检查数据相关 (挂起 )
4.2.2 动态算法之一：记分牌
1,命名 (Scoreboard)起源于 CDC 6600
2,将管理由指令移向功能部件
3,采用尽可能多的功能部件
CDC 6600采用 16个功能部件,4个浮点部件,5个存储器访问部件,7个整数操作部件。
在 DLX中，用于浮点部件：一个浮点乘法器，一个浮点加法器，一个浮点除法器，一个整数部件。
4,指令运行过程
(1)指令流出 (IS),如果指令所需的功能部件空闲，
并且其他正在运行的指令与它不发生目的寄存器冲突，则记分牌将向该功能部件流出指令，功能部件被置成准备运行该指令状态 (纪录于记分牌 )
解决了结构相关和写后写相关。
(2)读操作数 (RO),如果前面已流出的正在运行的指令不对本指令的源操作数进行写操作，或者一个正在工作的功能部件已完成对该寄存器的写操作，
则进行读操作数，并完成该步骤 (离开挂起状态 )。
有可能有多个功能部件挂起在这一步。
解决写后读相关。
(3)执行 (EX),对浮点运算来讲，这一步可能要化多个时钟周期，由于功能部件独立，不会发生冲突。
(4)写结果 (WR),记分牌知道功能部件执行完成后，
检查目标寄存器，如果前面没有指令读该寄存器或已完成对该寄存器的读操作，则完成这一步骤，否则将该功能部件挂起在这一步。
有可能有多个功能部件挂起在这一步。
解决读后写相关。
5,例子：
LD F6,34(R2)
LD F2,45(R3)
MULD F0,F2,F4
SUBD F8,F6,F2
DIVD F10,F0,F6
ADDD F6,F8,F2
(1)指令状态表,表示正在执行的各指令处于四步中的哪一步。
(2)功能状态表,表示各功能部件的状态，每个功能部件一共有九个域：
Busy,该功能部件是否在工作 (被分配 )
Op,该功能部件当前操作
Fi,目的寄存器编号
Fj,Fk:源寄存器编号
Qj,Qk:向源寄存器写结果的功能部件
Rj,Rk:源寄存器是否 就绪并且还未被使用
Yes,就绪并且还没有被使用过
(后面指令不可改写它 )
No,(1)未就绪
(前面指令可改写它 )
(2)已被使用过
(后面指令可改写它 )
(3)结果寄存器状态表,表示每个寄存器是当前哪一个功能部件的目的寄存器 (不是则为零 )。
指令状态表指令
IS RO EX WR
L D F 6,34 ( R 2)
L D F 2,45 ( R 3)
M U L D F 0,F 2,F 4?
S U B D F 8,F 6,F 2?
D I V D F 10,F 0,F 6?
A D D D F 6,F 8,F 2
功能部件状态表部件
Busy Op Fi Fj Fk Qj Qk Rj Rk
整数 Y es LD F2 R3 No
乘法 Y es M U L D F0 F2 F4 整数 No Y es
加法 Y es SU B D F8 F6 F2 整数 Y es No
除法 y es D I V D F 10 F0 F6 乘法 No Y es
结果寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
部件 乘法 整数 加法 除法
5,例子,假设流水线延迟如下：加法 2 个时钟周期,
乘法十个时钟周期,除法四十时钟周期,起始状态如上表,分别给出 MULD和 DIVD准备写结果之前的记分牌 。
指令状态表指令
IS RO EX WR
L D F 6,34( R2)
L D F 2,45( R3)
MUL D F 0,F 2,F 4
SU B D F 8,F 6,F 2
D I V D F 10,F 0,F 6?
A D D D F 6,F 8,F 2
功能部件状态表部件
B us y Op Fi Fj Fk Qj Qk Rj Rk
整数 NO
乘法 Y es M U L D F0 F2 F4 No No
加法 Y es A D D D F6 F8 F2 No No
除法 y es D I V D F 10 F0 F6 乘法 No Y es
结果寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
部件 乘法 加法 除法指令状态表指令
IS RO EX WR
L D F 6,34(R2)
L D F 2,45(R3)
MUL D F 0,F 2,F 4
SU B D F 8,F 6,F 2
D I V D F 10,F 0,F 6
A D D D F 6,F 8,F 2
功能部件状态表部件
B usy Op Fi Fj Fk Qj Qk Rj Rk
整数 NO
乘法 No
加法 No
除法 y es D I V D F 10 F0 F6 No No
结果寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
部件 除法
6,执行过程：
FU,指令使用的功能部件
D,目的寄存器
S1,S2,源寄存器
Op,要进行的操作
Fj(FU),功能部件 FU的数据项 Fj
result(?D?),结果寄存器中对应于 D的内容 (
产生结果 D的功能部件名 )
Fj(FU)S1?,将寄存器 S1的名送入 Fj(FU)
(1)指令流出 IS
进入条件：
not Busy(FU) and not result(?D?);
not result(?D?)表示结果寄存器状态表中 D 的内容为空。
记分牌纪录操作：
Busy(FU)? yes
Op(FU)? Op
Fi(FU)D?
Fj(FU)S1?
Fk(FU)S2?
Qj? result(?S1?)
Qk? result(?S2?)
Rj? not Qj
Rk? not Qk
result(?D?)? FU
not Qj表示 Qj为零则 yes,反之则 no 。
(2)读操作数 RO
进入条件：
Rj? Rk
记分牌纪录操作：
Rj? no
Rk? no
Qj? 0
Qk? 0
(3)执行 EX
结束条件：
功能部件操作结束
(4)写结果 WR
进入条件：
f( ( Fj(f)? Fi(FU) or Rj(f) = no )
and ( Fk(f)? Fi(FU) or Rk(f) = no ) )
f的两种情况前面指令,Rj(f) = no 表示操作数已取走后面指令,Rj(f) = no 一定成立记分牌纪录操作：
f( if Qj(f) = FU then Rj(f)? yes );
f( if Qk(f) = FU then Rk(f)? yes );
result(Fi(FU)) = 0
busy(FU) = no
性能 （ CDC 6600测试结果）
对 FORTRAN程序性能提高 1.7倍对汇编程序性能提高 2.5倍硬件并不太复杂，记分牌电路只相当于一个功能部件。
性能受限原因：
(1) 程序中可开发的并行性
(2) 记分牌容量
(3) 功能部件的数量和种类
(4) 反相关 (读后写 )和输出相关 (写后写 )
记分牌 (复习 )
记分牌信息分为三部分：
(1)指令状态表：表示正在执行的各指令处于四步中的哪一步。
(2)功能状态表：表示各功能部件的状态，每个功能部件一共有九个域：
Busy,该功能部件是否在工作 (被分配 )
Op,该功能部件当前操作
Fi,目的寄存器编号
Fj,Fk:源寄存器编号
Qj,Qk:向源寄存器写结果的功能部件
（没有则零）
Rj,Rk:源寄存器是否 就绪并且还没有被使用过
Yes,就绪并且还没有被使用过
(后面指令不可改写它 )
No,(1)未就绪
(前面指令可改写它 )
(2)已被使用过
(后面指令可改写它 )
(3)结果寄存器状态表：表示每个寄存器是当前哪一个功能部件的目的寄存器 (否则为零 )。
(1)指令流出 IS
进入条件：
not Busy(FU) and not result(?D?);
not result(?D?)表示结果寄存器状态表中 D 的内容为零。
记分牌纪录操作：
Busy(FU)? yes
Op(FU)? Op
Fi(FU)D?
Fj(FU)S1?
Fk(FU)S2?
Qj? result(?S1?)
Qk? result(?S2?)
Rj? not Qj
Rk? not Qk
result(?D?)? FU
not Qj表示 Qj为零则 yes,Qj为非零则 no
(2)读操作数 RO
进入条件：
Rj? Rk ( Rj 和 Rk 同时为 Yes )
记分牌纪录操作：
Rj? no
Rk? no
Qj? 0
Qk? 0
(3)执行 EX
结束条件：
功能部件操作结束
(4)写结果 WR
进入条件：
f( ( Fj(f)? Fi(FU) or Rj(f) = no )
and ( Fk(f)? Fi(FU) or Rk(f) = no ) )
记分牌纪录操作：
f( if Qj(f) = FU then Rj(f)? yes );
f( if Qk(f) = FU then Rk(f)? yes );
result(Fi(FU)) = no
busy = no
性能 （ CDC 6600测试结果）
对 FORTRAN程序性能提高 1.7倍对汇编程序性能提高 2.5倍硬件并不太复杂，记分牌电路只相当于一个功能部件。
性能受限原因：
(1) 程序中可开发的并行性 （ 写后读 ）
(2) 记分牌容量
(3) 功能部件的数量和种类
(4) 反相关 (读后写 )和输出相关 (写后写 )
4.2.2 动态算法之二,Tomasulo算法
1,采用于 IBM 360/91浮点部件 (1967年 )；
2,将记分牌技术和寄存器重命名技术结合起来，更有效地解决 写后写,读后写 相关；
3,寄存器重命名技术使得在不改变指令系统前提下 实际寄存器数量得到增加。
开发这种技术的原因：
IBM 360/91一方面需要获得很高的浮点性能，一方面又希望整个 360系列只用一个指令系统和编译器
只能有四个浮点寄存器，指令和指令之间较易产生读后写、写后写相关
通过寄存器重命名技术增加实际的寄存器数量保留站
一旦浮点运算指令流出，进入保留站
保留站记录指令的操作，如果任何一个操作数就绪，
则将其值立即取入保留站，使得指令执行时无需再访问相应的寄存器 (解决了读后写 )
保留站中相关指令之间的数据传递直接进行 (不通过浮点寄存器 )，使得保留站中某些指令可以没有目的寄存器（ 减少了寄存器使用量? 增加了寄存器数量 ）
如果保留站中有两条指令的目的寄存器相同，则前面指令的目的寄存器会被删除 (解决了写后写 )
基本结构 (DLX)
三个 FP加法保留站可记录三条浮点加减法指令
两个 FP乘法保留站可记录两条浮点乘除法指令
六个取缓冲可记录六条读存储器指令
三个存缓冲可记录三条写存储器指令
（ 149页 图 4.5）
浮点运算指令留在保留站的原因是等待操作数的形成 (写后读 )或等待运算操作的完成访存指令留在存取缓冲的原因是等待访存操作的完成或等待存操作数的形成指令运行过程
(1)指令流出 (IS)：取一条浮点指令，如果有相应的空闲保留站就流出，如果操作数就绪 (在寄存器中 )就将值送入保留站；如果是访存指令，有空的缓冲则流出。否则等待。
解决了 结构相关 。
(2)执行 (EX)：如果操作数未就绪，监视公共数据总线等待结果 (某个操作完成后会以广播方式通知所有等待该结果的保留站 )，当两个操作数都就绪则开始运行。
解决了 写后读 相关。
(3)写结果 (WB)：结果计算完，写入公共数据总线，广播至所有等待该结果的保留站和目的寄存器 (如果存在 )。
数据结构
(1)指令状态表,表示正在执行的各指令处于三步中的哪一步。
(2)寄存器状态表,表示各寄存器分别是哪一个保留站的目的寄存器。
(3)保留站,一共有六个域
Busy,该保留站是否空闲
Op,对操作数 S1,S2的操作
Vj,Vk,操作数值
Qj,Qk,将产生操作数值的保留站号，为零表示操作数值已在 Vj,Vk中或不需要。
(4)取缓冲,一共有两个域
Busy,该保留站是否空闲
Address,地址值
(5)存缓冲,一共有四个域
Busy,该保留站是否空闲
Address,地址值
Vj,操作数值
Qj,将产生操作数值的保留站号，为零表示操作数值已在 Vj中。
例子：
LD F6,34(R2)
LD F2,45(R3)
MULD F0,F2,F4
SUBD F8,F6,F2
DIVD F10,F0,F6
ADDD F6,F8,F2
指令状态表指令
IS EX WB
L D F 6,3 4 ( R 2 )
L D F 2,4 5 ( R 3 )
MU L D F 0,F 2,F 4?
S U B D F 8,F 6,F 2?
D I V D F 1 0,F 0,F 6?
A D D D F 6,F 8,F 2? 功能部件状态表名称
B u s y Op Vi Vk Qj Qk
A D D 1 Y e s S U B D M E M [3 4 + R E G S [R 2 ]] L O A D 2
A D D 2 Y e s A D D D A D D 1 L O A D 2
A D D 3 No
M U L T 1 Y e s M U L T D R E G [ F 4 ] L O A D 2
M U L T 2 Y e s D I V D M E M [3 4 + R E G S [R 2 ]] M U L T 1
寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
Qi M U L T 1 L O A D 2 A D D 2 A D D 1 M U L T 2
取缓冲,取缓冲域 L O A D 1 L O A D 2 L O A D 3
A dd r es s R eg s [ R 3 ] + 34
bu s y No y es No
存缓冲：
存缓冲域 S T O R E 1 S T O R E 2 S T O R E 3
Vj
Qj
A dd r es s
bu s y No No No
例子,假设流水线延迟如下：加法 2 个时钟周期，乘法十个时钟周期，除法四十时钟周期，起始状态如上表，给出 MULD准备写结果之前的记分牌。
指令状态表指令
IS EX WB
L D F 6,3 4 ( R 2 )
L D F 2,4 5 ( R 3 )
MU L D F 0,F 2,F 4
S U B D F 8,F 6,F 2
D I V D F 1 0,F 0,F 6?
A D D D F 6,F 8,F 2
功能部件状态表名称
B u s y Op Vi Vk Qj Qk
A D D 1 No
A D D 2 No
A D D 3 No
M U L T 1 Y e s M U L T D M E M [4 5 + R E G S [R 3 ]] R E G [ F 4 ]
M U L T 2 Y e s D I V D M E M [3 4 + R E G S [R 2 ]] M U L T 1
寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
Qi M U L T 1 M U L T 2
(1)指令流出 IS
进入条件：
保留站或缓冲器有空闲记录内容：
if (reg[?S1?].Qi? 0)
{ RS[R].Qj? reg[?S1?].Qi }
else
{ RS[R].Vj? S1; RS[R].Qj? 0 } ;
if (reg[?S2?].Qi? 0)
{ RS[R].Qk? reg[?S2?].Qi }
else
{ RS[R].Vk? S2; RS[R].Qk? 0 } ;
RS[R].Busy? yes ;
reg[?D?].Qi? R ;
RS[R].Op? Op ;
(2)执行 EX
进入条件：
(RS[R].Qj = 0) and (RS[R].Qk = 0)
记录内容：
无 (操作数在 Vj和 Vk中 )
(3)写结果 WR
进入条件：
保留站 R执行结束，且公共数据总线可用记录内容：
x( if (reg[x].Qi = R )
{ Fx? result; reg[x].Qi? 0 } );
x( if (RS[x].Qj = R )
{ RS[x].Vj? result; RS[x].Qj? 0 } );
x( if (RS[x].Qk = R )
{ RS[x].Vk? result; RS[x].Qk? 0 } );
x( if (store[x].Qj = R )
{ store[x].V? result;
store[x].Qi? 0 } );
RS[R].Busy = no;
例子：
LOOP,LD F0,0(R1)
MULTD F4,F0,F2
SD 0(R1),F4
SUBI R1,R1,#8
BNEZ R1,LOOP
设连续两个循环的所有指令全都流出，但所有的浮点存取及浮点运算都没完成，给出状态表信息。
指令状态表指令 循环层数
IS EX WR
L D F 0,0( R 1) 1
MU L T D F 4,F 0,F 2 1?
SD 0( R 1),F 4 1?
L D F 0,0( R 1) 2
MU L T D F 4,F 0,F 2 2?
SD 0( R 1),F 4 2?
功能部件状态表名称
B u s y Op Vj Vk Qj Qk
A D D 1 No
A D D 2 No
A D D 3 No
M U L T 1 Y e s M U L T R E G S [ F 2] L O A D 1
M U L T 2 Y e s M U L T R E G S [ F 2] L O A D 2
寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
Qi L O A D 2 M U L T 2
取缓冲域 L O A D 1 L O A D 2 L O A D 3
A dd r es s R eg s [ R 1] R eg s [ R 1 ] - 8
bu s y y es y es No
存缓冲域 S T O R E 1 S T O R E 2 S T O R E 3
Vj
Qj M U L T 1 M U L T 2
A dd r es s R eg s [ R 1] R eg s [ R 1 ] - 8
bu s y y es y es No
注,这里 Regs[R1] 表示第一次循环前寄存器 R1
的值。
4.3 控制相关的动态解决技术上一章解决控制相关：
(1)“冻结,或,排空,流水线的方法
(2)“预测分支失败,的方法
(3)“预测分支成功,的方法
(4)“延迟分支,的方法
a)从前调度
b)从目标处调度
c)从失败处调度除了,延迟分支,方法的,从前调度,以外，性能的获得都是以预测成功为前提。
如果预测在编译时进行 （ 或固定 ）
----控制相关的静态解决技术执行时进行动态进行
----控制相关的动态解决技术
上一章的方法都是 静态解决技术。
4.3.1 减少分支延迟：分支预测缓冲技术基本思想,基于该分支指令的历史记录 ----根据该分支指令在最近一次或几次的运行情况 (分支成功或失败 )，
来预测该分支指令的本次运行情况 (分支成功或失败 )。
实现方法,建立一片缓冲区，记录各运行过的分支指令的运行情况 (分支成功或失败 )。
缓冲区如何寻址 ----根据分支指令地址的低位，究竟多少位取决于缓冲区大小。
缓冲区的内容 ----预测位，其长度 (多少位 )决定能记录该指令前多少次运行情况。
分支指令的执行过程：
(1)现场保留。
(2)按预测方向取后继指令。
(3)得到分支结果后如果预测成功，继续运行；
如果预测失败，恢复保留的现场，从分支处重新执行；
(4)修改预测位。
i - 1
分支指令
i
i + 1 i + 2
p + 2p + 1
得到分支结果
(1)预测位长度为 1
预测位内容,记录该指令最近一次分支是否成功,
如,1”表示分支成功,,0”表示分支失败。
预测方法,如果该指令最近一次分支成功则预测分支成功，反之则预测分支失败。
预测位修改,如果实际运行该指令发现分支成功，则置预测位为,1”，反之为,0”。
1 0
分支不成功分支成功分支不成功分支成功
(2)预测位长度为 n
预测位内容：为 0 到 2n-1 计数器，每次分支结果出来后，如 分支成功则加 1，分支失则减 1，计数器值增加到 2n-1 后不再增加，减小到 0 后不再减小。
预测方法,如果计数器值大于或等于最大值的一半 2n-1,预测分支成功，反之预测分支失败。
11 10
分支不成功分支成功分支不成功分支成功
01 00
分支不成功分支成功分支不成功分支成功分支预测成功分支预测不成功
N 为 2 时的预测位：
实际试验：
(1)预测位为 2 和预测位为 n 的预测性能差别不大。
(2)预测缓冲区大小增加到 4096 个记录项后预测性能不再明显增加 (只用取指令地址的低 12 位 )
(3)在预测位为 2,预测缓冲区为 4096 个记录项情况下，预测准确率为 82％?99％，即 预测失败率为
1％?18％。
起作用的前提：目标地址的计算要快于分支结果计算。
4.3.2 进一步减少分支延迟：分支目标缓冲分支指令无延迟的前提：
(1)分支预测成功
(2)分支预测和目标地址计算都在 IF 阶段就能完成。
基本思想,设立一个缓冲区 (称为 分支目标缓冲区,或
BTB )，其中存放最近一次运行时分支成功的分支指令的信息 (指令地址、分支目标 PC )，如果当前指令属于分支目标缓冲 (与其中某一条指令的地址相同 )，则确定该指令是分支指令，并预测分支成功，从分支目标缓冲直接获得目标 PC ；反之，则顺序取指令 (普通指令或预测分支失败的分支指令 )。
地址标示 分支目标 PC
当前 PC
查找、比较分支目标缓冲命中？ 认为本指令是分支指令并且分支成功，
以分支目标 PC 作为下一条指令地址
Y
N
认为本指令不是分支成功的分支指令，
按普通指令处理当前 PC 值访问指令存储器和查询 B T B
预测错误，清除取来的指令并从分支的另外一个目标取指令，删除
B T B 中对应项
Y e s No
B T B 中存在？
以 分支目标 PC 值 送 PC
成功分支指令？
当前分支成功？
预测成功，后继指令无延迟执行以当前 指令 PC
值 和 分支目标
PC 送入 B T B 中作为一个新项普通指令
No Y e s
No Y e s
取指令指令译码指令执行作为 下一条指令地址例,根据下面的假设计算分支目标缓冲的性能。
(1) 预测准确率 90％
(2) 缓冲区命中率 90％
(3) 假设分支转移成功的比例为 60％
指令在 B T B 中？ 预测结果 实际动作 延迟周期是 成功 成功 0
是 成功 不成功 2
不是 成功 2
解：一共分四种情况，
分支指令在 BTB 中？ 为成功分支指令？ 延迟周期是 (90 % ) 0
是 (90 % )
不是 (1 0%) 2
是 (60 % ) 2
不是 (1 0%)
不是 (4 0%) 0
分支延迟 =90％?10％?2 + 10％?60％?2
=0.18 + 0.12
=0.30 时钟周期地址标示 分支目标 PC
当前 PC
查找、比较分支目标缓冲命中？ 认为本指令是分支指令并且分支成功，
以分支目标 PC 作为下一条指令地址
Y
N
认为本指令不是分支成功的分支指令，
按普通指令处理分支目标指令优点,(1)可以有更多时间访问缓冲区 (使用更大缓冲区 )
(2)可以进行分支目的指令缓冲优化 ---实现无条件分支指令（甚至某些情况下的条件分支指令）的零周期。
如果分支指令的目的地址会变化,
如过程指针,CASE语句,RETURN语句等应采用预测非直接分支技术 (不在这里讨论 )。
4.3.3 基于硬件的推断执行分支预测方法进一步提高并行性的障碍：错误预测造成的状态改变。
保留站方法中，指令运行分 取指令、执行、写结果 三个阶段。写结果改变浮点寄存器的值 ----改变处理机状态。
推断执行,将写结果分成两步,写结果 和 确认 。
写结果：将结果写在一个缓冲器中，后继指令可以通过访问缓冲器使用该结果。
仅到达这一步的指令可任意删除而不会影响 机器的状态 (寄存器的值 )
确认,在延迟一定时间，按照指令的流出顺序对指令是否应该运行进行逐个确认，
指令得到确认后，才将结果从缓冲器写到寄存器。
这样，分支指令后流出的指令 (预测运行的指令 )只有等到分支指令被确认后才能被确认，如果分支指令确认时发现预测错误，后继指令可删除而不影响 机器的状态 (寄存器的值 )
异常处理变得容易。 虽然各指令的执行为并行和乱序进行的，但各指令的确认顺序严格按照指令的流出顺序进行，这使得机器的状态 (寄存器的值 )可以确定。
再定序缓冲器：存放推断执行过程中未被确认的指令的结果，有三个域，
(1)指令类型,分支指令、存存储器指令 (改变内存 )或寄存器指令 (改变寄存器 )
(2)目的地址,确认后将结果写到哪里
(3)值域,指令的结果
---对保留站结构的扩充，同时可取代保留站结构中的存、取缓冲。
---环形 FIFO结构。
执行步骤：
(1)指令流出,如果 有空的保留站 和 再定序缓冲,则从浮点指令队列中取一条指令。如果操作数在寄存器或再定序缓冲中，则送入保留站；更新缓冲器的控制域 (BUSY)
表示正在使用；该再定序缓冲的编号也要送入对应的保留站，以便保留站获得结果后知道写入哪个再定序缓冲中。
(2)执行,如果全部操作数有效，则开始执行，否则等待并检测 CDB。
(3)写结果,结果获得后写到 CDB,到达对应的 再定序缓冲 和 等待该结果的其他保留站 。也可以不使用 CDB，
等待该结果的其他保留站总是到再定序缓冲中获得结果。
(4)确认,当一条指令到达再定序缓冲出口时，
如果它不是分支指令,并且结果已获得 (否则等待 )，将结果写入目的地址 (寄存器或存储器 )，指令运行结束，
从再定序缓冲中清除；
如果该指令是分支指令,并且分支结果已获得 (否则等待 )，则根据分支结果决定从再定序缓冲中只清除该指令 (预测正确 )或所有指令 (预测错误，从正确入口重新运行 )。
例,设浮点功能单元的延迟为加法 2 个时钟周期，乘法 10 个时钟周期，除法 40 个时钟周期，给出下面的代码段当指令 MULTD要确认时的状态。
LD F6,34(R2)
LD F2,45(R3)
MULTD F0,F2,F4
SUBD F8,F6,F2
DIVD F10,F0,F6
ADDD F6,F8,F2
寄存器状态表
F0 F2 F4 F6 F8 F 1 0 …… F 3 0
Qi #3 #6 #4 #5
忙 y e s N o N o y e s y e s y e s No
再定序缓冲编号
B u s y 指令 状态 目的 值
1 No LD F 6,3 4 ( R 2 ) 确认 F6 M e m [ 3 4 + R e g s [ R 2 ] ]
2 No LD F 2,4 5 ( R 3 ) 确认 F2 M e m [ 4 5 + R e g s [ R 3 ] ]
3 Y e s M U L T D F 0,F 2,F 4 写结果 F0 #2? R e g s [ F 4 ]
4 Y e s S U B D F 8,F 6,F 2 写结果 F8 #1 - #2
5 Y e s D I V D F 1 0,F 0,F 6 执行 F 1 0
6 Y e s A D D D F 6,F 8,F 2 写结果 F6 # 4 + # 2
保留站状态名称
B us y Op Vi Vk Qj Qk 目的
A D D 1 No
A D D 2 No
A D D 3 No
M U L T 1 No M U L T D M E M [4 5 + R E G S [R 2] ] R E G [ F 4] #3
M U L T 2 Y e s D I V D M E M [3 4 + R E G S [R 2] ] #3 #5
技术的核心,动态预测 + 推断性执行 + 保留站技术优点,在不改变指令系统 (不改变编译器 )情况下大幅度提高流水线性能。
缺点,实现技术非常复杂。
应用,PowerPC 620,MIPS R10000,Intel P6,PII、
AMD K5,K6等。
