流水方式.ppt

《流水方式.ppt》由会员分享，可在线阅读，更多相关《流水方式.ppt（134页珍藏版）》请在三一办公上搜索。

1、2 流水方式,基本概念流水线处理机的主要性能 流水机器的相关处理和控制机构,空间并行性设置多个独立的操作部件多操作部件处理机超标量处理机时间并行性采用流水线技术。不增加或只增加少量硬件就能使运算速度提高几倍流水线处理机超流水线处理机,基本概念,流水是重叠的延伸.一次重叠：只是把一条指令的解释分解为两个子过程；流水：分解为更多的子过程。时空图表示。,流水线的表示方法,连接图时空图预约表,说明,流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。会增加指令的执

2、行时间。为了简化，在一般流水线中不画出流水锁存器,说明,流水线经过装入、充满、排空三个阶段流水的最大吞吐率：当流水线正常符合流动时的吞吐率。每隔t流出一个结果。流水的最大吞吐率取决于子过程所经过的时间t,一个浮点加法器流水线的时空图,由求阶差、对阶、尾数加和规格化4个流水段组成,流水线的特点,只有连续提供同类任务才能充分发挥流水线的效率对于指令流水线：要尽量减少因条件分支造成的“断流”对于操作部件：主要通过编译技术，尽量提供连续的同类操作在流水线的每一个流水线段中都要设置一个流水锁存器时间开销：流水线的执行时间加长是流水线中需要增加的主要硬件之一各流水段的时间应尽量相等流水线处理机的基本时钟周

3、期等于时间最长的流水段的时间长度流水线需要有装入时间、充满时间和排空时间在理想情况下，当流水线充满后，每隔t时间将会有一个结果流出流水线。,流水线的分类,从不同角度，有不同的分类依据向下扩展和向上扩展思路，可分类出在计算机系统不同等级上使用的流水线向下扩展：子过程细分向上扩展：多个处理机之间进行流水,流水线的分类（续）,按流水处理的级别部件级（操作流水线），如浮点加法器流水线,流水线的分类（续）,处理机级，指令流水线(Instruction Pipelining)例如：在采用先行控制器的处理机中，各功能部件之间的流水线,流水线的分类（续）,系统级：宏流水线(Macro Pipelining)每

4、个处理机对同一个数据流的不同部分分别进行处理,流水线的分类（续）,按功能多少单功能：只能完成一种固定功能的流水线Cray-1计算机中有12条；YH-1计算机有18条；Pentium有一条5段的定点和一条8段的浮点流水线；Pentium有三条指令流水线，其中两条定点指令流水线，一条浮点指令流水线。多功能：流水线的各段通过不同连接实现不同功能Texas公司的ASC计算机中的8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。,流水线的分类（续）,按多功能的连接方式静态：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种

5、固定的功能。只有连续出现同一种运算时，流水线的效率才能得到充分的发挥。动态：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。,流水线的分类（续）,按数据表示标量流水：没有向量数据，只能用标量循环方式来对向量、数组进行处理。Amdahl 470V/6IBM 360/91向量流水：设置有向量指令和向量运算硬件，能对向量、数组中的各个元素流水地处理。CRAY-1,流水线的分类（续）,按是否有反馈回路线性(Linear Pipelining)：每个流水段都流过一次，且仅流过一次非线性(Nonlinear Pipelining)：在流水线的某些流水段之间有反馈回路或前馈回路

6、,流水线的分类（续）,按照控制方式：同步流水线异步流水线顺序流水线与乱序流水线：乱序流水线又称为无序流水线、错序流水线或异步流水线等,流水线处理机的主要性能,通过时空图分析 吞吐率（TP,Thoughput Rate）加速比（Speed Ratio）效率（Efficiency）,吞吐率（TP,Thoughput Rate）,是流水线单位时间里能流出的任务数或结果数。,吞吐率（续）,解决瓶颈子过程的办法细分,细分,吞吐率（续）,瓶颈段并联,并联,吞吐率（续）,说明：,加速比（Speed Ratio）,指流水线的速度与等效的非流水线的速度之比。,加速比（续）,加速比（续）,效率（Efficienc

