本科系统结构课件 chapter5-2

§2流水方式

基本概念流水线处理机的主要性能流水机器的相关处理和控制机构

空间并行性设置多个独立的操作部件多操作部件处理机超标量处理机时间并行性采用流水线技术。不增加或只增加少量硬件就能使运算速度提高几倍流水线处理机超流水线处理机基本概念

流水是重叠的延伸.一次重叠：只是把一条指令的解释分解为两个子过程；流水：分解为更多的子过程。时空图表示。流水线的表示方法连接图时空图预约表取指令指令译码取操作数执行入出12345123451234512345取指令指令译码取操作数执行空间时间t1t2t3t4t5t6t7t8流水线的时-空图说明流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。会增加指令的执行时间。为了简化，在一般流水线中不画出流水锁存器说明流水线经过装入、充满、排空三个阶段流水的最大吞吐率：当流水线正常符合流动时的吞吐率。每隔Δt流出一个结果。流水的最大吞吐率取决于子过程所经过的时间Δt一个浮点加法器流水线的时空图由求阶差、对阶、尾数加和规格化4个流水段组成ED1时间空间0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL：规格化MA：尾数加EA：对阶ED：求阶差流水线的特点只有连续提供同类任务才能充分发挥流水线的效率对于指令流水线：要尽量减少因条件分支造成的“断流”对于操作部件：主要通过编译技术，尽量提供连续的同类操作在流水线的每一个流水线段中都要设置一个流水锁存器时间开销：流水线的执行时间加长是流水线中需要增加的主要硬件之一各流水段的时间应尽量相等流水线处理机的基本时钟周期等于时间最长的流水段的时间长度流水线需要有装入时间、充满时间和排空时间在理想情况下，当流水线充满后，每隔Δt时间将会有一个结果流出流水线。流水线的分类从不同角度，有不同的分类依据向下扩展和向上扩展思路，可分类出在计算机系统不同等级上使用的流水线向下扩展：子过程细分向上扩展：多个处理机之间进行流水流水线的分类（续）

按流水处理的级别部件级（操作流水线），如浮点加法器流水线求阶差输入输出Dt1对阶尾数加规格化Dt2Dt3Dt4流水线的分类（续）处理机级，指令流水线(InstructionPipelining)例如：在采用先行控制器的处理机中，各功能部件之间的流水线先行指令

缓冲栈输入先行控制方式

中的指令流水线先行指令

分析器先行读数栈

先行操作栈取指译码取操作数指令执行部件后行写数栈输出执行写结果流水线的分类（续）系统级：宏流水线(MacroPipelining)

每个处理机对同一个数据流的不同部分分别进行处理处理机1处理机2处理机n数据集处理机间的流水处理流水线的分类（续）按功能多少单功能：只能完成一种固定功能的流水线Cray-1计算机中有12条；YH-1计算机有18条；Pentium有一条5段的定点和一条8段的浮点流水线；PentiumⅢ有三条指令流水线，其中两条定点指令流水线，一条浮点指令流水线。多功能：流水线的各段通过不同连接实现不同功能Texas公司的ASC计算机中的8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。流水线的分类（续）按多功能的连接方式静态：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能。只有连续出现同一种运算时，流水线的效率才能得到充分的发挥。动态：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。1时间空间023…n123…n123…n123…n123…n123…n1234…123…12……1输入求阶差对阶尾数加规格化尾数乘累加输出静态流水线时空图浮点加法定点乘法1时间空间023…n123…n123…n123…n123…n123…n输入求阶差对阶尾数加规格化尾数乘累加输出动态流水线时空图………………123546123541234123…………浮点加法定点乘法流水线的分类（续）按数据表示标量流水：没有向量数据，只能用标量循环方式来对向量、数组进行处理。Amdahl470V/6IBM360/91向量流水：设置有向量指令和向量运算硬件，能对向量、数组中的各个元素流水地处理。CRAY-1流水线的分类（续）按是否有反馈回路线性(LinearPipelining)：每个流水段都流过一次，且仅流过一次非线性(NonlinearPipelining)：在流水线的某些流水段之间有反馈回路或前馈回路1234入出非线性流水线流水线的分类（续）按照控制方式：同步流水线异步流水线顺序流水线与乱序流水线：乱序流水线又称为无序流水线、错序流水线或异步流水线等流水线处理机的主要性能

