第5章 流水线教材

第5章重叠、流水和向量处理机5.1重叠解释方式5.2流水方式5.3向量的流水处理与向量流水处理机5.4指令级高度并行的超级处理机概述计算机组成设计的基本任务：加快机器语言的解释提高每条指令的执行速度通过控制机构采用同时解释两条、多条甚至整段程序来加快（重叠、流水）5.1重叠解释方式5.1.1基本思想和一次重叠指令的执行过程可以被分解为相互独立的几个阶段，具体的分法要根据各种处理机的情况而确定。取指--按照指令计数器的内容访问主存储器，取出一条指令送到指令寄存器。分析--是指对指令的操作码进行译码，按照给定的寻址方式和地址字段中的内容形成操作数的地址，并用这个地址读取操作数（主存储器或寄存器中）。执行--是指根据操作码的要求，完成指令规定的功能，在此期间，要把运算结果写到寄存器或主存储器中。1、顺序执行方式采用顺序执行方式执行n条指令所用的时间为：如果取指令、分析指令和执行指令的时间都相等，每段的时间都为t，则执行n条指令所用的时间为：T＝3nt优点：是控制简单，节省设备。缺点：一是处理机执行指令的速度慢。只有当上一条指令全部执行完之后，下一条指令才能够开始执行。一次重叠执行方式。如果执行一条指令的两个过程的时间均相等，则执行n条指令所用的时间为：T＝(1＋2n）t优点：一是指令的执行时间缩短了近二分之一，二是功能部件的利用明显提高。缺点：需要增加一些硬件，控制过程也要复杂一些。

例如，为了能够在执行第k条指令的同时，分析第k+1条指令，必须再增加一个指令寄存器。用原来的指令寄存器存放当前正在执行的第k条指令，而新增加的一个指令寄存器存放新取出来的第k+1条指令。二次重叠执行方式。

如果执行一条指令的三过程的时间相等，则执行n条指令所用的时间为：

T＝(2＋n）t

采用二次重叠执行方式能够使指令的执行时间缩短近三分之二，这是一种理想的指令执行方式。在正常情况下，处理机中同时有三条指令在执行。

采用二次重叠执行方式，在处理机中同时有三条指令分别在取指令、分析和执行。要使指令能够正确地重叠执行，必须解决如下两个问题：

第一，为了实现取指令，分析指令和执行指令同时进行，需要有独立的取指令部件、指令分析部件和指令执行部件。因此，要把顺序执行方式中的一个集中的指令控制器，分解成三个相对独立的控制器，它们是：存储控制器，简称存控；指令控制器，简称指控；运算控制器，简称运控。

第二，要解决访问主存储器的冲突问题。例如，取指令时要访问主存储器，分析指令时可能要取操作数，执行指令时可能要向主存储器写运算结果。常规的主存储器体系结构无法实现指令的重叠执行。解决办法把主存储器分成两个独立编址的存储器，一个专门存放指令，称为指令存储器，另一个专门存放操作数，称为数据存储器。两个存储器可以同时独立访问；这样，就解决了取指令和读操作数的冲突。如果再规定，在执行指令阶段产生的运算结果只写到通用寄存器中，不写到主存，那么，取指令、分析指令和执行指令就可以同时进行。在许多高性能处理机内部，一级Cache一般都设置有两个，其中，一个是指令Cache，另一个是数据Cache。这样，可以减少取指令和读操作数的访问冲突。这种结构被称为哈佛结构。

指令和数据仍然混合存放在同一个主存储器内，采用第三章中介绍的低位交叉存取方式，在一个存储器周期中可以访问多个存储单元。如果处理机同时执行的取指令和读操作数所访问的不是同一个存储体，则可以实现指令重叠执行。如果正好访问同一个存储体，则指令无法重叠执行。M0M1M2M3…………在处理机内部设置一定容量的指令缓冲寄存器，把指令分析器所需要的指令事先取到指令缓冲寄存器中，而不必访问主存储器。这样，就能够使取指令、分析指令和执行指令重叠起来执行。

如果指令分析器每次取指令都能够在先行指令缓冲寄存器中得到，则取指令只需要很短的时间就能够完成，因此，可以把取指令与分析指令合并到一起，从而构成如图所示的一次重叠执行方式。

实际上要达到这个速度还有许多困难，主要有如下三个问题需要解决：

1、现代计算机的指令系统是很复杂的，各种类型的指令，其“分析”和“执行”所需要的时间相差往往很大。因此，指令分析部件和指令执行部件经常要相互等待，从而造成功能部件的浪费。

2、当出现转移或转子程序指令时，程序的执行过程就不是顺序的。这时，在先行指令缓冲器中预取的指令和已经分析完成的下一指令等都可能要作废。

图5.4当第k条指令是条件转移时3、如果“分析k+1”所要读取的操作数正好是“执行k”的结果，则它们不能重叠执行，这种情况称为数据相关。

如果采用VonNeumann型机器上指令可修改的办法经第k条指令的执行来形成第k+1条指令，如

k：存通用寄存器，

k+1；(通用寄存器)→k+1k+1:……

由于在“执行k”的末尾才形成第k+1条指令，按照一次重叠的时间关系，“分析k+1”所分析的是早已取进指缓的第k+1条指令的旧内容，这就会出错。第k、k+1条指令就不能同时解释，我们称此时这两条指令之间发生了“指令相关”。特别是当指令缓冲器可缓冲存放n条指令情况下，执行到第k条指令时，与已预取进指缓的第k+1到第k+n条指令都有可能发生指令相关。指缓容量越大，或者说指令预处理能力愈强的机器发生指令相关的概率就愈高。5.1.2相关处理

数据相关主要有四种。分别是指令相关、主存操作数相关、通用寄存器相关和变址相关等。需分不同情况来进行讨论。1.指令相关的处理(指令相关数相关)“执行”指令是IBM370机器为此设置的一条指令，其形式为执行R1X2B2D2当执行到“执行”指令时，按第二操作数(X2)+(B2)+D2地址取出操作数区中单元的内容作为指令来执行。这样指令相关转为数相关，只需统一按数相关进行处理就可以了。图5.5IBM370“执行”指令的执行2.主存空间数相关的处理图5.6主存数相关的处理3.通用寄存器组相关的处理设机器的基本指令格式为操作码L1L3B2d2或操作码L1L3L2图5.7指令解释过程中与通用寄存器内容有关的微操作时间关系图5.8“执行k”、“分析k+1”重叠时，访问通用寄存器组的时间关系L3

(L1)

(L2)

图5.9用相关专用通路解决通用寄存器组的数相关设操作数的有效地址由分析器内的地址加法器形成。由于通常情况下，“分析”周期等于主存周期，所以，从时间关系上要求在“分析”周期的前半段，就能由通用寄存器输出总线取得(B2)，送入地址加法器。由于运算结果是在“执行”周期的末尾才送入通用寄存器组的，它当然不能立即出现在通用寄存器输出总线上。也就是说，在“执行k”得到的、送入通用寄存器的运算结果来不及作为“分析k+2”的基址值用，更不用说作为“分析k+1”的基址值用。因此，虽然是一次重叠，但基址值相关(B相关)就不止会出现一次相关，还会出现二次相关。即当出现B(k+1)=L3(k)时，称为发生了B一次相关；而当出现B(k+2)=L3(k)时，称为发生了B二次相关，如图5.10所示。图5.10B一次相关与二次相关图5.11B一次、二次相关的推后处理图5.12B相关专用通路法5.2流水方式5.2.1基本概念流水线方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行。流水线的每一个子过程称为一个流水节拍、流水段或流水级等。在处理机的各个部分几乎都可以采用流水线方式工作。指令的执行过程可以采用流水线，称为指令流水线。运算器中的操作部件，如浮点加法器、浮点乘法器等可以采用流水线，称为操作部件流水线。访问主存储器部件也可以采用流水线。甚至在处理机之间，机器之间也可以采用流水线。

流水是重叠的引申分解为流水段之后，需要在每个流水段功能部件的输出端都设置一个锁存器。这样，各个功能部件各自独立，可以并行工作。一次重叠执行方式，就是一种简单的指令流水线。由于在指令分析器和指令执行部件的输出端各有一个锁存器，可以分别保存指令“分析”和指令“执行”的结果，因此，指令分析器和指令执行部件能够成为两个完全独立的功能部件，它们可以同时并行工作，“分析k+1”与指令执行部件“执行k”可以同时进行。时空图中，能够很清楚地看出各个任务在流水线的各段中流动过程。从横坐标方向看，流水线中的各个功能部件在逐个连续地完成自己的任务。从纵坐标方向看，在同一个时间段内有多的流水段在同时工作。因此，时空图是描述流水线工作过程的一种比较好的方法。流水线的特点1、在流水线中处理的必须是连续任务，只有连续不断地提供任务才能充分发挥流水线的效率。2、把一个任务（一条指令或一个操作）分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。3、在流水线的每一个功能部件的后面要要设置一个缓冲寄存器，或称为锁存器、闸门寄存器等，用于保存本段的执行结果。这是因为流水线中每一段的延迟时间一般不可能都相等，因此，在段与段之间传送子任务时，必须通过缓冲寄存器。当某一个流水段的执行时间变化范围比较大时，要设置多个缓冲寄存器。4、流水线中各段的时间应尽量相等，否则将引起“堵塞”、“断流”等。执行时间长的一段将成为整个流水线的“瓶颈”，这时，流水线中的各个功能部件将不能充分发挥作用。

5、流水线需要有“装入时间”和“排空时间”。只有流水线完全充满时，整个流水线的效率才能得到充分发挥。

在流水线处理机的设计过程中，要充分注意上述问题，以设计出高效率的流水线。在流水线处理机上设计程序时，也必须注意流水线的上述特点，以充分发挥流水线处理机的高效率。

2.流水线的分类按流水线的级别不同部件级系统级（宏流水）处理器级按流水线功能单功能流水线多功能流水线一条流水线只能完成一种固定的功能，这种流水线称为单功能流水线（UnifunctionPipelining）。例如，浮点加法器流水线专门完成浮点加法运算，浮点乘法器流水线专门完成浮点乘法运算。当要实现多种不同功能时，可以采用多条单功能流水线。如Cray-1计算机种有12条单功能流水线，我国研制的YH-1计算机有18条单功能流水线。Pentium处理机有一条5段的整数运算流水线和一条8段的浮点运算流水线。多功能流水线（MultifunctionPipelining）是指流水线的各段可以进行不同的连接。在不同时间内，或在同一时间内，通过不同的连接方式实现不同的功能。多功能流水线的典型代表是Texas仪器公司的高级科学计算机ASC中采用的8段流水线。在一台ASC处理机内有4条相同的流水线，每条流水线通过不同的连接方式可以完成整数加减法运算、整数乘法运算、浮点加法运算、浮点乘法运算等。图5.16ASC机运算器的多功能流水线在处理机中采用多功能流水线的优点是流水线中各个功能部件的利用率比较高。由于在实际的标量运算程序中，各种运算操作一般是混合在一起的，这一点与向量运算操作有很大的不同，因此，在标量计算机的指令执行部件中采用多功能流水线是一种比较合理的选择。与采用多功能流水线不同的另一种方案是设置多条专门的单功能流水线，在许多向量流水线处理机中就是这样做的。在多功能流水线中，按照在同一时间内是否能够连接成多种方式，同时执行多种功能，可以把多功能流水线分为静态流水线和动态流水线两种。静态流水线（StaticPipelining）是指在同一段时间内，多功能流水线中的各个流水段只能按照一种固定的方式连接，实现一种固定的功能。动态流水线（DynamicPipelining）是指在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。当然，同时实现多种连接发生是有条件的，即流水线中的各个功能部件之间不能发生冲突。在一般情况下，动态流水线的效率和功能部件的利用率要比静态流水线高，但是，动态流水线的控制比静态流水线要复杂得多。目前，在大多数处理机中均采用静态流水线。图5.17静、动态多功能流水线时-空图举例按照流水线的各个流水段之间是否有反馈信号，可以把流水线分为线性流水线和非线性流水线两类。线性流水线（LinearPipelining）是将流水线的各段逐个串接起来。输入数据从流水线的一端进入，从另一端输出。数据在流水线中的各个流水段流过时，每一个流水段都流过一次，而且仅仅流过一次。非线性流水线（NonlinearPipelining）在流水线的各个流水段之间除了有串行的连接之外，还可以有前馈和反馈连接。

图5.18非线性流水线举例5.2.2流水线处理机的主要性能吞吐率吞吐率是流水线单位时间里能流出的任务数或结果数。

在图5.14的流水线例子中，各个子过程经过的时间都是Δt2，满负荷后，流水线每隔Δt2解释完一条指令，其最大吞吐率TPmax为1/Δt2。实际上，各个子过程进行的工作不相同，所经过的时间也就不一定相同，所以前述在子过程间设置了接口锁存器，让各锁存器都受同一时钟脉冲同步。时钟脉冲周期直接影响流水线的最大吞吐率，总希望它越小越好。如果各个子过程所需的时间分别为Δt1、Δt2、Δt3、Δt4，时钟周期应当为max｛Δt1,Δt2,Δt3,Δt4｝，即流水线的最大吞吐率

它受限于流水线中最慢子过程所需要的时间。称流水线中经过时间最长的子过程为瓶颈子过程。图5.19最大吞吐率取决于瓶颈段的时间图5.20瓶颈子过程再细分图5.21瓶颈子过程并联

设一m段流水线的各段经过时间均为Δt0，则第1条指令从流入到流出需要T0=mΔt0的流水建立时间，之后每隔Δt0就可以流出一条指令，其时—空图如图5.22所示(这里设m=4)。这样，完成n个任务的解释共需时间T=m·Δt0+(n-1)Δt0。在这段时间里，流水线的实际吞吐率图5.22从时—空图分析实际的吞吐率

不仅实际的吞吐率总是小于最大的吞吐率，而且只有当n>>m时，才能使实际的吞吐率接近于理想的最大吞吐率。如果用加速比(SpeedupRatio,Sp)表示流水线方式相对非流水线顺序串行方式速度提高的比值，那么，非流水线顺序串行方式工作，连续完成n个任务需要n·m·Δt0的时间，因此，流水线方式工作的加速比

如果线性流水线各段经过的时间Δti不等，其中瓶颈段的时间为Δtj，则完成n个任务所能达到的实际吞吐率其加速比2.效率

流水线的效率是指流水线中的设备实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。由于流水线存在有建立时间和排空时间(最后一个任务流入到流出的时间)，在连续完成n个任务的时间里，各段并不总是满负荷工作的。如果是线性流水线，且各段经过时间相同，如图5.22那样，则在T时间里，流水线各段的效率都相同，均为η0，即整个流水线的效率式中，分母m·T是时—空图中m个段和流水总时间T所围成的总面积，分子m·nΔt0则是时—空图中n个任务实际占用的总面积。因此，从时—空图上看，效率实际上就是n个任务占用的时—空区面积和m个段总的时—空区面积之比。显然，与吞吐率类似，只有当n>>m时，η才趋近于1。同时还可看出，对于线性流水且每段经过时间相等时，流水线的效率是正比于吞吐率的，即

如果流水线各段经过的时间不等，各段的效率就会不等，但是，参照图5.22，不难得出整个流水线的效率在计算一条实际流水线的效率时，往往还要考虑流水线各段所使用的设备量不相等，或者流水线各段的价格不相等的情况。在上面给出的所有流水线时空图中，都默认每一个流水段的设备量或设备的价格都是相等的，因此，在纵坐标上每一个流水段都占有一个相等的长度单位。对于可能出现的每一个流水段的设备量或流水段的价格不等的情况，应该根据各个流水段所用的设备量或设备价格在流水线总设备中所占的比例，分别赋予不同的“权”值ai。在绘制流水线时空图时，要根据各流水段权值ai的大小，确定每个流水段在纵坐标上所占的长度其中，分母为m个段的总的加权时—空区，分子为n个任务总的加权时—空区。当时，有

对于复杂的非线性流水线，实际的吞吐率TP和效率η需要通过画出实际工作时的时—空图，才能分别用下列两个式子求得：3.流水线工作举例例1、单功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。用下图所示的一条4段浮点加法器流水线计算8个浮点数的和：Z＝A＋B＋C＋D＋E＋F＋G＋H由于存在数据相关，要在A＋B的运算结果在第4个时钟周期末尾产生之后，在第5个时钟周期才能继续开始做加C的运算。这样，在每两个加法运算之间，每个功能部件都要空闲3个时钟周期。这时候，实际上与不采用流水线的顺序执行方式完全一样。作一个简单的变换，得到：Z＝[（A＋B）＋（C＋D）]＋[（E＋F）＋（G＋H）]小括号内的4个加法操作之间，由于没有数据相关，可以连续输入到流水线中。只要前两个加法的结果出来之后，第一个中括号内的加法就可以开始进行。假设每一个流水段的延迟时间均相等，都为△t，则有Tk＝15△t，n＝7。那么，流水线的吞吐率TP为：TP=7/15△t=0.47/△t

流水线的加速比Sp为：Sp=4×7△t/15△t=1.87

流水线的效率η为：η=4×7△t/4×15△t=0.47例2、多功能、线性流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。用多功能静态流水线计算两个向量的点积：Z＝AB＋CD＋EF＋GH为了尽量减少数据相关性，充分发挥流水线的作用。计算的顺序应该是先做4个乘法：AB、CD、EF和GH，然后做两个加法AB＋CD和EF＋GH，最后求总的结果Z＝[（A*B）＋（C*D）]＋[（E*F）＋（G*H）]从流水线时空图中看到，用20个时钟周期完成了7个运算。当每一个流水段的延迟时间都为△t时，有：流水线的吞吐率TP为：7/20⊿t如果采用顺序执行方式，完成一次乘法要用4个⊿t，完成一次加法要用6个⊿t，则完成全部运算要用：4×4⊿t＋3×6⊿t＝34⊿t则流水线的加速比S为：34⊿t/20⊿t=1.70整个流水线共有8段，流水线效率E为：34⊿t/8×20⊿t=0.21流水线性能分析整个流水线的效率很低，其原因主要有如下四个。一是多功能流水线在做某一种运算时，总有一些流水段是空闲的；二是静态流水线必须等待前一种运算全部排出流水线之后，才能重新进行连接；三是流水线有装入与排空部分，当输入到流水线中的任务不多时，装入与排空部分所占的比例比较大；四是题目本身存在有数据相关，当发生数据相关时，必须等待前一个运算结果产生之后，下一个运算才能开始。5.2.3流水机器的相关处理和控制机构局部相关与全局相关局部相关指令相关，主存数相关，通用寄存器组相关全局相关是指因为程序的执行方向可能被改变而引起的相关。可能改变程序执行方向的指令通常有无条件转移、一般条件转移、复合条件转移、子程序调用、中断等。在流水线中，控制相关对流水线的吞吐率和效率的影响相对于数据相关要大得多。1.局部性相关的处理

在一般情况下，一串连续任务在流水线中是依次在各个流水段中间流过的。从流水线的输出端看，任务流出流水线的顺序与输入端的任务流入顺序完全相同，这种控制方式称为顺序流动方式。

在正常情况下，6个流水段S6、S5、……、S1分别同时执行k、k+1、……、k+5共6条指令。在图中，流水段S2要读操作数，流水段S6写运算结果。现在把如下一段程序输入到这条流水线中：

指令k与指令k+2之间有“先写后读”数据相关。

k：R0←（R1）

k+1：……

k+2：R2←（R0）＋（R3）

k+3：……

k+4：……

k+5：……

……

在时钟周期ti，指令k+2在流水段S2中要读操作数；但是，由于指令k还没有到达流水段S6；因此，指令k+2无法继续执行，要在流水段S2中等待。后续的指令k+4、k+5、……等也不能进入流水线。在以后的ti+1、ti+2、ti+3、……时钟周期，流水段S3、S4、S5将逐渐空闲。在时钟周期ti+3，指令k执行完成，把运算结果写到寄存器R0中。从时钟周期ti+4开始，指令又可以在流水线中继续往前流动。然而，三个“空闲段”要在流水线的后四个流水段中流过，直至全部流出流水线。采用顺序流动方式，流水线的控制逻辑比较简单。但是，在程序中有“先写后读”数据相关时，流水线可能会“断流”，这将降低流水线的吞吐率和效率。为了充分发挥流水线的效率，在发生数据相关时，要允许没有数据相关的后续指令进入相关指令所占用的流水段线执行，并超越相关的指令继续往前流动，这种控制方式称为异步流动方式。从一条指令流水线的输出端看，指令流出流水线的顺序与输入端指令输入流水线的顺序是不一样。在流水线的输入端，指令是按照它的地址从小到大顺序进入流水线的；但在流水线的输出端，指令执行完成的顺序可能是混乱的；因此，把流水线的这种控制方式称为乱序（Outoforder）流动方式。

如果后续的指令k+3、k+4、……等与指令k+2没有数据相关，在ti+1、ti+2、ti+3时钟周期，可以把指令k+2一直保存在流水段S2中，而让后续的指令k+3、k+4、k+5进入流水段S2执行，并超越指令k+2进入以后的流水段。在时钟周期ti+3，指令k执行完成，把运算结果写到寄存器R0中。在时钟周期ti+4，流水段S2可以执行指令k+2，于是，指令k+2可以跟在指令k+5之后继续往前流动。因此，从流水线的输出端看，指令流出流水线的顺序与输入端指令进入流水线的顺序是不一样的。在乱序流动方式中，除了有“先写后读”数据相关之外，还可能发生“先读后写”数据相关和“写-写”数据相关。“先写后读”数据相关又称为数据相关、写读相关、流相关、WR相关、RAW相关等。“先读后写”相关又称为变量名相关、读写相关、反相关、RW相关、WAR相关等。“写-写”数据相关又称为输出相关、WW相关、WAW相关或写后再写相关等。

例如，下面一小段程序输入到动态多功能流水线，或者多条单功能流水线中，指令k与指令k+2之间有“先写后读”数据相关，指令k+2不能继续执行。后续的指令k+3、k+4、……等可以进入读操作流水段先执行，并超越指令k+2进入以后的流水段。另外由于指令k和指令k+2是乘法指令，执行的时间比较长，指令k+3有可能超越指令k先到达写流水段，把它的执行结果写到了寄存器R3中。产生“先读后写”数据相关。同样，如果指令k+4超越指令k+2先到达写流水段，寄存器R2中的最终结果必然是错误的，这就是“写-写”数据相关。数据相关避免方法在流水线中避免发生数据相关的方法可以分为两大类，其中一类是延迟执行，另一类是建立专用路径。延迟执行是避免数据相关最简单的方法。优点是流水线的控制简单，缺点是流水线的吞吐率和效率低。（如前所述）建立专用路径可以减少指令等待的时间，提高流水线的吞吐率和效率。当流水线的流水段比较多，或者在一个处理机中有多条流水线时，需要的专用路径的条数很多，专用路径的控制非常复杂；因此，出现了多种设置专用路径的专门方法，如采用分散控制的公共数据总线法（又称为Tomasulo算法），采用集中控制的CDC记分牌法等。

指令k+2可以提前两个时钟周期执行；从而流水线的吞吐率和效率有比较大的提高。由于在一般程序中，这类数据相关发生的概率很大；因此，在流水线中建立专用数据路径已经成为高性能处理机普遍采用的方法。图5.25IBM360/91的浮点执行部件结构框图

浮点操作站FLOS(FloatingPointOperandStack)缓冲的浮点操作命令的格式为操作源1(目的)，源2

操作可以是浮点加、减、乘、除。源1指明存放源操作数的浮点寄存器FLR的号，并兼作存放中间结果的目的寄存器的号。源2指明存放经存贮器总线送来的浮点操作数的缓冲器FLB的号。它们分别经FLR总线和FLB总线将数据送入浮点加法流水线或浮点乘/除法流水线输入端的保存站。浮点加法器流水线的输入端设有3个保存站A1至A3，浮点乘/除法器流水线的输入端设有两个保存站M1和M2，分别用规定的站号标记。保存站由控制部分控制，只要任意一个保存站的两个源操作数都到齐，且流水段空闲时就可以进入流水线向前流动，因此是采用异步流动方式工作的。

由于操作命令中源1兼作目的，因此同时进入两条流水线的操作命令之间发生操作数相关的概率是较高的。设k+i表示k之后同时在两条流水线流动的第i条指令，则只要k+i

的源1与k的目的一样，就会发生“先写后读”相关，k+i的目的与k的目的一样，就会发生“写—写”相关，k+i的目的与k的源1一样，就会发生“先读后写”相关。也就是说，只要同时进入流水线的各个操作命令中使用了同一个浮点寄存器FLR的号就会发生相关。

现在，以FLOS依次送出

ADDF2,FLB1;(F2)+(FLB1)→F2MDF2,FLB2;(F2)*(FLB2)→F2两条操作命令为例，来说明是怎样判出发生相关以及怎样控制推后和相关直接通路的联接的。很明显，这两条命令异步流动时，“先写后读”、“写—写”、“先读后写”三种相关都会发生。当FLOS送出

ADDF2,FLB1操作命令时，它控制由FLR取得(F2)，由FLB取得(FLB1)送往加法器保存站，例如送往A1，同时立即将F2的“忙位”置“１”，以指明该寄存器的内容已送往保存站等待运算，这样F2的内容再不能被其他操作命令作源操作数读出用。由于F2这时已成为“目的”寄存器，准备接收由加法器来的运算结果，因此将F2的“站号”字段置成是A1的站号“1010”

，以便控制把站号为1010的保存站A1在加法流水线流出的运算结果经CDB总线送回F2。一旦结果送回后，立即将F2的“忙位”和“站号”都置成“０”，以释放出F2为别的操作命令使用。

问题在于，当F2的“忙位”为“１”，而加法结果并未流出加法流水线时，FLOS又送出操作命令

MDF2,FLB2由译码控制去访问F2取源1操作数时，由于其“忙位”为“１”，表明出现了F2相关，此时就不能直接将(F2)送往乘法器保存站，而改成为把原存在F2的“站号”字段中的站号A1(即1010，指明F2应有内容的来源)送往M1的“源1站号”，并把F2内的站号由A1(1010)改为M1(1000)以指明应改为从M1接收运算结果。2全局相关的处理在流水线中，全局相关对流水线的吞吐率和效率的影响相对于数据相关要大得多。因此，处理好条件转移和中断引起的控制相关是很重要的；其中的关键问题有两个，一是要确保流水线能够正常工作，二是减少因“断流”引起的吞吐率和效率的下降。

猜测法

在遇到条件转移指令时，为了使流水线不“断流”，通常采用“猜测法”。在条件转移指令之后，选择一个分支方向，让后续指令进入流水线执行。猜测的分支方向一般选择转移不成功的方向。当分支方向猜测错误时，不仅流水线中有多个流水段要浪费，更严重的是可能造成程序执行结果发生错误。因此，当流水线沿猜测方向执行第i+1、i+2、……条指令时，一定不能破坏通用寄存器和主存储器中的内容。为做到这一点，目前的处理机有两种做法。一种方法是只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算；另一种方法是一直执行到运算完成，但不送回运算结果。前一种方法，即使猜测正确时，也可能造成流水线流水段的浪费，但控制逻辑比较简单；后一种方法则要设置一定数量的缓冲寄存器来存放中间运算结果，而且，控制逻辑比较复杂。2)加快和提前形成条件码条件转移指令造成流水线吞吐率下降的主要原因是条件码形成得太晚。因此，尽早产生条件码对减少流水线吞吐率和效率的损失非常有效。对于一般条件转移指令，转移条件码是由上一条运算型指令产生的。对于大多数情况，可以在运算实际开始之前或者在运算中间就能产生条件码，不必等到运算完成之后。因此，在运算部件的入口处设置一个条件码预判部件，如果能够在一个时钟之前内就产生条件码，则正好可以提供给下一条条件转移指令使用；这样，流水线就不会“断流”。3)采取延迟转移4)加快短循环程序的处理

