第05章标量处理机 eng2

1、central south university余腊生 版权所有，违者必究 空间并行性设置多个独立的操作部件多操作部件处理机超标量处理机 时间并行性采用流水线技术。不增加或只增加少量硬件就能使运算速度提高几倍流水线处理机超流水线处理机5.2 流水线技术 Pipelining central south university2022-4-21余腊生 版权所有，违者必究5-2流水线的表示方法流水线的表示方法 流水线的表示法有三种：连接图、时空图、预约表。主要考虑前二种。1、简单流水线的连接图表示 流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。一

2、个流水阶段与另一个流水阶段相连形成流水线。指令从流水线一端进入，经过流水线的处理，从另一端流出。 有些复杂指令 在执行阶段也采用流水线方式工作，称为操作流水线。取指令译码执行保存结果t1t2t3t4central south university余腊生 版权所有，违者必究2、一种指令流水线 一般4至12个流水段，等于及大于8个流水段的称为超流水线处理机取指形成操作数地址译码取操作数执行保存结果central south university余腊生 版权所有，违者必究3、流水线的时空图采用“时空图”表示流水线的工作过程。在时空图中，横坐标表示时间，也就是输入到流水线中的各个任务在流水线中所经过的

3、时间。当流水线中各个流水段的执行时间都相等时，横坐标被分割成相等长度的时间段。纵坐标表示空间，即流水线的每一个流水段 一条简单流水线的时空图：分析k分析k+1 分析k+2 分析k+3执行k执行k+1 执行k+2 执行k+3时间空间0t1t2t3t4t5central south university余腊生 版权所有，违者必究 一个浮点加法器流水线的时空图(由求阶差、对阶、尾数加和规格化4个流水段组成)：ED1时间空间0t1t2t3t4t5ED2 ED3 ED4 ED5EA1 EA2 EA3 EA4 EA5MA1 MA2 MA3 MA4 MA5NL1 NL2 NL3 NL4 NL5t6t7t8N

4、L：规格化MA：尾数加EA：对阶ED：求阶差central south university2022-4-21余腊生 版权所有，违者必究5-6.12345.n-1 n.12345.n-1 n.12345.n-1 n.12345.n-1 n1234t t0 0 t t0 0 t t0 0 t t0 0T T0=m 0=m t t0 0n n t t0 0T T(m-1) (m-1) t t0 0(n-1) (n-1) t t0 0填入填入 正常正常 排空排空 流水时空图流水时空图空间空间时间时间central south university2022-4-21余腊生 版权所有，违者必究5-72、

5、流水线特点、流水线特点： 1）流水一定重叠，比重叠更苛刻。）流水一定重叠，比重叠更苛刻。 2）一条流水线通常有多个流水段组成。）一条流水线通常有多个流水段组成。 3）每段有专用功能部件，各部件顺序连接，不断流。）每段有专用功能部件，各部件顺序连接，不断流。 4）流水线有建立时间、满载时间、排空时间，）流水线有建立时间、满载时间、排空时间， 5）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。 6）给出指标如最大吞吐率，为满负载最佳指标。）给出指标如最大吞吐率，为满负载最佳指标。建立时间：建立时间：在流水线开始时有一段流水线填入时间，使得流水线填

6、满。在流水线开始时有一段流水线填入时间，使得流水线填满。正常流动时间：正常流动时间：流水线正常工作，各功能段源源不断满载工作。流水线正常工作，各功能段源源不断满载工作。排空时间：排空时间：在流水线第一条指令结束时，其他指令还需要一段释放时间。在流水线第一条指令结束时，其他指令还需要一段释放时间。central south university2022-4-21余腊生 版权所有，违者必究5-81234出出入入非线性流水线非线性流水线流水的分级、分类流水的分级、分类分级分级：（处理的级别分类）：（处理的级别分类）v 部件级：将复杂的算逻运算组成流水工作方式；部件级：将复杂的算逻运算组成流水工作方式

7、； v 指令级：把一条指令解释过程分成多个子过程指令级：把一条指令解释过程分成多个子过程 ；v 处理机级：每个处理机完成某一专门任务，各个处理机所处理机级：每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中得到的结果需存放在与下一个处理机所共享的存储器中 其他分类：其他分类： 功能：单功能流水线（如功能：单功能流水线（如CRAY-1）、多功能流水线）、多功能流水线 （如（如TI-ASC） 工作方式：静态流水线、动态流水线工作方式：静态流水线、动态流水线 连接方式：线性、非线性连接方式：线性、非线性 处理数据：标量流水、向量流水处理数据：标量流水、向量流水c