通过时空图分析

吞吐率（TP,ThoughputRate）

加速比（SpeedRatio）效率（Efficiency）

吞吐率（TP,ThoughputRate）

是流水线单位时间里能流出的任务数或结果数。

1时间空间S123……n-1nS2S3S4123……n-1n123……n-1n123……n-1nmDt(n-1)DtnDt(m-1)DtTS1输入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt输出1时间空间S1S2S3S4SDti(n-1)Dt2Tk23…n123…n123…n123…n吞吐率（续）

解决瓶颈子过程的办法细分S1输入输出DtS2-1DtS2-2DtS2-3DtS3DtS4DtS2(3Dt)细分1471014710Ss3bs3as2s1t1t12t17Ts3cs468111235911122359268147103591112268147103591112268147103591112268147103591112268吞吐率（续）瓶颈段并联S1输入输出Dt1=DtS2-1S2-1S2-1S3S4Dt3=DtDt4=DtDt2=3Dt1时间空间23nS1S2-1456…14…-2-1n-225…n-136…n123n456…-2-1123n456…-2-1S2-2S2-3S3S4并联吞吐率（续）说明：加速比（SpeedRatio）

指流水线的速度与等效的非流水线的速度之比。加速比（续）加速比（续）m=6m=10任务

个数加速比10246811248163264128效率（Efficiency）Eta

是指流水线中的设备实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。

效率（续）效率举例1：用一条4段浮点加法器流水线求8个浮点数的和：

Z＝A＋B＋C＋D＋E＋F＋G＋H解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]1时间空间23求阶差4567123456712345671234567对阶尾数加规格化加数ACEGA+BE+FBDFHC+DG+HA+B+C+DE+F+G+H结果A+BC+DE+FG+HA+B+C+DE+F+G+HZ7个浮点加法共用了15个时钟周期。流水线的吞吐率为：流水线的加速比为：流水线的效率为举例2:（静态多功能流水线）设有两个向量A和B，各有4个元素，要在如图所示的静态双功能流水线上，计算向量点积AB，其中1-〉2-〉3-〉5组成加法流水线，1-〉4-〉5组成乘法流水线，又设每个流水线所经过的时间均为Dt，而且流水线的输出结果可以直接返回到输入或存于相应的缓冲寄存器中，其延迟时间和功能切换所需的时间都可以忽略不计。12354xyzA*B=a1b1+a2b2+a3b3+a4b4空间时间12345678910111213141516静态多功能流水线实际吞吐率TP=7/15Dt加速比Sp=24Dt/(15Dt)=1.6效率η=（3*4Dt+4*3Dt）/（5*15Dt)=0.32=32%A*B=a1b1+a2b2+a3b3+a4b4空间时间12345678910111213141516动态多功能流水线实际吞吐率TP=7/14Dt加速比Sp=24Dt/(14Dt)=1.714效率η=（3*4Dt+4*3Dt）/（5*14Dt)=0.343=34.3%举例3：书中P190第6题有一个双输入端的加-乘双功能静态流水线，由经过时间分别为Dt、2Dt、2Dt、Dt的1、2、3、4四个子过程构成，加法时按1-〉2-〉4连接，乘法时按1-〉3-〉4连接。流水线输出设有缓冲器，也可将数据直接回授到流水线输入端。现要执行

A*(B+C*(D+E*F))+G*H