7、y）Eta,是指流水线中的设备实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。,效率（续）,效率,举例1：,用一条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGH解：Z=(A+B)+(C+D)+(E+F)+(G+H),7个浮点加法共用了15个时钟周期。流水线的吞吐率为：流水线的加速比为：流水线的效率为,举例2:（静态多功能流水线）,设有两个向量A和B，各有4个元素，要在如图所示的静态双功能流水线上，计算向量点积AB，其中1-2-3-5组成加法流水线，1-4-5组成乘法流水线，又设每个流水线所经过的时间均为Dt，而且流水线的输出结果可以直接返回到输入或存于相应的缓冲寄存器中，

8、其延迟时间和功能切换所需的时间都可以忽略不计。,A*B=a1b1+a2b2+a3b3+a4b4,静态多功能流水线,实际吞吐率TP=7/15 Dt加速比Sp=24Dt/(15Dt)=1.6效率=（3*4Dt+4*3Dt）/（5*15Dt)=0.32=32%,A*B=a1b1+a2b2+a3b3+a4b4,动态多功能流水线,实际吞吐率TP=7/14 Dt加速比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、

9、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,效率=（6*4Dt+3*4Dt）/（4*24Dt)=3/8,时间,效率=（6*4Dt+3*4Dt）/（6*

10、18Dt)=1/3,效率=（6*4Dt+3*4Dt）/（6*18Dt)=1/3,流水线最佳段数的选择,假设在非流水线的机器上采用顺序执行方式完成一个任务所需要的时间为t，那么在同等速度的有k段流水线的机器上执行一个任务需要的时间为：t/k+d,其中d为锁存器的延迟时间。流水线的最大吞吐率：流水线的总价格：a为所有功能段本身的总价格，b为每个锁存器的价格。,流水线最佳段数的选择,流水线的性能价格比对k求导，求极值：一般处理机的流水线段数在2-10之间。,流水机器的相关处理和控制机构,流水线只有连续不断地流动，不出现断流，才能获得高效率。如果处理不当，就会使流水效率显著下降。全局相关：转移相关局部

11、相关,流水机器的相关处理和控制机构,局部性相关的处理 全局性相关的处理-转移相关 流水机器的中断处理 流水线调度-非线性流水线,局部相关与全局相关,如果程序内有一个两路的条件分支操作指令，它把程序分为三个部分B0、B1和B2，在每一个部分内部不再有分支操作指令在同一个基本块内部的相关成为局部相关（Local Correlation）对程序执行的过程的影响相对较小，仅影响到相关指令前后的一条或几条指令的执行在基本块之间相关成为全局相关（Global Correlation）影响到整个程序的执行方向,局部性相关的处理,局部性相关：指令相关、访存操作数相关、通用寄存器组相关原因：在机器同时解释多条指

12、令之间出现了对同一主存单元或寄存器要求“先写后读”而产生的。解决：推后后续指令对相关单元的读，直至在先的指令写入完成设置相关直接通路，将运算结果经相关直接通路直接送入所需部件,局部性相关的处理（续）,任务在流水线中流动顺序的安排和控制顺序流动方式（同步流动方式）：任务流出流水线的顺序保持与流入流水线的顺序一致控制简单，但相关后吞吐率和效率下降异步流动方式,举例：流动顺序的控制,8段流水线，第2段为读段，第7段为写段一串指令流入：h,i,j,k,l,m,n当指令j的源操作数地址与指令h的目的操作数相同时，发生先写后读的操作数相关顺序流动时：j读段是停下来等待，直到h到达写段并完成后，才流动。推后