8、entral south university余腊生 版权所有，违者必究 1、线性流水线与非线性流水线 流水线的各个流水段之间是否有反馈信号 线性流水线(Linear Pipelining)每个流水段都流过一次，且仅流过一次 非线性流水线(Nonlinear Pipelining)在流水线的某些流水段之间有反馈回路或前馈回路 线性流水线能够用流水线连接图唯一表示非线性流水线必须用流水线连接图流水线预约表等共同表示S1输入S2S3输出前馈回路反馈回路一种简单的非线性流水线5.2.2 流水线的分类central south university余腊生 版权所有，违者必究 2、按照流水线的级别来分

9、处理机级流水线, 又称为指令流水线 (Instruction Pipelining)例如：在采用先行控制器的处理机中，各功能部件之间的流水线先行指令缓冲栈输入先行控制方式中的指令流水线先行指令分析器先行读数栈先行操作栈取指译码取操作数指令执行部件后行写数栈输出执行写结果central south university余腊生 版权所有，违者必究求阶差输入输出t1对阶尾数加规格化t2t3t4P1输入任务1MMP2任务2MP3任务3输出处理机之间的流水线称为宏流水线 (Macro Pipelining)每个处理机对同一个数据流的不同部分分别进行处理部件级流水线（操作流水线），如浮点加法器流水线cen

10、tral south university余腊生 版权所有，违者必究 3、单功能流水线与多功能流水线 单功能流水线：只能完成一种固定功能的流水线Cray-1计算机中有12条；YH-1计算机有18条；Pentium有一条5段的定点和一条8段的浮点流水线；Pentium有三条指令流水线，其中两条定点指令流水线，一条浮点指令流水线。 多功能流水线：流水线的各段通过不同连接实现不同功能 Texas公司的ASC计算机中的8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。central south university余腊生 版权所有，违者必究 A

11、B A B A B A B 输入 输入 输入 输入 求阶差 求阶差 求阶差 求阶差 对阶 对阶 对阶 对阶 尾数加 尾数加 尾数加 尾数加 规格化 规格化 规格化 规格化 尾数乘 尾数乘 尾数乘 尾数乘 累加 累加 累加 累加 输出 输出 输出 输出 g=f(A,B) 定点乘 浮点加 浮点点积 (a)功能段间的互连 (b)定点乘法 (c)浮点加法 (d)浮点点积 central south university余腊生 版权所有，违者必究 4、静态流水线与动态流水线静态流水线：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能。只有连续出现同一种运算时，流水线

12、的效率才能得到充分的发挥。动态流水线：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。central south university2022-4-21余腊生 版权所有，违者必究5-15.1234.n-1 n.1234.n-1 n.1234.n-1n.1234.n-1 n12345867.1234.n-1 n.1234.n-1 n时间时间空间空间(段号段号)浮加浮加一一 二二 三三 四四二二 三三一一二二一一一一定乘定乘.静态多功能流水线时静态多功能流水线时-空图空图静态流水线：静态流水线：只有当进入的是一串相同运算的指令时，流水的只有当进入的是一串相同运算的指令

13、时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。进行流水处理。 central south university2022-4-21余腊生 版权所有，违者必究5-16.12345.n-1 n.12345.n-1 n.12345.n-1 n.12345.n-1 n12345867.12345.n-1 n.12345.n-1 n时间时间浮加浮加定乘定乘一一二二三三 四四 五五 六六一一二二三三 四四 五五 六六七七一一二二三三 四四 五五一一二二三三 四四动态多功能流水线时动态多功能流水线时-空图空图区别：区别：如果

14、从软硬功能分配的观点上来看，静态流水线其实如果从软硬功能分配的观点上来看，静态流水线其实是把功能负担较多地加到软件上，以简化硬件，动态流水线是把功能负担较多地加到软件上，以简化硬件，动态流水线则是把功能负担较多地加在硬件上，以提高流水的效能。则是把功能负担较多地加在硬件上，以提高流水的效能。central south university余腊生 版权所有，违者必究 5、流水线的其他分类方法按照数据表示方式：标量流水线和向量流水线按照控制方式：同步流水线和异步流水线顺序流水线与乱序流水线：乱序流水线又称为无序流水线、错序流水线或异步流水线等S1就绪回答S2就绪回答S3就绪回答输出就绪回答输入ce

