关于流水线CPU
并行性概念
1．并行性的含义
同时性——指两个或者两个以上事件在同一时刻发生。
并发性——指两个或者两个以上事件在同一时间间隔内发生。
流水CPU
并行性概念
2．并行处理技术的主要形式
（1） 时间并行— 时间重叠
让多个处理过程在时间上相互错开，轮流重叠地使用
同一套硬件的各个部分，从而赢得高速度。
实现方式：采用流水处理部件。
（2）空间并行—— 资源重复
例：奔腾CPU采用的超标量流水技术。
用多个相同部件处理多个事件。
实现方式：多处理器系统和多计算机系统或单处理器系统。
(3) 时间并行+空间并行
既采用时间并行性又采用空间并行性。
流水线计算机的系统组成
现代流水线计算机系统组成原理如左图所示。其中CPU按流水线方式组织，通常由三部分组成：指令部件、指令队列、执行部件。这三个功能部件可以组成一个3级流水线。
图 流水线计算机系统组成原理示意图
流水线CPU的结构
指令流水线原理
问题的提出
串行执行方式存在部件利用率不高（有闲置时间）的问题。
CPU周期
使用部件
闲置部件
取指令
PC，MS，IR等
ALU，GRS
取数
MS
PC，ALU，GRS
执行
ALU，GRS
PC，MS
每个过程段所用的部件不同
在某个过程段时，其他过程段的部件处于空闲
（2）流水线工作原理
① 指令周期的三个主要过程：
图 指令周期的三个过程段
取数
取指
执行
入
出
② 指令执行过程的时空图
a．非流水线时空图
I1
I1
I1
I2
I2
I2
I3
I3
I3
I1
I2
I3
空间S
时间T
执行
取数
取指
（a）非流水线时空图
b．标量流水线时空图
I1
I1
I1
I2
I2
I2
I3
I3
I3
I4
I4
I4
I1
I2
I3
空间S
时间T
执行
取数
取指
（b）标量流水线时空图
I4
图 非流水线与流水线对比
c. 超标量流水线时空图
I1
I3
I5
I2
I4
I6
I1
I3
I5
I7
I2
I4
I6
I8
I1
I3
I5
I7
I9
I2
I4
I6
I8
I10
I1
I2
I3 I4 I5 I6
执行
取数
取指
空间S
时间T
（C）超标量流水线时空图
流水线 vs 非流水线
① 非流水线指令的执行是串行的；
② 标量流水线从满载起，每经1个周期做完一条指令；
③ 超标量流水线，提高了吞吐量，但需二套（或二
套以上）流水线的硬件及其他电路。（见附图）
常见的超标量流水线结构
（3）流水线工作方式的特点
① 具有时间的并行性；
② 流水线分工越细，可同时运行的指令越多，
吞吐率就越高。 但需增加硬件，控制更复杂；
③ 流水线每个阶段的执行时间应尽量一致；
④ 流水线充满（满载）时达到最大的吞吐率。
流水线相关问题
流水线相关：是指邻近指令之间由于某种关系，出现了不能同时被流水操作的现象。
流水线的相关会造成流水线的断流，影响整个流水线的效率。
造成流水线相关的原因
资源相关
数据相关
变址转移
中断
全局性相关
局部性相关
局部性相关：资源相关
在同一机器时钟周期内争用同一个功能部件所发生的冲突。
时钟
指令
1
2
3
4
5
I1
取指
译码
取数
执行
I2
取指
译码
取数
执行
I3
取指
译码
取数
在时钟3发生争用内存的问题—资源相关。
解决方法：
① 将取指操作推迟一个时钟进行；
② 增设一个存储器，将指令和数据分开存放；
③ 采用双端口存储器。
局部性相关：数据相关
在程序中，一条指令的执行需等前一条指令执行完后才能进行，则有数据相关。
例：
取数
译码
取指
ADD
执行
取数
译码
取指
SUB
4
3
2
1
时钟
指令
解决方法：
① 推迟ADD指令的取数操作；
② 采用数据旁路（内部向
前）技术，直接把结果
送给下一条指令。
全局性相关：控制相关
由条件转移指令或中断引起的。
解决方法：
① 延迟转移法：加入空操作，等待转移条件形成。
② 猜测法：选择出现概率较高的分支进行指令预取。
【例4】 流水线中有三类数据相关冲突：
写后读相关；读后写相关；写后写相关。
判断以下三组指令各存在哪种类型的数据相关。
(1) I1: ADD R1，R2，R3 ； (R2) + (R3)->R1
I2: SUB R4，R1，R5 ； (R1) - (R5)->R4
(2) I3: STA M(x)，R3 ； R3)->M(x)，M(x)是存储器单元 I4: ADD R3，R4，R5 ； (R4)+(R5)->R3
(3) I5: MUL R3，R1，R2 ； (R1)×(R2)->R3
I6: ADD R3，R4，R5 ； (R4) + (R5)->R3
(1) I1: ADD R1，R2，R3 ； (R2) + (R3)->R1
I2: SUB R4，R1，R5 ； (R1) - (R5)->R4
第(1)组指令中，I1指令运算结果应先写入R1，然后在I2指令中读出R1内容。由于I2指令进入流水线，变成I2指令在I1指令写入R1前就读出R1内容，发生RAW（写后读）相关。
局部性相关：数据相关
(2) I3: STA M(x)，R3 ；（R3)->M(x)，M(x)是存储器单元
I4: ADD R3，R4，R5 ； (R4)+(R5)->R3
第(2)组指令中，I3指令应先读出R3内容并存入存储单元M(x)，然后在I4指令中将运算结果写入R3。但由于I4指令进入流水线，变成I4指令在I3指令读出R3内容前就写入R3，发生WAR（读后写）相关。
局部性相关：数据相关
(3) I5: MUL R3，R1，R2 ； (R1)×(R2)->R3
I6: ADD R3，R4，R5 ； (R4) + (R5)->R3
第(3)组指令中，如果I6指令的加法运算完成时间早于I5指令的乘法运算时间，变成指令I6在指令I5写入R3前就写入R3，导致R3的内容错误，发生WAW(写后写）相关 。
局部性相关：数据相关
局部性相关的处理方法
指令调度法
设置多个功能部件
内部数据定向
静态调度
动态调度
（1）指令调度法
指令调度
改变指令的执行顺序以解决相关性带来的问题
静态指令调度
改变程序中指令的位置
由编译程序实现
动态指令调度
改变指令的实际执行顺序
不改变取指令和指令译码的顺序
无序执行
由控制器硬件实现
计分牌法
保存站法
静态调度：流水线延迟
X=Y+Z
A=BC
指令发射：启动指令去处理器功能单元执行的过程
静态调度：编译检测
编译器优化后，所需时间为17个时钟周期
动态调度-计分牌法
计分牌是一个位向量、每一位对应寄存器堆中的一个寄存器。
指令发射时，目的寄存器在计分牌中相应位 置1；
写回后，目的寄存器在计分牌中相应位 清0。
判断指令可否发射的条件是：
该指令所有目的寄存器及源寄存器在计分牌中对应位都为0 ；否则等待上述位清除。
解决数据相关采用定向传送技术：
将前面指令执行的结果直接送给后面指令所需此源操作数的功能部件
动态调度-计分牌法
动态调度-计分牌法
动态调度-计分牌法
依靠流水线停顿来解决相关性
没有消除数据相关
集中式调度
记分牌部件是性能瓶颈
记分牌的缺点
动态调度-保存站法
动态调度-保存站法
发射
如果有空的保存站，就发射指令；
只要操作数有效，就将其取到保存站，避免指令发射时才到寄存器中取数据的情况.
如果没有空的保存站或缓存部件，则指令暂等
执行
一条指令发射时，存放操作数的寄存器名被换成为对应于该寄存器的保存站名称（寄存器重命名）
写结果
结果写回时通过数据总线直接送到等待此结果的所有保存站
动态调度-保存站法
具有分布的阻塞检测机制；
消除了数据写后写和先读后写相关导致的阻塞
保存站法的优点(相对记分牌法)
动态调度-保存站法
保存站法又称作 Tomasulo调度法
（2）设置多个功能部件
流水线的瓶颈会在某一个流水线段产生；
这种瓶颈段一定对应于预约表中符号最多的那一行；
可设置几个相同的段来解决该段的瓶颈问题。
例：
（2）设置多个功能部件
（3）内部数据定向
内部数据定向的原则：是要消除一些不必要的访存储器或访寄存器的中间环节，从而减少资源和数据的相关性，以提高流水线的吞吐率。
数据定向分成：写－读定向、读－读定向、写－写定向。
（3）内部数据定向
可减少或者消除数据相关性带来的影响
Data forwarding
IF
Id
Ex
M
W
（3）内部数据定向
2. 全局性相关：变址转移
全局性相关由转移指令引起；
当指令流足够长时，转移引起的流水线性能将会下降46％左右。
解决方法：
延迟转移法
转移预测法
1）延迟转移法
延迟转移法：目的是转移成功时，转移指令后面进入流水线的指令不作废，想办法使之有用，以减少延迟时间的损失。
…
I0 LD R4, B
I1 LD R1， A
I2 DEC R3， 1
I3 JZ R3，I50
I4 ADD R2，R4
I5 SUB R5，R6
…
I50 …
…
I2 DEC R3， 1
I3 JZ R3，I50
I0 LD R4, B
I1 LD R1， A
I4 ADD R2，R4
I5 SUB R5，R6
…
I50 …
例：
…
I0 LD R4, B
I1 LD R1， A
I2 DEC R3， 1
I3 JZ R3，I50
I4 ADD R2，R4
I5 SUB R5，R6
I6 LD B, R5
…
I50 …
1）延迟转移法
转移延迟槽：
将转移指令的执行在流水线中提前进行
1）延迟转移法
2）转移预测法
转移预测法：在程序执行以前，就静态地根据转移代码的类型或动态地根据转移历史表来预测下一次转移是否会成功。
得到的预测值都是试探性的值，不能把结果作为最后结果。
根据运行结果，如果预测正确，把试探性结果上的试探标记去掉，成为正式结果。
如果不正确，则要清除试探性结果。
利用预取缓冲器进行转移预测
预取缓冲器有三种类型：
顺序缓冲器：顺序流入流水线的指令。
目标缓冲器：从转移目标开始取出的指令。
循环缓冲器：保存了一个小循环的顺序指令。
顺序缓冲器和目标缓冲器在条件转移指令到来之前，就按预测策略装满各自的指令。在转移条件被检测出之后，选取两个缓冲器中的一个缓冲器的指令流进入流水线，而另一个缓冲器中的指令流被作废。
按原程序顺序，经顺序缓冲器一方把指令流装入流水线。
预测正确的话，取消试探标志，结果存入用户寄存器或存储器，报废掉目标缓冲器中指令。
如果预测错误，重新从目标缓冲器装入指令到流水线。
转移预测策略
分支预测执行不成功和重新执行过程
转移预测策略
分支预测branch prediction
静态
永远不转移
永远转移
后向转移
动态
1位
2位
多位（1级，2级）
1位动态分支预测
根据上次转移情况预测下次情况
2位动态分支预测
根据上两次转移情况预测下次分支
预测状态机
00: strongly not taken
01: weakly not taken
10: weakly taken
11: strongly taken
例
设某转移指令在每次执行过程的转移序列如下，T表示转移发生，N表示转移未发生：
T, T, T, N, T, T, N, T, N, N, T, N, N,
试分析在每次对该指令进行预测的状态和预测的成功率。假设：
1）采用1位动态预测，预测器初始状态为T；
2）采用2位动态预测，预测器初始状态为11。
解答
（1）每次对指令进行预测时的状态和结果如下
预测成功6次，成功率为。
事件序列
T
T
T
N
T
T
N
T
N
N
T
N
N
预测器状态
T
T
T
T
N
T
T
N
T
N
N
T
N
准确性
Y
Y
Y
Y
Y
Y
解答
（2）每次对指令进行预测时的状态和结果如下
预测成功8次，成功率为。
事件序列
T
T
T
N
T
T
N
T
N
N
T
N
N
预测器状态
11
11
11
11
10
11
11
10
11
10
00
01
00
预测结果
T
T
T
T
T
T
T
T
T
T
N
N
N
准确性
Y
Y
Y
Y
Y
Y
Y
Y
3. 全局性相关：中断
中断也会引起转移；
中断一般是不可预测的；
中断处理目的不是如何缩短断流时间，而是如何处理好断点现场和中断后的恢复问题。
中断的处理（1）
不精确断点法：不论在哪条指令的哪一段发生了中断申请，都不再允许当时还未进入流水线的后继指令再进入，但已在流水线中的指令可流动到执行完为止，然后再转入中断处理程序。
例：输入输出设备申请的中断
中断的处理（2）
精确断点法：是指采用后援寄存器来保存进入流水线的各指令的现场状态。所以不管在进入流水线的指令的任何段发生中断申请，断点都是精确的。
例：执行错误的中断
4. 超标量流水线
超标量流水线
标量流水线：在每个时钟周期只发射一条指令，并要求每个时钟周期只从流水线流出一条指令的结果。
超标量流水线：是指在每个时钟周期向流水线发射多条指令，并能从流水线流出多个结果。
例：三发射超标量流水线
超标量流水线会因数据相关、资源冲突、转移指令、循环及中断等造成流水线的断流；
断流延迟时间与超标量流水线的调度方法有关 ；
调度方法有：
按序发射按序完成
按序发射无序完成
无序发射无序完成
超标量流水线的调度方法
有序执行 vs 无序执行
无序执行
后续指令比前面的指令先开始进入执行阶段
后续指令比前面的指令先执行完成
真相关的指令停顿
继续读取操作数
没有改变取指和译码的顺序
有序执行
有序开始执行
有序执行完成
EX
EX
例：
I1 R1 M（A）
I2 R2（R1）＋（R2）
I3 R3（R3）＋（R4）
I4 R4（R4）×（R5）
I5 R6
I6 R6（R6）×（R7）
超标量流水线的调度方法
超标量流水线的调度方法
按序发射按序完成
I1 R1 M（A）
I2 R2（R1）＋（R2）
I3 R3（R3）＋（R4）
I4 R4（R4）×（R5）
I5 R6
I6 R6（R6）×（R7）
按序发射无序完成
I1 R1 M（A）
I2 R2（R1）＋（R2）
I3 R3（R3）＋（R4）
I4 R4（R4）×（R5）
I5 R6
I6 R6（R6）×（R7）
无序发射无序完成
I1 R1 M（A）
I2 R2（R1）＋（R2）
I3 R3（R3）＋（R4）
I4 R4（R4）×（R5）
I5 R6
I6 R6（R6）×（R7）
超标量流水线的调度方法
无序执行机制
指令预取
功能部件之间可无序执行
功能部件之内有序执行
可以提高程序执行速度
5.超流水线技术
超流水线：把一般完成一条指令的流水线段再细分成更多的流水线段。这样原时钟周期的几分之一的时间间隔就可以发射一条指令，并从流水线流出一个结果。
超流水线超标量处理技术
同时使用超流水线和超标量技术。
超标量的度为3，超流水线的度为3，超流水线超标量的度为9。
动态多重指令启动
性能分析
设有N条不相关的指令通过流水线，流水线的基准段为S，超流水线的度为n，超标量流水线的度为m，则基准标量机、超流水线机、超标量机的所需处理时间（基本时钟周期）分别为：
流水线加速比
1. 超流水线对基准标量流水线：
2.超标量流水线对基准标量流水线：
3.超流水线超标量流水线对基准标量流水线：
多重指令启动的局限性
流水线中功能部件之间的不平衡性
一个时钟周期中启动的多条指令可能资源冲突
每个循环迭代中的开销
一般存在数据相关性
循环体的数据相关性
需要大量相关性检测逻辑
控制相关性
缩短了转移指令的间距
多重启动的相关性检测逻辑
n重启动的指令流水线需要比较操作的数量：
2(n-1) + 2(n-2) + … + 21 = n2 – n
[例6] 超标度为2的超标量流水线结构模型如图(a)所示。它分为4个段，即取指(F)段、 译码(D)段、执行(E)段和写回(W)段。F，D，W 段只需1个时钟周期完成。E段有多个功能部件，其中LOAD/STORE部件完成数据cache访问，只需一个时钟周期；加法器完成需2个时钟周期，乘法器需3个时钟周期，它们都已流水化。F段和D段要求成对输入。E段有内部数据定向传送，结果生成即可使用。
现有如下6条指令序列：
I1 LAD R1，A ；M(A)→R1，M(A)是存储器单元I2 ADD R2，R1 ；(R2) + (R1)->R2
I3 ADD R3，R4 ；(R3) + (R4)->R3
I4 MUL R4，R5 ；(R4)×(R5)->R4
I5 LAD R6，B ；M(B)→R6，M(B)是存储器单元
I6 MUL R6，R7 ；(R6)×(R7) → R6
其中 I1，I2有RAW相关，
I3，I4有WAR相关，
I5，I6有WAW相关和RAW相关。
请画出：(1)按序发射按序完成各段推进情况图；
(2)按序发射按序完成的流水线时空图。
I1 LAD R1，A ；M(A)→R1，M(A)是存储器单元
I2 ADD R2，R1 ；(R2) + (R1)->R2
由于I1，I2间有RAW相关，I2要推迟一个时钟才能发射。
I3 ADD R3，R4 ；(R3) + (R4)->R3
I4 MUL R4，R5 ；(R4)×(R5)->R4
I3，I4之间有WAR相关，但按序发射，即使I3，I4并行操作，也不会导致错误。
I5 LAD R6，B ；M(B)→R6，M(B)是存储器单元
I6 MUL R6，R7 ；(R6)×(R7) → R6
I5，I6间还有WAW相关，只要I6的完成放在I5之后，就不会出错。I6要推迟一个时钟才能发射。
解：
译码段
执行段
写回段
时钟
2
3
4
5
6
7
8
9
10
注意：I5实际上已在时钟6执行完毕，但一直推迟到时钟9
才写回，这是为了保持按序完成。超标量流水线完
成6条指令的执行任务总共需要10个时钟周期。
在一台计算机中，指令的执行分为取指IF、译码ID、执行EX和写回WB四个阶段，每个阶段在一个时钟周期只能接受一个新任务，取指阶段和译码阶段不受指令类型或相关性的影响。在执行阶段中有乘法器和加法器等运算功能部件，乘法器是一个六级流水部件，加法器是一个两级流水部件，运算功能部件的输出可通过结果总线直接送入所有运算功能部件的输入端。对于以下指令序列：
mult r3, r1, r4 /* s1 */
add r4, r1, r5 /* s2 */
mult r6, r4, r8 /* s3 */
画出以下情况下指令执行的时空图并指出所需的执行时间：
(1) 无序执行无序写回
(2) 有序执行有序写回
(3) 无序执行有序提交
第五章: 典型习题与解答
解答
(1) 指令执行的时空图：
共需12周期
S1
IF
ID
EX
EX
EX
EX
EX
EX
WB
S2
IF
ID
EX
EX
WB
S3
IF
ID
-
EX
EX
EX
EX
EX
EX
WB
解：
(2) 指令执行的时空图：
共需16周期
解：
(3) 指令执行的时空图：
共需12周期
第五章: 典型习题与解答