13、读。优点：控制比较简单相关后流水线的吞吐率和效率下降,入,指令地址：,顺序流动和异步流动,指令j的源操作数地址与指令h的目的操作数地址相同时，h和j就发生先写后读的操作数相关。,举例：流动顺序的控制（续）,异步流动：如果让j之后的指令，如k,l,m,n，只要与j没有相关，就越过j继续向前流动。会发生其他相关写-写相关：对同一单元，要求在先的指令先写入，在后的指令后写入的关联。先读后写相关：对同一单元，要求在先的指令先读出，在后的指令再写入的关联。,数据相关,“先写后读”相关,“写-写”相关,“先读后写”相关,单条流水线的“先写后读”相关的数据重定向,单条流水线的“写-写”相关的数据重定向,B,

14、A,C,B,A,C,t,t+t,t+t,全局性相关的处理,指的是已进入流水线的转移指令（尤其是条件转移指令）和其后续指令之间的相关。,全局性相关的处理-转移相关,猜测法 加快和提前形成条件码加快单条指令内部的条件码的形成在一段程序内提前形成条件码（适合循环）采用延迟转移-采用软件进行静态指令调度加快短循环程序的处理,猜测法,具体分析条件转移指令对流水线性能的影响,对一条有k个功能段的流水线，由于条件转移指令的影响，在最坏情况下，每一次条件转移将造成k-1个时钟周期的“断流”假设条件转移指令在一般程序中所占的比例为p，转移成功的概率为q，因此，对于一个由n条指令组成的程序，在执行这个程序指令的过

15、程中，由于条件转移需要额外增加的时钟周期数：pqn(k-1)t，包括条件转移指令在内的n条指令的总的执行时间为,有条件转移影响的流水线的吞吐率：当n-时，有条件转移影响的流水线的吞吐率：由于条件转移指令的影响，流水线吞吐率下降的百分比为：,在典型的标量类机器指令程序中，条件转移指令占20%，其中转移成功的概率有约占其中的60%。对于一条有8个功能段的指令流水线，流水线的最大吞吐率要下降：如果段数为10，则下降：,采取的措施,延迟转移技术和指令取消技术SUN：SPARC，HP：HP-RISC，SGI：MIPS静态转移预测技术TI:SuperSPARC动态转移预测技术,流水机器的中断处理,中断的出

16、现概率比条件转移的概率要低。处理中断的主要问题：断点现场的保护和恢复，而不是缩短流水线的断流时间。,不精确断点：无论指令I在流水线的哪一段发生中断，都不再允许尚未进入流水线的后续指令再进入，但已在流水线的所有指令仍继续流动到执行完毕，然后才转入中断处理程序。IBM 360/91不利于编程和程序的排错精确断点：无论指令I是在流水线中的哪一段响应中断，给中断现场全都是对应I的，I之后流入流水线内的指令的原有现场都能保存和恢复。需设置很多后援寄存器控制逻辑比较复杂,相关问题,相关（correlation）：指在一段程序的相近指令之间有某种关系，这种关系可能影响指令的重叠执行。数据相关：局部相关控制相

17、关：全局相关,数据相关,在执行本条指令的过程中，如果用到的指令、操作数、变址偏移量等正好是前面指令的执行结果，则必须等待前面的指令执行完成，并把结果写到主存或通用寄存器中之后，本条指令才能执行。指令相关主存操作数相关通用寄存器相关变址相关,控制相关,指由条件分支指令、转子程序指令、终断等引起的相关。,指令相关,第k+1条指令本身的内容取决于第k条指令的执行结果。解决：程序中不允许修改指令。,主存操作数相关,当指令的执行结果写到主存储器，所读取的操作数也取自主存储器时。解决：推后处理法,通用寄存器相关,在寄存器-寄存器型和寄存器-存储器型指令的执行过程中有可能发生通用寄存器数据相关。解决在通用寄

