流水方式ppt课件

1、2 流水方式 n根本概念n流水线处置机的主要性能 n流水机器的相关处置和控制机构 n空间并行性n设置多个独立的操作部件n多操作部件处置机n超标量处置机n时间并行性n采用流水线技术。n不添加或只添加少量硬件就能使运算速度提高几倍n流水线处置机n超流水线处置机根本概念 n流水是重叠的延伸.n一次重叠：只是把一条指令的解释分解为两个子过程；n流水：分解为更多的子过程。n时空图表示。流水线的表示方法n衔接图n时空图n约定表取指令指令译码取操作数执行入出12345123451234512345取指令指令译码取操作数执行空间时间t1t2t3t4t5t6t7t8流水线的时-空图阐明n流水线的每一个阶段称为流

2、水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。n在每一个流水段的末尾或开头必需设置一个存放器，称为流水存放器、流水锁存器、流水闸门存放器等。会添加指令的执行时间。n为了简化，在普通流水线中不画出流水锁存器阐明n流水线经过装入、充溢、排空三个阶段n流水的最大吞吐率：当流水线正常符合流动时的吞吐率。每隔t流出一个结果。n流水的最大吞吐率取决于子过程所经过的时间t一个浮点加法器流水线的时空图n由求阶差、对阶、尾数加和规格化4个流水段组成ED1时间空间0t1t2t3t4t5ED2 ED3 ED4 ED5EA1 EA2 EA3 EA4 EA5MA1 MA2 MA3 MA4

3、MA5NL1 NL2 NL3 NL4 NL5t6t7t8NL：规格化MA：尾数加EA：对阶ED：求阶差流水线的特点n只需延续提供同类义务才干充分发扬流水线的效率n对于指令流水线：要尽量减少因条件分支呵斥的“断流n对于操作部件：主要经过编译技术，尽量提供延续的同类操作n在流水线的每一个流水线段中都要设置一个流水锁存器n时间开销：流水线的执行时间加长n是流水线中需求添加的主要硬件之一n各流水段的时间应尽量相等n流水线处置机的根本时钟周期等于时间最长的流水段的时间长度n流水线需求有装入时间、充溢时间和排空时间n在理想情况下，当流水线充溢后，每隔t时间将会有一个结果流出流水线。流水线的分类n从不同角度

4、，有不同的分类n根据向下扩展和向上扩展思绪，可分类出在计算机系统不同等级上运用的流水线n向下扩展：子过程细分n向上扩展：多个处置机之间进展流水流水线的分类续 n按流水处置的级别n部件级操作流水线，如浮点加法器流水线求阶差输入输出Dt1对阶尾数加规格化Dt2Dt3Dt4流水线的分类续n处置机级，指令流水线 (Instruction Pipelining)n例如：在采用先行控制器的处置机中，各功能部件之间的流水线先行指令缓冲栈输入先行控制方式中的指令流水线先行指令分析器先行读数栈先行操作栈取指译码取操作数指令执行部件后行写数栈输出执行写结果流水线的分类续n系统级：宏流水线 (Macro Pipel

5、ining)每个处置机对同一个数据流的不同部分分别进展处置处置机1处置机2处置机n数据集处置机间的流水处置流水线的分类续n按功能多少n单功能：只能完成一种固定功能的流水线nCray-1计算机中有12条；nYH-1计算机有18条；nPentium有一条5段的定点和一条8段的浮点流水线；nPentium有三条指令流水线，其中两条定点指令流水线，一条浮点指令流水线。n多功能：流水线的各段经过不同衔接实现不同功能nTexas公司的ASC计算机中的8段流水线，可以实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。 A B A B A B A B 输入 输入 输入

6、输入 求阶差 求阶差 求阶差 求阶差 对阶 对阶 对阶 对阶 尾数加 尾数加 尾数加 尾数加 规格化 规格化 规格化 规格化 尾数乘 尾数乘 尾数乘 尾数乘 累加 累加 累加 累加 输出 输出 输出 输出 g=f(A,B) 定点乘 浮点加 浮点点积 (a)功能段间的互连 (b)定点乘法 (c)浮点加法 (d)浮点点积 流水线的分类续n按多功能的衔接方式n静态：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式衔接，实现一种固定的功能。n只需延续出现同一种运算时，流水线的效率才干得到充分的发扬。n动态：在同一段时间内，多功能流水线中的各段可以按照不同的方式衔接，同时执行多种功能。1时

