计算机系统结构课件：第四章 流水线技术

1、第四章 流水线技术,加快指令执行过程的两种方法：,在设计中，选用高速的器件、更好的算法及提高指令内部的并行程度等措施，可以加快每条指令的解释过程； 可以通过提高指令间的并行性，使控制结构能并发地解释两条、多条甚至整段程序来加快整个机器语言程序的解释过程。,提高处理速度和系统使用效率的三条途径：,时间重叠 资源重复 资源共享,CPU工作方式: 顺序 重叠 流水,1.顺序解释方式(Sequence)：各条机器指令之间顺序串行地执行，执行完一条指令后才取出下条指令来执行，而且每条机器指令内部的各个微操作也是顺序串行地执行。,取指令：按指令计数器的内容访主存，取出该指令送到指令寄存器； 分析：对指令的

2、操作码进行译码，按寻址方式和地址字段形成操作数地址，并用此地址取操作数，还要为取下条指令提前形成其地址； 执行：对操作数进行运算、处理或存储运算结果。,一、 流水线处理概述,第四章 流水线技术,取指令,分析,执行,每阶段时间为t，共n条指令,优点：控制简单； 缺点：速度慢，机器各部件的利用率很低。,若取指令、分析和执行指令周期都相等，设为t，则顺序解释n条指令，需时间T=3nt。,如果每个阶段所需时间不等，各为t取、t分和t执，则顺序执行n条指令所需时间：,第四章 流水线技术,（1） 流水线处理概念和特点 1、流水线的基本概念,流水线技术：将一个重复的时序过程分成若干个子过程，每个子过程都可有

3、效的在其专用功能段上和其它子过程同时执行的一种技术。,流水线的基本结构中主要包括三大部分：锁存器、时钟、功能段（站）。 流水线中每个功能段（站）都是由一些执行算术和逻辑功能的组合逻辑线路组成的，它们可以互相独立地对流过的信息进行某种操作，相邻两个功能段（站）由高速锁存器（latch）隔开，信息在各站间的流动靠同时送到各站的时钟信号来控制。,二、流水工作方式,第四章 流水线技术,S1,S2,Sk,输入,输出,流水线的基本结构,。,L L L L L,第四章 流水线技术,如果每个子过程经过的时间都是t，则指令的流水线处理过程可用时空图来描述。,第四章 流水线技术,2、流水线特点： 1）流水一定重叠

4、，比重叠更苛刻。 2）一条流水线通常由多个流水段组成。 3）每段有专用功能部件，各部件顺序连接，不断流。 4）流水线有建立时间、满载时间、排空时间， 5）各段时间尽量短、一致，不一致时最慢子过程为瓶颈。 6）给出的最大吞吐率等指标，为满负载最佳指标。,建立时间：在流水线开始时有一段流水线填入时间，使得流水线填满。即第1条指令从流入到流出所需的时间。 正常流动时间：流水线正常工作，各功能段源源不断满载工作。 排空时间（释放时间）：流水线最后一条指令流入后到流出的时间。,流水线的时空图是描述流水线工作、分析评价流水线效能的重要工具。,第四章 流水线技术,1、流水线的分级：（按处理的级别分级） 操作

5、部件级(arithmetic pipelining)：将复杂的算逻运算组成流水工作方式； 指令级(instruction pipelining) ：把一条指令解释过程分成多个子过程 ； 处理机级或宏流水线级(macro pipelining) ：由两个以上处理机串行地对同一数据流进行处理，每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中。,（2） 流水线的分级、分类,第四章 流水线技术,多功能流水线从一种功能变为另一种功能时需要重新连接，虽然它对资源的利用率可以较高，应用时也较灵活，但它的控制比单功能流水线复杂得多。因此大多数流水计算机主要采用单功能流水

6、线。,2、流水线的分类： 按功能分类：单功能流水线、多功能流水线 单功能流水线(unifunction pipelining)：只能实现一种固定的专门功能的流水线（如CRAY-1）。 多功能流水线(multifunction pipelining) ：通过各站间的不同连接方式可以同时或不同时地实现多种功能的流水线（如TI-ASC）。,第四章 流水线技术,按工作方式分类：静态流水线、动态流水线 静态流水线(static pipelining)：在同一时间内各功能段只能按一种运算（功能）的连接方式工作。 动态流水线(dynamic pipelining) ：在同一时间内各功能段允许按多种不同运算（