15、ntral south university余腊生 版权所有，违者必究 Example 1central south university2022-4-21余腊生 版权所有，违者必究5-19Example 2 在静态、加乘双功能流水线上实现。在静态、加乘双功能流水线上实现。41)(iiiba143265xyz乘乘加加 in the pipeline ,stage 1 and 5 needs 3 time units： algorithmsalgorithms：消除相关性，可并行执行的操作先执行；消除相关性，可并行执行的操作先执行； 使流水线尽可能长时间执行同一种功能。使流水线尽可能长时间执行同

16、一种功能。 the best orderthe best order： x1=a1+b1x1=a1+b1，x2=a2+b2,x3=a3+b3,x4=a4+b4x2=a2+b2,x3=a3+b3,x4=a4+b4； y1=x1y1=x1* *x2,y2=x3x2,y2=x3* *x4x4； z=y1z=y1* *y2y2central south university余腊生 版权所有，违者必究 衡量流水线性能的主要指标有：吞吐率、加速比和效率1 1、吞吐率（、吞吐率（ThoughPutThoughPut） 求流水线吞吐率的最基本公式： TP = n / Tkn为任务数, Tk为完成n个任务所用时

17、间 各段执行时间相等，输入连续任务情况下完成n个连续任务需要的总时间为：Tk= (k+n-1) t k为流水线的段数， t为时钟周期线性流水线的性能分析线性流水线的性能分析central south university余腊生 版权所有，违者必究1timespaceS123 n-1 nS2S3S4123 n-1 n123 n-1 n123 n-1 nkt(n-1) tnt(k-1)tTcentral south university余腊生 版权所有，违者必究 Throughput ：最大吞吐率为：各段执行时间不相等、输入连续任务情况下：吞吐率为：最大吞吐率为：tnknTP) 1(nTPLimn

18、knttmax() 11),max() 1(211kkiitttntnTP ),max(121maxktttTP central south university余腊生 版权所有，违者必究流水线各段执行时间不相等的解决办法S1输入t1=tS2t2=3tS3t3=tS4t4=t输出1时间空间S1S2S3S4Sti(n-1)t2Tk23n123n123n123ncentral south university余腊生 版权所有，违者必究 一是将“瓶颈”流水段细分(如果可分的话)：/合并？ 二是将 “瓶颈”流水段重复设置：S1输入输出tS2-1tS2-2tS2-3tS3tS4tS2(3t)S1输入输出

19、t1=tS2-1S2-1S2-1S3S4t3=tt4=tt2=3tcentral south university2022-4-21余腊生 版权所有，违者必究5-25 如何解决瓶颈问题？如何解决瓶颈问题？ a. a.将此段进一步细化，保证细化后的段与其将此段进一步细化，保证细化后的段与其它段处理时间相同或相近；它段处理时间相同或相近；123a3b43c1471014710S s3b s3a s2 s1t1t12t17T s3c s46811 1235911 122 3592681471035911 122681471035911 122681471035911 122681471035911

20、12268central south university2022-4-21余腊生 版权所有，违者必究5-26147101471014710S s3b s3a s2 s1t1t12t17T s3c s46811 1235911 122 35926825811369121471035911 12268 b. b.并联设置多套功能部件，通过并联设置多套功能部件，通过控制器控制器进行调度。进行调度。1243b3a3ct3t3ttt 此方法运行效果与过程细化方法效果相同。此方法运行效果与过程细化方法效果相同。central south university余腊生 版权所有，违者必究 2 2、加速比（、

21、加速比（SpeedupSpeedup） 计算流水线加速比的基本公式：S = 顺序执行时间T0 / 流水线执行时间Tk 各段执行时间相等，输入连续任务情况下加速比为： 最大加速比为： 各段执行时间不等，输入连续任务情况下实际加速比为：1) 1(nknktnktnkSSLimk nknknmax1central south university余腊生 版权所有，违者必究K=6K=10任务个数加速比10246811 248 16 32 64 128Snttntttiikiikk 11121() max(, ,）central south university余腊生 版权所有，违者必究3 3、效率（、

22、效率（EfficiencyEfficiency）计算流水线效率的一般公式：各流水段执行时间相等，输入n个连续任务流水线的效率为： 流水线的最高效率为：各流水段执行时间不等，输入n个连续任务流水线的效率为：kTkTknE0个流水段的总的时空区个任务占用的时空区1) 1(nkntnkktnkE11maxnknLimEncentral south university余腊生 版权所有，违者必究 流水线各段的设备量或各段的价格不相等时：流水线的效率为：即： 其中，ai M流水性能才发挥得更好流水性能才发挥得更好central south university2022-4-21余腊生 版权所有，违者必究

23、5-39例例4 4 在静态、加乘双功能流水线上实现。在静态、加乘双功能流水线上实现。41)(iiiba143265xyz乘乘加加 流水线结构如下：流水线结构如下： 实现算法：实现算法：消除相关性，可并行执行的操作先执行；消除相关性，可并行执行的操作先执行； 使流水线尽可能长时间执行同一种功能。使流水线尽可能长时间执行同一种功能。 最佳最佳实现顺序：实现顺序： x1=a1+b1x1=a1+b1，x2=a2+b2,x3=a3+b3,x4=a4+b4x2=a2+b2,x3=a3+b3,x4=a4+b4； y1=x1y1=x1* *x2,y2=x3x2,y2=x3* *x4x4； z=y1z=y1*

24、*y2y2central south university2022-4-21余腊生 版权所有，违者必究5-40 T TP P= = S SP P= = E E = =7/(17t)7/(17t)(4(4* *3t+33t+3* *5t)/(17t)=27/17=1.885t)/(17t)=27/17=1.88(3(3* *4t+34t+3* *5t)/(65t)/(6* *17t)=9/34=26.4%17t)=9/34=26.4%134S s4 s3 s2 s1t6t12T221212121333313421342 s5 s6213(a1+b1)(a2+b2)(a3+b3)(a4+b4)(a

25、1+b1)(a2+b2)(a3+b3)(a4+b4)(a1+b1)(a2+b2)(a3+b3)(a4+b4)t17加法加法乘法乘法1乘法乘法2a1b1a2b2a3b3(a1+b1)(a2+b2)(a3+b3)(a4+b4)(a1+b1)(a2+b2)(a3+b3)(a4+b4)a4b4central south university2022-4-21余腊生 版权所有，违者必究5-41 结果分析：结果分析： 流水线适用范围？流水线适用范围？ 流水线适合于操作相同、操作数间无相关性的多流水线适合于操作相同、操作数间无相关性的多个指令的执行。个指令的执行。 功能切换必须等待排空后进行。功能切换必须等

26、待排空后进行。（静态通病）（静态通病） 如何提高流水线效率？如何提高流水线效率？ 尽量细化各功能段，尽量细化各功能段，尽量减少功能切换，尽量减尽量减少功能切换，尽量减少数据相关，尽量增加一次处理的指令数量。少数据相关，尽量增加一次处理的指令数量。 建立、排空时间过多；建立、排空时间过多； （流水线断流（流水线断流数据相关和操作变换数据相关和操作变换 ） 对此题动态流水线结果如何？对此题动态流水线结果如何？（减少（减少2 2个个tt）课堂作业 stage 1 : 1 t ,Stage 2: 3 t , stage 3: 2 t, stage 4 :1 t, 每隔每隔3 t输入一个任务输入一个任务

27、,求求Tp,E,Spcentral south university2022-4-21余腊生 版权所有，违者必究5-42流水线的实现与控制流水线的实现与控制一、流水线的中断处理一、流水线的中断处理1.1.解决问题解决问题 中断现场的保护与恢复。中断现场的保护与恢复。 处理时不在乎断流时间长短。处理时不在乎断流时间长短。（概率低，不可预知）概率低，不可预知）2.2.解决方法解决方法（1 1）不精确断点法）不精确断点法 断点精确到中断请求时最后进入流水线的那条指令。断点精确到中断请求时最后进入流水线的那条指令。 特点：特点：硬件开销小，控制简单，程序排错不方便。硬件开销小，控制简单，程序排错不方便

28、。central south university2022-4-21余腊生 版权所有，违者必究5-43（2 2）精确断点法）精确断点法 断点精确到中断请求时已进入流水线的各条断点精确到中断请求时已进入流水线的各条指令。指令。 硬件要求：硬件要求：增设大量的后援寄存器。增设大量的后援寄存器。central south university2022-4-21余腊生 版权所有，违者必究5-44Nonlinear pipelining什么是非线性流水线？ 如果存在反馈回路，当一个任务在流水线中流过时，在同一个流水段中可能要经过多次。不能每一个时钟周期向流水线输入一个新任务。这样的流水线就是非线性流水线

29、。 非线性流水线的调度问题就是要解决要隔多少个时钟周期向流水线输入一个新任务才能使流水线 的各个流水段都不发生冲突。 表示一个非线性流水线需要用到连接图和预约表。如图：central south university2022-4-21余腊生 版权所有，违者必究5-45S1S2S3S4输出输入反馈线 时间流水段1234567S1XXXS2XXS3XXS4X非线性流水线的连接图非线性流水线的预约表central south university2022-4-21余腊生 版权所有，违者必究5-46 预约表横坐标表示流水线的时钟周期，纵坐标表示流水线的各个流水段，中间有“X”表示该流水段在这一个时钟周

30、期处于工作状态，空白表示该流水段在这一个时钟周期不工作。 一行中可以有多个“X”，表示一个任务在不同时钟周期重复使用了同一流水段；一列中有多个“X”表示在同一个时钟周期同时占用了多个流水段。预约表的行数是流水线的段数，预约表的列数是一个任务从进入流水线到流水线中输出所经过的时钟周期数。 向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离，以时钟周期数表示。 当使用3为启动距离，则对上述的流水线，将在某些流水段发生冲突，即两个以上任务同时争用一个流水段。引起非线性流水线流水段冲突的启动距离称为禁启动止距离。 不发生冲突的启动距离是一个循环数列。使非线性流水线的任何

31、一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。central south university2022-4-21余腊生 版权所有，违者必究5-47X3X2X1S4X4X2X3X1X2X1S3X3X4X2X3X1X2X1S2X2X3X4X1X2X3X1X2X1S11110987654321 时间流水段启动距离为3的流水线冲突情况两个任务争用一个流水段S1两个任务争用一个流水段S1central south university2022-4-21余腊生 版权所有，违者必究5-48X3X2X1X1S4X2X2X2X1S3X3X1X1S2X2X1X1X1S1111098

32、7654321 时间流水段启动距离为5的流水线预约表X2X3启动周期重复启动周期（5）是一个循环，称为恒定循环。central south university2022-4-21余腊生 版权所有，违者必究5-49时间流水段12345678910111213141516S1X1X2X1X2X1X2X3X4X3X4X3X4S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4启动距离为（1，7）循环时的流水线预约表要正确地调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。所有禁止启动启动距离组合在一起成为一个数列，称为禁止向量。central sout

33、h university2022-4-21余腊生 版权所有，违者必究5-50 由预约表得到禁止向量的方法： 将预约表的每一行中任意两个“X”之间的距离都计算出来，去掉重复的，这种数组成的一个数列就是这条非线性流水线的禁止向量。 例如：前述的非线性流水线，其禁止向量为 （3，4，6）。 把一个启动循环内的所有启动距离相加，然后再除以这个循环内的启动距离个数，就得到这个启动循环的平均启动距离。 非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有流水段在任何时间都没有冲突。central south

34、 university2022-4-21余腊生 版权所有，违者必究5-51 例子：一条有4个流水段的非线性流水线，每个流水段的延迟时间都相等，它的预约表如下图： 时间流水段1234567S1XXS2XXS3XXS4X（1）写出流水线的禁止向量和初始冲突向量（2）画出调度流水线的状态图（3）求流水线的最小启动循环和最小启动距离（4）求平均启动距离最小的恒定循环。central south university2022-4-21余腊生 版权所有，违者必究5-52 解：（1）禁止向量为（2，4，6）冲突向量：用二进制表示，长度是禁止向量的最大距离。冲突向量C=（C1C2C3C4C5C6），由禁止向量

35、，C2=C4=C6=1，其余位为0，冲突向量为 C=（101010）。 （2）由冲突向量构造一张图：将C放到一个6位逻辑右移移位器，当从移位器移出0，用移位器中的值与初始冲突向量做“按位或”，得到一个新的冲突向量。当移位器移出1，不做任何处理。重复这个步骤。对产生的每一个新的冲突向量做同样处理。在初始冲突向量和所有形成的冲突向量之间，箭头连接。central south university2022-4-21余腊生 版权所有，违者必究5-531010101111111011111010117*157*3537*当右移2、4、6位，时移出位为1，表示用这些启动距离输入新任务要发生冲突，不做任何处

36、理。当右移1、3、5和大于等于7位时，移出位是0，表示用这些启动距离输入新任务不会发生冲突。7*表示大于等于75central south university2022-4-21余腊生 版权所有，违者必究5-54（3）从状态图中可以找到许多不发生流水段冲突的启动循环。，只要找到简单循环，进而确定平均启动距离最小的启动循环。它们是： （1，7）、（3，5，7）、（5，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最小启动循环是具有最小平均最小启动距离的启动循环。central south university2022-4

37、-21余腊生 版权所有，违者必究5-55 最小循环为（1，7）、（3，5） 最小恒定循环为（5） 时间流水12345678910111213141516S1X1X2X1X3X2X4X3S2X1X2X1X2X3X4X3S3X1X1X2X2X3X3X4S4X1X2X3X4最小启动循环为（3，5）的流水线工作状态central south university2022-4-21余腊生 版权所有，违者必究5-56 时间流水段123456789101112131415S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4最小启动循环为

38、（1，7）的流水线工作状态central south university2022-4-21余腊生 版权所有，违者必究5-57 时间流水段123456789101112131415S1X1 X2X1 X3X2 S2X1 X1X2X2X3 S3X1 X1 X2X2 X3 X3S4X1 X2 X3恒定启动循环（5）的流水线工作状态启动周期重复启动周期central south university2022-4-21余腊生 版权所有，违者必究5-58例例2 非线性流水线调度非线性流水线调度某流水线结构如下：某流水线结构如下：S1S2S3S4S5入入出出 流水线调度方案如下：流水线调度方案如下：cen

39、tral south university2022-4-21余腊生 版权所有，违者必究5-59（1 1）形成预约表）形成预约表 指令总拍数为指令总拍数为n，流水线有，流水线有k个段，则形成个段，则形成nk的预约表，段的使用情况用的预约表，段的使用情况用“”表示。表示。 预约表如下：预约表如下：543 21987654382716tS转上页central south university2022-4-21余腊生 版权所有，违者必究5-60（2 2）由预约表形成禁止表）由预约表形成禁止表F F F= F=各段中冲突间隔拍数各段中冲突间隔拍数 本例：本例： F=1F=1，5 5，6 6，88543

40、21987654382716tS543 21987654382716tS5681central south university2022-4-21余腊生 版权所有，违者必究5-61（3 3）由禁止表）由禁止表F F形成初始冲突向量形成初始冲突向量C C0 0 C C0 0= =（c cN Nc c0 0），），c ci i=1=1冲突，冲突，=0=0不冲突。不冲突。 本例：本例：C C0 0 = =（1011000110110001）。）。（4 4）由初始冲突向量）由初始冲突向量C C0 0形成状态转换图形成状态转换图 a.a.C C0 0每过一拍逻辑右移一位，若移出每过一拍逻辑右移一位，若移

41、出0 0，则允许后续，则允许后续指令进入流水线，再与指令进入流水线，再与C C0 0按位按位“或或”，形成新的冲突，形成新的冲突向量向量C Ci i；10110001101101111011110110111011初始状态初始状态3427central south university2022-4-21余腊生 版权所有，违者必究5-62 2拍后，新指令拍后，新指令(-I2-I2 )进入后：进入后：54321987654321tS643I1I1与与I3I3的的F=3,4,6F=3,4,6，I2I2与与I3I3的的F=1,5,6,8, F=1,5,6,8, 新新F=1,3,4,5,6,8F=1,3

42、,4,5,6,8，C C2 2=(10111101)=(10111101)。 注意：注意：C Ci i为第为第i拍后流水线的冲突向量，此时流水线拍后流水线的冲突向量，此时流水线中已有两条指令，中已有两条指令，C Ci i用于判断第三条指令的进入。用于判断第三条指令的进入。central south university2022-4-21余腊生 版权所有，违者必究5-631011000110110111101111011011101110111111初始状态初始状态34422777 b.b.各各C Ci i再每过一拍逻辑右移一位，若移出再每过一拍逻辑右移一位，若移出0 0，允许后续指令进入，再与

43、允许后续指令进入，再与C C0 0按位按位“或或”，形成，形成新的冲突向量新的冲突向量C Cijij； 注意：注意：C Cijij为第为第i+j拍后流水线的冲突向量，此时流水拍后流水线的冲突向量，此时流水线中已有三条指令，线中已有三条指令， C Cijij用于判断第四条指令的进入。用于判断第四条指令的进入。central south university2022-4-21余腊生 版权所有，违者必究5-64 对对C C2 2，再，再2 2拍后，新指令拍后，新指令( (-I3-I3) )进入后：进入后： 42 154321987654321tS98I1I1与与I4I4的的F=1,2,4F=1,2,

44、4， I2I2与与I4I4的的F=3,4,6,F=3,4,6,I3I3与与I4I4的的F=1,5,6,8,F=1,5,6,8,新新F=1,2,3,4,5,6,8F=1,2,3,4,5,6,8，C C2222=(10111111)=(10111111)。643 注意：注意：C Cijij为第为第i+j拍后流水线的冲突向量，此时流水拍后流水线的冲突向量，此时流水线中已有三条指令，线中已有三条指令， C Cijij用于判断第四条指令的进入。用于判断第四条指令的进入。central south university2022-4-21余腊生 版权所有，违者必究5-65 c.c.重复上一步骤，直到不再生成

45、新的冲突向重复上一步骤，直到不再生成新的冲突向量为止。量为止。1011000110110111101111011011101110111111初始状态初始状态34342277777（5 5）找出最加调度方案）找出最加调度方案 从各个从各个闭合回路闭合回路中找出平均间隔最小的一个。中找出平均间隔最小的一个。central south university2022-4-21余腊生 版权所有，违者必究5-66 本例中调度方案如下：本例中调度方案如下：调度策略平均间隔拍数调度策略平均间隔拍数(2, 7)4.50(3, 4, 3, 7) 4.25(2, 2, 7)3.67(4, 3, 7)4.67(3,

46、 4)3.50(4, 7)5.00(3, 7)5.00(7)7.00(3, 4, 7)4.67 可见，调度方案为（可见，调度方案为（3，4）。）。 对非对非C0开始的调度方案由开始的调度方案由流水线控制器流水线控制器完成控制的完成控制的过渡。过渡。central south university2022-4-21余腊生 版权所有，违者必究5-672.2.多功能非线性流水线调度多功能非线性流水线调度 如：加（如：加（A）、乘（）、乘（B）双功能流水线预约）双功能流水线预约表如下：表如下：1234 5S1ABA BS2ABS3BABAV VAAAA =(0110)=(0110)， V VABAB

47、=(1011)=(1011)；V VBBBB =(0110)=(0110)， V VBABA =(1010)=(1010)。V VABAB表示先执行表示先执行B B后执行后执行A A；V VBABA表示先执行表示先执行A A后执行后执行B B。 M MA A为为A A的初始冲突矩阵的初始冲突矩阵( (从从A A开始开始) )，包含，包含V VAAAA和和V VBABA； M MB B为为B B的初始冲突矩阵的初始冲突矩阵( (从从B B开始开始) )，包含，包含V VBBBB和和V VABAB。central south university2022-4-21余腊生 版权所有，违者必究5-68

48、 a.a.同单功能调度方法，首先生成同单功能调度方法，首先生成n个个初始初始冲突矩阵冲突矩阵（按在先功能分类）。（按在先功能分类）。 调度方案：调度方案：0110101010110110MAMB b.b.再由初始冲突矩阵按后续功能再由初始冲突矩阵按后续功能分类按位右移分类按位右移，形成新的冲突矩阵，最终形成状态转换图。形成新的冲突矩阵，最终形成状态转换图。 新冲突矩阵形成规则：新冲突矩阵形成规则： V VB B= =（V Vxx）|M|MB B，V V后续操作为后续操作为B B； V VA A= =（V Vxx）|M|MA A，V V后续操作为后续操作为A A。central south un

49、iversity2022-4-21余腊生 版权所有，违者必究5-69011010101011011010110111011111111111011101111010B1,B3A4MAB4B4B1B4MBB5A5A3B1,B3A3A4A1A4 c.c.从闭合回路中找出调度方案（按功能顺序分成从闭合回路中找出调度方案（按功能顺序分成几种）。几种）。central south university2022-4-21余腊生 版权所有，违者必究5-703.3.利用延迟线改善性能利用延迟线改善性能 目的：目的：通过修改预约表，减少瓶颈段冲突通过修改预约表，减少瓶颈段冲突概率。概率。 分析：分析：设设num

50、=max各段使用的次数各段使用的次数;拍启动一个任务每隔最大启动速度numnum1 结论：结论：若实际调度速度最大启动速度，则流水线若实际调度速度最大启动速度，则流水线性能可改善。性能可改善。 方法：方法：以以接近或等于最大启动速度接近或等于最大启动速度为目标，重点分为目标，重点分析析瓶颈段瓶颈段，在适当位置，在适当位置插入延迟线插入延迟线作为流水线的一个作为流水线的一个段，来调整预约表，以达到最大速度。段，来调整预约表，以达到最大速度。central south university2022-4-21余腊生 版权所有，违者必究5-71 举例：举例：流水线预约表如下图：流水线预约表如下图： 调

51、度方案：调度方案：间隔间隔5拍；拍； 最大启动速度：最大启动速度：间隔间隔3拍；拍； 结果：结果：性能性能可改善！可改善！ 实现步骤：实现步骤： (1)(1)预约表中设置第一个预约表中设置第一个，在目标速度拍内填，在目标速度拍内填F F，表示该位置（表示该位置（F F位置）不允许有实际的位置）不允许有实际的。central south university2022-4-21余腊生 版权所有，违者必究5-72F FF F (2)(2)从第二拍开始，有从第二拍开始，有时填时填，但不允许，但不允许填在填在F F位置，且在目标速度拍内填位置，且在目标速度拍内填F F。 (3)(3)若当前若当前位置为位

52、置为F F时，置此位置为时，置此位置为D D，且在其目，且在其目标速度拍内填标速度拍内填F F，重复，重复(3)(3)，直到遇到空位置为止。，直到遇到空位置为止。 D DF FF FF FF F F FF FF FF FF Fcentral south university2022-4-21余腊生 版权所有，违者必究5-73 (4)(4)将将填入空位置，所有相关填入空位置，所有相关均右移一均右移一个位置。个位置。 D D F FF FF FF FF F (5)(5)重复重复(2)(2)(4)(4)，得到新的预约表。，得到新的预约表。D D改善后改善后结果：结果： 间隔间隔3拍。拍。 D D F

53、 FF FF FF F F Fcentral south university2022-4-21余腊生 版权所有，违者必究5-74 可改善原因：可改善原因： (1)流水线实际速度最大启动速度；流水线实际速度最大启动速度； (2)流水线性能与指令处理过程流水线性能与指令处理过程(m)无关，无关，只与只与t有关；有关； (3)流水线中各段及各拍之间为相对关系。流水线中各段及各拍之间为相对关系。 总结：总结：非线性流水线调度方案；非线性流水线调度方案； 非线性流水线调度优化。非线性流水线调度优化。central south university余腊生 版权所有，违者必究Scheduling 静态指令

54、调度静态指令调度 静态调度(static scheduling)是由优化的编译程序来完成，其基本思想是重排指令序列，拉开具有数据相关的有关指令间的距离。由于是用编译程序判测潜在的数据相关，并在程序运行之前完成调度，故称为静态调度静态调度。 【例例4】 有A、B、C、D四个存储器操作数，要求完成(AB)(C+D)的运算。若原来程序如图 (a)所示，为拉开I3与I1、I2的距离，I6与I4、I5的距离，重排后的指令序列如图 (b)所示。central south university2022-4-21余腊生 版权所有，违者必究5-76Static SchedulingHave compiler r

55、e-order code to mitigate the effects of data and control dependencesConcepts A comparison of static and dynamic scheduling Each has advantages/disadvantages Bottom line: find good combination of the two Support for high-performance static scheduling Register pressure: large architectural register fi

56、le Branches: compile-time region formation Ambiguous memory dependences: speculative loads Basic scheduling techniques Basic block scheduling Loop unrolling Software pipelining (modulo scheduling) Trace scheduling Predicationcentral south university2022-4-21余腊生 版权所有，违者必究5-77Static / Dynamic Scheduli

57、ng Dynamic StaticModeratelyScheduled Codedynamicallyre-orderinstructionsFUFUFUFUModeratelyScheduled Codestaticallyre-orderinstructionsFUFUFUFUcompilerhardwarecompilerhardwareVLIWPROCESSORSUPERSCALARPROCESSORcentral south university2022-4-21余腊生 版权所有，违者必究5-78Hardware(+) Precise view of program at run-

58、time (+) Accurate and adaptable branch prediction (+) Can handle dependences unknown at compile time (e.g., Ambiguous Memory & Control dependences)(-) Limited view of program (-) Limited or no knowledge of program structure (-) Limited (but accurate) scheduling scope (-) Expend resources regeneratin

59、g information available in compiler but not conveyed in the binary(-) Hardware complexity (-) Complex: circuits may impact cycle time (-) Expensive: die area and hardware verificationcentral south university2022-4-21余腊生 版权所有，违者必究5-79Compiler (+) Global view of the program (+) Better understanding of

60、 program structure and coarse-grain parallelism (loops, functions, etc.) (+) Potentially much larger scheduling scope (+) Very sophisticated analysis possible Not constrained by die area or cycle time Although compile time + memory usage still importantcentral south university2022-4-21余腊生 版权所有，违者必究5