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

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

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

3、线技术：将一个重复的时序过程分成若干个子过程，每个子过程都可有效的在其专用功能段上和其它子过程同时执行的一种技术。 流水线的基本结构中主要包括三大部分：锁存器、时钟、功能段（站）。流水线中每个功能段（站）都是由一些执行算术和逻辑功能的组合逻辑线路组成的，它们可以互相独立地对流过的信息进行某种操作，相邻两个功能段（站）由高速锁存器（latch）隔开，信息在各站间的流动靠同时送到各站的时钟信号来控制。二、流水工作方式第四章 流水线技术S1S2Sk输入输出流水线的基本结构取指访存执行译码写回IFIDEXMEMWBS1S2S3S4S5输入输出指令的流水处理。 L L L L L第四章 流水线技术如果每

4、个子过程经过的时间都是t，则指令的流水线处理过程可用时空图来描述。 T时间流水时空图1234S空间（段号）.12345.n-1n.12345.n-1n.12345.n-1n.12345.n-1nttttm t(n-1) t 填入 正常 排空 t第四章 流水线技术2、流水线特点： 1）流水一定重叠，比重叠更苛刻。 2）一条流水线通常由多个流水段组成。 3）每段有专用功能部件，各部件顺序连接，不断流。 4）流水线有建立时间、满载时间、排空时间， 5）各段时间尽量短、一致，不一致时最慢子过程为瓶颈。 6）给出的最大吞吐率等指标，为满负载最佳指标。建立时间：在流水线开始时有一段流水线填入时间，使得流水

5、线填满。即第1条指令从流入到流出所需的时间。正常流动时间：流水线正常工作，各功能段源源不断满载工作。排空时间（释放时间）：流水线最后一条指令流入后到流出的时间。 流水线的时空图是描述流水线工作、分析评价流水线效能的重要工具。第四章 流水线技术1、流水线的分级：（按处理的级别分级） 操作部件级(arithmetic pipelining)：将复杂的算逻运算组成流水工作方式； 指令级(instruction pipelining) ：把一条指令解释过程分成多个子过程 ； 处理机级或宏流水线级(macro pipelining) ：由两个以上处理机串行地对同一数据流进行处理，每个处理机完成某一专门任

6、务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中。 （2） 流水线的分级、分类第四章 流水线技术多功能流水线从一种功能变为另一种功能时需要重新连接，虽然它对资源的利用率可以较高，应用时也较灵活，但它的控制比单功能流水线复杂得多。因此大多数流水计算机主要采用单功能流水线。 2、流水线的分类： 按功能分类：单功能流水线、多功能流水线 单功能流水线(unifunction pipelining)：只能实现一种固定的专门功能的流水线（如CRAY-1）。 多功能流水线(multifunction pipelining) ：通过各站间的不同连接方式可以同时或不同时地实现多种功能的流水线（如

7、TI-ASC）。 第四章 流水线技术 按工作方式分类：静态流水线、动态流水线静态流水线(static pipelining)：在同一时间内各功能段只能按一种运算（功能）的连接方式工作。动态流水线(dynamic pipelining) ：在同一时间内各功能段允许按多种不同运算（功能）的连接方式工作。特点：静态流水线仅当指令都是同一类型时才能连续不断地执行。当从一种功能方式变为另一种功能方式时，必须先排空流水线，然后再切换成另一种功能进行流水处理。静态流水线的功能不能频繁地变换，否则它的效率将很低。动态流水线可以提高流水线的吞吐率和设备的利用率。第四章 流水线技术按连接方式（流水线中是否有反馈回

8、路）分类：线性流水线、非线性流水线。线性流水线(linear pipelining) ：从输入到输出，每个功能段只允许经过一次，不存在反馈回路。一般的流水线均属于这一类。非线性流水线(non-linear pipelining) ：存在反馈回路，从输入到输出过程中，某些功能段将数次通过流水线，这种流水线常用于进行递归运算。 1234出入非线性流水线第四章 流水线技术1、TI-ASC算术运算流水线（多功能）（3） 流水线举例乘12345678输入减阶对阶移位相加规格化相乘累加输出输入减阶对阶移位相加规格化输出123458加或减输入相乘累加输出1678功能段第四章 流水线技术.1234.n-1n.