3.流水机器的中断处理中断会引起流水线断流。然而，其出现概率比条件转移的概率要低得多，且又是随机发生的。所以，流水机器处理中断主要是如何处理好断点现场的保存和恢复，而不是如何缩短流水线的断流时间。在执行指令i时有中断，断点本应在指令i执行结束，指令i+1尚未开始执行的地方，但流水机器是同时解释多条指令，指令i+1、i+2…可能已进入流水线被部分解释。流水线中断处理方法不精确断点-----现场简单精确断点-----后援寄存器非线性流水线的调度技术线性流水线的调度非常简单，可以在每一个时钟周期向流水线输入一个新任务。而在非线性流水线中，由于存在有反馈回路，当一个任务在流水线中流过时，在同一个流水段中可能要经过多次。因此，就不能每一个时钟周期向流水线输入一个新任务，否则会发生在同一个时刻有几个任务争用同一个流水段的情况。这种情况称为功能部件冲突，或流水线冲突。

非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个流水段都不会发生冲突，而且流水线的吞吐率和效率最高。

线性与非线性流水线1234567s1s2s3s4为了避免流水线发生冲突，一般采用延迟输入新任务的方法。那么，在非线性流水线的输入端，究竟每间隔多少个时钟周期向流水线输入一个新任务才能使流水线的各个流水段都不发生冲突，这就是非线性流水线的调度问题。当然，在一般情况下，这个间隔的时钟周期数应该愈小愈好。在许多非线性流水线中，间隔的周期数往往不是一个常数，而是一串周期变化的数字，也叫循环数列。