7、功能）的连接方式工作。,特点：静态流水线仅当指令都是同一类型时才能连续不断地执行。当从一种功能方式变为另一种功能方式时，必须先排空流水线，然后再切换成另一种功能进行流水处理。 静态流水线的功能不能频繁地变换，否则它的效率将很低。 动态流水线可以提高流水线的吞吐率和设备的利用率。,第四章 流水线技术,按连接方式（流水线中是否有反馈回路）分类：线性流水线、非线性流水线。 线性流水线(linear pipelining) ：从输入到输出，每个功能段只允许经过一次，不存在反馈回路。一般的流水线均属于这一类。 非线性流水线(non-linear pipelining) ：存在反馈回路，从输入到输出过程中

8、，某些功能段将数次通过流水线，这种流水线常用于进行递归运算。,第四章 流水线技术,1、TI-ASC算术运算流水线（多功能）,（3） 流水线举例,第四章 流水线技术,静态多功能流水线时-空图,静态流水线：只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。,第四章 流水线技术,动态多功能流水线时-空图,区别：如果从软硬功能分配的观点上来看，静态流水线其实是把功能负担较多地加到软件上，以简化硬件；动态流水线则是把功能负担较多地加在硬件上，以提高流水的效能。,空间 (段号),第四章 流水线技术,（一）VAX8600的流水结构 a. I部件：预

9、取指令，操作码译码，预取操作数，并存放运算结果。 b. E部件：执行指令。 c. F部件：浮点加速器。 d. M部件：控制CPU和输入输出设备对主存的访问，有16k字节的cache和把虚存地址转换成实存地址的地址转换表（快表）。 e. 操作台：提供同操作员，引导设备和远程诊断的界面。,指令流水线：一条指令的取指令、译码、取操作数和执行等几个过程能同它前后的指令在时间上重叠，用这种指令重叠的方法构成的流水线就是指令流水线，又叫指令先行控制。,2VAX8600和长城386计算机的指令流水线,第四章 流水线技术,VAX8600的CPU结构图,第四章 流水线技术,I部件和E部件这两个互相独立的部件组成

10、指令流水线。 I部件与E部件的关系：I部件有一个8个字节的指令缓冲寄存器。预取的操作数也包括从通用寄存器中的取数，为此在I部件中还有一组寄存器用作存放16个通用寄存器相同内容的副本，E部件在修改通用寄存器内容时，也同时自动修改I部件中副本的内容。 I部件向E部件（或F部件）提供执行所需的操作码和操作数，当E部件执行完后，I部件提供存储结果所需的写数地址。指令整个工作过程是 流水线化的。,第四章 流水线技术,VAX8600指令流水线的工作顺序,实框：表示CPU在执行一条典型的指令时的动作顺序。 虚线：表示6个动作是各自分开进行的，可以同其它指令的动作并行进行。,第四章 流水线技术,内部有六个部件

11、 总线接口部件：同外部的接口，读取指令、读写数据。 I部件： 指令预取部件：取指令放在指令预取队列中，容量为16个字节。 指令译码部件：形成指令微码，指令队列中可放3条指令。 E部件： 执行部件：控制部件、数据部件、保护测试部件 分段部件 分页部件,存储管理部件,（二）长城386指令流水线,第四章 流水线技术,第四章 流水线技术,（4）流水线性能分析计算,（一）技术指标,衡量流水线处理机的性能主要是吞吐率、加速比和效率。 1吞吐率(TP,Throughput Rate)：单位时间内能处理的指令条数或能输出的数据量。吞吐率越高，计算机系统的处理能力就越强。就流水线而言，吞吐率就是单位时间内能流出

12、的任务数或能流出的结果数。,第四章 流水线技术,最大吞吐率：流水线达到稳定状态后可获得的吞吐率。 （1）TPmax=1/t（理想情况） （2）TPmax=1/ maxt1，t2，t3，t4,第四章 流水线技术,子过程3为瓶颈段的时空图,最大吞吐率TPmax=1/3t,第四章 流水线技术,解决瓶颈有两种方法：,A： B：,第四章 流水线技术,T,重复设置瓶颈流水段后的工作时空图,第四章 流水线技术,实际吞吐率,设： m：指令流水线的段数； t0: 各段经过的时间； n：指令条数。,（1）完成n条指令的解释共需时间： T=mt0+(n-1) t0,第四章 流水线技术,2. 效率(Efficienc

13、y)：流水线的设备利用率；即在整个运行时间里，流水线的设备有多少时间是真正用于工作的。直接反映了处理机结构的有效程度。,各段时间相等：,各段时间不等：,其中， tj为瓶颈段的时间。,第四章 流水线技术,其中，分母为m个段总的加权时空区，分子为n个任务实际占用的总的加权时空区。 从时空图来看，所谓效率就是n个任务占用的时空区和m个段总的时空区面积之比。,设备利用率占整个系统设备利用率的比重不同，可以给每个段赋予不同的“权”值i，这样，线性流水线总效率的一般式为：,=,第四章 流水线技术,各段时间相等:,各段时间不等:,3. 加速比(Speedup Ratio)：m段流水线的速度与等效的非流水线的