9、1234.n-1n.1234.n-1n.1234.n-1n12345867.1234.n-1n.1234.n-1n时间空间(段号)浮加一二三四二三一二一一定乘.静态多功能流水线时-空图静态流水线：只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。 第四章 流水线技术.12345.n-1n.12345.n-1n.12345.n-1n.12345.n-1n12345867.12345.n-1n.12345.n-1n时间浮加定乘一二三四五六一二三四五六七一二三四五一二三四动态多功能流水线时-空图区别：如果从软硬功能分配的观点上来看，静态流水

10、线其实是把功能负担较多地加到软件上，以简化硬件；动态流水线则是把功能负担较多地加在硬件上，以提高流水的效能。空间(段号)第四章 流水线技术（一）VAX8600的流水结构a. I部件：预取指令，操作码译码，预取操作数，并存放运算结果。b. E部件：执行指令。c. F部件：浮点加速器。d. M部件：控制CPU和输入输出设备对主存的访问，有16k字节的cache和把虚存地址转换成实存地址的地址转换表（快表）。e. 操作台：提供同操作员，引导设备和远程诊断的界面。 指令流水线：一条指令的取指令、译码、取操作数和执行等几个过程能同它前后的指令在时间上重叠，用这种指令重叠的方法构成的流水线就是指令流水线，

11、又叫指令先行控制。 2VAX8600和长城386计算机的指令流水线第四章 流水线技术操作台E部件F部件I部件M部件主存标准SBI适配器选件SBI适配器SBISBIC总线诊断总线写总线操作数总线虚拟地址存储器数据总线适配器总线数组总线I/O子系统I/O子系统VAX8600的CPU结构图第四章 流水线技术I部件和E部件这两个互相独立的部件组成指令流水线。I部件与E部件的关系：I部件有一个8个字节的指令缓冲寄存器。预取的操作数也包括从通用寄存器中的取数，为此在I部件中还有一组寄存器用作存放16个通用寄存器相同内容的副本，E部件在修改通用寄存器内容时，也同时自动修改I部件中副本的内容。I部件向E部件（

12、或F部件）提供执行所需的操作码和操作数，当E部件执行完后，I部件提供存储结果所需的写数地址。指令整个工作过程是 流水线化的。 第四章 流水线技术取指令指令译码形成操作数地址取操作数执行指令存储结果N-1N-2N-1N-2N-1N-1N-1N-1N+1N+1N+1N+1N+1N+1N+2N+2N+2 周期 操作VAX8600指令流水线的工作顺序实框：表示CPU在执行一条典型的指令时的动作顺序。虚线：表示6个动作是各自分开进行的，可以同其它指令的动作并行进行。 第四章 流水线技术 内部有六个部件总线接口部件：同外部的接口，读取指令、读写数据。I部件：指令预取部件：取指令放在指令预取队列中，容量为1

13、6个字节。指令译码部件：形成指令微码，指令队列中可放3条指令。 E部件：执行部件：控制部件、数据部件、保护测试部件分段部件分页部件存储管理部件（二）长城386指令流水线第四章 流水线技术 取指令1 取指令2 取指令3 取指令4 存结果1 取指令5 取指令6 指令译码器1 指令译码2 指令译码3 指令译码4 指令译码5 执行1 执行2 执行3 执行4 地址变换和MMU 地址变换和MMU80386的指令流水处理第四章 流水线技术（4）流水线性能分析计算（一）技术指标衡量流水线处理机的性能主要是吞吐率、加速比和效率。 1吞吐率(TP,Throughput Rate)：单位时间内能处理的指令条数或能输

14、出的数据量。吞吐率越高，计算机系统的处理能力就越强。就流水线而言，吞吐率就是单位时间内能流出的任务数或能流出的结果数。第四章 流水线技术 最大吞吐率：流水线达到稳定状态后可获得的吞吐率。（1）TPmax=1/t（理想情况） （2）TPmax=1/ maxt1，t2，t3，t4 “瓶颈”子过程： 1234t t 3t t 第四章 流水线技术子过程3为瓶颈段的时空图最大吞吐率TPmax=1/3t STS1S2S3S4t1t2t3t4t5t6t7t8t9t10t12t13t14t151234t11123412 3 41234输出第四章 流水线技术13a23b3c4瓶颈段细分 2 1 4 3a 3b

