《第3章 流水线技术PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第3章 流水线技术PPT讲稿.ppt（157页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 流水线技术第1页，共157页，编辑于2022年，星期一3.1流水线的基本概念3.2流水线的性能指标3.3 非线性流水线的调度3.4流水线的相关与冲突 3.5流水线的实现第2页，共157页，编辑于2022年，星期一1.工业生产流水线 下面通过一个例子来说明流水线的好处:两种方案两种方案的工作过程对比流水线生产过程的抽象描述这种流水工作方式的主要特点3.1 流水线的基本概念3.1.1 什么是流水线第3页，共157页，编辑于2022年，星期一3.1 流水线的基本概念2.流水线技术把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段
2、，这样，每个子过程就可以与其它的子过程并行进行。3.流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。第4页，共157页，编辑于2022年，星期一3.1 流水线的基本概念4.指令流水线把指令的解释过程分解为分析和执行两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。理想情况：速度提高一倍4段指令流水线 第5页，共157页，编辑于2022年，星期一3.1 流水线的基本概念5.浮点加法流水线把流水线技术应用于运算的执行过程，就形成了 运算操作流水线，也称为部件级流水线。把浮点加法的全过程分解为求阶差、对阶、尾数 相加、规格化
3、四个子过程。理想情况：速度提高3倍第6页，共157页，编辑于2022年，星期一6.时空图时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。浮点加法流水线的时空图第7页，共157页，编辑于2022年，星期一3.1 流水线的基本概念7.流水技术的特点流水线把一个处理过程分解为若干个子过程（段），每个子过程由一个专门的功能部件来实现。流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。时间最长的段将成为时间最长的段将成为流水线的瓶颈。流水线的瓶颈。流水线每一个段的后面都要有一个缓冲寄存器（锁存器），称为流水寄存器。q作用：作用：在相邻的两段
4、之间传送数据，以保证提供后在相邻的两段之间传送数据，以保证提供后 面要用到的信息，并把各段的处理工作相互隔离。面要用到的信息，并把各段的处理工作相互隔离。第8页，共157页，编辑于2022年，星期一3.1 流水线的基本概念流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。流水线需要有通过时间和排空时间。q通过时间：通过时间：第一个任务从进入流水线到流出结果第一个任务从进入流水线到流出结果 所需的时间。所需的时间。q排空时间：排空时间：最后一个任务从进入流水线到流出结最后一个任务从进入流水线到流出结 果所需的时间。果所需的时间。第9页，共157页，编辑于20
5、22年，星期一3.1 流水线的基本概念1.部件级、处理机级及处理机间流水线（按照流水技术用于计算机系统的等级不同）（按照流水技术用于计算机系统的等级不同）部件级流水线（运算操作流水线）：把处理机中的部件分段，再把这些分段相互连接起来，使得各种类型的运算操作能够按流水方式进行。处理机级流水线（指令流水线）：把指令的执行过程按照流水方式处理。把一条指令的执行过程3.1.2 流水线的分类从不同的角度和观点，把流水线分成多种不同的种类。第10页，共157页，编辑于2022年，星期一3.1 流水线的基本概念 分解为若干个子过程，每个子过程在独立的功能 部件中执行。系统级流水线（宏流水线）：把多台处理机串
6、行连接起来，对同一数据流进行处理，每个处理机完成整个任务中的一部分。动画解析第11页，共157页，编辑于2022年，星期一3.1 流水线的基本概念2.单功能流水线与多功能流水线 （按照流水线所完成的功能来分类）（按照流水线所完成的功能来分类）单功能流水线：只能完成一种固定功能的流水线。多功能流水线：流水线的各段可以进行不同的 连接，以实现不同的功能。例：例：ASCASC的多功能流水线的多功能流水线第12页，共157页，编辑于2022年，星期一第13页，共157页，编辑于2022年，星期一3.1 流水线的基本概念3.静态流水线与动态流水线（按照同一时间内各段之间的连接方式对多功能流水线作（按照同
7、一时间内各段之间的连接方式对多功能流水线作进一步的分类）进一步的分类）静态流水线：在同一时间内，多功能流水线中的 各段只能按同一种功能的连接方式工作。q对于静态流水线来说，只有当输入的是一串相同的对于静态流水线来说，只有当输入的是一串相同的 运算任务时，流水的效率才能得到充分的发挥。运算任务时，流水的效率才能得到充分的发挥。例如：例如：ASCASC的的8 8段流水线段流水线第14页，共157页，编辑于2022年，星期一3.2 流水线的基本概念动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。动画q优点优点 灵活，能够提高流水线各段的使用率，从而灵活，能够提
8、高流水线各段的使用率，从而 提高处理速度。提高处理速度。q缺点缺点 控制复杂。控制复杂。静、动态流水线时空图的对比第15页，共157页，编辑于2022年，星期一第16页，共157页，编辑于2022年，星期一3.1 流水线的基本概念4.线性流水线与非线性流水线（按照流水线中是否有反馈回路来进行分类）（按照流水线中是否有反馈回路来进行分类）线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。非线性流水线：流水线中除了有串行的连接外，还有反馈回路。（举例）非线性流水线的调度问题q确定什么时候向流水线引进新的任务，才能使该任务不确定什么时候向流水线引进新的
9、任务，才能使该任务不会与先前进入流水线的任务发生冲突会与先前进入流水线的任务发生冲突争用流水段。争用流水段。第17页，共157页，编辑于2022年，星期一3.1 流水线的基本概念第18页，共157页，编辑于2022年，星期一3.1 流水线的基本概念5.顺序流水线与乱序流水线（根据任务流入和流出的顺序是否相同来进行分类（根据任务流入和流出的顺序是否相同来进行分类）顺序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序完全相同。每一个任务在流 水线的各段中是一个跟着一个顺序流动的。乱序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序可以不同，允许后进入流水 线的任务先完成（从输出
10、端流出）。也称为无序流水线、错序流水线、异步流水线也称为无序流水线、错序流水线、异步流水线第19页，共157页，编辑于2022年，星期一3.1 流水线的基本概念6.标量处理机与向量流水处理机 把指令执行部件中采用了流水线的处理机称为流 水线处理机。标量处理机：处理机不具有向量数据表示和向量 指令，仅对标量数据进行流水处理。向量流水处理机：具有向量数据表示和向量指令 的处理机。向量数据表示和流水技术的结合。向量数据表示和流水技术的结合。第20页，共157页，编辑于2022年，星期一 吞吐率：在单位时间内流水线所完成的任务数量或输 出结果的数量。3.2 流水线的性能指标3.2.1 吞吐率n：任务数
11、Tk：处理完成n个任务所用的时间第21页，共157页，编辑于2022年，星期一3.2 流水线的性能指标各段时间均相等的流水线各段时间均相等的流水线时空图第22页，共157页，编辑于2022年，星期一3.2 流水线的性能指标流水线完成n个连续任务所需要的总时间为：（假设一条（假设一条k k段段线性流水线）线性流水线）Tkkt(n1)t(kn1)t 流水线的实际吞吐率最大吞吐率第23页，共157页，编辑于2022年，星期一3.2 流水线的性能指标最大吞吐率与实际吞吐率的关系 q流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流
12、水线的段数有关外，还与流水线的段数k k以及输入到流水线中的任务数以及输入到流水线中的任务数n n等有关。等有关。q只有当只有当nknk时，才有时，才有TPTPTPTPmaxmax。第24页，共157页，编辑于2022年，星期一3.2 流水线的性能指标2.各段时间不完全相等的流水线 各段时间不等的流水线及其时空图 举例1（时空图）q一条一条4 4段段的流水线的流水线qS1S1，S3S3，S4S4各段的时间：各段的时间：ttqS2S2的时间：的时间：3t 3t（瓶颈段）瓶颈段）流水线中这种时间最长的段称为流水线的瓶颈段。第25页，共157页，编辑于2022年，星期一3.2 流水线的性能指标第26
13、页，共157页，编辑于2022年，星期一举例2：一条5段的流水线qS S1 1，S S2 2，S S3 3，S S5 5各段的时间：各段的时间：ttqS S4 4的时间：的时间：3t 3t（瓶颈段）瓶颈段）第27页，共157页，编辑于2022年，星期一3.2 流水线的性能指标各段时间不等的流水线的实际吞吐率为：（tti i为第为第i i段的时间，共有段的时间，共有k k个段个段 ）流水线的最大吞吐率为：第28页，共157页，编辑于2022年，星期一3.2 流水线的性能指标对前面举例2中的5段流水线最大吞吐率为：第29页，共157页，编辑于2022年，星期一3.2 流水线的性能指标3.解决流水线
14、瓶颈问题的常用方法 举例细分瓶颈段 例如：例如：对前面的对前面的5 5段段流水线流水线把瓶颈段把瓶颈段S S4 4细分为细分为3 3个子流水线段：个子流水线段：S S4-14-1，S S4-24-2，S S4-34-3改进后的流水线的吞吐率改进后的流水线的吞吐率 ：第30页，共157页，编辑于2022年，星期一3.2 流水线的性能指标重复设置瓶颈段q举例：举例：时时-空图空图q缺点：缺点：控制逻辑比较复杂，所需的硬件增加了。控制逻辑比较复杂，所需的硬件增加了。例如：例如：对前面的对前面的5 5段流水线段流水线 重复设置瓶颈段重复设置瓶颈段S S4 4：S S4a4a，S S4b4b，S S4c
15、4c第31页，共157页，编辑于2022年，星期一3.2 流水线的性能指标重复设置瓶颈段后的时空图重复设置瓶颈段后的时空图第32页，共157页，编辑于2022年，星期一3.2 流水线的性能指标加速比：完成同样一批任务，不使用流水线所用的时间 与使用流水线所用的时间之比。假设：不使用流水线（即顺序执行）所用的时间为假设：不使用流水线（即顺序执行）所用的时间为T Ts s，使用流水线后所用的时间为使用流水线后所用的时间为T Tk k，则该流水线的加速比，则该流水线的加速比为：为：3.2.2 流水线的加速比第33页，共157页，编辑于2022年，星期一3.2 流水线的性能指标流水线各段时间相等（都是
16、t）一条k段流水线完成n个连续任务 所需要的时间为：所需要的时间为：Tk=(kn1)t顺序执行n个任务 所需要的时间：所需要的时间：Ts=nkt （解释）解释）流水线的实际加速比为：第34页，共157页，编辑于2022年，星期一3.2 流水线的性能指标最大加速比当当nknk时，时，S S k k思考：思考：流水线的段数愈多愈好？流水线的段数愈多愈好？第35页，共157页，编辑于2022年，星期一3.2 流水线的性能指标2.流水线的各段时间不完全相等时一条k段流水线完成n个连续任务的实际加速比为：第36页，共157页，编辑于2022年，星期一3.2 流水线的性能指标 流水线的效率：流水线中的设备
17、实际使用时间与整个运行时间的比值，即流水线设备的利用率。由于流水线有通过时间和排空时间，所以在连续由于流水线有通过时间和排空时间，所以在连续完成完成n n个个任务的时间内，各段并不是满负荷地工作。任务的时间内，各段并不是满负荷地工作。各段时间相等各段的效率ei相同 (解释)3.2.3 流水线的效率第37页，共157页，编辑于2022年，星期一3.2 流水线的性能指标整条流水线的效率为：可以写成：最高效率为：当当nknk时，时，E1E1。第38页，共157页，编辑于2022年，星期一3.2 流水线的性能指标当流水线各段时间相等时，流水线的效率与吞吐率 成正比。E=TPt 2.流水线的效率是流水线
18、的实际加速比S与它的最大加速 比k的比值。当当E=1E=1时，时，S=kS=k，实际加速比达到最大。，实际加速比达到最大。第39页，共157页，编辑于2022年，星期一3.2 流水线的性能指标3.从时空图上看，效率就是n个任务占用的时空面积和 k个段总的时空面积之比。当各段时间不相等时：第40页，共157页，编辑于2022年，星期一3.2 流水线的性能指标 例例3.13.1 设在下图所示的静态流水线上计算：设在下图所示的静态流水线上计算：流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，试计算其吞吐率、加速比和效率。试计算其吞吐
19、率、加速比和效率。3.2.4 流水线的性能分析举例(每段的时间都为每段的时间都为t t)第41页，共157页，编辑于2022年，星期一3.2 流水线的性能指标解解：（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）画出时空图）画出时空图 第42页，共157页，编辑
20、于2022年，星期一第43页，共157页，编辑于2022年，星期一3.2 流水线的性能指标p在在1818个个t t时间中，给出了时间中，给出了7 7个个结果。吞吐率为：结果。吞吐率为：p 不用流水线，由于一次求和需不用流水线，由于一次求和需66t t，一次求积需一次求积需44t t，则产生上述则产生上述7 7个结果共需个结果共需（46+3446+34）t t=36=36t t 加速比为：加速比为：（3 3）计算性能）计算性能第44页，共157页，编辑于2022年，星期一3.2 流水线的性能指标p 流水线的效率流水线的效率 可以看出，在求解此问题时，该流水线的效率不高。(原因)第45页，共157
21、页，编辑于2022年，星期一3.2 流水线的性能指标主要原因q多功能流水线在做某一种运算时，总有一些段是空多功能流水线在做某一种运算时，总有一些段是空闲的；闲的；q静态流水线在进行功能切换时，要等前一种运算全静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算；部流出流水线后才能进行后面的运算；q运算之间存在关联，后面有些运算要用到前面运算运算之间存在关联，后面有些运算要用到前面运算的结果；的结果；q流水线的工作过程有建立与排空部分。流水线的工作过程有建立与排空部分。第46页，共157页，编辑于2022年，星期一3.2 流水线的性能指标 例例3.2 3.2 有一条动态多
22、功能流水线由有一条动态多功能流水线由5 5段组成，加法用段组成，加法用1 1、3 3、4 4、5 5段，乘法用段，乘法用1 1、2 2、5 5段，第段，第4 4段的时间为段的时间为2t2t，其余各段时间均，其余各段时间均为为t t，而且流水线的输出可以直接返回输入端或暂存于相应的，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算流水寄存器中。若在该流水线上计算:试计算其吞吐率、加速比和效率。试计算其吞吐率、加速比和效率。第47页，共157页，编辑于2022年，星期一3.2 流水线的性能指标解解:(1)(1)选择适合于流水线工作的算法选择适合于流水线工作的算法p应
23、先计算应先计算A A1 1BB1 1、A A2 2BB2 2、A A3 3BB3 3和和A A4 4BB4 4；p再计算再计算(A(A1 1BB1 1)(A(A2 2BB2 2)(A (A3 3BB3 3)(A(A4 4BB4 4)；p然后求总的累加结果。然后求总的累加结果。(2)(2)画出时空图画出时空图(3)(3)计算性能计算性能第48页，共157页，编辑于2022年，星期一3.2 流水线的性能指标第49页，共157页，编辑于2022年，星期一3.2 流水线的性能指标 下面我们再看一个例子：下面我们再看一个例子：例例 在静态流水线上计算在静态流水线上计算:求：吞吐率，加速比，效率。求：吞吐
24、率，加速比，效率。解：解：(1)(1)确定适合于流水处理的计算过程确定适合于流水处理的计算过程 (2)(2)画时空图画时空图 (3)(3)计算性能计算性能 吞吐率吞吐率 TPTP7 7(20(20tt)加速比加速比 S S(34(34tt)(20(20tt)1.71.7 效率效率 E E(44(4436)36)(820)(820)0.210.21第50页，共157页，编辑于2022年，星期一3.2 流水线的性能指标第51页，共157页，编辑于2022年，星期一3.2 流水线的性能指标可以看出，在求解此问题时，该流水线的效率不高。动态流水线的时空图 举例举例 :这样行不行？正确答案第52页，共1
25、57页，编辑于2022年，星期一3.2 流水线的性能指标1.瓶颈问题理想情况下，流水线在工作时，其中的任务是同步地每一个时钟周期往前流动一段。当流水线各段不均匀时，机器的时钟周期取决于瓶颈段的延迟时间。在设计流水线时，要尽可能使各段时间相等。2.流水线的额外开销p流水寄存器延迟流水寄存器延迟p时钟偏移开销时钟偏移开销3.2.5 流水线设计中的若干问题第53页，共157页，编辑于2022年，星期一3.2 流水线的性能指标流水寄存器需要建立时间和传输延迟q建立时间：建立时间：在触发写操作的时钟信号到达之前，寄在触发写操作的时钟信号到达之前，寄 存器输入必须保持稳定的时间。存器输入必须保持稳定的时间
26、。q传输延迟：传输延迟：时钟信号到达后到寄存器输出可用的时时钟信号到达后到寄存器输出可用的时 间。间。时钟偏移开销q流水线中，时钟到达各流水寄存器的最大差值时间。流水线中，时钟到达各流水寄存器的最大差值时间。（时钟到达各流水寄存器的时间不是完全相同）（时钟到达各流水寄存器的时间不是完全相同）第54页，共157页，编辑于2022年，星期一3.2 流水线的性能指标几个问题q流水线并不能减少（而且一般是增加）单条指令的流水线并不能减少（而且一般是增加）单条指令的执行时间，但却能提高吞吐率。执行时间，但却能提高吞吐率。q增加流水线的深度（段数）可以提高流水线的性能。增加流水线的深度（段数）可以提高流水
27、线的性能。q流水线的深度受限于流水线的额外开销。流水线的深度受限于流水线的额外开销。q当时钟周期小到与额外开销相同时，流水已没意义。当时钟周期小到与额外开销相同时，流水已没意义。因为这时在每一个时钟周期中已没有时间来做有用因为这时在每一个时钟周期中已没有时间来做有用的工作。的工作。3.冲突问题 流水线设计中要解决的重要问题之一。第55页，共157页，编辑于2022年，星期一在非线性流水线中，存在反馈回路，当一个任务在流水线中流过时，可能要多次经过某些段。流水线调度要解决的问题：应按什么样的时间间隔向流水线输入新任务，才能既不发生功能应按什么样的时间间隔向流水线输入新任务，才能既不发生功能段使用
28、冲突，又能使流水线有较高的吞吐率和效率？段使用冲突，又能使流水线有较高的吞吐率和效率？3.3 非线性流水线的调度第56页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离。会引起非线性流水线功能段使用冲突的启动距离则称为禁用启动距离。启动距离和禁用启动距离一般都用时钟周期数来表示，是一个正整数。预约表 q横向（向右）：时间（一般用时钟周期表示）横向（向右）：时间（一般用时钟周期表示）q纵向（向下）：流水线的段纵向（向下）：流水线的段3.3.1 单功能非线性流水线的最优调度第57页，共157页，编辑于
29、2022年，星期一例：一个例：一个5功能段非线性流水线预约表功能段非线性流水线预约表 q如果在第如果在第n个时钟周期使用第个时钟周期使用第k段，则在第段，则在第k行和第行和第n列的交列的交叉处的格子里有一个叉处的格子里有一个。q如果在第如果在第k行和第行和第n列的交叉处的格子里有一个列的交叉处的格子里有一个，则表，则表示在第示在第n个时钟周期要使用第个时钟周期要使用第k段。段。第58页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度1.根据预约表写出禁止表F禁止表F：一个由禁用启动距离构成的集合。具体方法 对于预约表的每一行的任何一对对于预约表的每一行的任何一对，用它们所在，用
30、它们所在的列号相减（大的减小的），列出各种可能的差值，的列号相减（大的减小的），列出各种可能的差值，然后删除相同的，剩下的就是禁止表的元素。然后删除相同的，剩下的就是禁止表的元素。在上例中q第一行的差值只有一个：第一行的差值只有一个：8；q第二行的差值有第二行的差值有3个：个：1，5，6；q第第3行只有一个行只有一个，没有差值；，没有差值；q第第4和第和第5行的差值都只有一个：行的差值都只有一个：1；其禁止表是：其禁止表是：F=1，5，6，8 第59页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度2.根据禁止表F写出初始冲突向量C0（进行从一个集合到一个二进制位串的变换（进行
31、从一个集合到一个二进制位串的变换）冲突向量C：一个N位的二进制位串。设C0=（cNcN-1cic2c1），则：qci=0：允许间隔：允许间隔i个时钟周期后送入后续任务个时钟周期后送入后续任务qci=1：不允许间隔：不允许间隔i个时钟周期后送入后续任务个时钟周期后送入后续任务 对于上面的例子 F=1，5，6，8 C0=（10110001）第60页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度3.根据初始冲突向量C0画出状态转换图当第一个任务流入流水线后，初始冲突向量C0决定了下一个任务需间隔多少个时钟周期才可以流入。在第二个任务流入后，新的冲突向量是怎样的呢？q假设第二个任务是
32、在与第一个任务间隔假设第二个任务是在与第一个任务间隔j个时钟周期个时钟周期流入，这时，由于第一个任务已经在流水线中前进了流入，这时，由于第一个任务已经在流水线中前进了j个时钟周期，其相应的禁止表中各元素的值都应该个时钟周期，其相应的禁止表中各元素的值都应该减去减去j，并丢弃小于等于，并丢弃小于等于0的值。的值。q对冲突向量来说，就是对冲突向量来说，就是逻辑右移逻辑右移j位位（左边补（左边补0）。）。第61页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度q在冲突向量上，就是对它们的冲突向量进行在冲突向量上，就是对它们的冲突向量进行“或或”运运算算。SHR(j)（C0）C0 其中
33、其中:SHR(j)表示逻辑右移表示逻辑右移j位位 推广到更一般的情况假设假设:Ck：当前的冲突向量：当前的冲突向量 j:允许的时间间隔允许的时间间隔则新的冲突向量为：则新的冲突向量为：SHR(j)（Ck）C0对于所有允许的时间间隔都按上述步骤求出其新的冲突向量，并且把新的冲突向量作为当前冲突向量，反复使用上述步骤，直到不再产生新的冲突向量为止。第62页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度从初始冲突向量C0出发，反复应用上述步骤，可以求得所有的冲突向量以及产生这些向量所对应的时间间隔。由此可以画出用冲突向量表示的流水线状态转移图。q有向弧有向弧：表示状态转移的方向：表
34、示状态转移的方向q弧上的数字弧上的数字：表示引入后续任务（从而产生新的冲突：表示引入后续任务（从而产生新的冲突向量）所用的时间间隔（时钟周期数）向量）所用的时间间隔（时钟周期数）第63页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度对于上面的例子对于上面的例子（1 1）C C0 0=（1011000110110001）引入后续任务可用的时间间隔为：引入后续任务可用的时间间隔为：2 2、3 3、4 4、7 7个时钟周期个时钟周期 如果采用如果采用2 2，则新的冲突向量为：，则新的冲突向量为：（0010110000101100）（1011000110110001）=（101111
35、0110111101）如果采用如果采用3 3，则新的冲突向量为：，则新的冲突向量为：（0001011000010110）（1011000110110001）=（1011011110110111）如果采用如果采用4 4，则新的冲突向量为：，则新的冲突向量为：（0000101100001011）（1011000110110001）=（1011101110111011）如果采用如果采用7 7，则新的冲突向量为：，则新的冲突向量为：（0000000100000001）（1011000110110001）=（1011000110110001）第64页，共157页，编辑于2022年，星期一（2 2）对于新
36、向量）对于新向量（1011110110111101），其可用的时间间隔为，其可用的时间间隔为2 2个个和和7 7个个时钟时钟 周期。用类似上面的方法，可以求出其后续的冲突向量分别为周期。用类似上面的方法，可以求出其后续的冲突向量分别为 （1011110110111101）和和（1011000110110001）。（3 3）对于其他新向量，也照此处理。）对于其他新向量，也照此处理。（4 4）在此基础上，画出状态转移示意图。）在此基础上，画出状态转移示意图。第65页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度4.根据状态转换图写出最优调度方案 根据流水线状态图，由初始状态出发，
37、任何一个闭合回路即为一种调度方案。列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其最小者即为最优调度方案。上例中，各种调度方案及其平均间隔时间。q最佳方案：最佳方案：（3，4）平均间隔时间：平均间隔时间：3.5个时钟周期（吞吐率最高）个时钟周期（吞吐率最高）q方案（方案（4，3）的平均间隔时间也是）的平均间隔时间也是3.5，但它不是最，但它不是最佳方案，为什么？佳方案，为什么？第66页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度调度策略 平均延迟拍数(2,7)(2,2,7)(3,7)(3,4)(3,4,3,7)(3,4,7)(4,3,7)(4,7)（7）4.
38、53.6753.54.254.674.675.57 各种调度策略及平均延迟拍数各种调度策略及平均延迟拍数 第67页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度方案（3，4）是一种不等时间间隔的调度方案，与等间隔的调度方案相比，在控制上要复杂得多。为了简化控制，也可以采用等间隔时间的调度方案，但吞吐率和效率往往会下降不少。q在上述例子中，等时间间隔的方案只有一个：在上述例子中，等时间间隔的方案只有一个：（7），其吞吐率下降了一半。其吞吐率下降了一半。第68页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度 以双功能（功能A和B）非线性流水线为例。1.状态转移图
39、中结点状态的表示由两个冲突向量构成的冲突矩阵，这两个冲突向量分别对应于下一个任务的功能是A类和B类的情况。2.初始结点有两个，分别对应于第一个任务是A类和B类的情况。当第一个任务是A类时，冲突矩阵为M(0)A。当第一个任务是B类时，冲突矩阵为M(0)B。3.3.2 多功能非线性流水线的调度第69页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度其中：qCpq（p,qA,B）表示的是：在一个）表示的是：在一个p类任务流入流类任务流入流水线后，对后续水线后，对后续q类任务的冲突向量。类任务的冲突向量。它们可以由预约表求得。它们可以由预约表求得。qCpq共有共有22=4个。个。q对于
40、对于N功能流水线，这种冲突向量有功能流水线，这种冲突向量有N2个。个。第70页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度3.由下式求得后续状态的冲突矩阵 SHR(i)（Mk）Mr(0)其中：qMk：当前状态：当前状态qr：下一个流入任务的类型（：下一个流入任务的类型（A或或B）qi：当前状态允许的流入：当前状态允许的流入r型任务的时间间隔型任务的时间间隔qSHR(i)（Mk）：把当前状态中的各冲突向量逻辑右移：把当前状态中的各冲突向量逻辑右移i位位例如：例如：SHR(3)（Mk）MA(0)表示的是：把当前状态表示的是：把当前状态Mk中中的各冲突向量逻辑右移的各冲突向量逻辑
41、右移3位，再与初始矩阵位，再与初始矩阵MA(0)进行进行“或或”运算。运算。4.举例说明双功能非线性流水线的最优调度第71页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度 例例3.3 有一条有一条3段双功能非线性流水线，实现的功能是段双功能非线性流水线，实现的功能是A和和B，其预约表分别如，其预约表分别如表表1和和表表2所示。各段的通过时间都是一个时钟周期。请找出该流水线单独处理所示。各段的通过时间都是一个时钟周期。请找出该流水线单独处理A类任务和单独类任务和单独处理处理B类任务以及混合处理两类任务的最优调度方案。类任务以及混合处理两类任务的最优调度方案。1 12 23 34
42、 45 5S1S1S2S2S3S3时间时间段段 1 12 23 34 45 5S1S1S2S2S3S3时间时间段段表表1 A类对象预约表类对象预约表表表2 B类对象预约表类对象预约表第72页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度解：解：（1）把两个预约表重叠起来，得到如表把两个预约表重叠起来，得到如表3所示的预约表。所示的预约表。（2）由预约表求初始冲突向量和初始冲突矩阵）由预约表求初始冲突向量和初始冲突矩阵 1 12 23 34 45 5S1S1A AB BA AB BS2S2A AB BS3S3B BABABA A时间时间段段第73页，共157页，编辑于2022年
43、，星期一3.3 非线性流水线的调度qCAA：一个：一个A类任务流入流水线后，对下一个类任务流入流水线后，对下一个A类任务进入流水类任务进入流水线的时间间隔的限制。线的时间间隔的限制。根据预约表表根据预约表表1可知，禁用时间间隔是可知，禁用时间间隔是2和和3，故禁止表为：，故禁止表为：2，3，所以，所以CAA=（0110）。qCBB：一个：一个B类任务流入流水线后，对下一个类任务流入流水线后，对下一个B类任务进入流水类任务进入流水线的时间间隔的限制。线的时间间隔的限制。根据预约表表根据预约表表2可知，禁用时间间隔是可知，禁用时间间隔是2和和3，所以，所以CBB=（0110）。）。qCAB：一个：
44、一个A类任务流入流水线后，对下一个类任务流入流水线后，对下一个B类任务进入流水类任务进入流水线的时间间隔的限制。根据预约表表线的时间间隔的限制。根据预约表表3可知：可知：n为了避免在为了避免在S1发生冲突，禁用时间间隔是：发生冲突，禁用时间间隔是：4-2=2 第74页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度n在在S2，不会发生冲突，这是因为根据表，不会发生冲突，这是因为根据表3，A类任务先于类任务先于B类任务通过类任务通过S2，而现在的实际情况又是，而现在的实际情况又是A类任务先于类任务先于B类任类任务流入流水线；务流入流水线；n为了避免在为了避免在S3发生冲突，禁用时
45、间间隔是：发生冲突，禁用时间间隔是：3-1=2，5-1=4，5-3=2n综合起来，有：综合起来，有：CAB=（1010）qCBA表示一个表示一个B类任务流入流水线后，对下一个类任务流入流水线后，对下一个A类任务进入流类任务进入流水线的时间间隔的限制。根据预约表表水线的时间间隔的限制。根据预约表表3可知：可知：n为了避免在为了避免在S1发生冲突，禁用时间间隔有：发生冲突，禁用时间间隔有：2-1=1，5-1=4，5-4=1n为了避免在为了避免在S2发生冲突，禁用时间间隔是：发生冲突，禁用时间间隔是：4-2=2第75页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度n在在S3，不会发
46、生冲突，这是因为根据表，不会发生冲突，这是因为根据表3，B类类任务先于任务先于A类任务通过类任务通过S3，或者同时通过，或者同时通过S3（第（第3个时钟周期），而现在的实际情况又是个时钟周期），而现在的实际情况又是B类任类任务先于务先于A类任务流入流水线。类任务流入流水线。n综合起来，有：综合起来，有：CAB=（1011）初始矩阵为：初始矩阵为：第76页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度（3）由初始冲突矩阵画出状态图）由初始冲突矩阵画出状态图 如果第一个流入的任务是如果第一个流入的任务是A类，初始状态就是类，初始状态就是MA(0)；如果第一个；如果第一个流入的任务
47、是流入的任务是B类，则初始状态是类，则初始状态是MB(0)。求所有后续状态的冲突矩阵：求所有后续状态的冲突矩阵：例如：在流入一个例如：在流入一个A A类任务后，从类任务后，从C CAAAA=（01100110）可知，可以隔可知，可以隔一个一个或或4 4个个时钟时钟周期再流入一个周期再流入一个A A类任务。类任务。假设是前者，则把初始状态假设是前者，则把初始状态MA(0)中的各冲突向量同时中的各冲突向量同时右移一位右移一位（即（即进行进行SHRSHR(1)(1)操作），再与操作），再与MA(0)进行或运算，可以得到新的冲突矩阵。根据该进行或运算，可以得到新的冲突矩阵。根据该矩阵的第一个冲突向量矩
48、阵的第一个冲突向量（01110111）可知，只有隔可知，只有隔4 4个时钟周期流入一个个时钟周期流入一个A A类类任务，才能不发生冲突。把冲突矩阵中的各冲突向量同时右移任务，才能不发生冲突。把冲突矩阵中的各冲突向量同时右移4 4位位（即进行（即进行SHRSHR(4)(4)操作），再与操作），再与MA(0)进行按位或运算，可以得到新的冲进行按位或运算，可以得到新的冲突矩阵。突矩阵。第77页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度 再如，在流入一个再如，在流入一个A类任务后，从类任务后，从CAB=（1010）可知，可以隔可知，可以隔一个一个或或3个个时钟周期再流入一个时钟周
49、期再流入一个B类任务。假设是前者，则把初始状态类任务。假设是前者，则把初始状态MA(0)中中的各冲突向量同时的各冲突向量同时右移一位右移一位（即进行（即进行SHR(1)操作），再与操作），再与MB(0)进行或进行或运算，可以得到新的冲突矩阵。运算，可以得到新的冲突矩阵。据此可知，允许的流入为：或者是隔据此可知，允许的流入为：或者是隔3个时钟周期流入一个个时钟周期流入一个A类任务，类任务，或者是隔或者是隔4个时钟周期流入一个个时钟周期流入一个B类任务。按类似与上述类似的方法，又可类任务。按类似与上述类似的方法，又可以得到新的冲突矩阵。以得到新的冲突矩阵。求出所有可能的状态后，就可以画出状态图。求
50、出所有可能的状态后，就可以画出状态图。弧线上的标记弧线上的标记“r.i”表示：隔表示：隔i个时钟周期流入个时钟周期流入r类的任务。类的任务。第78页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度双功能非线性流水线的状态图双功能非线性流水线的状态图 第79页，共157页，编辑于2022年，星期一3.3 非线性流水线的调度（4）由状态图得出最优调度方案）由状态图得出最优调度方案 从状态图可以找出各种情况下的从状态图可以找出各种情况下的最优调度方案最优调度方案：只流入只流入A类任务的最优调度方案是：类任务的最优调度方案是：（A.1，A.4）流入流入B类任务的最优调度方案是：类任务的