14、速度之比。,总结：,若各t 相等： =TP* t,第四章 流水线技术,（二） 实例分析:性能分析（实测法, 分析法, 时空图法） 例1. 四段流水线, t1=t3=t4=t, t2=3t,求4个任务、10个任务时的TP，、SP 。,（1）分析法: 各段时间不等（ n =10 ）,第四章 流水线技术,第四章 流水线技术,(2) 时空图法:,TP=4/(6+3*3) t)=4/(15t)=0.267/t,=6*4 t /(4*15t)=2/5=40%,Sp=4*6t /15t=8/5=1.6,n=4时：,n=10时：同上。,第四章 流水线技术,比较:,n=4 0.267,n=10 0.303,n=

15、100 0.33,40%,45%,50%,1.6,1.8,1.98,Sp,TP(1 / t),m=4,说明:nm时流水性能才发挥得更好。,第四章 流水线技术,例2.四段浮点加法运算器流水线，各段时间相等，计算 Z=A+B+C+D+E+F+G+H，求流水线的吞吐率TP、效率 及加速比Sp ，注意有相关。,Z=A+B+C+D+E+F+G+H,1,2,3,4,5,6,7,解： TP=7/（15t）= 0.47/ t =7*4/(15*4)=7/15 = 47 Sp=4*7/15=28/15 = 1.87,5,5,5,5,6,6,6,6,7,7,7,7,第四章 流水线技术,例3. ASC计算机静态多功