非线性流水线的表示一条线性流水线通常只用各个流水段之间的连接图就能够表示清楚，但是，在非线性流水线中，由于一个任务在流水线的各个流水段中不是线性流动的，有些流水段要反复使用多次，因此，只用连接图并不能正确地表示一条非线性流水线的工作过程。一条非线性流水线一般需要一个各流水段之间的连接图和一张预约表共同来表示。

预约表的横坐标表示流水线工作的时钟周期，纵坐标表示流水线的流水段。一行中可以有多个“×”，其含义是一个任务在不同时钟周期重复使用了同一个流水段，一列中有多个“×”是指在同一个时钟周期同时使用了多个流水段。预约表的行数就是非线性流水线的段数，这与线性流水线相同，而预约表的列数是指一个任务从进入流水线到从流水线中输出所经过的时钟周期数。连接图预约表一张非线性流水线的预约表可能与多个非线性流水线连接图相对应。产生这种情况的原因是：在预约表的同一列中可能有多个“×”，即在这个时钟周期有多个流水段段有输出，从而造成下一个功能段的输入可能有多种来源。同样，一个非线性流水线的连接图也可能对应有多张预约表。造成这种情况的原因是：在非线性流水线的有些功能段可能有多个输出端，也有些功能段可能有多个输入端，这些输出端与输入端之间连接的先后次序就形成了多张预约表。非线性流水线的冲突向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离（InitiationInterval）或等待时间（Latency）。启动距离通常用时钟周期数来表示，它是一个正整数。