7、间空间02 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 4 1 2 3 1 2 1输入求阶差对阶尾数加规格化尾数乘累加输出静态流水线时空图浮点加法定点乘法1时间空间02 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n1 2 3 n输入求阶差对阶尾数加规格化尾数乘累加输出动态流水线时空图1 2 35461 2 3541 2 3 41 2 3浮点加法定点乘法流水线的分类续n按数据表示n标量流水：没有向量数据，只能用标量循环方式来对向量、数组进展处置。nAmdahl 470V/6nIBM 360/91n向量流水：设置有向量指令和向量运算硬件

8、，能对向量、数组中的各个元素流水地处置。nCRAY-1流水线的分类续n按能否有反响回路n线性(Linear Pipelining)：每个流水段都流过一次，且仅流过一次n非线性(Nonlinear Pipelining)：在流水线的某些流水段之间有反响回路或前馈回路1234入出非线性流水线流水线的分类续n按照控制方式：n同步流水线n异步流水线n顺序流水线与乱序流水线：乱序流水线又称为无序流水线、错序流水线或异步流水线等流水线处置机的主要性能 n经过时空图分析 n吞吐率TP, Thoughput Rate n加速比Speed Ration效率Efficiency 吞吐率TP, Thoughput

9、Rate n是流水线单位时间里能流出的义务数或结果数。 nmTPnmttntmnTPtmtntntmTttttTP11)11 (1) 1(*) 1(*) 1(*,max1max00000004321maxDDDDDDDDDDD1时间空间S123 n-1 nS2S3S4123 n-1 n123 n-1 n123 n-1 nmDt(n-1) DtnDt(m-1)DtTS1输入Dt1DtS2Dt23DtS3Dt3DtS4Dt4Dt输出1时间空间S1S2S3S4SDti(n-1)Dt2Tk23n123n123n123n吞吐率续n 处理瓶颈子过程的方法n细分S1输入输出DtS2-1DtS2-2DtS2-

10、3DtS3DtS4DtS2(3Dt)细分1471014710S s3b s3a s2 s1t1t12t17T s3c s46811 1235911 1223592681471035911 122681471035911 122681471035911 122681471035911 12268吞吐率续n瓶颈段并联S1输入输出Dt1DtS2-1S2-1S2-1S3S4Dt3DtDt4DtDt23Dt1时间空间2 3nS1S2-14 5 614-2 -1n-225n-136n1 2 3n4 5 6-2 -11 2 3n4 5 6-2 -1S2-2S2-3S3S4并联吞吐率续n阐明：为最慢的一段时间

11、。其中：如各段时间不相等，则时，有关与jmijittntnTPTPTPmnnmtTPTPTPDDDD,) 1(. 4. 3,. 2. 11max0max加速比Speed Ratio n指流水线的速度与等效的非流水线的速度之比。nmmtntmtmnTTStmnTp11) 1(*0000DDDD非流水非流水加速比续为最慢一段的时间。其中：如各段时间不相等，则大越多越好时，当jjmiimiippttnttnSnMmSmnDDDD,) 1(. 3. 2. 111加速比续m=6m=10义务个数加速比10246811 248 16 32 64 128效率EfficiencyEta n是指流水线中的设备实践

12、运用时间占整个运转时间之比，也称流水线设备的时间利用率。 TmtnmmmmnmntttnTtnTmm*.1*) 1n(*m*.002100000210DDDDD，即：都相等，为时间内，流水线的效率则在段经过时间相等，如为线性流水线，且各效率续；时，效率。速比与最大加速比之比流水线的效率是实际加吐率。流水线的效率正比与吞效率是面积之比；积，个任务是实际占用的面而分子是时空图中所围成的总面积，段与是时空图中分母1.4111)1(.3*)1(*.2*.100DDmNmSnmmnntTPmnnTtnnTmTmp效率jmiimiiimiijmiimiimiiijjmiimiitnttntnttnttnt

13、mtnDDDDDDDDDD)1(*1.7)1(*.6,)1(*.511111111时，有：当同，加权统设备利用率的比重不其设备利用率占整个系为最慢的一段时间。其中：如各段时间不相等，则举例1：n用一条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGHn解：Z = (A+B) + (C+D) + (E+F) + (G+H)1时间空间2 3求阶差45671 2 3 45671 2 3 45671 2 3 4567对阶尾数加规格化加数 A C E GA+B E+FB D F HC+DG+HA+B+C+DE+F+G+H结果A+BC+DE+FG+HA+B+C+DE+F+G+HZ Zn7个浮点加法共

14、用了15个时钟周期。n流水线的吞吐率为：n流水线的加速比为：n流水线的效率为ttTnTPkDD147015787115740DDttTTSk470154740DDttTkTEk举例2:静态多功能流水线n设有两个向量A和B，各有4个元素，要在如下图的静态双功能流水线上，计算向量点积AB，其中1-2-3-5组成加法流水线，1-4-5组成乘法流水线，又设每个流水线所经过的时间均为Dt，而且流水线的输出结果可以直接前往到输入或存于相应的缓冲存放器中，其延迟时间和功能切换所需的时间都可以忽略不计。12354xyzA*B=a1b1+ a2b2+ a3b3+ a4b4空间时间12345678910 11 1

15、2 13 14 15 16静态多功能流水线n实践吞吐率TP=7/15 Dtn加速比Sp=24Dt/(15Dt)=1.6n效率=3*4Dt+4*3Dt/5*15Dt)n =0.32=32%A*B=a1b1+ a2b2+ a3b3+ a4b4空间时间12345678910 11 12 13 14 15 16动态多功能流水线n实践吞吐率TP=7/14 Dtn加速比Sp=24Dt/(14Dt)=1.714n效率=3*4Dt+4*3Dt/5*14Dt)n =0.343=34.3%举例3：书中P190 第6题n有一个双输入端的加-乘双功能静态流水线，由经过时间分别为Dt、2Dt、2Dt、Dt的1、2、3、