18、存器和运算器之间建立直接数据通路推后处理设置专用数据通路,变址相关,变址寄存器发生相关。解决推后分析设置专用通路,总结：数据相关的解决方法,采用硬件或软件的办法尽量避免数据相关发生是在确保指令正确执行的前提下，推后指令分析设置专用通路,转移相关,无条件转移一般条件转移复合条件转移,无条件转移相关,一般能够在指令分析器中就执行完成。对程序执行速度的影响很小。,一般条件转移,对程序执行速度造成的影响很大。缓冲深度越深，影响越大。,复合条件转移,本身是一条运算指令，根据结果决定后转移。影响比一般条件转移指令要大。,转移预测技术,软件“猜测法”不改变硬件结构，只修改编译器。硬件“猜测法”增设指令分析器

19、两个先行指令缓冲栈增设先行目标缓冲栈,短循环程序的处理,短循环程序的三个条件循环体的长度小于等于先行指令缓冲栈的深度循环次数的控制采用计数转移指令控制循环的条件转移指令一般是向后转移的指令,短循环程序的处理（续）,解决好三个问题指令分析器如何发现短循环程序如何控制短循环程序在先行指令缓冲栈中不被清除如何控制循环体的执行次数,短循环程序的处理（续）,在指令系统中设置专门的短循环程序的开门指令和关门指令用专门的硬件来识别短循环程序,流水线调度-非线性流水线,由于非线性流水线有反馈回路，因此会出现几个任务争用同一功能段的冲突现象前馈线、后馈线功能部件冲突（流水线冲突）,非线性流水线的表示,线性流水线

20、能够用流水线连接图唯一表示连接图不能用唯一表示非线性流水线的工作流程,非线性流水线的表示,对非线性流水线，采用：二维预约表（Reservation Table）1971年E.S.Davidson提出。,段号 k,拍号n,一张预约表可能与多个流水线连接图相对应,一个流水线连接图对应与多张预约表,非线性流水线的冲突,向一条非线性流水线的输入端连续输入两个任务之间间隔称为非线性流水线的启动距离或等待时间。,段号 k,拍号n,启动距离为3的流水线冲突情况,非线性流水线的冲突,非线性流水线的调度,是要找出一个最小的循环周期，按照这个周期向流水线输入新任务。流水线的各个功能段不会发生冲突，而且流水线的吞吐

21、率和效率最高,举例,段号k,拍号n,预约表,延迟禁止表F(Forbidden List)1,5,6,8,相邻两个任务的间隔拍数不能为1，5，6，8冲突向量C(Collision Vector)第i位的状态用以表示与当时相隔i拍给流水线送入后继任务是否会发生功能段的使用冲突。如不发生，0，否则，1 C=(10110001)初始冲突向量,（1）形成预约表,指令总拍数为n，流水线有k个段，则形成nk的预约表，段的使用情况用“”表示。预约表如下：,（2）由预约表形成禁止表F,F=各段中冲突间隔拍数,（3）由禁止表F形成初始冲突向量C0,C0=（cNc0），ci=1冲突，=0不冲突。本例：C0=（101

22、10001）。,（4）由初始冲突向量C0形成状态转换图,a.C0每过一拍逻辑右移一位，若移出0，则允许后续指令进入流水线，再与C0按位“或”，形成新的冲突向量Ci；,2拍后，新指令(-I2)进入后：,I1与I3的F=3,4,6，,I2与I3的F=1,5,6,8,新F=1,3,4,5,6,8，C2=(10111101)。,注意：Ci为第i拍后流水线的冲突向量，此时流水线中已有两条指令，Ci用于判断第三条指令的进入。,b.各Ci再每过一拍逻辑右移一位，若移出0，允许后续指令进入，再与C0按位“或”，形成新的冲突向量Cij；,注意：Cij为第i+j拍后流水线的冲突向量，此时流水线中已有三条指令，Ci