当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个流水段，或某几个流水段中发生有几个任务同时争用同一个流水段的情况，这种情况就是非线性流水线中的冲突（collision）。启动距离为3的流水线冲突情况

1234567891011S1X1X1

X2X1

X2

X3X2

X3

X4S2X1X1X2X2

X3X3

X4S3X1X2X1X3X2X4S4X1X2X3时间流水段引起非线性流水线流水段冲突的启动距离称为禁止启动距离。使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。只有一个启动距离的启动循环又称为恒定循环。要正确地调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。把一条非线性流水线的所有禁止启动距离组合在一起就形成一个数列，通常把这个数列称为非线性流水线的延迟禁止表。下图所示非线性流水线的延迟禁止表为（3，4，6）。

用冲突向量来表示是否发生功能段冲突。冲突向量C＝（Cn-1Cn-2…C3C2C1）

1234567s1s2s3s4由冲突向量构造一张状态图。把上面得到的冲突向量C作为初始冲突向量送入一个n-1位逻辑右移移位器，当从移位器移出的位为0时，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；若移位器移出的位为1，不作任何处理；移位器继续右移，如此重复。对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理。在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，表示各种状态之间的转换关系。当新形成的冲突向量出现重复时可以合并到一起。

无冲突调度方法非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有流水段在任何时间都没有冲突。一条有4个流水段的非线性流水线，每个流水段的延迟时间都相等，它的预约表如下图所示。(1)写出流水线的延迟禁止表和初始冲突向量。