16、4四个子过程构成，加法时按1-2-4衔接，乘法时按1-3-4衔接。流水线输出设有缓冲器，也可将数据直接回授到流水线输入端。现要执行n A*(B+C*(D+E*F)+G*Hn 的运算，请对运算顺序进展交换，画出能获得尽能够高的吞吐率的流水时空图；标出流水线入、出端的操作数变化情况；求出完成全部运算所需时间及此期间整个流水线的效率。如对流水线瓶颈子过程细分，最少需多少时间完成全部运算？假设子过程3已无法再细分，只能采用并联方法改良，问流水线的效率为多少？A*B+A*C*D+A*C*E*F+G*H空间时间123456789 10 11 12 13 14 15 16 17 18 19 20 21 22

17、 23 24效率=6*4Dt+3*4Dt/4*24Dt) =3/8时间空间12345678910 11 12 13 14 15 16 17 18效率=6*4Dt+3*4Dt/6*18Dt) =1/3空间12345678910 11 12 13 14 15 16 17 18效率=6*4Dt+3*4Dt/6*18Dt) =1/3流水线最正确段数的选择n假设在非流水线的机器上采用顺序执行方式完成一个义务所需求的时间为t，那么在同等速度的有k段流水线的机器上执行一个义务需求的时间为：t/k+d,其中d为锁存器的延迟时间。n流水线的最大吞吐率：n流水线的总价钱：na为一切功能段本身的总价钱，b为每个锁存

18、器的价钱。 dktP/1bkaC流水线最正确段数的选择n流水线的性能价钱比n对k求导，求极值：n普通处置机的流水线段数在2-10之间。bkadktCPPCR1/1bdatk0流水机器的相关处置和控制机构n流水线只需延续不断地流动，不出现断流，才干获得高效率。假设处置不当，就会使流水效率显著下降。n全局相关：转移相关n部分相关流水机器的相关处置和控制机构 n部分性相关的处置 n全局性相关的处置-转移相关 n流水机器的中断处置 n流水线调度-非线性流水线 部分相关与全局相关n假设程序内有一个两路的条件分支操作指令，它把程序分为三个部分B0、B1和B2，在每一个部分内部不再有分支操作指令n在同一个根

