第3章流水线技术

1、1 1/163/163第3章 流水线技术张晨曦张晨曦 刘依刘依www.A微信公众号： arch3652 2/163/1633.1流水线的基本概念3.2流水线的性能指标3.3流水线的相关与冲突 3.4流水线的实现3.5向量处理机3 3/163/1631. 工业生产流水线 下面通过一个例子来说明流水线的好处:两种方案两种方案的工作过程对比流水线生产过程的抽象描述这种流水工作方式的主要特点3.1 流水线的基本概念3.1.1 什么是流水线4 4/163/1633.1 流水线的基本概念 流水线技术把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各

2、功能段，这样，每个子过程就可以与其他的子过程并行进行。 流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。5 5/163/1633.1 流水线的基本概念 指令流水线把指令的解释过程分解为分析和执行两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。理想情况：速度提高一倍4段指令流水线 取取指指令令 译译 码码 执执 行行 存存结结果果 入入 出出 6 6/163/1633.1 流水线的基本概念 浮点加法流水线把流水线技术应用于运算的执行过程，就形成了 运算操作流水线，也称为部件级流水线。把浮点加法的全过程分解为求阶差、对阶

3、、尾数 相加、规格化4个子过程。 理想情况：速度提高3倍 求求阶阶差差 对对 阶阶 尾尾数数相相加加 规规格格化化 t t t t 入入 出出 时空图时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。 4段指令流水线的时空图 取取指指令令 译译 码码 执执 行行 存存结结果果 空空间间 时时间间 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 5 6 6 （单单位位： t） 0 1 2 3 4 5 6 7 8 9 8 8/163/1633.1 流水线的基本概念 流水技术的特点流水线把一个处理过程分解为若

4、干个子过程（段），每个子过程由一个专门的功能部件来实现。流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。 时间长的段将成为时间长的段将成为流水线的瓶颈。流水线的瓶颈。流水线每一个功能部件的后面都要有一个缓冲寄存器（锁存器），称为流水寄存器。q作用：作用：在相邻的两段之间传送数据，以保证提供后在相邻的两段之间传送数据，以保证提供后 面要用到的数据，并把各段的处理工作相互隔离。面要用到的数据，并把各段的处理工作相互隔离。9 9/163/1633.1 流水线的基本概念流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。 流水线需要有通过时间和排空时间。

5、q通过时间：通过时间：第一个任务从进入流水线到流出结果第一个任务从进入流水线到流出结果 所需的时间。所需的时间。q排空时间：排空时间：最后一个任务从进入流水线到流出结最后一个任务从进入流水线到流出结 果所需的时间。果所需的时间。1010/163/1633.1 流水线的基本概念 从不同的角度和观点，把流水线分成多种不同的种类。1. 单功能流水线与多功能流水线 （按照流水线所完成的功能来分类）（按照流水线所完成的功能来分类）单功能流水线：只能完成一种固定功能的流水线。多功能流水线：流水线的各段可以进行不同的 连接，以实现不同的功能。例：例： ASCASC的多功能流水线的多功能流水线3.1.2 流水

6、线的分类 求求 阶阶 差差 对对 阶阶 相相 加加 规规格格化化 相相 乘乘 累累 加加 输输 出出 1 2 3 4 6 5 7 8 输输 入入 输输 入入 相相 加加 规规格格化化 输输 出出 输输 出出 累累 加加 相相 乘乘 输输 入入 求求 阶阶 差差 对对 阶阶 2 3 4 5 6 7 8 6 7 8 （b）浮浮点点连连接接 （a）分分段段 （c）定定乘乘连连接接 1 1 2 3 4 5 1212/163/1633.1 流水线的基本概念 静态流水线与动态流水线（按照同一时间内各段之间的连接方式对多功能流水线做（按照同一时间内各段之间的连接方式对多功能流水线做进一步的分类）进一步的分类

7、）静态流水线：在同一时间内，多功能流水线中的 各段只能按同一种功能的连接方式工作。q对于静态流水线来说，只有当输入的是一串相同的对于静态流水线来说，只有当输入的是一串相同的 运算任务时，流水的效率才能得到充分的发挥。运算任务时，流水的效率才能得到充分的发挥。例如：例如：ASCASC的的8 8段流水线段流水线1313/163/1633.1 流水线的基本概念动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。 动画q优点优点 灵活，能够提高流水线各段的使用率，从而灵活，能够提高流水线各段的使用率，从而 提高处理速度。提高处理速度。q缺点缺点 控制复杂。控制复杂。

8、静、动态流水线时空图的对比1515/163/1633.1 流水线的基本概念 部件级、处理机级及处理机间流水线（按照流水的级别来进行分类）（按照流水的级别来进行分类）部件级流水线（运算操作流水线）：把处理机的算术逻辑运算部件分段，使得各种类型的运算操作能够按流水方式进行。处理机级流水线（指令流水线）：把指令的解释执行过程按照流水方式处理。把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。 例如：前面的例如：前面的4 4段段指令流水线指令流水线1616/163/1633.1 流水线的基本概念处理机间流水线（宏流水线）：它是由两个或者 两个以上的处理机串行连接起来，对同一数据