(2)画出调度流水线的状态图。

(3)求流水线的最小启动循环和最小平均启动距离。

(4)求平均启动距离最小的恒定循环。

延迟禁止表（6，4，2）。根据延迟禁止表很容易得到冲突向量，得到C6＝C4＝C2＝1，其余位为0，因此，冲突向量为C＝（101010）。(2)对于上图，初始冲突向量为101010，把它逻辑右移2、4、6位时，由于移出去的位是1，表示用这些启动距离向流水线输入新任务，在流水线中会发生流水段的冲突，因此，在状态图中不作任何处理。当逻辑右移的位数为1、3、5和大于等于7时，移出去的位是0，表示用这些启动距离向流水线输入新任务时，在流水线的各个流水段中都不会发生冲突。但是，这里所说的不发生流水段冲突，只能保证输入一个新任务时，在流水线的各个流水段都不发生冲突。在输入这个新任务之后，流水线又将产生新的冲突向量，这时，要根据新产生的冲突向量来判断流水线发生冲突的情况。

1234567s1s2s3s4从状态图中可以看到，当启动距离大于或等于7时，流水线的任何一个流水段在任何时钟周期都不会发生冲突；但是，这时流水线的吞吐率、加速比和效率都将很差；因此，非线性流水线调度的任务就是要找出平均启动距离小于7的启动循环，按照这个启动循环向流水线的输入端连续输入新任务，流水线的任何一个流水段在任何时钟周期都不会发生冲突。