19、本块内部的相关成为部分相关Local Correlationn对程序执行的过程的影响相对较小，仅影响到相关指令前后的一条或几条指令的执行n在根本块之间相关成为全局相关Global Correlationn影响到整个程序的执行方向B0B2B1部分性相关的处置n部分性相关：指令相关、访存操作数相关、通用存放器组相关n缘由：在机器同时解释多条指令之间出现了对同一主存单元或存放器要求“先写后读而产生的。n处理：n推后后续指令对相关单元的读，直至在先的指令写入完成n设置相关直接通路，将运算结果经相关直接通路直接送入所需部件部分性相关的处置续n义务在流水线中流动顺序的安排和控制n顺序流动方式同步流动方式：

20、义务流出流水线的顺序坚持与流入流水线的顺序一致n控制简单，但相关后吞吐率和效率下降n异步流动方式举例：流动顺序的控制n8段流水线，第2段为读段，第7段为写段n一串指令流入：h,i,j,k,l,m,nn当指令j的源操作数地址与指令h的目的操作数一样时，发生先写后读的操作数相关n顺序流动时：j读段是停下来等待，直到h到达写段并完成后，才流动。推后读。n优点：控制比较简单n相关后流水线的吞吐率和效率下降入指令地址：顺序流动和异步流动指令j的源操作数地址与指令h的目的操作数地址一样时，h和j就发生先写后读的操作数相关。读段写段相关直接通路12345678nkkjjjm空il空hk空iihh可以不顺序流

21、动的顺序流动的推后判出j、h相关出读段写段相关直接通路12345678nkkjjjm空il空hk空iihh出举例：流动顺序的控制续n异步流动：假设让j之后的指令，如k,l,m,n，只需与j没有相关，就越过j继续向前流动。n会发生其他相关n写-写相关：对同一单元，要求在先的指令先写入，在后的指令后写入的关联。n先读后写相关：对同一单元，要求在先的指令先读出，在后的指令再写入的关联。数据相关S(j)D(i)D(j)D(i)S(i)D(j)S(j)D(i)“先写后读相关S(i)D(i)S(j)D(j)“写-写相关D(i)S(i)D(j)S(j)“先读后写相关D(j)S(i)单条流水线的“先写后读相关

22、的数据重定向BACBACtt+ttt+t单条流水线的“写-写相关的数据重定向BACBACtt+tt+t全局性相关的处置n指的是已进入流水线的转移指令尤其是条件转移指令和其后续指令之间的相关。全局性相关的处置-转移相关 n猜测法 n加快和提早构成条件码n加快单条指令内部的条件码的构成n在一段程序内提早构成条件码适宜循环n采用延迟转移-采用软件进展静态指令调度n加快短循环程序的处置 猜测法i-3i-2i-1ii+1i+2i+3i+4pp+1p+2p+3猜测途径转移不胜利途径转移胜利途径转移不胜利分支转移指令详细分析条件转移指令对流水线性能的影响n对一条有k个功能段的流水线，由于条件转移指令的影响，