的运算，请对运算顺序进行交换，画出能获得尽可能高的吞吐率的流水时空图；标出流水线入、出端的操作数变化情况；求出完成全部运算所需时间及此期间整个流水线的效率。如对流水线瓶颈子过程细分，最少需多少时间完成全部运算？若子过程3已无法再细分，只能采用并联方法改进，问流水线的效率为多少？A*B+A*C*D+A*C*E*F+G*H空间时间123456789101112131415161718192021222324效率η=（6*4Dt+3*4Dt）/（4*24Dt)=3/8时间空间123456789101112131415161718效率η=（6*4Dt+3*4Dt）/（6*18Dt)=1/3空间123456789101112131415161718效率η=（6*4Dt+3*4Dt）/（6*18Dt)=1/3流水机器的相关处理和控制机构流水线只有连续不断地流动，不出现断流，才能获得高效率。如果处理不当，就会使流水效率显著下降。全局相关：转移相关局部相关流水机器的相关处理和控制机构

局部性相关的处理

全局性相关的处理------转移相关

流水机器的中断处理

流水线调度-----非线性流水线

局部性相关的处理局部性相关：指令相关、访存操作数相关、通用寄存器组相关原因：在机器同时解释多条指令之间出现了对同一主存单元或寄存器要求“先写后读”而产生的。解决：推后后续指令对相关单元的读，直至在先的指令写入完成设置相关直接通路，将运算结果经相关直接通路直接送入所需部件局部性相关的处理（续）任务在流水线中流动顺序的安排和控制顺序流动方式（同步流动方式）：任务流出流水线的顺序保持与流入流水线的顺序一致控制简单，但相关后吞吐率和效率下降异步流动方式入指令地址：顺序流动和异步流动指令j的源操作数地址与指令h的目的操作数地址相同时，h和j就发生先写后读的操作数相关。读段写段相关直接通路12345678nkkjjjm空il空hk空iihh可以不顺序流动的顺序流动的（推后）判出j、h相关出读段写段相关直接通路12345678nkkjjjm空il空hk空iihh出举例：流动顺序的控制8段流水线，第2段为读段，第7段为写段一串指令流入：h,i,j,k,l,m,n当指令j的源操作数地址与指令h的目的操作数相同时，发生先写后读的操作数相关顺序流动时：j读段是停下来等待，直到h到达写段并完成后，才流动。推后读。优点：控制比较简单相关后流水线的吞吐率和效率下降举例：流动顺序的控制（续）异步流动：如果让j之后的指令，如k,l,m,n，只要与j没有相关，就越过j继续向前流动。会发生其他相关写-写相关：对同一单元，要求在先的指令先写入，在后的指令后写入的关联。先读后写相关：对同一单元，要求在先的指令先读出，在后的指令再写入的关联。全局性相关的处理指的是已进入流水线的转移指令（尤其是条件转移指令）和其后续指令之间的相关。全局性相关的处理------转移相关

猜测法

加快和提前形成条件码加快单条指令内部的条件码的形成在一段程序内提前形成条件码（适合循环）采用延迟转移------采用软件进行静态指令调度加快短循环程序的处理