在状态图中可以找到很多不发生流水段冲突的启动循环。实际上，这样的启动循环有无穷多个。因为非线性流水线调度的主要目标的要找出平均启动距离最小的启动循环，因此，在这些无穷多个启动循环中，只要找出简单循环即可。简单循环：在状态图中各种冲突向量只经过一次的启动循环称为简单循环。在一个状态图中，简单循环的个数一般是有限的。例如，在图5.36中，启动循环（1，7）、（5，7）、（3，5，7）等都是简单循环，而（3，5，3，7）和（3，5，5，3，7）等不是简单循环；因为（3，5，3，7）两次经过冲突向量（101111），（3，5，5，3，7）两次经过冲突向量（101011）和（101011）。

状态图中的所有简单循环均包括在下表中，共有8个简单循环。在表中，还分别计算出了这些简单循环的平均启动距离。所有的简单循环及其平均启动距离

简单循环平均启动距离（1，7）4（3，5）4（5，7）6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）7

3)从表5.1中可以很容易找到最小启动循环（平均启动距离最小）。在状态图5.36中的最小启动循环是（1，7）或（3，5），其平均启动距离是4。(4)为了简化流水线的控制逻辑，也可以采用相等间隔的调度方法，即采用恒定循环来启动流水线。从表中可以看出，启动距离最小的恒定循环是（5）。按照恒定循环（5）工作的流水线预约表如下图所示。4.流水线调度图5.27流水线预约表及状态图举例表5.1各种调度方案的平均间隔拍数的例子非线性流水线的优化调度方法预约表中“×”最多的一行所对应的流水段一定是整个流水线的瓶颈流水段。要使整个流水线充分发挥效率，瓶颈流水段必须不间断工作，不能有空闲。因此，非线性流水线调度的关键是充分使用瓶颈流水段，只要让瓶颈流水段不空闲，则非线性流水线的吞吐率、加速比和效率必然是最好的，按照这种方法调度流水线，流水线的平均启动距离也一定是最小的。最小平均启动距离等于预约表中任意一行中“×”的最大个数。初始冲突向量C=（1010100）从状态图中可以很容易看到，流水线的最小启动循环是（2）图5.28多功能流水线预约表及状态图举例