23、j用于判断第四条指令的进入。,对C2，再2拍后，新指令(-I3)进入后：,I1与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)。,注意：Cij为第i+j拍后流水线的冲突向量，此时流水线中已有三条指令，Cij用于判断第四条指令的进入。,c.重复上一步骤，直到不再生成新的冲突向量为止。,（5）找出最加调度方案,从各个闭合回路中找出平均间隔最小的一个。,10110001,10111101,10111111,10110111,10111011,2,7,7,2,7,7,7,4,4,3,3,10110001

24、,10111101,10111111,10110111,10111011,2,7,7,2,7,7,7,4,4,3,3,10110001,10111101,10111111,10110111,10111011,2,7,7,2,7,7,7,4,4,3,3,10110001,10111101,10111111,10110111,10111011,2,7,7,2,7,7,7,4,4,3,3,按(3,4)进行调度,按(3,4)进行调度 TP=6/26 Sp=(6*10)/26=30/13 e=(6*10)/(26*5)=60/130=6/13,按(4,3)进行调度 TP=6/27 Sp=(6*10)/2

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

26、向量做“按位或”，得到一个新的冲突向量。当移位器移出1，不做任何处理。重复这个步骤。对产生的每一个新的冲突向量做同样处理。在初始冲突向量和所有形成的冲突向量之间，箭头连接。,（3）从状态图中可以找到许多不发生流水段冲突的启动循环。，只要找到简单循环，进而确定平均启动距离最小的启动循环。它们是：（1，7）、（3，5，7）、（5，7）等,最小启动循环是具有最小平均最小启动距离的启动循环。,最小循环为（1，7）、（3，5）最小恒定循环为（5）,最小启动循环为（3，5）的流水线工作状态,最小启动循环为（1，7）的流水线工作状态,恒定启动循环（5）的流水线工作状态,启动周期,重复启动周期,举例,（1）写

27、出流水线的禁止向量和初始冲突向量（2）画出调度流水线的状态图（3）求流水线的最小启动循环和最小启动距离（4）求平均启动距离最小的恒定循环。,7*,最小启动循环为（1，1，7）的流水线工作状态,最小启动循环为（5）的流水线工作状态,优化调度方法,从上图看出，当采用最小启动循环启动非线性流水线时，流水线中的许多功能段还有空闲。L.E.Shar于1972年提出了流水线最小平均启动距离的限制范围，对于一条静态可重构的流水线，通过预约表可以得到其最小平均启动距离的范围最小平均启动距离的下限是预约表中任意一行里“”的最多个数，实际上也就是同一个任务通过流水线中任意一个功能段的最多次数最小平均启动距离应小于

28、或等于状态图中任意一个简单循环的平均启动距离。最小平均启动距离的上限是冲突向量中1的个数再加上1.1992年，L.E.Shar又证明了上述限制,采用预留算法来调度非线性流水线,确定流水线的最小平均启动距离。最小平均启动距离等于预约表中任意一行中“”的最大个数，或者是同一个任务通过流水线中任意一个功能段的最多次数。确定最小启动循环。结合流水线预约表和连接图，采用预留算法，通过插入非计算延迟功能段实现最小启动循环。,a.同单功能调度方法，首先生成n个初始冲突矩阵（按在先功能分类）。,调度方案：,b.再由初始冲突矩阵按后续功能分类按位右移，形成新的冲突矩阵，最终形成状态转换图。,新冲突矩阵形成规则：VB=（Vx）|MB，V后续操作为B；VA=（Vx）|MA，V后续操作为A。,c.从闭合回路中找出调度方案（按功能顺序分成几种）。,练习,书中 p191 习题5-11,F=1,3,4,8C=(10001101),平均延迟=3.5Tpmax=1/3.5最佳调度方案(2,5),(5,2)不合适。Tp=6/25,按(2,5)进行调度 TP=6/25 Sp=(6*11)/25=12/5 e=(6*11)/(25*5)=12/25,