15、3c 333重复设置瓶颈流水段解决瓶颈有两种方法：A：B：第四章 流水线技术T重复设置瓶颈流水段后的工作时空图SS1S2S3aS3cS3bS4123546789101112123546789101112147102581136912123546789101112t1t12t17第四章 流水线技术实际吞吐率设： m：指令流水线的段数； t0: 各段经过的时间； n：指令条数。（1）完成n条指令的解释共需时间： T=mt0+(n-1) t0（2）流水线的实际吞吐率为 ： 可以看出不仅实际的吞吐率总是小于最大的吞吐率，而且只有当nm时，实际的吞吐率才能接近于理想的最大吞吐率。第四章 流水线技术2.

16、效率(Efficiency)：流水线的设备利用率；即在整个运行时间里，流水线的设备有多少时间是真正用于工作的。直接反映了处理机结构的有效程度。=n个任务实际占用的时-空区m个段总的时-空区各段时间相等：各段时间不等：n *tim*ti+(n-1)tjmi=1=mi=1其中， tj为瓶颈段的时间。=m Tm nt0=nt0mt0+(n-1) t0第四章 流水线技术=其中，分母为m个段总的加权时空区，分子为n个任务实际占用的总的加权时空区。从时空图来看，所谓效率就是n个任务占用的时空区和m个段总的时空区面积之比。 设备利用率占整个系统设备利用率的比重不同，可以给每个段赋予不同的“权”值i，这样，线

17、性流水线总效率的一般式为：=第四章 流水线技术nSp=T非流水T流水=n*m*tm*t+(n-1)*t=n*mm+n-1=m1+m-1各段时间相等:各段时间不等:Sp=n * timi=1ti+(n-1)*tjmi=13. 加速比(Speedup Ratio)：m段流水线的速度与等效的非流水线的速度之比。总结： 若各t 相等： =TP* t第四章 流水线技术（二） 实例分析:性能分析（实测法, 分析法, 时空图法）例1. 四段流水线, t1=t3=t4=t, t2=3t,求4个任务、10个任务时的TP，、SP 。=n个任务实际占用的时-空区m个段总的时-空区（1）分析法: 各段时间不等（ n