9、流 进行处理，每个处理机完成整个任务中的一部 分。 动画解析 数据流数据流 处理机处理机 1 处理机处理机 2 处理机处理机 n 存储器存储器 存储器存储器 存储器存储器 任务任务 1 任务任务 2 任务任务 n 1717/163/1633.1 流水线的基本概念 线性流水线与非线性流水线（按照流水线中是否有反馈回路来进行分类）（按照流水线中是否有反馈回路来进行分类）线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。非线性流水线：流水线中除了有串行的连接外，还有反馈回路。 （举例）非线性流水线的调度问题q确定什么时候向流水线引进新的任务，才能使该任

10、务不确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突会与先前进入流水线的任务发生冲突争用流水段。争用流水段。 1818/163/1633.1 流水线的基本概念1919/163/1633.1 流水线的基本概念 顺序流水线与乱序流水线（根据任务流入和流出的顺序是否相同来进行分类（根据任务流入和流出的顺序是否相同来进行分类）顺序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序完全相同。每一个任务在流 水线的各段中是一个跟着一个顺序流动的。乱序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序可以不同，允许后进入流水 线的任务先完成（从输出端流出）。

11、也称为无序流水线、错序流水线、异步流水线也称为无序流水线、错序流水线、异步流水线2020/163/1633.1 流水线的基本概念 标量处理机与向量流水处理机 把指令执行部件中采用了流水线的处理机称为流 水线处理机。标量处理机：处理机不具有向量数据表示和向量 指令，仅对标量数据进行流水处理。向量流水处理机：具有向量数据表示和向量指令 的处理机。 向量数据表示和流水技术的结合。向量数据表示和流水技术的结合。2121/163/163 吞吐率：在单位时间内流水线所完成的任务数量或输 出结果的数量。3.2 流水线的性能指标3.2.1 吞吐率KTnTP n：任务数Tk：处理完成n个任务所用的时间2222/