23、在最坏情况下，每一次条件转移将呵斥k-1个时钟周期的“断流n假设条件转移指令在普通程序中所占的比例为p，转移胜利的概率为q，因此，对于一个由n条指令组成的程序，在执行这个程序指令的过程中，由于条件转移需求额外添加的时钟周期数：pqn(k-1)t，包括条件转移指令在内的n条指令的总的执行时间为tknpqtknDD) 1() 1(TIF-kn有条件转移影响的流水线的吞吐率：n当n-时，有条件转移影响的流水线的吞吐率：n由于条件转移指令的影响，流水线吞吐率下降的百分比为：tknpqtknnDD) 1() 1(TPIFtkpqD)1(1 (1TPIF-MAX) 1(1) 1(DkpqkpqTPTPTP

24、MAXIFMAXMAXn在典型的标量类机器指令程序中，条件转移指令占20%，其中转移胜利的概率有约占其中的60%。对于一条有8个功能段的指令流水线，流水线的最大吞吐率要下降：n假设段数为10，那么下降：%46) 18(*60. 0*20. 01) 18(*60. 0*20. 0D8%52) 110(*60. 0*20. 01) 110(*60. 0*20. 0D10采取的措施n延迟转移技术和指令取消技术nSUN：SPARC，HP：HP-RISC，SGI：MIPSn静态转移预测技术nTI:SuperSPARCn动态转移预测技术流水机器的中断处置n中断的出现概率比条件转移的概率要低。n处置中断的主

25、要问题：断点现场的维护和恢复，而不是缩短流水线的断流时间。n不准确断点：无论指令I在流水线的哪一段发生中断，都不再允许尚未进入流水线的后续指令再进入，但已在流水线的一切指令仍继续流动到执行终了，然后才转入中断处置程序。nIBM 360/91n不利于编程和程序的排错n准确断点：无论指令I是在流水线中的哪一段呼应中断，给中断现场全都是对应I的，I之后流入流水线内的指令的原有现场都能保管和恢复。n需设置很多后援存放器n控制逻辑比较复杂S1S2S3S4S5S6S7S8不准确断点准确断点流水线处置机的中断处置相关问题n相关correlation：指在一段程序的相近指令之间有某种关系，这种关系能够影响指令

26、的重叠执行。n数据相关：部分相关n控制相关：全局相关数据相关n在执行本条指令的过程中，假设用到的指令、操作数、变址偏移量等正好是前面指令的执行结果，那么必需等待前面的指令执行完成，并把结果写到主存或通用存放器中之后，本条指令才干执行。n指令相关n主存操作数相关n通用存放器相关n变址相关控制相关n指由条件分支指令、转子程序指令、终断等引起的相关。指令相关n第k+1条指令本身的内容取决于第k条指令的执行结果。n处理：程序中不允许修正指令。主存操作数相关n当指令的执行结果写到主存储器，所读取的操作数也取自主存储器时。n处理：推后处置法通用存放器相关n在存放器-存放器型和存放器-存储器型指令的执行过程

27、中有能够发生通用存放器数据相关。n处理n在通用存放器和运算器之间建立直接数据通路n推后处置n设置公用数据通路变址相关n变址存放器发生相关。n处理n推后分析n设置公用通路总结：数据相关的处理方法n采用硬件或软件的方法尽量防止数据相关发生n是在确保指令正确执行的前提下，推后指令分析n设置公用通路转移相关n无条件转移n普通条件转移n复合条件转移无条件转移相关n普通可以在指令分析器中就执行完成。n对程序执行速度的影响很小。分析k执行k分析k+1取指令L分析L执行L分析L执行L分析L+1执行L+1指令L不在先行指令缓冲栈中：指令L在先行指令缓冲栈中：普通条件转移n对程序执行速度呵斥的影响很大。缓冲深度越

28、深，影响越大。分析k执行k分析k+1分析k+2执行k+2分析k+1分析L执行L分析k+1取指令L分析L执行L转移不胜利胜利，L在指缓栈中胜利，L不在指缓栈中产生转移条件CC根据转移条件CC判别转移能否胜利复合条件转移n本身是一条运算指令，根据结果断定后转移。n影响比普通条件转移指令要大。分析K执行k分析K+1执行k+1分析L执行L取指令L分析L执行L转移不胜利胜利，L在先行指令缓冲栈中胜利，L不在先行指令缓冲栈中转移预测技术n软件“猜测法n不改动硬件构造，只修正编译器。n硬件“猜测法n增设指令分析器n两个先行指令缓冲栈n增设先行目的缓冲栈短循环程序的处置n短循环程序的三个条件n循环体的长度小于

29、等于先行指令缓冲栈的深度n循环次数的控制采用计数转移指令n控制循环的条件转移指令普通是向后转移的指令短循环程序的处置续n处理好三个问题n指令分析器如何发现短循环程序n如何控制短循环程序在先行指令缓冲栈中不被去除n如何控制循环体的执行次数短循环程序的处置续n在指令系统中设置专门的短循环程序的开门指令和关门指令n用专门的硬件来识别短循环程序流水线调度-非线性流水线 n由于非线性流水线有反响回路，因此会出现几个义务争用同一功能段的冲突景象n前馈线、后馈线n功能部件冲突流水线冲突S1S2S3S4S5入入出出非线性流水线的表示n线性流水线可以用流水线衔接图独一表示n衔接图不能用独一表示非线性流水线的任务

30、流程非线性流水线的表示n对非线性流水线，采用：n二维约定表Reservation Table1971年E.S.Davidson提出。1234567891XX2XXX3X4XX5XX段号 k拍号n一张约定表能够与多个流水线衔接图相对应一个流水线衔接图对应与多张约定表非线性流水线的冲突n向一条非线性流水线的输入端延续输入两个义务之间间隔称为非线性流水线的启动间隔或等待时间。段号 k 拍号n1234567891011121314151X1X2X3X1X2X32X1X1X2X2X1X3X3X2X33X1X2X34X1X1X2X2X3X35X1X1X2X2X3X3启动间隔为3的流水线冲突情况非线性流水线

31、的冲突非线性流水线的调度n是要找出一个最小的循环周期，按照这个周期向流水线输入新义务。流水线的各个功能段不会发生冲突，而且流水线的吞吐率和效率最高举例1 2 3 4 5 6 7 8 91 *2* *3*4* *5* *段号k拍号n约定表延迟制止表F(Forbidden List)1,5,6,8,相邻两个义务的间隔拍数不能为1，5，6，8冲突向量C(Collision Vector)第i位的形状用以表示与当时相隔i拍给流水线送入后继义务能否会发生功能段的运用冲突。如不发生，0，否那么，1 C=(10110001) 初始冲突向量1 1构成约定表构成约定表 指令总拍数为指令总拍数为n n，流水线有，

32、流水线有k k个段，那么构个段，那么构成成n nk k的约定表，段的运用情况用的约定表，段的运用情况用“表示。表示。 约定表如下：约定表如下：543 21987654382716tS2 2由约定表构成制止表由约定表构成制止表F F F= F=各段中冲突间隔拍数各段中冲突间隔拍数 本例：本例： F=1F=1，5 5，6 6，88543 21987654382716tS543 21987654382716tS56813 3由制止表由制止表F F构成初始冲突向量构成初始冲突向量C0C0 C0= C0=cNc0cNc0，ci=1ci=1冲突，冲突，=0=0不冲突。不冲突。 本例：本例：C0 =C0 =

33、1011000110110001。4 4由初始冲突向量由初始冲突向量C0C0构成形状转换图构成形状转换图 a.C0 a.C0每过一拍逻辑右移一位，假设移出每过一拍逻辑右移一位，假设移出0 0，那么允，那么允许后续指令进入流水线，再与许后续指令进入流水线，再与C0C0按位按位“或，构成新或，构成新的冲突向量的冲突向量CiCi；10110001101101111011110110111011初始形状初始形状3427 2 2拍后，新指令拍后，新指令( (-I2 )-I2 )进入后：进入后：54321987654321tS643I1I1与与I3I3的的F=3,4,6F=3,4,6，I2I2与与I3I3

34、的的F=1,5,6,8, F=1,5,6,8, 新新F=1,3,4,5,6,8F=1,3,4,5,6,8，C2=(10111101)C2=(10111101)。 留意：留意：CiCi为第为第i i拍后流水线的冲突向量，此时流水拍后流水线的冲突向量，此时流水线中已有两条指令，线中已有两条指令，CiCi用于判别第三条指令的进入。用于判别第三条指令的进入。1011000110110111101111011011101110111111初始形状初始形状34422777 b. b.各各CiCi再每过一拍逻辑右移一位，假设移再每过一拍逻辑右移一位，假设移出出0 0，允许后续指令进入，再与，允许后续指令进入

35、，再与C0C0按位按位“或，或，构成新的冲突向量构成新的冲突向量CijCij； 留意：留意：CijCij为第为第i+ji+j拍后流水线的冲突向量，此时流拍后流水线的冲突向量，此时流水线中已有三条指令，水线中已有三条指令， CijCij用于判别第四条指令的进用于判别第四条指令的进入。入。 对对C2C2，再，再2 2拍后，新指令拍后，新指令( (-I3)-I3)进入后：进入后： 42 154321987654321tS98I1I1与与I4I4的的F=1,2,4F=1,2,4， I2I2与与I4I4的的F=3,4,6,F=3,4,6,I3I3与与I4I4的的F=1,5,6,8,F=1,5,6,8,新

36、新F=1,2,3,4,5,6,8F=1,2,3,4,5,6,8，C22=(10111111)C22=(10111111)。643 留意：留意：CijCij为第为第i+ji+j拍后流水线的冲突向量，此时流拍后流水线的冲突向量，此时流水线中已有三条指令，水线中已有三条指令， CijCij用于判别第四条指令的进用于判别第四条指令的进入。入。 c. c.反复上一步骤，直到不再生成新的冲突反复上一步骤，直到不再生成新的冲突向量为止。向量为止。1011000110110111101111011011101110111111初始形状初始形状343422777775 5找出最加调度方案找出最加调度方案 从各个

37、闭合回路中找出平均间隔最小的一个。从各个闭合回路中找出平均间隔最小的一个。1011000110111101101111111011011110111011277277744331011000100101100右移2位101111011011000110111101101111111011011110111011277277744331011000100101100右移2位101111011011000100101111右移2位101111111011000110111101101111111011011110111011277277744331011000100101100右移2位101111

38、011011000100101111右移2位101111111011000100010110右移3位101101111011000110111101101111111011011110111011277277744331011000100101100右移2位101111011011000100101111右移2位101111111011000100010110右移3位101101111011000100001011右移4位10111011调度方案平均间隔拍数调度方案平均间隔拍数（2，2，7）3.67（3，7）5.00（2，7）4.50（4，3，7）4.67（3，4）3.50（4，7）5.50（

39、4，3）3.50（7）7.00（3，4，7）4.671234567891011121314151X1X2X3X1X22X1X1X2X2X1X3X3X2X33X1X2X34X1X1X2X2X3X35X1X1X2X2X3X3按(3,4)进展调度 11111222221333332444436455666655612 4355456按(3,4)进展调度 TP=6/26 Sp=(6*10)/26=30/13 e=(6*10)/(26*5)=60/130=6/1311111222221333332444436455666655612 4 355456按(4,3)进展调度 TP=6/27 Sp=(6*10

40、)/27=20/9 e=(6*10)/(27*5)=12/27n举例：一条有4个流水段的非线性流水线，每个流水段的延迟时间都相等，它的约定表如以下图： 1234567S1XXS2XXS3XXS4X1写出流水线的制止向量和初始冲突向量2画出调度流水线的形状图3求流水线的最小启动循环和最小启动间隔4求平均启动间隔最小的恒定循环。n解：1制止向量为2，4，6n冲突向量：用二进制表示，长度是制止向量的最大间隔。冲突向量C=C1C2C3C4C5C6，由制止向量，C2=C4=C6=1，其他位为0，冲突向量为n C=101010。n 2由冲突向量构造一张图：将C放到一个6位逻辑右移移位器，当从移位器移出0，

41、用移位器中的值与初始冲突向量做“按位或，得到一个新的冲突向量。当移位器移出1，不做任何处置。反复这个步骤。对产生的每一个新的冲突向量做同样处置。在初始冲突向量和一切构成的冲突向量之间，箭头衔接。1010101111111011111010117*157*3537*当右移2、4、6位，时移出位为1，表示用这些启动间隔输入新义务要发生冲突，不做任何处置。当右移1、3、5和大于等于7位时，移出位是0，表示用这些启动间隔输入新义务不会发生冲突。7*表示大于等于753从形状图中可以找到许多不发生流水段冲突的启动循环。，只需找到简单循环，进而确定平均启动间隔最小的启动循环。它们是： 1，7、3，5，7、5

42、，7等简单循环平均启动距离（1，7）4（3，5）4（5，7）6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）7最小启动循环是具有最小平均最小启动间隔的启动循环。n最小循环为1，7、3，5n最小恒定循环为5 时间流水12345678910111213141516S1X1X2X1X3X2X4X3S2X1X2X1X2X3X4X3S3X1X1X2X2X3X3X4S4X1X2X3X4最小启动循环为3，5的流水线任务形状 时间流水段123456789101112131415S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X

43、4最小启动循环为1，7的流水线任务形状 时间流水段123456789101112131415S1X1 X2X1 X3X2 S2X1 X1X2X2X3 S3X1 X1 X2X2 X3 X3S4X1 X2 X3恒定启动循环5的流水线任务形状启动周期反复启动周期举例 时间流水段1234567S1XXXS2XXS3XXS4XS1S2S3S41写出流水线的制止向量和初始冲突向量2画出调度流水线的形状图3求流水线的最小启动循环和最小启动间隔4求平均启动间隔最小的恒定循环。7*101100101101101111111111111110552527*7*7*7*11简单循环平均启动距离（1，7）4（1,1,7）3（2，7）4.5（2，5）3.5（2，5，7）4.7（5，7）6（5）5（7）7(5,2,7)4.7 时间流水段123456789101112131415S1X1X2X3X1X2X3X1X2X3X4X5X6X4X5X6S2X1X2X3X1X2X3X