使用交叉冲突向量(CrosscollisionVector)来反映有A、B两种功能的动态流水线各个后继任务流入流水线所禁止使用的间隔拍数。这样，对于本例就应有4个交叉冲突向量，即

VAB=(1011)，VBA=(1010),VAA=(0110),VBB=(0110)。其中，VAA和VBB分别表示同按A功能和B功能流水时，后继任务流入流水线的冲突向量；而VAB表示先前按B功能流水流入的任务与后继按A功能流水流入的任务之间的冲突向量，VBA则表示先前按A功能流水流入的任务与后继按B功能流水流入的任务之间的冲突向量。

就一般情况而言，一个有P个功能的流水线将有P2个交叉冲突向量，它们可以分别归类写成P个冲突矩阵Mp，其中p分别为1至P。冲突矩阵Mp表示按p功能流水线进入一个任务后与按各种功能流水线流入后继任务所产生的全部冲突向量的集合。对本例来说有两个初始冲突矩阵，分别为

例如，按A功能刚流入一个任务后，根据VAA的(0110)，知道可隔1拍或4拍流入一个A功能的新任务。将MA初始冲突矩阵各行同时右移1位，再与A功能的初始冲突矩阵MA对应行按位“或”，形成新的冲突矩阵。根据此时VAA的(0111)，知道只有隔4拍流入一个A功能的新任务才能不发生冲突，从而形成在此基础上的新的冲突矩阵。

再如，根据初始冲突矩阵中的VBA为(1010)，知道可在第一拍或第三拍进行B功能的新任务的送入而不发生冲突。于是将MA初始冲突矩阵均右移1位或3位，再与MA的初始冲突矩阵对应行按位“或”，形成新的冲突矩阵，它们恰好都为。据此可知，或者是隔3拍流入A功能的新任务，或者是隔4拍流入B功能的新任务，又将分别产生不同的新的冲突矩阵。5.3向量的流水处理与向量流水处理机5.3.1向量的流水处理

例如，要计算D=A*(B+C)，其中，A、B、C、D都是具有N个元素的向量，应该采用什么样的处理方式才能最充分发挥流水线的效能呢?

如果采用逐个求D向量元素的方法，即访存取ai、bi、ci元素，按上述算术表达式求出di，再取ai+1、bi+1、ci+1，求di+1，这种处理方式我们称其为横向(水平)处理方式。

如果向量的长度N太长，超出了向量寄存器组中寄存器的个数，可以将该向量分割成若干个组，使每组都能装得进向量寄存器组中。这样，每一组内均按纵向方式处理，而组和组之间则采用软件方法编制循环程序的方法依次循环处理。我们称这种处理方式为分组纵横处理方式。有了这种分组纵横处理的方式，就可以对向量长度N的大小不加限制。CRAY—1就是采用这种方式来进行向量的流水处理的。5.3.2向量流水处理机

1.向量处理机的指令系统

向量处理机的指令系统一般应包含有向量型和标量型两类指令。向量型运算类指令一般又可以有如下几种：向量V1运算得向量V2，如V2=SIN(V1)；向量V运算得标量S，如 ；向量V1与向量V2运算得向量V3，如V3=V1∧V2；向量V1与标量S运算得向量V2，如V2=S*V1。2.向量流水处理机的结构CRAY—1是由中央处理机、诊断维护控制处理机、大容量磁盘存贮子系统、前端处理机组成的功能分布异构型多处理机系统。中央处理机的控制部分里有总容量为256个16位的指令缓冲器，分成4组，每组为64个。中央处理机的运算部分有12条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算。另外，还有可由流水线功能部件直接访问的向量寄存器组V0~V7、标量寄存器S0~S7及地址寄存器A0~A7。图5.29CRAY—1的向量流水处理部分简图

为了能充分发挥向量寄存器和可并行工作的6个流水线功能部件的作用，加快对向量的处理，将CRAY—1设计成每个Vi组都有连到6个功能部件的单独总线，而每个功能部件也都有把运算结果送回向量寄存器组的输出总线。这样，只要不出现Vi冲突和功能部件冲突，各个Vi之间和各个功能部件之间都能并行工作，大大加快了向量指令的处理，这是CRAY—1向量处理的一个显著特点。

所谓Vi冲突指的是，并行工作的各向量指令的源向量或结果向量使用了相同的Vi。除了相关情况之外，就是出现源向量冲突，例如

V4←V1+V2V5←V1∧V3这两条向量指令不能同时执行，必须在第一条向量指令执行完，释放出V1之后，第二条向量指令才能开始执行。因为虽然这两条向量指令的源向量之一都取自V1，由于二者的首元素下标可能不同，向量长度也可能不同，难以由V1同时提供两条指令所需要的源向量。