12、163/1633.2 流水线的性能指标1. 各段时间均相等的流水线各段时间均相等的流水线时空图 S1 S2 S3 S4 空间空间 时间时间 1 （单位：单位：t） 1 1 1 2 2 2 2 3 3 3 3 n-1 n-1 n-1 n-1 n n n n kt (n-1)t Tk 2323/163/1633.2 流水线的性能指标流水线完成n个连续任务所需要的总时间为（假设一条（假设一条k k段段线性流水线）线性流水线）Tkkt(n-1)t(kn-1)t 流水线的实际吞吐率tnknTP) 1(ttnknTPn11limmax最大吞吐率2424/163/1633.2 流水线的性能指标最大吞吐率与实

13、际吞吐率的关系 max1TPnknTPq流水线的实际吞吐率小于最大吞吐率，它除了与每流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数个段的时间有关外，还与流水线的段数k k以及输入到以及输入到流水线中的任务数流水线中的任务数n n等有关。等有关。q只有当只有当n nk k时，才有时，才有TPTPTPTPmaxmax。 2525/163/1633.2 流水线的性能指标 各段时间不完全相等的流水线 各段时间不等的流水线及其时空图 举例（时空图）q一条一条4 4段段的流水线的流水线qS1S1，S3S3，S4S4各段的时间：各段的时间：t tqS2S2的时间：的时间：33

14、t t （瓶颈段）瓶颈段）流水线中这种时间最长的段称为流水线的瓶颈段。 2626/163/1633.2 流水线的性能指标2727/163/1633.2 流水线的性能指标各段时间不等的流水线的实际吞吐率：（ t ti i为第为第i i段的时间，共有段的时间，共有k k个段个段 ）kikitttntnTP121),max() 1(流水线的最大吞吐率为),max(121maxktttTP2828/163/1633.2 流水线的性能指标 例如：一条4段的流水线中，S1，S2，S4各段的时间都是t，唯有S3的时间是3t。 S1 S3 S2 S4 入入 出出 t t 3t t 最大吞吐率为tTP31max

15、2929/163/1633.2 流水线的性能指标 解决流水线瓶颈问题的常用方法 举例细分瓶颈段 例如：例如：对前面的对前面的4 4段段流水线流水线把瓶颈段把瓶颈段S S3 3细分为细分为3 3个子流水线段：个子流水线段：S S3a3a，S S3b3b，S S3c3c S1 S2 入入 出出 S4 t t t t t t S3a S3c S3b 改进后的流水线的吞吐率改进后的流水线的吞吐率 ：tTP1max3030/163/1633.2 流水线的性能指标重复设置瓶颈段q举例：举例：时空图时空图q缺点：缺点：控制逻辑比较复杂，所需的硬件增加了。控制逻辑比较复杂，所需的硬件增加了。例如：例如：对前面

16、的对前面的4 4段流水线段流水线 重复设置瓶颈段重复设置瓶颈段S S3 3：S S3a3a，S S3b3b，S S3c3c S1 S3a S2 S3b 入入 出出 S3c S4 t t t 3t 3131/163/1633.2 流水线的性能指标 段段 S3b S3a S2 S3c S4 时时间间 S1 1 6 2 3 4 5 7 1 2 3 4 5 6 7 8 9 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 重复设置瓶颈段后的时空图重复设置瓶颈段后的时空图3232/163/1633.2 流水线的性能指标加速比：完成同样一批任务，不使用流水线所用的时间 与使用

17、流水线所用的时间之比。假设：不使用流水线（即顺序执行）所用的间假设：不使用流水线（即顺序执行）所用的间为为T Ts s，使用流水线后所用的时间为，使用流水线后所用的时间为T Tk k，则该流，则该流水线的加速比为水线的加速比为3.2.2 加速比ksTTS 3333/163/1633.2 流水线的性能指标1. 流水线各段时间相等（都是t）一条k段流水线完成n个连续任务 所需要的时间为所需要的时间为 Tk = (kn-1)t顺序执行n个任务 所需要的时间：所需要的时间： Ts= nkt （解释）解释）流水线的实际加速比为1nknkS3434/163/1633.2 流水线的性能指标最大加速比knkn

18、kSn1limmax当当n nk k时，时，S S k k思考：思考：流水线的段数愈多愈好？流水线的段数愈多愈好？ 3535/163/1633.2 流水线的性能指标 流水线的各段时间不完全相等时一条k段流水线完成n个连续任务的实际加速比为kikikiitttnttnS1211),max() 1(3636/163/1633.2 流水线的性能指标效率：流水线中的设备实际使用时间与整个运行时间 的比值，即流水线设备的利用率。 由于流水线有通过时间和排空时间，所以在连续由于流水线有通过时间和排空时间，所以在连续完成完成n n个个任务的时间内，各段并不是满负荷地工作。任务的时间内，各段并不是满负荷地工作

19、。1. 各段时间相等各段的效率ei相同 3.2.3 效率3737/163/163 S1 S2 S3 S4 空间空间 时间时间 1 （单位：单位：t） 1 1 1 2 2 2 2 3 3 3 3 n-1 n-1 n-1 n-1 n n n n kt (n-1)t Tk 121nknTtneeekk3.2 流水线的性能指标3838/163/1633.2 流水线的性能指标整条流水线的效率为kkkTtknkkekeeeE1211nknE11limmaxnknEn 可以写成 最高效率为 当当n nk k时，时，E E11。 3939/163/1633.2 流水线的性能指标当流水线各段时间相等时，流水线的

20、效率与吞吐率 成正比。 E=TPt 流水线的效率是流水线的实际加速比S与它的最大加速 比k的比值。 kSE 当当E E=1=1时，时，S S= =k k，实际加速比达到最大。，实际加速比达到最大。4040/163/1633.2 流水线的性能指标 从时空图上看，效率就是n个任务占用的时空面积和 k个段总的时空面积之比。个段总的时空区区个任务实际占用的时空knE kikikiitttntktnE1211),max() 1(当各段时间不相等时 举例4141/163/163 S1 S2 S3 S4 空间空间 时间时间 1 （单位：单位：t） 1 1 1 2 2 2 2 3 3 3 3 n-1 n-1

21、n-1 n-1 n n n n kt (n-1)t Tk 3.2 流水线的性能指标4242/163/1633.2 流水线的性能指标 例例3.13.1 设在下图所示的静态流水线上计算：设在下图所示的静态流水线上计算： 流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，试计算其吞吐率、加速比和效率。试计算其吞吐率、加速比和效率。3.2.4 流水线的性能分析举例)(41iiiBA 1 2 3 4 5 乘法乘法 加减法加减法 6 7 8 ( (每段的时间都为每段的时间都为t t) )4343/163/1633.2 流水线的性能指标解解：

22、（1 1）选择适合于流水线工作的算法选择适合于流水线工作的算法q先计算先计算A A1 1+ +B B1 1、A A2 2+ +B B2 2、A A3 3+ +B B3 3和和A A4 4+ +B B4 4；q再计算再计算( (A A1 1+ +B B1 1) )( (A A2 2+ +B B2 2) )和和( (A A3 3+ +B B3 3) )( (A A4 4+ +B B4 4) )；q然后求总的乘积结果。然后求总的乘积结果。（2 2）画出时空图）画出时空图 4444/163/1633.2 流水线的性能指标 时间 段 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 9

23、 10 11 12 13 14 15 16 17 18 输 入 A1 B1 A2 B2 A3 B3 A4 B4 A B C D A B C D AB CD AB CD ABCD A=A1+B1 B=A2+B2 C=A3+B3 D=A4+B4 tTP18721836ttS25. 01884364E4545/163/1633.2 流水线的性能指标p在在1818个个t t时间中，给出了时间中，给出了7 7个个结果。吞吐率为：结果。吞吐率为： tTP187p 不用流水线，由于一次求和需不用流水线，由于一次求和需6 6t t，一次求积需一次求积需4 4t t， 则产生上述则产生上述7 7个结果共需个结果

24、共需（4 46+36+34 4）t t = 36 = 36t t 加速比为加速比为（3 3）计算性能）计算性能21836ttS4646/163/1633.2 流水线的性能指标p 流水线的效率流水线的效率 25. 01884364E可以看出，在求解此问题时，该流水线的效率不高。 4747/163/1633.2 流水线的性能指标主要原因q多功能流水线在做某一种运算时，总有一些段是空多功能流水线在做某一种运算时，总有一些段是空闲的。闲的。q静态流水线在进行功能切换时，要等前一种运算全静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算。部流出流水线后才能进行后面的运算。q运算

25、之间存在关联，后面有些运算要用到前面运算运算之间存在关联，后面有些运算要用到前面运算的结果。的结果。q流水线的工作过程有建立与排空部分。流水线的工作过程有建立与排空部分。 4848/163/1633.2 流水线的性能指标 例例3.2 3.2 有一条动态多功能流水线由有一条动态多功能流水线由5 5段组成，加法用段组成，加法用1 1、3 3、4 4、5 5段，乘法用段，乘法用1 1、2 2、5 5段，第段，第2 2段的时间为段的时间为2 2t t，其余各段时间，其余各段时间均为均为t t，而且流水线的输出可以直接返回输入端或暂存于相应，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。

26、若在该流水线上计算的流水寄存器中。若在该流水线上计算: : 试计算其吞吐率、加速比和效率。试计算其吞吐率、加速比和效率。)(41iiiBA 1 2 3 4 5 乘乘法法 加加法法 t 2t t t t 4949/163/1633.2 流水线的性能指标解解: : (1) (1) 选择适合于流水线工作的算法选择适合于流水线工作的算法p应先计算应先计算A A1 1B B1 1、A A2 2B B2 2、A A3 3B B3 3和和A A4 4B B4 4；p再计算再计算( (A A1 1B B1)1)( (A A2 2B B2)2) ( (A A3 3B B3)3)( (A A4 4B B4)4)；

27、p然后求总的累加结果。然后求总的累加结果。(2) (2) 画出时空图画出时空图(3) (3) 计算性能计算性能5050/163/1633.2 流水线的性能指标 时间 段 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 输 入 A1 B1 A2 B2 A3 B3 A4 B4 A B C D A B C D AB CD AB CD ABCD A=A1B1 B=A2B2 C=A3B3 D=A4B4 18 56. 11828ttStTP18731. 01854344E5151/163/1633.2 流水线的性能指标1. 瓶颈问题理想情况下，流

28、水线在工作时，其中的任务是同步地每一个时钟周期往前流动一段。当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间。在设计流水线时，要尽可能使各段时间相等。2. 流水线的额外开销p流水寄存器延迟流水寄存器延迟p时钟偏移开销时钟偏移开销3.2.5 流水线设计中的若干问题5252/163/1633.2 流水线的性能指标流水寄存器需要建立时间和传输延迟q建立时间：建立时间：在触发写操作的时钟信号到达之前，寄在触发写操作的时钟信号到达之前，寄 存器输入必须保持稳定的时间。存器输入必须保持稳定的时间。q传输延迟：传输延迟：时钟信号到达后到寄存器输出可用的时时钟信号到达后到寄存器输出可用的时 间。间。

29、时钟偏移开销q流水线中，时钟到达各流水寄存器的最大差值时间。流水线中，时钟到达各流水寄存器的最大差值时间。（时钟到达各流水寄存器的时间不是完全相同）（时钟到达各流水寄存器的时间不是完全相同）5353/163/1633.2 流水线的性能指标几个问题q流水线并不能减少（而且一般是增加）单条指令的流水线并不能减少（而且一般是增加）单条指令的执行时间，但却能提高吞吐率。执行时间，但却能提高吞吐率。q增加流水线的深度（段数）可以提高流水线的性能。增加流水线的深度（段数）可以提高流水线的性能。q流水线的深度受限于流水线的额外开销。流水线的深度受限于流水线的额外开销。q当时钟周期小到与额外开销相同时，流水已

30、没意义。当时钟周期小到与额外开销相同时，流水已没意义。因为这时在每一个时钟周期中已没有时间来做有用因为这时在每一个时钟周期中已没有时间来做有用的工作。的工作。 冲突问题 流水线设计中要解决的重要问题之一。 5454/163/163介绍一个经典的5段RISC流水线 首先讨论在非流水情况下是如何实现的1. 一条指令的执行过程分为以下5个周期：取指令周期（IF）qIR MemPC IR MemPC 。qPCPC值加值加4 4。（假设每条指令占。（假设每条指令占4 4个字节）个字节） 3.3 流水线的相关与冲突3.3.1 一个经典的5段流水线5555/163/1633.3 流水线的相关与冲突指令译码/

31、读寄存器周期（ID）q译码。译码。q用用IRIR中的寄存器编号去访问通用寄存器组，读出所需中的寄存器编号去访问通用寄存器组，读出所需的操作数。的操作数。执行/有效地址计算周期（EX） 不同指令所进行的操作不同：q存储器访问指令：存储器访问指令：ALUALU把所指定的寄存器的内容与偏把所指定的寄存器的内容与偏 移量相加，形成用于访存的有效地址。移量相加，形成用于访存的有效地址。q寄存器寄存器寄存器寄存器ALUALU指令：指令：ALUALU按照操作码指定的操按照操作码指定的操 作对从通用寄存器组中读取的数据进行运算。作对从通用寄存器组中读取的数据进行运算。5656/163/1633.3 流水线的相

32、关与冲突q寄存器立即数寄存器立即数ALUALU指令：指令：ALUALU按照操作码指定的操按照操作码指定的操 作对从通用寄存器组中读取的第一操作数和立即数作对从通用寄存器组中读取的第一操作数和立即数 进行运算。进行运算。q分支指令：分支指令：ALUALU把偏移量与把偏移量与PCPC值相加，形成转移目标值相加，形成转移目标 的地址。同时，对在前一个周期读出的操作数进行的地址。同时，对在前一个周期读出的操作数进行 判断，确定分支是否成功。判断，确定分支是否成功。存储器访问分支完成周期（MEM） 该周期处理的指令只有load、store和分支指令。 其他类型的指令在此周期不做任何操作。5757/163

33、/1633.3 流水线的相关与冲突qloadload和和storestore指令指令loadload指令：指令：用上一个周期计算出的有效地址从存储器中用上一个周期计算出的有效地址从存储器中 读出相应的数据。读出相应的数据。storestore指令：指令：把指定的数据写入这个有效地址所指出的存把指定的数据写入这个有效地址所指出的存 储器单元。储器单元。q分支指令分支指令 分支分支“成功成功”，就把转移目标地址送入，就把转移目标地址送入PCPC。 分支指令执行完成。分支指令执行完成。5858/163/1633.3 流水线的相关与冲突写回周期（WB） ALU运算指令和load指令在这个周期把结果数据

34、写入通用寄存器组。 ALUALU运算指令：运算指令：结果数据来自结果数据来自ALUALU。 loadload指令：指令：结果数据来自存储器系统。结果数据来自存储器系统。 在这个实现方案中：p分支指令需要分支指令需要4 4个时钟个时钟周期（如果把分支指令的执行周期（如果把分支指令的执行 提前到提前到IDID周期，则只需要周期，则只需要2 2个个周期）。周期）。pstorestore指令需要指令需要4 4个个周期。周期。p其他指令需要其他指令需要5 5个个周期才能完成。周期才能完成。 将上述实现方案修改为流水线实现一个经典的5段流水线 q每一个周期作为一个流水段。每一个周期作为一个流水段。q在各段

35、之间加上锁存器（流水寄存器）。在各段之间加上锁存器（流水寄存器）。 6060/163/1633.3 流水线的相关与冲突5段流水线的两种描述方式q第一种描述（类似于时空图）第一种描述（类似于时空图）第二种描述（按时间错开的数据通路序列）6262/163/163 采用流水线方式实现时，应解决以下几个问题：要保证不会在同一时钟周期要求同一个功能段做 两件不同的工作。例如，不能要求例如，不能要求ALUALU同时做有效地址计算和算术运算。同时做有效地址计算和算术运算。避免IF段的访存（取指令）与MEM段的访存（读/写数据）发生冲突。q可以采用分离的指令存储器和数据存储器；可以采用分离的指令存储器和数据存

36、储器；q一般采用分离的指令一般采用分离的指令CacheCache和数据和数据CacheCache。ID段和WB段都要访问同一寄存器文件。 IDID段：读段：读WBWB段：写段：写3.3 流水线的相关与冲突6363/163/1633.3 流水线的相关与冲突如何解决对同一寄存器的访问冲突？如何解决对同一寄存器的访问冲突？ 把写操作安排在时钟周期的前半拍完成，把读操作把写操作安排在时钟周期的前半拍完成，把读操作安排在后半拍完成。安排在后半拍完成。考虑PC的问题q流水线为了能够每个时钟周期启动一条新的指令，流水线为了能够每个时钟周期启动一条新的指令，就必须在每个时钟周期进行就必须在每个时钟周期进行PC

37、PC值的加值的加4 4操作，并保留操作，并保留新的新的PCPC值。这种操作值。这种操作必须在必须在IFIF段完成，段完成，以便为取下以便为取下一条指令做好准备。一条指令做好准备。 （需设置一个专门的加法器）（需设置一个专门的加法器）q但分支指令也可能改变但分支指令也可能改变P PC C的值，而且是在的值，而且是在MEMMEM段段进行，进行，这会导致冲突。这会导致冲突。请考虑一下，如何处理分支指令？请考虑一下，如何处理分支指令？6464/163/1633.3 流水线的相关与冲突相关：两条指令之间存在某种依赖关系。 如果两条指令相关，则它们就有可能不能在流如果两条指令相关，则它们就有可能不能在流水

38、线中重叠执行或者只能部分重叠执行。水线中重叠执行或者只能部分重叠执行。相关有3种类型q数据相关（也称真数据相关）数据相关（也称真数据相关）q名相关名相关q控制相关控制相关3.3.2 相关与流水线冲突1. 相关6565/163/1633.3 流水线的相关与冲突（1）数据相关 对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。 q指令指令j j使用指令使用指令i i产生的结果；产生的结果；q指令指令j j与指令与指令k k数据相关，而指令数据相关，而指令k k又与指令又与指令i i数据相关。数据相关。数据相关具有传递性。 数据相关反映了数据的流动关系

39、，即如何从其产 生者流动到其消费者。 6666/163/1633.3 流水线的相关与冲突 例如：例如：下面这一段代码存在数据相关。下面这一段代码存在数据相关。LoopLoop： L.D L.D F0F0，0 0（R1R1）/ F0/ F0为数组元素为数组元素 ADD.D ADD.D F4F4，F0F0，F2F2/ / 加上加上F2F2中的值中的值 S.D S.D F4F4，0 0（R1R1）/ / 保存结果保存结果 DADDIU DADDIU R1R1，R1R1，8 8/ / 数组指针递减数组指针递减8 8个字节个字节 BNE BNE R1R1，R2R2，LoopLoop/ / 如果如果R1R

40、2R1R2，则分支，则分支 6767/163/1633.3 流水线的相关与冲突当数据的流动是经过寄存器时，相关的检测比较 直观和容易。当数据的流动是经过存储器时，检测比较复杂。q相同形式的地址其有效地址未必相同。相同形式的地址其有效地址未必相同。q形式不同的地址其有效地址却可能相同。形式不同的地址其有效地址却可能相同。（2）名相关名：指令所访问的寄存器或存储器单元的名称。如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。6868/163/1633.3 流水线的相关与冲突指令j与指令i之间的名相关有两种：q反相关：反相关：如果指令如果指令j j写的名与指令写的名与指

41、令i i读的名相同，则读的名相同，则 称指令称指令i i和和j j发生了反相关。发生了反相关。 指令指令j j写的名指令写的名指令i i读的名读的名q输出相关：输出相关：如果指令如果指令j j和指令和指令i i写相同的名，则称指写相同的名，则称指 令令i i和和j j发生了输出相关。发生了输出相关。 指令指令j j写的名指令写的名指令i i写的名写的名6969/163/1633.3 流水线的相关与冲突名相关的两条指令之间并没有数据的传送。如果一条指令中的名改变了，并不影响另外一条指令的执行。换名技术q换名技术：换名技术：通过改变指令中操作数的名来消除名相关。通过改变指令中操作数的名来消除名相关

42、。q对于寄存器操作数进行换名称为对于寄存器操作数进行换名称为寄存器换名。寄存器换名。既可以用编译器静态实现，也可以用硬件动态完成。既可以用编译器静态实现，也可以用硬件动态完成。7070/163/1633.3 流水线的相关与冲突例如：例如：考虑下述代码：考虑下述代码： DIV.DDIV.DF2F2，F6F6，F4F4 ADD.D ADD.DF6F6，F0F0，F12F12 SUB.D SUB.DF8F8，F6F6，F14F14 DIV.DDIV.D和和ADD.DADD.D存在反相关。存在反相关。 进行寄存器换名（进行寄存器换名（F6F6换成换成S S）后，变成：）后，变成： DIV.DDIV.D

43、F2F2，F6F6，F4F4 ADD.D ADD.DS S，F0F0，F12F12 SUB.D SUB.DF8F8，S S，F14 F14 7171/163/1633.3流水线的相关与冲突（3）控制相关 控制相关是指由分支指令引起的相关。q为了保证程序应有的执行顺序，必须严格按控制相为了保证程序应有的执行顺序，必须严格按控制相 关确定的顺序执行。关确定的顺序执行。典型的程序结构是“if-then”结构。请看一个示例：if p1 if p1 S1 S1； ；S S；if p2 if p2 S2 S2； ；7272/163/1633.3 流水线的相关与冲突控制相关带来了以下两个限制：q与一条分支指

44、令控制相关的指令不能被移到该分支与一条分支指令控制相关的指令不能被移到该分支 之前，否则这些指令就不受该分支控制了。之前，否则这些指令就不受该分支控制了。 对于上述的例子，对于上述的例子，thenthen 部分中的指令不能移到部分中的指令不能移到ifif语语句之前。句之前。 q如果一条指令与某分支指令不存在控制相关，就不如果一条指令与某分支指令不存在控制相关，就不 能把该指令移到该分支之后。能把该指令移到该分支之后。对于上述的例子，不能把对于上述的例子，不能把S S移到移到ifif语句的语句的thenthen部分中。部分中。7373/163/1633.3 流水线的相关与冲突 流水线冲突是指对于

45、具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。 流水线冲突有3种类型：q结构冲突：结构冲突：因硬件资源满足不了指令重叠执行的要因硬件资源满足不了指令重叠执行的要 求而发生的冲突。求而发生的冲突。q数据冲突：数据冲突：当指令在流水线中重叠执行时，因需要当指令在流水线中重叠执行时，因需要 用到前面指令的执行结果而发生的冲突。用到前面指令的执行结果而发生的冲突。q控制冲突：控制冲突：流水线遇到分支指令和其他会改变流水线遇到分支指令和其他会改变PCPC值值 的指令所引起的冲突。的指令所引起的冲突。2.流水线冲突7474/163/1633.3 流水线的相关与冲突带来

46、的几个问题：导致错误的执行结果。流水线可能会出现停顿，从而降低流水线的效率 和实际的加速比。我们约定 当一条指令被暂停时，在该暂停指令之后流出的所当一条指令被暂停时，在该暂停指令之后流出的所有指令都要被暂停，而在该暂停指令之前流出的指令则有指令都要被暂停，而在该暂停指令之前流出的指令则继续进行（否则就永远无法消除冲突）。继续进行（否则就永远无法消除冲突）。7575/163/1633.3 流水线的相关与冲突（1）结构冲突在流水线处理机中，为了能够使各种组合的指令 都能顺利地重叠执行，需要对功能部件进行流水 或重复设置资源。如果某种指令组合因为资源冲突而不能正常执 行，则称该处理机有结构冲突。常见

47、的导致结构相关的原因：q功能部件不是完全流水功能部件不是完全流水q资源份数不够资源份数不够7676/163/1633.3 流水线的相关与冲突结构冲突举例：访存冲突 有些流水线处理机只有一个存储器，将数据和指令放在一起，访存指令会导致访存冲突。q解决办法解决办法：插入暂停周期插入暂停周期 （“流水线气泡流水线气泡”或或“气泡气泡”） 引入暂停后的时空图引入暂停后的时空图q解决方法解决方法： 设置相互独立的指令存储器和数据存储器设置相互独立的指令存储器和数据存储器 或设置相互独立的指令或设置相互独立的指令CacheCache和数据和数据CacheCache。7777/163/1633.3 流水线的

48、相关与冲突由于访问同一个存储器而引起的结构冲突由于访问同一个存储器而引起的结构冲突 7878/163/1633.3 流水线的相关与冲突 时间（时钟周期）时间（时钟周期） 1 2 3 4 5 6 M Reg ALU M Reg M Reg ALU M Reg M Reg ALU M Reg 7 8 load 指令指令 i+1 指令指令 i+2 暂暂 停停 M Reg ALU M 指令指令 i+3 气泡气泡 气泡气泡 气泡气泡 气泡气泡 气泡气泡 为消除结构冲突而插入的流水线气泡为消除结构冲突而插入的流水线气泡 7979/163/1633.3 流水线的相关与冲突引入暂停后的时空图引入暂停后的时空图

49、指令编号指令编号 时钟周期时钟周期 1 12 23 34 45 56 67 78 89 91010指令指令i i IF IF ID ID EX EX MEM MEM WB WB 指令指令i+1 i+1 IF IF ID ID EX EX MEM MEM WB WB 指令指令i+2 i+2 IF IF ID ID EX EX MEM MEM WB WB WB WB 指令指令i+3 i+3 stallstall IFIFID ID EX EX MEM MEM WB WB 指令指令i+4 i+4 IFIFID ID EX EX MEM MEM WB WB 指令指令i+5 i+5 IFIFIDIDEX

50、 EX MEM MEM 8080/163/1633.3 流水线的相关与冲突有时流水线设计者允许结构冲突的存在主要原因：主要原因：减少硬件成本减少硬件成本q如果把流水线中的所有功能单元完全流水化，或者如果把流水线中的所有功能单元完全流水化，或者 重复设置足够份数，那么所花费的成本将相当高。重复设置足够份数，那么所花费的成本将相当高。（2）数据冲突 当相关的指令靠得足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们非流水实现时的顺序，则发生了数据冲突。8181/163/1633.3 流水线的相关与冲突举例： DADD DADD R1R1，R2R2，R3R3

51、DSUB R4 DSUB R4，R1R1，R5R5 XOR R6 XOR R6，R1R1，R7R7 AND R8 AND R8，R1R1，R9R9 OR R10 OR R10，R1R1，R11R118282/163/1633.3 流水线的相关与冲突 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1， R2， R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 IM Reg OR R10，R1，R11 流水线的数据冲突举例流水线的数据

52、冲突举例 8383/163/1633.3 流水线的相关与冲突根据指令读访问和写访问的顺序，可以将数据冲 突分为3种类型。 考虑考虑两条指令两条指令i i和和j j ，且，且i i在在j j之前进入流水线，之前进入流水线，可能发生的数据冲突有：可能发生的数据冲突有：q写后读冲突（写后读冲突（RAWRAW） 在在 i i 写入之前，写入之前，j j 先去读。先去读。 j j 读出的内容是错误的。读出的内容是错误的。 这是最常见的一种数据冲突，它对应于真数据相关。这是最常见的一种数据冲突，它对应于真数据相关。 8484/163/1633.3 流水线的相关与冲突q写后写冲突（写后写冲突（WAWWAW）

53、 在在 i i 写入之前，写入之前，j j 先写。先写。 最后写入的结果是最后写入的结果是 i i 的。错误！的。错误！ 这种冲突对应于输出相关。这种冲突对应于输出相关。 写后写冲突仅发生在这样的流水线中：n流水线中不只一个段可以进行写操作。流水线中不只一个段可以进行写操作。n当先前某条指令停顿时，允许其后续指令继续前进。当先前某条指令停顿时，允许其后续指令继续前进。 前面介绍的5段流水线不会发生写后写冲突。（只在（只在WBWB段写寄存器）段写寄存器） 8585/163/1633.3 流水线的相关与冲突q读后写冲突（读后写冲突（WARWAR） 在在 i i 读之前，读之前，j j 先写。先写。

54、 i i 读出的内容是错误的！读出的内容是错误的！ 由反相关引起。由反相关引起。 这种冲突仅发生在这样的情况下：n有些指令的写结果操作提前了，而且有些指令有些指令的写结果操作提前了，而且有些指令 的读操作滞后了。的读操作滞后了。n指令被重新排序了。指令被重新排序了。 读后写冲突在前述5段流水线中不会发生。（读操作（在（读操作（在IDID段）在写结果操作（在段）在写结果操作（在WBWB段）之前）段）之前）8686/163/1633.3 流水线的相关与冲突通过定向技术减少数据冲突引起的停顿 （定向技术也称为旁路或短路）（定向技术也称为旁路或短路）q关键思想：关键思想：在某条指令产生计算结果之前，其

55、他指在某条指令产生计算结果之前，其他指 令并不真正立即需要该计算结果，如果能够将该计令并不真正立即需要该计算结果，如果能够将该计 算结果从其产生的地方直接送到其他指令需要它的算结果从其产生的地方直接送到其他指令需要它的 地方，那么就可以避免停顿。地方，那么就可以避免停顿。q采用定向技术消除上例中的相关采用定向技术消除上例中的相关 8787/163/1633.3 流水线的相关与冲突 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU DADD R1，R2，R3 DSUB R4，R1，R

56、5 XOR R6，R1，R7 AND R8，R1，R9 IM Reg OR R10，R1，R11 采用定向技术后的流水线数据通路采用定向技术后的流水线数据通路 8888/163/1633.3 流水线的相关与冲突q当定向硬件检测到前面某条指令的结果寄存器就是当前当定向硬件检测到前面某条指令的结果寄存器就是当前指令的源寄存器时，控制逻辑会将前面那条指令的结果指令的源寄存器时，控制逻辑会将前面那条指令的结果直接从其产生的地方定向到当前指令所需的位置。直接从其产生的地方定向到当前指令所需的位置。q结果数据不仅可以从某一功能部件的输出定向到其自身结果数据不仅可以从某一功能部件的输出定向到其自身的输入，而

57、且还可以定向到其他功能部件的输入。的输入，而且还可以定向到其他功能部件的输入。 举例举例: DSUB DSUB R1R1，R2R2，R3R3LD LD R5R5，0 0（R1R1）SD SD R5R5，1212（R1R1）8989/163/1633.3 流水线的相关与冲突 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU LD R1，0(R2) DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 更多的定向路径更多的定向路径 9090/163/1633.

58、3 流水线的相关与冲突需要停顿的数据冲突 q并不是所有的数据冲突都可以用定向技术来解决。并不是所有的数据冲突都可以用定向技术来解决。 举例举例: LD LD R1R1，0 0（R2R2）DADD R4DADD R4，R1R1，R5R5AND R6AND R6，R1R1，R7R7XOR R8XOR R8，R1R1，R9R9q增加流水线互锁硬件，插入增加流水线互锁硬件，插入“暂停暂停”。 作用：作用：检测发现数据冲突，并使流水线停顿，直至检测发现数据冲突，并使流水线停顿，直至冲突消失。冲突消失。 举例：举例：演示演示A A 演示演示B B9191/163/1633.3 流水线的相关与冲突 时间（时

59、钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU LD R1，0(R2) DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 无法将无法将LDLD指令的结果定向到指令的结果定向到DADDDADD指令指令 9292/163/1633.3 流水线的相关与冲突 时间（时钟周期） 1 2 3 4 5 6 IM Reg ALU DM Reg IM Reg ALU DM IM Reg ALU IM Reg LD R1，0(R2) DADD R4，R1，R5 AND R6，

60、R1， R7 XOR R8，R1，R9 气泡 气泡 气泡 流水线互锁机制插入气泡后的执行过程流水线互锁机制插入气泡后的执行过程 9393/163/1633.3 流水线的相关与冲突LD R1LD R1，0 0（R2R2） IF IF ID ID EX EX MEM MEM WB WB DADD R4DADD R4，R1R1，R5 R5 IF IF ID ID EX EX MEM MEM WB WB AND R6AND R6，R1R1，R7 R7 IF IF ID ID EX EX MEM MEM WB WB XOR R8XOR R8，R1R1，R9 R9 IF IF ID ID EX EX ME