16、能算术运算流水线各段时间相等，求计算6次浮点加、 5次定点乘的吞吐率、效率及加速比 （m=8,n=11）,第四章 流水线技术,分析：T加=（6+(6-1)）* t = 11t T乘=（4+(5-1)）* t = 8t,则 TP = 11/(（11+8）t） =11/19t=0.58/t =（6*6+5*4）t /(19*8t)=6/52=7/19=36.8 Sp =（6*6+5*4）t /19t = 56t /19t =2.95,第四章 流水线技术,例4：为提高流水线效率用哪两种主要途径来克服速度瓶颈？现有3段流水线，各段经过时间依次为t、3t、t。 （1）分别计算在连续输入3条指令时和30条

17、指令时的吞吐率和效率。 （2）按两种途径之一改进，画出你的流水线结构示意图，同时计算连续输入3条指令和30条指令时的吞吐率和效率。 （3）通过对（1）（2）两小题的计算比较可得出什么结论？,第四章 流水线技术,解：提高流水线效率，消除速度瓶颈主要有将瓶颈段再细分以及重复设置多个瓶颈段并联工作，给其轮流分配任务的两种途径。,（1）在3段流水线，各段经过时间依次为t、3t、t的情况下，连续流入3条指令时，将n=3，m=3，t1=t，t2 =3t，t3=t，tj=3t代入，可得吞吐率TP和效率为 ：,第四章 流水线技术,连续流入30条指令时，只需将上式中的n改为30，其它参数不变。,（2）若采取将第

18、2段细分成3个子段，每个子段均为t，构成的流水线结构如图所示。,t t t t t,段1 段2 段3,第四章 流水线技术,连续流入3条时，将n=3，m=5，ti= tj= t代入，得,7,3,7,5,5,3,7,5,3,7,3,2,5,3,),1,3,(,3,5,1,5,1,=,D,*,D,=,D,*,D,=,D,=,D,+,D,=,D,-,+,D,=,=,=,t,t,t,t,t,t,t,t,t,TP,i,i,i,i,i,h,= 43%,n=30： TP=0.88t =88%,= 0.43t,第四章 流水线技术,若采取将3个2段并联构成的流水线，其构成如图所示。 连续流入3条指令及流入30条指

19、令时的吞吐率Tp和效率所计算的结果分别与子过程细分的相同。,3t t 3t t 3t,有瓶颈（1） 消除瓶颈（2） n=3： n=3： TP=0.237t TP=0.43t =45% =43% n=30： n=30： TP=0.326t TP=0.88 t =54% =88%,第四章 流水线技术,（3）将题（1）中n=3和n=30的计算结果进行比较可以看出，只有当连续流入流水线的指令越多时，流水线的实际吞吐率和效率才会提高。 将（1）（2）题的计算结果进行比较，同样可以看出，无论采用瓶颈子过程再细分，还是将多个瓶颈子过程并联来消除流水线瓶颈，都只有在连续流入流水线的指令数越多时，才能使实际吞吐

20、率和效率得到显著的提高。若连续流入流水线的指令数越少，消除流水线瓶颈虽可以提高流水线的实际吞吐率Tp，而效率却可能下降。,第四章 流水线技术,例5有一个双输入端的加-乘双功能静态流水线，由经过时间为t、2t、2t、3t的1、2、3、4四个子过程构成。加按12 4连接，乘按134连接，流水线输出设有数据缓冲器，也可将数据直接返回输入。现要执行 A*（B+C*（D+E*F）+G*H 的运算；（1）请调整计算顺序，画出能获得吞吐率尽量高的流水时空图，标出流水线入、出端数据的变化情况，求出完成全部运算的时间及此期间流水线的效率。（2）如对流水线瓶颈子过程再细分，最少只需多少时间可完成全部运算？（3）若

21、子过程3不能再细分，只能用并联方法改进，问流水线的效率为多少？,第四章 流水线技术,结论：消除瓶颈方法，对较少任务而言，可减少计算时间，提高吞吐率；但因使用多套设备、且因静态流水线需排空后才可切换功能，因此，可能使效率降低。,注： 消除瓶颈。 功能切换。 数据相关控制。 （1）T=36 t，=38% （2） T=26 t （3） =26%,第四章 流水线技术,分段时间t尽量小、尽量一致，则TP越大； 当n m 时，TP=1/ t； 若m太多，需锁存器也越多，则处理时间长。 2. t选取：各级微操作所需逻辑门的延迟、加走线延迟、再加3%冗余量。 3. 缓冲深度影响（缓冲器个数）。 4. 非线性流

22、水的合理控制。,（二）相关处理 定义 ：相近指令出现某种关联而使其不能同时执行。 资源相关 数据相关 控制相关,（5） 流水的控制和设计 （一）时序和缓冲,第四章 流水线技术,1. 资源相关（resource dependence）,资源相关是指当有多条指令进入流水线后在同一机器周期内争用同一功能部件所发生的冲突。,两条指令同时要用一个乘法器,指 令,流水段,不同类型指令中各流水段进行的操作,第四章 流水线技术,两条指令同时访存造成资源相关,冲突,取指 译码 执行 访存 写回,例2：,第四章 流水线技术,（1）使i+3指令停顿一拍进入流水线，以解决访存相关。 （2）重复设置一个存储器。,解决方

23、法：,第四章 流水线技术,流水线顺序流动方式：流水线输出端任务的流出顺序和输入端的流入顺序一致。 流水线乱序流动方式（异步流动方式、不按顺序流动方式）：流水线输出端任务的流出顺序和输入端的流入顺序可以不一致。,2. 数据相关（data dependence）,数据相关：当一条指令需要用到前面指令的执行结果，而前面的指令均在流水线中重叠执行，还未产生相应的结果时，就会引起“数据相关”。,第四章 流水线技术,例：有i 和j两条指令，i指令在前，j指令在后，则可能发生三种不同类型的数据相关： RAW(Read After Write) (先写后读)（写读：WR）相关 - 指令 j 试图在指令 i 写

24、入寄存器前就读出该寄存器内容，这样，指令j就会错误地读出该寄存器旧的内容。 如：i: R1+R2-R3 j: R3*R4-R5,数据相关例,顺序流动,第四章 流水线技术,WAR (Write After Read) (先读后写)（读写：RW）相关- 指令 j 试图在指令 i读出寄存器之前就写入该寄存器，这样，指令i就错误地读得该寄存器新的内容。 如：i: R3*R4-R5 j: R1+R2-R3,不按顺序流动,WAW (Write After Write) (先写后写)（写写：WW）相关- 指令j试图在指令i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令i写入的值

25、成为该寄存器内容。 如：i: R1*R2-R3 j: R4+R5-R3,不按顺序流动,第四章 流水线技术,例1：如果流水线要执行以下的两条指令： X3=X1-X2 X5=X3+X4,这是一个典型的先写后读的（RAW）写读相关。,例2：结果寄存器的冲突： X3=X4/X5 X3=X1-X2,这是个先写后写的（WAW）写写相关，两条指令都要用X3存放结果，此时第二条指令要等待第一条指令完成后才能写。,第四章 流水线技术,解决数据相关的方法：（可采用软件和硬件技术） 时间推后法 旁路技术或相关专用通路技术（定向技术） 定向技术：将一个计算结果直接传送到所有需要它的功能单元的输入端。,例3：一条指令要

26、把结果存放到上一条指令存放操作数的寄存器中时发生的冲突。 X1=X2*X3 X3=X0-X4,这是个先读后写的（WAR）读写相关。如果这两条指令接连地送到乘法功能部件和加法功能部件中，由于加法比乘法快得多，第二条的结果X3先产生，但必须等待第一条指令做完后才能送X3。,第四章 流水线技术,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,IF,ID,EX,MEM,WB,ADD R1,R2,R3,SUB R4,R1,R5,AND R6,R1,R7,OR R8,R1,R9,XOR R10,R1,R11,定向传递R1值,数

27、据相关和定向传递指令,例：五段流水线的数据相关及采用定向技术解决此相关。,第四章 流水线技术,IF,EX,MEM,ID,R,IF,EX,MEM,ID,R,W,IF,EX,MEM,ID,R,W,IF,EX,MEM,ID,R,IF,EX,MEM,ID,R,ADD R1,R2,R3,SUB R4,R1,R5,AND R6,R1,R7,OR R8,R1,R9,XOR R10,R1,R11,定向传递R1值,减少定向传送次数的方法,第四章 流水线技术,定向传送及具有旁路的ALU,第四章 流水线技术,控制相关（control dependence） 控制相关主要由无条件转移和条件转移引起。 （转移指令概率占

28、1/4左右，不可忽视） 解决控制相关主要使用的技术： 加快和提前形成条件码：有的指令的条件码并不一定要等执行完毕得到运算结果后才能形成； 静态转移预测技术：在硬件和软件设计完成后，转移预测方向则确定。 猜测法：按一个方向流水，预测成功或不成功方向； 预取转移目标：向两个分支方向预取指令； 加快短循环程序处理 ：设置特殊循环指令、利用硬件向后检测若干条指令（IBM360/91：向后检测8条）；,第四章 流水线技术,流水机器的中断处理 流水机器处理中断的关键不在于如何缩短断流时间，而是如何处理好断点现场及中断后的恢复问题。 不精确断点法(同外部设备中断处理一样)：不论第i条指令在流水线的哪一段发出

29、中断申请，都不再允许那时还未进入流水线的后续指令再进入，允许已流入的指令执行完；现场是最后一条指令的。 精确断点法：不论第i条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第i条的，在第i条之后进入流水线的指令的原有现场都能恢复 (增加设备，增加后援R，保存流水线内各条指令的原有状态） 。,第四章 流水线技术,（1） 先进的流水调度方法 - 动态调度,静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。目前比较流行。 动态调度：通过硬件重新安排指令的执行顺序以减少流水的停顿。,优点： （1）能处理某些在编译时无法知道的相关情况；

30、（2）能简化编译程序设计； （3）使代码有可移植性。 缺点：相应的硬件较为复杂。,三、先进的流水技术,第四章 流水线技术,（2） 非线性流水线的冲突及调度,非线性流水线的冲突：由于段间设置有反馈回路，一个任务在流水的整个执行过程中可能会多次通过同一流水段，因此不能每拍均向流水线送入新任务。若仍每拍送入一个新任务，则在某些时刻会发生几个任务同时争用同一流水段的现象，即产生功能段的使用冲突。 解决方法：间隔恰当的拍数后再向流水线送入下一个任务。这就需要对流水线作适当的调度。 流水线调度解决的问题：间隔几拍再向流水线送入下一个任务，才不发生功能段使用冲突。,第四章 流水线技术,流水线调度常借助于二维

31、预约表和状态转换图来进行分析。 二维预约表（也称预约表：Reservation Table ）：流水线各段的时间关系表。反映一个任务使用各段所需间隔的拍数。,根据预约表可较容易地推算出一个任务执行时，各段所需 间隔的周期拍数。,1、预约表,设：非线性、单功能流水线P，由K段组成，每个任务流过流水线需N个时钟周期（t1,t2,tn），段为纵坐标，时间为横坐标。,第四章 流水线技术,二维预约表,图中每一行代表P的一个段，每一列表示相应的时钟周期（节拍）。若某个任务在周期ti需要使用Sj段进行处理，则在行Sj和列ti 的相交处以“X”（ “” ）表示。,第四章 流水线技术,禁止表F=1，5，6，8,

32、表明：要想使流入的任务不发生同时争用功能段的情况，相邻两个任务进入流水线的间隔拍数就一定不能为1、5、6、8拍。 即：非线性流水线的禁止启动距离为：1、5、6、8拍。,2、禁止表F（Forbidden List）：非线性流水线中，各段对一个任务流过时会重复使用同一个功能段的节拍（时钟周期）间隔数的集合。即表示：禁止使用此集合中的间隔拍数向流水线送入任务。,第四章 流水线技术,3、冲突向量C（Collision Vector）（或称位向量）： C=(CnCn-1. C2 C1) 其中第i位的状态表示与当时相隔 i 拍时间间隔，给流水线送入后继任务是否会发生功能段的使用冲突。 若不会发生冲突：令该

33、位为“0”，即Ci=0, 表示允许送入； 若会发生冲突：令该位为“1”，即Ci=1, 表示禁止送入。 冲突向量C的位数n：为最大禁止间隔数。 例：禁止表F=1，3，6，则n 为6，可构成6位冲突向量C： C = （100101） 前例中禁止表F=1，5，6，8，则可形成8位冲突向量C： C = （10110001）,第四章 流水线技术,原始（初始）冲突向量：第1个 任务第1拍流入流水线时的冲突向量（可从禁止表F生成）。 从冲突向量C=（10110001）可知，隔2、3、4、7拍可送入新任务（第2个任务）。 但当新任务（第2个任务）送入后，应当产生新的冲突向量，以便决定下一个（第3个）任务可进入

34、的时刻。,第四章 流水线技术,新的冲突向量的产生方法：若某任务K是在上一个任务间隔2拍时送入流水线，则把上一个任务当时的冲突向量向右移2位（左边空位补0），与当前任务K的原始冲突向量按位“或”。 例：原始冲突向量C=（10110001） 选择第2个任务在间隔3拍时流入：3：00010110 V 10110001（原始） 10110111（新） 选择第3个任务在间隔4拍时流入：4：00001011 V 10110001（原始） 10111011（新）,第四章 流水线技术,4、状态转移图： 从原始冲突向量开始，选择可输入任务的节拍向流水线输入新任务，产生新的冲突向量。按新的冲突向量流入新任务，又可

35、产生新的冲突向量，一直进行到不再产生不同的冲突向量为止。按此，可画出用冲突向量表示的状态图。图中两个冲突向量之间用有向弧上的数字表示引入后继任务产生其新的冲突向量所用的间隔拍数。,非线性流水线预约表相应状态图,禁止表F=1，5，6，8,第四章 流水线技术,过程: 1. 按给出的预约表写出禁止表 F=1，5，6，8；,2. 写出n位初始冲突向量（10110001）；,3. 按禁止表约束条件列出新的冲突向量，直到不再生成新的冲突 向量为止（当前冲突向量和初始冲突向量按位“或”）；,4. 画出用冲突向量表示的流水线状态转移图；,5. 列出按流水线状态转移图中任何一个闭合回路进行流水线调度的方法。 6

36、. 求出各种调度方法的平均间隔拍数（平均延迟、平均等待时间）；,7. 求出最佳等间隔和非等间隔调度拍数；,第四章 流水线技术,非线性流水线预约表相应状态图,调度策略 ： 平均间隔拍数： 非等间隔（2，2，7） （2+2+7）/ 3 = 3. 67 （3，4） （3+4）/ 2 = 3. 5 等间隔（7） 7,本例子中最佳非等间隔调度为（3，4），即：3拍，4拍，. 平均间隔为3.5拍，而等间隔调度为7拍。,第四章 流水线技术,例：在一个4段非线性流水线处理机上需经7拍才能完成一个任务，其预约表如表所示。分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟、流水线的最大吞吐率

37、及其调度时的最佳方案。按此流水调度方案，输入6个任务，求实际的吞吐率。,解：延迟禁止表F=2，4，6 初始冲突向量C=（101010）,5、单功能流水线的调度控制：用状态转移图对流水线进行调度，控制产生等间隔或不等间隔的调度策略。,第四章 流水线技术,各种调度方案及其相应的平均延迟：,第四章 流水线技术,由上表可知，最小的平均延迟为4拍。此时流水线的最大吞吐率： TPmax=1/4（任务/拍） 最小平均延迟调度方案有（1，7）、（3，5）两种非等间隔周期性调度方案。 按（1，7）调度方案输入6个任务，全部完成的时间为： 1+7+1+7+1+7=24拍 实际吞吐率 TP=6/24（任务/拍）=0

38、.25 （任务/拍）,第四章 流水线技术,若按（3，5）调度方案输入6个任务，全部完成的时间为： 3+5+3+5+3+7=26拍 实际吞吐率 TP=6/26（任务/拍） =0.23 （任务/拍） 若按（5，3）调度方案输入6个任务，全部完成的时间为： 5+3+5+3+5+7=28拍 实际吞吐率 TP=6/28（任务/拍） =0.21 （任务/拍） 可见最佳方案应当为（1，7）调度方案，输入6个任务的实际吞吐率比其它方案更高些。,第四章 流水线技术,粗粒度并行性：在多处理机上分别运行多个进程，由多台处理机合作完成一个程序；,单发射结构的RISC：RISC机的体系结构关键技术是精心的流水线设计和优

39、化的编译技术，使得每个周期能够发射一条指令。它的CPI1（由于有相关等影响），这种结构称为单发射结构的RISC。,细粒度并行性：指在一个进程中进行操作一级或指令一级的并行处理。RISC机进一步开发细粒度并行性。现在新的系统结构设计，基本思想是要挖掘指令级的并行性，使单处理机达到一个时钟周期完成多条指令。,对一个周期能发射多条指令计算机有超标量、超流水、超长指令字计算机，此外还有数据流计算机也属于多发射结构。,四、流水中指令级并行性的进一步开发,第四章 流水线技术,（1） 超级标量计算机,超标量（Superscalar）计算机：每个时钟周期内能同时发射（启动）多条指令的计算机。,主要特点： （1

40、）配置有多个性能不同的处理部件，采用多条流水线并行处理。 （2）能同时对若干条指令进行译码，将可并行的指令送往不同的执行部件，从而达到每个周期启动多条指令。 （3）在程序运行期间由硬件（通常是状态记录部件和调度部件）完成指令调度。,（4）超级标量机的硬件是不能重新安排指令的前后次序的，但可以在编译程序中采取优化的办法，事先在编译时对指令的执行次序进行精心安排，把能并行执行的指令搭配起来，挖掘更多的指令并行性。 （5）超级标量处理机特别适合于求解象稀疏矩阵这样的复杂标量问题。,第四章 流水线技术,每拍启动3条指令 并行度=3,超级标量机,1超级标量计算机的原理：,第四章 流水线技术,2. 超标量

41、流水线调度Cyclone计算机,超标量流水线的指令调度策略： 按序发射按序完成 按序发射无序完成 无序发射无序完成 无论那种调度策略，都要保证程序运行的最终结果是正确的。 Pentium处理器采用的是按序发射按序完成策略。 PentiumII/III处理器采用的是按序发射无序完成。,指令发射：启动指令进入流水线的过程。 指令发射策略：指令发射所使用的协议或规则。 按序发射（in-order issue）：指令按原有次序发射。 无序发射或乱序发射（out-of-order issue）：将具有相关的指令推后发射，而将后面的无相关性的指令提前发射，即不按程序原有次序发射指令。,第四章 流水线技术,

42、超长指令字（VLIW：Very Long Instruction Word）：由编译程序在编译时找出指令间潜在的并行性，进行适当调度安排，把多个能并行执行的操作组合在一起，成为一条具有多个操作段的超长指令字。 在VLIW机器中，采用多个独立的功能部件，以一条长指令（利用其中每个操作段）控制实现多个操作的并行执行（相当于同时执行多条指令），减少存储器访问。,主要特点： （1）单一的控制流。只有一个控制器，每个周期启动一条指令。 （2）超长指令字被分成多个控制字段，每个字段直接独立地控制每个功能部件。 （3）含有大量的数据通路和功能部件，由于编译器在编译时间已考虑可能出现的数据相关和资源相关，故控

43、制硬件较简单。 （4）在编译阶段完成超长指令中多个可并行执行操作的调度。,（2） 超长指令字计算机（VLIW）,第四章 流水线技术,每拍启动一条长指令，执行3个操作，相当于3条指令，并行度=3。,超长指令字计算机（VLIW）,超长指令字计算机的例子：Cycra 5计算机,第四章 流水线技术,（3） 超级流水线计算机,即：超流水结构是把每一个功能段流水级（一个基本时钟周期）分成多个（例如3个）子流水级（多个超流水线机器周期）；而在每一个子流水级中取出的仍只有一条指令，但总的来看，在一个基本时钟周期内取出了三条指令。,硬件结构特点：对于超流水线结构，其中指令部件可以只有一套，也可以有多套独立的执行

44、部件。虽然每个机器周期只能流出一条指令，但它的周期比其它机器短，一台m度的超级流水线计算机的周期为一般机器周期的1/m，它的一个操作需要m个周期，因而在流水线能充分发挥作用时，其并行度能达到m。,超流水线（Super Pipelining）计算机：每个时钟周期内能分时发射（启动）多条指令的计算机。,第四章 流水线技术,并行度=3： 每1/3拍启动一条指令,超级流水线的原理结构图,第四章 流水线技术,这种方法主要通过提高流水线运行速度来增强机器性能。为提高运行速度，必须要加深流水深度，既增加流水段数，以减少每一段的延迟时间，这样就可加快流水线的运行频率。 例：MIPS公司的64位RISC计算机R

45、4000超级流水处理机，分8段：取指1（IF），取指2（IS），读RF，执行（EX），取数1（DF），取数2（ DS），标记检查（TC），写RF（WB）。,第四章 流水线技术,（4） 超标量超流水计算机,把超标量技术与超流水技术结合在一起，这就是超标量超流水线处理机。超标量超流水线处理机在一个时钟周期内要发射指令n次，每次发射指令m条，因此，超标量超流水线处理机每个时钟周期总共要发射指令m*n条。,超标量超流水线处理机的指令执行时空图,第四章 流水线技术,Pentium流水线结构（五级双流水线） 一个周期发射两条整数指令,1、Pentium的超标量流水线,（5） 奔腾系列处理机流水处理,第四章

46、 流水线技术,结构特点：Pentium是超标量结构，它可以并行地在一个周期内执行两条整数指令。 Pentium的两个整数流水线分别称为“U”和“V”，而并行发射两条指令称为“成对”。 U管道可执行IntelX86体系结构中的任何指令，而V管道只可执行“指令成对法则”中规定的“简单”指令。当指令是成对的，发给V管道的指令永远是发给U管道的那条指令后的顺序的下一条指令。,2、PentiumCPU的体系结构,第四章 流水线技术,(2)分立的指令CACHE和数据CACHE 不仅使指令预取和数据读写能无冲突地同时完成，而且可同时与U、V两条流水线分别交换数据。,(3)重新设计的浮点运算部件 执行过程是分

47、为8段的流水线。前4段为指令预取（PF）、指令译码（D1）、地址生成（D2）、取操作数（EX），在U、V流水线完成；后4段为执行1（X1）、执行2（X2）、结果写回寄存器堆（WF）、错误报告（ER），在浮点运算部件中完成。一般情况下，只能由U流水线完成一条浮点操作指令；少数情况下，V流水线也能同时完成一条如浮点数交换这样的指令。,(4)以设置转移目标缓存器BTB方式实现动态转移预测 Pentium采用动态转移预测技术，来减少由于控制相关性引起的流水线性能损失 。,(1)超标量流水线 超标量流水线是Pentium系统结构的核心。它的U和V两条指令流水线都有自己的ALU、地址生成电路和与数据cac

48、he的接口。U、V流水线采用的是按序发射、按序完成的调度策略。,第四章 流水线技术,例如：向量计算：A*(B+C) 的循环程序,用FORTRAN语言为 ： Do 10 I=1,n 10 D（I）=A（I）*（B（I）+C（I）,1.水平处理法(横向) d1=a1*(b1+c1) d2=a2*(b2+c2) dn=an*(bn+cn),2.垂直处理法（纵向） Bi+CiEi(i=1到n) Ai*EiDi(i=1到n),适合于流水处理,（1） 向量处理方式,五、 向量的流水处理,第四章 流水线技术,3.分组纵横处理法 分成k组, 每组长度为m，组内垂直处理，组间水平处理。 n=k*m+r (r为第

49、k+1组剩余分量) Bi+CiEi (1到m) Bi+CiEi (m+1到2m) Ei*AiDi (1到m) Ei*AiDi (m+1到2m) ,（2） 向量处理机的结构,向量（流水）处理机（Vector Processor）：由向量数据表示和流水线技术相结合构成的向量流水处理机。,第四章 流水线技术,一、存储器存储器型结构,参加运算的向量数据在存储器中，运算的结果也送到存储器中。 例：向量加法 C=A+B,存储器,A,B,C,流水线运算部件,存储器-存储器型结构 （一种能实现两个向量相加的流水结构的加法器）,第四章 流水线技术,A、B、C的向量长度为8，加法流水线分为4个功能段，主存储器采取

50、了8个存储体，多体交叉访问，如果不出现存储体冲突，带宽将是单体存储器的8倍。,改进多存储模块结构,第四章 流水线技术,C=A+B向量处理时序图,第四章 流水线技术,二、寄存器寄存器型（如CRAY_1机）,原理：在运算部件中设置多个向量寄存器，需要进行向量处理时，先执行存储器取指令，将向量数据传送至向量寄存器中，流水线运算部件由向量寄存器提供数据、处理后的结果也送至向量寄存器中。Cray-1向量计算机就是一个典型的寄存器寄存器型。,结构： （1）Cray-1机的主存储器容量为8M字节，包含64个存储模块。 （2）Cray-1机设置了8个向量寄存器组（V0-V7)，每个寄存器组包含64个向量R，每个R为64位； Vi 最多可存64位。 （3）8个64位标量寄存器。 （4）8个24位地址寄存器。 （5）256个长度为16位的指令缓冲寄存器。 （6）机器的运算部件，采用独立的多个功