所谓功能部件冲突指的是，同一个功能部件被一条以上的要求并行工作的向量指令所使用。例如

V4←V2*V3V5←V1*V6这两条向量指令都需要使用浮点相乘流水功能部件，那就需在第一条向量指令执行到计算完最后一个结果分量，释放出功能部件之后，第二条向量指令才能开始执行。图5.30CRAY—1的4种向量指令CRAY—1向量处理的另一个显著特点是，只要不出现功能部件冲突和源向量冲突，通过链接机构可使有数据相关的向量指令仍能重叠并行处理。例如，对前述向量运算D=A*(B+C)若向量长度N≤64，向量为浮点数，则在B、C取到V0、V1后，就可用以下3条向量指令求解：V3←存贮器(访存取A向量)V2←V0+V1(B向量和C向量浮点加)V4←V2*V3(浮点乘，存D向量)图5.31通过链接技术实现向量指令之间大部分时间并行CRAY—1启动访存，把元素送往功能部件，把结果存入Vi都需要有1拍的传送延迟。由于第一、二条指令之间没有冲突，可以同时执行，并且“访存”拍数正好与“浮加”的一样，因此，从访存开始，直至把第一个结果分量存入V4，所需拍数(亦称为链接流水线的建立时间)为此后，每拍就可取得一个结果分量存入V4，一共只需17+(N-1)拍就可以执行完这3条向量指令，获得全部结果分量。显然，这要比第一、二条指令全执行完，所有分量全部送入V2、V3后，才开始执行第三条指令要快得多，因为后者需1+6+1+N-1+1+7+1+N-1=15+2N拍。CRAY—1指令可以链接的特点，使得它能灵活地组织各流水线功能部件的并行操作。最多能并行处理6条向量指令，进一步发挥这些流水线功能部件的效能。因此，链接技术是提高机器整体运算速度的一个非常重要的措施。

CRAY—1的向量指令还可以通过让源向量和结果向量使用同一个向量寄存器组，并控制分量计数器值的修改，来实现递归操作。

CRAY—1的每个向量寄存器组Vi都有一个相应的分量计数器。当一条向量指令开始执行时，它的源向量寄存器和结果向量寄存器相应的分量计数器均置成“０”。下面考虑用浮点加法流水线完成递归向量求和V0=V0+V1，其中向量寄存器V1保存要进行递归相加的浮点数，向量寄存器V0同时用作操作数寄存器和结果寄存器。令C1和C2分别是与向量寄存器V0和V1相关的分量计数器。初始时，计数器C0和C1都置成0，V0的第一个分量寄存器V00中的初始值也置成0。通过浮点加法流水线需要6个时钟周期，寄存器和浮点加法流水线之间的往返传送各还需要1个时钟周期，因此，一次加法计算总共需要1+6+1＝8个时钟周期，如下图所示。假定向量长度寄存器的值为64，只作一个向量循环。图5.32递归向量和的部分时间关系

加法指令在t0时启动，两个源向量的第0个分量V00和V11被送到浮点加功能部件，等到t1时开始计算V00+V10。由于V1的分量计数器已在t0结束时加“１”，而V0的分量计数器仍保持为0，所以t1时又将源向量分量V00和V11送往功能部件。这样，功能部件在t2时计算V00+V11，并将V00和V12送往功能部件。依次类推，一直继续到t8，V00接收V00+V10的运算结果。此后，V0的分量计数器也开始每周期加1。t8时，送往功能部件的V00和V18中的V00已不是初始的“０”值，而是0+V10(即V10值)了。t

8以后，由于V0的分量计数器的变化，所以每次送V0的下一分量的内容。运算结束后，V0中各个分量的内容如下：可以看出，第八部分(结果部分)V056到V063中存放的是V1的64个分量的8个部分和。这种递归向量和的运算是很有用的。例如在科学计算中，经常需要计算两个向量A=(a0,a1,…,aN-1)和B=(b0,b1,…,bN-1)的点积在STAR—100机中，需用专门处理点积的指令来完成，而在CRAY—1机上，未专门设置处理点积的指令，只需用一个向量循环和一个标量循环即可。在向量循环中，就可以利用这种递归特性组成一个乘—加链：V1←V3*V4(A、B分别放在V3、V4中)V0←V0+V1(递归向量和)如果向量长度N=64，乘—加链执行完毕时，点积的64个部分和就已减少成只有8个，并存放在V056到V063中。这样，下一步的标量循环只需求此8个部分和的和。因此，速度有了显著的提高。3.超级向量流水处理机举例

美国CRAY研究公司成立于1972年，至今已生产了400台以上安装于世界各地的CRAY超级计算机。1979年生产的CRAY—1S是对CRAY—1的改进，它有10条流水线，时钟周期为12.5ns，使用CRAY操作系统COS，只允许单用户批处理。

1983年的CRAYX—MP系列采用多处理机配置。

1985年的CRAY—2S最多可采用4台CRAY—1，有2GB的共享存贮器，超流水线时钟为4.1ns。主要特点是，将操作系统由批处理COS改为多用户UNIX系统Ⅴ。1988年的CRAYY—MP，由8台处理机组成，时钟周期为6ns，共享1GB中央存贮器，采用256个体交叉访问。

1991年问世的CRAYY—MPC—90是目前最大的CRAY机器，它是由16个类似于Y—MP的CPU组成的集成系统。

CRAY公司1992年10月公布了MPP研究计划，目的是想解决目前大多数用RISC微处理器作为MPP系统构造块在性能、效率上的不足。CDC公司于1973年推出了第一台超级计算机STAR—100之后，于1982年生产了CYBER205。以后又推出了有8个CPU，共享存贮器和18台I/O处理机的ETA10，性能可达10GFLOPS。

日本早期由Fujitsu公司生产的VP—2000系列最高性能为5GFLOPS，时钟周期为3.2ns。1991年NEC公司生产的SX—X