猜测法i-3i-2i-1ii+1i+2i+3i+4pp+1p+2p+3猜测路径（转移不成功路径）转移成功路径转移不成功分支转移指令猜测法（续）在典型的标量类机器指令程序中，条件转移指令占20%，其中转移成功的概率有约占其中的60%。流水机器的中断处理中断的出现概率比条件转移的概率要低。处理中断的主要问题：断点现场的保护和恢复，而不是缩短流水线的断流时间。不精确断点：无论指令I在流水线的哪一段发生中断，都不再允许尚未进入流水线的后续指令再进入，但已在流水线的所有指令仍继续流动到执行完毕，然后才转入中断处理程序。IBM360/91不利于编程和程序的排错精确断点：无论指令I是在流水线中的哪一段响应中断，给中断现场全都是对应I的，I之后流入流水线内的指令的原有现场都能保存和恢复。需设置很多后援寄存器控制逻辑比较复杂S1S2S3S4S5S6S7S8不精确断点精确断点流水线处理机的中断处理相关问题相关（correlation）：指在一段程序的相近指令之间有某种关系，这种关系可能影响指令的重叠执行。数据相关：局部相关控制相关：全局相关数据相关在执行本条指令的过程中，如果用到的指令、操作数、变址偏移量等正好是前面指令的执行结果，则必须等待前面的指令执行完成，并把结果写到主存或通用寄存器中之后，本条指令才能执行。指令相关主存操作数相关通用寄存器相关变址相关控制相关指由条件分支指令、转子程序指令、终断等引起的相关。指令相关第k+1条指令本身的内容取决于第k条指令的执行结果。解决：程序中不允许修改指令。主存操作数相关当指令的执行结果写到主存储器，所读取的操作数也取自主存储器时。解决：推后处理法通用寄存器相关在寄存器-寄存器型和寄存器-存储器型指令的执行过程中有可能发生通用寄存器数据相关。解决在通用寄存器和运算器之间建立直接数据通路推后处理设置专用数据通路变址相关变址寄存器发生相关。解决推后分析设置专用通路总结：数据相关的解决方法采用硬件或软件的办法尽量避免数据相关发生是在确保指令正确执行的前提下，推后指令分析设置专用通路转移相关无条件转移一般条件转移复合条件转移无条件转移相关一般能够在指令分析器中就执行完成。对程序执行速度的影响很小。分析k执行k分析k+1取指令L分析L执行L分析L执行L分析L+1执行L+1指令L不在先行指令缓冲栈中：指令L在先行指令缓冲栈中：一般条件转移对程序执行速度造成的影响很大。缓冲深度越深，影响越大。分析k执行k分析k+1分析k+2执行k+2分析k+1分析L执行L分析k+1取指令L分析L执行L转移不成功成功，L在指缓栈中成功，L不在指缓栈中产生转移条件CC根据转移条件CC判断转移是否成功复合条件转移本身是一条运算指令，根据结果决定后转移。影响比一般条件转移指令要大。分析K执行k分析K+1执行k+1分析L执行L取指令L分析L执行L转移不成功成功，L在先行指令缓冲栈中成功，L不在先行指令缓冲栈中转移预测技术软件“猜测法”不改变硬件结构，只修改编译器。硬件“猜测法”增设指令分析器两个先行指令缓冲栈增设先行目标缓冲栈短循环程序的处理短循环程序的三个条件循环体的长度小于等于先行指令缓冲栈的深度循环次数的控制采用计数转移指令控制循环的条件转移指令一般是向后转移的指令短循环程序的处理（续）解决好三个问题指令分析器如何发现短循环程序如何控制短循环程序在先行指令缓冲栈中不被清除如何控制循环体的执行次数短循环程序的处理（续）在指令系统中设置专门的短循环程序的开门指令和关门指令用专门的硬件来识别短循环程序流水线调度--非线性流水线

由于非线性流水线有反馈回路，因此会出现几个任务争用同一功能段的冲突现象前馈线、后馈线功能部件冲突（流水线冲突）流水线的调度S1S2S3S4S5入①②③④⑥⑤⑦⑧⑦⑨出⑧非线性流水线的表示对非线性流水线，采用：二维预约表（ReservationTable）1971年E.S.Davidson提出。1234567891XX2XXX3X4XX5XX段号k拍号n非线性流水线的冲突向一条非线性流水线的输入端连续输入两个任务之间间隔称为非线性流水线的启动距离或等待时间。段号

k拍号n1234567891011121314151X1X2X3X1X2X32X1X1X2X2X1X3X3X2X33X1X2X34X1X1X2X2X3X35X1X1X2X2X3X3启动距离为3的流水线冲突情况举例1234567891**2***3*4**5**段号k拍号n预约表延迟禁止表F(ForbiddenList){1,5,6,8},相邻两个任务的间隔拍数不能为1，5，6，8冲突向量C(CollisionVector)第i位的状态用以表示与当时相隔i拍给流水线送入后继任务是否会发生功能段的使用冲突。如不发生，0，否则，1C=(10110001)

初始冲突向量（1）形成预约表

指令总拍数为n，流水线有k个段，则形成n×k的预约表，段的使用情况用“×”表示。

预约表如下：××5××4×3××××2××1987654382716tS（2）由预约表形成禁止表F

F={各段中冲突间隔拍数}本例：F={1，5，6，8}××5××4×3××××2××1987654382716tS××××5×××4×3××××2××1987654382716tS5681（3）由禁止表F形成初始冲突向量C0