18、=10 ）TP=nti+(n-1)tjmi=1第四章 流水线技术6*10t605=4*6t+9*3*4t=24+108= 1145% TP=106*t+3*9* t =1033*t =0.303 / t =Sp=n *timi=1ti+(n-1)*tjmi=110*6 t(6+3*9) t=2011=1.8第四章 流水线技术时间12343111223234123123123444443t3t空间(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.6n=4时：n=10时：同上。第四章

19、流水线技术比较:n=4 0.267n=10 0.303n=100 0.3340%45%50%1.61.81.98SpTP(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+H1234567解：TP=7/（15t）= 0.47/ t=7*4/(15*4)=7/15 = 47Sp=4*7/15=28/15 = 1.871111222233334444555566667777时间空间求阶差对阶尾数加规格化第四

20、章 流水线技术例3. ASC计算机静态多功能算术运算流水线各段时间相等，求计算6次浮点加、 5次定点乘的吞吐率、效率及加速比 （m=8,n=11）12345612345612345612345612345867123456123456时间浮加定点乘一二三四五一二三四五一二三四五一二三四五第四章 流水线技术分析：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

21、=2.95第四章 流水线技术例4：为提高流水线效率用哪两种主要途径来克服速度瓶颈？现有3段流水线，各段经过时间依次为t、3t、t。（1）分别计算在连续输入3条指令时和30条指令时的吞吐率和效率。（2）按两种途径之一改进，画出你的流水线结构示意图，同时计算连续输入3条指令和30条指令时的吞吐率和效率。（3）通过对（1）（2）两小题的计算比较可得出什么结论？ 第四章 流水线技术解：提高流水线效率，消除速度瓶颈主要有将瓶颈段再细分以及重复设置多个瓶颈段并联工作，给其轮流分配任务的两种途径。 （1）在3段流水线，各段经过时间依次为t、3t、t的情况下，连续流入3条指令时，将n=3，m=3，t1=t，t

22、2 =3t，t3=t，tj=3t代入，可得吞吐率TP和效率为 ：ttttntnTPmijiD=D+D=D-+D=1133253)1(1第四章 流水线技术连续流入30条指令时，只需将上式中的n改为30，其它参数不变。 （2）若采取将第2段细分成3个子段，每个子段均为t，构成的流水线结构如图所示。 t t t t t 段1 段2 段3 = 45%第四章 流水线技术连续流入3条时，将n=3，m=5，ti= tj= t代入，得73755375373253)13(35151=D*D=D*D=D=D+D=D-+D=tttttttttTPiiiiih= 43%n=30：TP=0.88t=88%= 0.43t

23、第四章 流水线技术若采取将3个2段并联构成的流水线，其构成如图所示。连续流入3条指令及流入30条指令时的吞吐率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）题的计算结果进行比较，同样可以看出，无论采用瓶颈子过程再细分，还是将多个瓶颈

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

25、。（2）如对流水线瓶颈子过程再细分，最少只需多少时间可完成全部运算？（3）若子过程3不能再细分，只能用并联方法改进，问流水线的效率为多少？ 第四章 流水线技术分析：将计算式展开后得到 A*B + A * C*D + A * C * E*F+G*H 4 1 1 2 3 5 6 7 89结论：消除瓶颈方法，对较少任务而言，可减少计算时间，提高吞吐率；但因使用多套设备、且因静态流水线需排空后才可切换功能，因此，可能使效率降低。注：消除瓶颈。功能切换。数据相关控制。（1）T=36 t，=38% （2） T=26 t（3） =26% 第四章 流水线技术分段时间t尽量小、尽量一致，则TP越大； 当n m

26、时，TP=1/ t； 若m太多，需锁存器也越多，则处理时间长。2. t选取：各级微操作所需逻辑门的延迟、加走线延迟、再加3%冗余量。3. 缓冲深度影响（缓冲器个数）。4. 非线性流水的合理控制。（二）相关处理 定义 ：相近指令出现某种关联而使其不能同时执行。资源相关数据相关控制相关（5） 流水的控制和设计 （一）时序和缓冲第四章 流水线技术1. 资源相关（resource dependence）资源相关是指当有多条指令进入流水线后在同一机器周期内争用同一功能部件所发生的冲突。213例1：546XXXXXX*=*=两条指令同时要用一个乘法器ALULOAD/STOREIF取指取指ID译码、读寄存器

27、堆译码、读寄存器堆EX执行计算访存有效地址MEM-访存（读或写）WB结果写回寄存器堆将读出的数据写入寄存器堆指 令流水段不同类型指令中各流水段进行的操作第四章 流水线技术两条指令同时访存造成资源相关MEMEXIDIF指令i+4WBMEMEXIDIF指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321 时钟指令冲突取指 译码 执行 访存 写回例2：第四章 流水线技术EXIDIF指令i+4MEM EXIDIF停顿指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令8765

28、4321 时钟指令9WBMEM（1）使i+3指令停顿一拍进入流水线，以解决访存相关。（2）重复设置一个存储器。解决方法：第四章 流水线技术流水线顺序流动方式：流水线输出端任务的流出顺序和输入端的流入顺序一致。流水线乱序流动方式（异步流动方式、不按顺序流动方式）：流水线输出端任务的流出顺序和输入端的流入顺序可以不一致。2. 数据相关（data dependence）数据相关：当一条指令需要用到前面指令的执行结果，而前面的指令均在流水线中重叠执行，还未产生相应的结果时，就会引起“数据相关”。第四章 流水线技术例：有i 和j两条指令，i指令在前，j指令在后，则可能发生三种不同类型的数据相关： RAW

29、(Read After Write) (先写后读)（写读：WR）相关 - 指令 j 试图在指令 i 写入寄存器前就读出该寄存器内容，这样，指令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试图在

30、指令i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令i写入的值成为该寄存器内容。如：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存放结果，此时第二条指令要等待第一条指令完成后才能写。第四章 流水线技术解决数据相关的方法：（可采用软件和硬件技术）时间推后法旁路技术或相关专用通路技术（定向技术）定向技术：将一

31、个计算结果直接传送到所有需要它的功能单元的输入端。例3：一条指令要把结果存放到上一条指令存放操作数的寄存器中时发生的冲突。 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,R3SUB R4,R1,R5AND R6,R1,R7OR R8,R1,

32、R9XOR R10,R1,R11定向传递R1值数据相关和定向传递指令例：五段流水线的数据相关及采用定向技术解决此相关。第四章 流水线技术IF EX MEM IDR WBWIF EX MEM IDR WBWIF EX MEM IDR WBWIF EX MEM IDR WBWIF EX MEM IDR WBWADD R1,R2,R3SUB R4,R1,R5AND R6,R1,R7OR R8,R1,R9XOR R10,R1,R11定向传递R1值减少定向传送次数的方法第四章 流水线技术ALU运算结果写RF RF读RFALU操作数寄存器专用通路（旁路）寄存器堆RF多路开关多路开关ALUR4R1缓冲寄存器

33、（R1，R4）旁路定向传送及具有旁路的ALU第四章 流水线技术控制相关（control dependence）控制相关主要由无条件转移和条件转移引起。 （转移指令概率占1/4左右，不可忽视）解决控制相关主要使用的技术：加快和提前形成条件码：有的指令的条件码并不一定要等执行完毕得到运算结果后才能形成；静态转移预测技术：在硬件和软件设计完成后，转移预测方向则确定。猜测法：按一个方向流水，预测成功或不成功方向；预取转移目标：向两个分支方向预取指令；加快短循环程序处理 ：设置特殊循环指令、利用硬件向后检测若干条指令（IBM360/91：向后检测8条）；第四章 流水线技术 流水机器的中断处理 流水机器处

34、理中断的关键不在于如何缩短断流时间，而是如何处理好断点现场及中断后的恢复问题。 不精确断点法(同外部设备中断处理一样)：不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入，允许已流入的指令执行完；现场是最后一条指令的。 精确断点法：不论第i条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第i条的，在第i条之后进入流水线的指令的原有现场都能恢复 (增加设备，增加后援R，保存流水线内各条指令的原有状态） 。第四章 流水线技术（1） 先进的流水调度方法 - 动态调度静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起

35、流水线的停顿时间。目前比较流行。 动态调度：通过硬件重新安排指令的执行顺序以减少流水的停顿。优点： （1）能处理某些在编译时无法知道的相关情况； （2）能简化编译程序设计； （3）使代码有可移植性。缺点：相应的硬件较为复杂。三、先进的流水技术第四章 流水线技术（2） 非线性流水线的冲突及调度 非线性流水线的冲突：由于段间设置有反馈回路，一个任务在流水的整个执行过程中可能会多次通过同一流水段，因此不能每拍均向流水线送入新任务。若仍每拍送入一个新任务，则在某些时刻会发生几个任务同时争用同一流水段的现象，即产生功能段的使用冲突。解决方法：间隔恰当的拍数后再向流水线送入下一个任务。这就需要对流水线作适

36、当的调度。流水线调度解决的问题：间隔几拍再向流水线送入下一个任务，才不发生功能段使用冲突。第四章 流水线技术流水线调度常借助于二维预约表和状态转换图来进行分析。二维预约表（也称预约表：Reservation Table ）：流水线各段的时间关系表。反映一个任务使用各段所需间隔的拍数。根据预约表可较容易地推算出一个任务执行时，各段所需间隔的周期拍数。1、预约表设：非线性、单功能流水线P，由K段组成，每个任务流过流水线需N个时钟周期（t1,t2,tn），段为纵坐标，时间为横坐标。 第四章 流水线技术S/t 1 2 3 4 5 6 7 8 91 X X 2 X X X 3 X 4 X X 5 X X

37、 二维预约表 图中每一行代表P的一个段，每一列表示相应的时钟周期（节拍）。若某个任务在周期ti需要使用Sj段进行处理，则在行Sj和列ti 的相交处以“X”（ “” ）表示。第四章 流水线技术禁止表F=1，5，6，8 表明：要想使流入的任务不发生同时争用功能段的情况，相邻两个任务进入流水线的间隔拍数就一定不能为1、5、6、8拍。即：非线性流水线的禁止启动距离为：1、5、6、8拍。2、禁止表F（Forbidden List）：非线性流水线中，各段对一个任务流过时会重复使用同一个功能段的节拍（时钟周期）间隔数的集合。即表示：禁止使用此集合中的间隔拍数向流水线送入任务。第四章 流水线技术3、冲突向量C

38、（Collision Vector）（或称位向量）： C=(CnCn-1. C2 C1)其中第i位的状态表示与当时相隔 i 拍时间间隔，给流水线送入后继任务是否会发生功能段的使用冲突。若不会发生冲突：令该位为“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拍流入流水线时的冲突向量（可从禁

39、止表F生成）。从冲突向量C=（10110001）可知，隔2、3、4、7拍可送入新任务（第2个任务）。但当新任务（第2个任务）送入后，应当产生新的冲突向量，以便决定下一个（第3个）任务可进入的时刻。第四章 流水线技术新的冲突向量的产生方法：若某任务K是在上一个任务间隔2拍时送入流水线，则把上一个任务当时的冲突向量向右移2位（左边空位补0），与当前任务K的原始冲突向量按位“或”。例：原始冲突向量C=（10110001） 选择第2个任务在间隔3拍时流入：3：00010110 V 10110001（原始） 10110111（新） 选择第3个任务在间隔4拍时流入：4：00001011 V 1011000

40、1（原始） 10111011（新） 第四章 流水线技术4、状态转移图： 从原始冲突向量开始，选择可输入任务的节拍向流水线输入新任务，产生新的冲突向量。按新的冲突向量流入新任务，又可产生新的冲突向量，一直进行到不再产生不同的冲突向量为止。按此，可画出用冲突向量表示的状态图。图中两个冲突向量之间用有向弧上的数字表示引入后继任务产生其新的冲突向量所用的间隔拍数。非线性流水线预约表相应状态图 1011000110110111101111011011111110111011242=7 、 93=7 、934=7 、 9 =7 、 9 =7 、9原始冲突向量 禁止表F=1，5，6，8 第四章 流水线技术过

41、程:1. 按给出的预约表写出禁止表 F=1，5，6，8；2. 写出n位初始冲突向量（10110001）；3. 按禁止表约束条件列出新的冲突向量，直到不再生成新的冲突向量为止（当前冲突向量和初始冲突向量按位“或”）；4. 画出用冲突向量表示的流水线状态转移图；5. 列出按流水线状态转移图中任何一个闭合回路进行流水线调度的方法。6. 求出各种调度方法的平均间隔拍数（平均延迟、平均等待时间）；7. 求出最佳等间隔和非等间隔调度拍数；第四章 流水线技术非线性流水线预约表相应状态图 =7 、91011000110110111101111011011111110111011242=7 、93=7 、934

42、=7 、9=7 、9原始冲突向量 调度策略 ： 平均间隔拍数： 非等间隔（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；画出流水线状态转移图；求出最小平均延迟、流水线的最大吞吐率及其调度时的最佳方案。按此流水调度方案，输入6个任务，求实际的吞吐率。 S/t12345671234解：延迟禁止表F=2，4，6

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

44、成的时间为：1+7+1+7+1+7=24拍实际吞吐率 TP=6/24（任务/拍）=0.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个任务的实际吞吐率比其它方案更高些。 第四章 流水线技术粗粒度并行性：在多处理机上分别运行多个进程，由多台处理机合作完成一个程序；单发射结

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

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

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

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

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

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

51、 例：MIPS公司的64位RISC计算机R4000超级流水处理机，分8段：取指1（IF），取指2（IS），读RF，执行（EX），取数1（DF），取数2（ DS），标记检查（TC），写RF（WB）。IFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWB流水线周期主时钟周期流水段=8第四章 流水线技术（4） 超标量超流水计算机 把超标量技术与超流水技术结合在一起，这就是超标量超流水线处理机。超标量超

52、流水线处理机在一个时钟周期内要发射指令n次，每次发射指令m条，因此，超标量超流水线处理机每个时钟周期总共要发射指令m*n条。IFIFIFIDIDIDEXEXEXWRWRWRIFIFIFIDIDIDEXEXEXWRWRWRIFIFIFIDIDIDEXEXEXWRWRWR指令I3I2I1123456时钟周期超标量超流水线处理机的指令执行时空图第四章 流水线技术Pentium流水线结构（五级双流水线） 一个周期发射两条整数指令11121314151617181112131415161718111213141516171811121314151617181112131415161718预取级（取指令）

53、译码级1（译码）译码级2（计算地址）执行级（取数、运算）写回级U流水 V流水1、Pentium的超标量流水线（5） 奔腾系列处理机流水处理 第四章 流水线技术结构特点：Pentium是超标量结构，它可以并行地在一个周期内执行两条整数指令。 Pentium的两个整数流水线分别称为“U”和“V”，而并行发射两条指令称为“成对”。 U管道可执行IntelX86体系结构中的任何指令，而V管道只可执行“指令成对法则”中规定的“简单”指令。当指令是成对的，发给V管道的指令永远是发给U管道的那条指令后的顺序的下一条指令。 2、PentiumCPU的体系结构第四章 流水线技术(2)分立的指令CACHE和数据C

54、ACHE不仅使指令预取和数据读写能无冲突地同时完成，而且可同时与U、V两条流水线分别交换数据。 (3)重新设计的浮点运算部件执行过程是分为8段的流水线。前4段为指令预取（PF）、指令译码（D1）、地址生成（D2）、取操作数（EX），在U、V流水线完成；后4段为执行1（X1）、执行2（X2）、结果写回寄存器堆（WF）、错误报告（ER），在浮点运算部件中完成。一般情况下，只能由U流水线完成一条浮点操作指令；少数情况下，V流水线也能同时完成一条如浮点数交换这样的指令。(4)以设置转移目标缓存器BTB方式实现动态转移预测Pentium采用动态转移预测技术，来减少由于控制相关性引起的流水线性能损失 。(

55、1)超标量流水线超标量流水线是Pentium系统结构的核心。它的U和V两条指令流水线都有自己的ALU、地址生成电路和与数据cache的接口。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） 向量处理方式五、 向量的流水处理第四章

56、 流水线技术3.分组纵横处理法分成k组, 每组长度为m，组内垂直处理，组间水平处理。 n=k*m+r (r为第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存储器ABC流水线运算部件存储器-存储器型结构（一种能实现两个向量相加的流水结构的加法器）

57、第四章 流水线技术AB1234C=A+B加法流水线部件M1M2M3M4M5M6M7M8多模块存储器系统的向量处理机A、B、C的向量长度为8，加法流水线分为4个功能段，主存储器采取了8个存储体，多体交叉访问，如果不出现存储体冲突，带宽将是单体存储器的8倍。 改进多存储模块结构第四章 流水线技术功能部件4功能部件3功能部件2功能部件1存储体M8存储体M7存储体M6存储体M5存储体M4存储体M3存储体M2存储体M1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 t 1 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4

58、5 6 7 8RB6 RB6 RA8 RA8 WC4 WC4RB5 RB5 RA7 RA7 WC3 WC3RB4 RB4 RA6 RA6 WC2 WC2RB3 RB3 RA5 RA5 WC1 WC1RB2 RB2 RA4 RA4 RB1 RB1 RA3 RA3 RA2 RA2 RA1 RA1 WC8 WC8WC7 WC7WC6 WC6WC5 WC5RB8 RB8RB7 RB7C=A+B向量处理时序图第四章 流水线技术二、寄存器寄存器型（如CRAY_1机）原理：在运算部件中设置多个向量寄存器，需要进行向量处理时，先执行存储器取指令，将向量数据传送至向量寄存器中，流水线运算部件由向量寄存器提供数据、处理后的结果也送至向量寄存器中。Cray-1向量计算机就是一个典型的寄存器寄存器型。 结构：（1）Cray-1机的主存储器容量为8M字节，包含64个存储模块。（2）