C0=（cN…c0），ci=1冲突，=0不冲突。本例：C0=（10110001）。（4）由初始冲突向量C0形成状态转换图

a.C0每过一拍逻辑右移一位，若移出0，则允许后续指令进入流水线，再与C0按位“或”，形成新的冲突向量Ci；10110001101101111011110110111011初始状态3427

2拍后，新指令(×-I2)进入后：×××5××××4××3×××××2×××1987654321tS643I1与I3的F={3,4,6}，I2与I3的F={1,5,6,8},新F={1,3,4,5,6,8}，C2=(10111101)。

注意：Ci为第i拍后流水线的冲突向量，此时流水线中已有两条指令，Ci用于判断第三条指令的进入。1011000110110111101111011011101110111111初始状态34422777

b.各Ci再每过一拍逻辑右移一位，若移出0，允许后续指令进入，再与C0按位“或”，形成新的冲突向量Cij；

注意：Cij为第i+j拍后流水线的冲突向量，此时流水线中已有三条指令，Cij用于判断第四条指令的进入。对C2，再2拍后，新指令(×-I3)进入后：

421×××5×××××4×××3×××××××2××××1987654321tS×××××98I1与I4的F={1,2,4}，I2与I4的F={3,4,6},I3与I4的F={1,5,6,8},新F={1,2,3,4,5,6,8}，C22=(10111111)。643

注意：Cij为第i+j拍后流水线的冲突向量，此时流水线中已有三条指令，Cij用于判断第四条指令的进入。

c.重复上一步骤，直到不再生成新的冲突向量为止。1011000110110111101111011011101110111111初始状态34342277777（5）找出最加调度方案

从各个闭合回路中找出平均间隔最小的一个。1011000110111101101111111011011110111011277277744331011000100101100（右移2位）101111011011000110111101101111111011011110111011277277744331011000100101100（右移2位）101111011011000100101111（右移2位）101111111011000110111101101111111011011110111011277277744331011000100101100（右移2位）101111011011000100101111（右移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（4，3）3.50（7）7.00（3，4，7）4.671234567891011121314151X1X2X3X1X22X1X1X2X2X1X3X3X2X33X1X2X34X1X1X2X2X3X35X1X1X2X2X3X3按(3,4)进行调度111112222213333324444364556666556124355456按(3,4)进行调度

TP=6/26Sp=(6*10)/26=30/13e=(6*10)/(26*5)=60/130=6/13111112222213333324444364556666556124355456按(4,3)进行调度

TP=6/27Sp=(6*10)/27=20/9e=(6*10)/(27*5)=12/27举例：一条有4个流水段的非线性流水线，每个流水段的延迟时间都相等，它的预约表如下图：时间流水段1234567S1XXS2XXS3XXS4X（1）写出流水线的禁止向量和初始冲突向量（2）画出调度流水线的状态图（3）求流水线的最小启动循环和最小启动距离（4）求平均启动距离最小的恒定循环。解：（1）禁止向量为（2，4，6）冲突向量：用二进制表示，长度是禁止向量的最大距离。冲突向量C=（C1C2C3C4C5C6），由禁止向量，C2=C4=C6=1，其余位为0，冲突向量为

C=（101010）。（2）由冲突向量构造一张图：将C放到一个6位逻辑右移移位器，当从移位器移出0，用移位器中的值与初始冲突向量做“按位或”，得到一个新的冲突向量。当移位器移出1，不做任何处理。重复这个步骤。对产生的每一个新的冲突向量做同样处理。在初始冲突向量和所有形成的冲突向量之间，箭头连接。1010101111111011111010117*157*3537*当右移2、4、6位，时移出位为1，表示用这些启动距离输入新任务要发生冲突，不做任何处理。当右移1、3、5和大于等于7位时，移出位是0，表示用这些启动距离输入新任务不会发生冲突。7*表示大于等于75（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最小启动循环是具有最小平均最小启动距离的启动循环。最小循环为（1，7）、（3，5）最小恒定