搜索
第4章流水线技术系统结构中的并行性概念流水线结构原理向量处理技术指令级并行技术4.1系统结构中的并行性概念计算机系统增加并行性可以提高机器的处理速度。并行性的双重含义是指同时性和并发性。所谓同时性是指两个或两个以上的事件在同一时刻发生的。而并发性则是指两个或两个以上的事件在同一段时间间隔内发生。计算机系统并行性的开发途径有：时间重叠、资源重复和资源共享。（1）时间重叠：在并行性中引入时间因素。即让多个处理过程在时间上相互错开，重叠地轮流使用同一部件，以加快硬件的周转而提高速度，如指令的流水执行方式。（2）资源重复：在并行性中引入空间因素。即通过重复设置多个功能部件来提高处理性能或可靠性，如阵列处理机。（3）资源共享：利用软件的方法，让多个用户按一定的时间顺序轮流使用一套资源，以提高系统资源的利用率。如多道程序、分时系统等。4.1.1并行性概念计算机系统的并行处理的发展过程如图4-1所示。4.1.2并行处理的发展1．单机系统中并行处理的发展单处理机并行性开发主要是时间重叠途径。实现时间重叠的基础是部件功能专用化。将一件工作按功能分为若干联系的部分，然后按时间重叠的原则将各过程在时间上重叠起来，使所有部件依次完成一组同样工作，在处理机内部同时解释两条指令，以此提高处理机速度，称为重叠方式。2．多机系统中并行处理的发展多机系统包括多计算机系统和多处理机系统。（1）多机系统的耦合度。多机间相互通信能力或相互依赖程度称为系统的耦合度。多机系统的耦合度可分为最低耦合、松散耦合、紧密耦合等几类。（2）多机系统的发展。多机系统也沿着时间重叠、资源重复和资源共享的技术途径向前发展，有3种不同的发展方向，在技术措施上与单机系统有所区别，如图4-1所示。（3）多机系统的比较。从图4-1看出，无论单机系统还是多机系统，按不同途径向3个不同类型的多处理机方向发展。4.2流水线结构原理流水线就是将一条指令的执行或一个运算分解为多个子过程，在同一时刻不同的指令、运算的子过程重叠执行或处理。通过流水线可大大加快指令执行和运算处理，提高计算机的性能。根据处理对象，流水线可分为指令流水线和运算流水线。4.2.1一次重叠流水线当把一条指令分为多个过程段时，使在同一时刻，有不同的指令在不同过程段上重叠执行，以提高对CPU的利用率，称为重叠解释方式。1．重叠解释方式为方便讨论，一般将一条指令分为取指、分析、执行三个子过程。指令的解释方式有顺序和重叠方式两种。指令的顺序解释各指令之间串行的执行，一条指令执行完后才取出下一条指令来执行，且指令内部的各过程段也是串行执行的如图4-3所示。指令的重叠解释方式是在解释ｋ条指令的操作完成之前，就可开始解释第ｋ+１条指令。显然，重叠方式不能缩短一条指令的执行时间，但能缩短多条指令的执行时间。对分为三个过程段的指令，可有仅有两条指令的重叠方式和有三条指令重叠的重叠方式，如图4-4所示。2．重叠方式结构从以上可以看出，采用重叠执行方式可以成倍提高计算机执行的速度。但为了实现重叠方式，处理机必须从硬件组成上符合某些原则。图4-5为重叠方式的基本结构。3．先行控制（1）先行控制原理一次重叠方式进行时，都是“执行k”和“分析k+1”重叠。如果指令“分析”和“执行”的时间相等，则一次重叠非常流畅，无任何阻碍，指令的分析部件和执行部件的功能得到充分发挥，计算机运算速度得到显著提高。（2）先行控制结构采用先行控制方式的处理机结构如图4-9所示。“先行指令栈”实为指令缓冲栈（简称“指缓”），由一个指令缓冲寄存器堆和独立的控制逻辑构成。它可以把后续的指令“先行”取出，放入缓冲栈中，为指令分析器分析做好准备，使分析器分析指令时，不必访问主存。这样，就能使取指令、分析指令和执行指令重叠起来执行。１．流水处理方式在一次重叠方式中，把一条指令解释过程分解为“分析”和“执行”两个子过程，每个子过程需时间为△t1。如果把解释过程进一步细分为“取指”、“译码”、“取操作数”和“执行”4个子过程，且分别由各自独立的部件来实现，每个子过程需时间为△t2。描述流水线的工作过程，常采用时（间）-空（间）图的办法。图4-10是4个解释子过程的流水线处理5条指令时-空图，其中，横坐标表示时间，纵坐标表示流水线的各功能段。4.2.2流水技术原理2．流水线的特点流水技术一般具有如下特点：（1）流水线可以划分为若干个互有联系的子过程（功能段）。每个功能段有专用功能部件实现对任务的某种功能。（2）实现子过程的功能段所需时间应尽量可能相等，避免因时间不等而产生的处理瓶颈，影响系统整体速度。因为在流水线中，各结果出来的时间由各过程段的最大值确定。但在实际中，各流水段所需时间很难保持一致。我们常用流水线加细的方法使各过程段时间一致，对于不能加细的流水线我们可用多套相同的设备并联的方式来实现时间匹配（3）流水线工作状态分为建立、满载、排空三个阶段。从第一个任务进入流水线到流水线所有部件都处于工作状态称为流水线的建立阶段。当所有部件都处于工作状态时，称为流水线的满载阶段。从最后一个任务流入流水线到结果流出，称为流水线的排空阶段。（4）指令流不能顺序执行时，会使流水线中断，重新形成流水时，需要建立时间，所以流水线不能常“断流”，否则流水线效率不高。因此，流水技术适用于大量重复的程序过程，需在输入端连续提供服务，流水线效率才能充分发挥。从不同的角度可对流水线进步不同的分类。1.按流水线具有的功能分类从流水线具有功能的多少来划分，流水线可分为单功能流水线和多功能流水线。4.2.3流水线分类2.流水线多种功能的连接分类按多功能流水线的各段是否允许同时用于多种不同功能连接，可将流水线分为静态流水线和动态流水线。静态流水线(StaticPipelining)是指在同一时间内，多功能流水线中的各功能段只能按一种功能连接。只有一种连接的处理的所有对象排空之后，才能进行其它连接以处理其它功能。以TI-ASC机器的流水线为例，按图4-12所示的时-空图工作，则为一种静态流水线。动态流水线（DynamicPipelining）是指在同一时间内，多功能流水线中的各个功能段可以实现多种连接，同时执行多种功能。但是任何一个功能段只能参加到一种连接中。图4-13所示则为TI-ASC机器的动态流水线图。3．按流水线的级别分类（1）部件级流水线。又称运算操作流水线（ArithmeticPipelining），它是指处理机的算术逻辑部分分段，使各种数据类型能进行流水操作。如图4-11的例子就是部件级流水线。（2）处理机级流水线。又称指令流水线（InstructionPipelining），它是把一条指令的解释过程分解为多个子过程，每个过程在一个独立的功能部件中完成。（3）处理机间流水线。又称宏流水线，它是指两台以上的处理机串行地对同一数据流进行处理，每台处理机完成一个任务。4．按流水线的连接方式分类根据流水线各功能段之间是否有反馈回路，将流水线分为线性流水线和非线性流水线。线性流水线(LinePipelining)是指流水线各段串行连接，数据顺序流经流水线各段一次且仅流过一次。一般流水线均属此类，如图4-15所示。非线性流水线（NonlinearPipelining）是指流水线中存在反馈（或前馈）回路，因此从输入到输出过程中，一个任务将数次通过流水线中的某些功能段。如图4-16所示。１.吞吐率流水线的吞吐率(ThroughPutRate，TP)是指单位时间内从流水线中流出的任务（结果）数。如前所述，由于流水线并不是在任何时刻都在满负荷工作，因此，它又分为最大吞吐率和实际吞吐率。（1）最大吞吐率最大吞吐率是指流水线达到稳定（正常工作时间内）可获得的吞吐率。（２）实际吞吐率实际上，由于流水线在开始时有一段建立时间，结束时有一段排空时间，以及由于各种因素使流水线无法连续流动，所以，实际吞吐率总是小于最大吞吐率。２．流水线效率流水线的效率（Efficiency）是指流水线中的各功能段(或设备）的利用率。由于流水线存在建立时间和排空时间，因此各功能段不能一直处于忙状态，所以流水线的效率一定小于1。３．加速比流水线的加速比（SpeedupRatio）是指采用流水方式后的工作速度与等效的顺序串行方式的工作速度之比。4.2.4流水线性能分析要使流水线发生效率，就要使流水线连续不断地流动，尽量不出现断流情况。但是，断流现象还是会出现，其原因除了编译形成的目标程序不能发挥流水线作用，或存储系统不能为连续流动提供所需的指令和操作数外之外，就是出现了相关、转移和中断问题。所谓“相关”，是指由于机器语言程序的临近指令之间出现了某种关联后，为了避免出错使得他们不能同时被解释的现象。1.局部性相关及处理在实际的流水线结构里要解决可能出现的相关问题，按流水流动顺序的安排与控制，可有以下几种情况：（１）顺序流动的相关顺序流动方式是指任务从流水线输出端流出的顺序与它们进入流水线输入端的顺序一样，遇到相关，则使相关的指令解释过程停止，待过了这一环节再继续下去。（2）相关专用通路解决“先写后读”相关的另一种方法是建立相关专用通路，即在流水线的读段与写段之间增加一条专用通路，如图4-19中虚线所示。4.2.5流水线中的主要障碍与控制（3）异步流动的相关异步流动方式是指任务从流水线输出端流出的顺序与它们进入流水线输入端的顺序不一样。2．全局性相关及处理全局性相关指的是已进入流水线的转移指令（尤其是条件转移指令）和其后面的指令之间的相关。（1）猜测法对于条件转移指令，其执行必存在两个分支，即转移成和不成功分支。对于流水方式执行的指令，可采用猜测法进行处理。（2）采用延迟转移技术延迟转移技术是依靠编译器把转移指令之前的一条或几条没有数据相关和控制相关指令调整到转移指令的后面。当转移指令进入流水线之后，由这些指令填充流水线的各功能段以保证流水线不断流，且又不会出现相关问题，直到转移条件码的建立。（3）加快和提前形成条件码提前形成条件码，以便尽早知道程序流向哪个分支，会有利于流水机器简化对条件转移的处理。这可从两方面采取措施。（4）加快短循环程序的处理由于程序中广泛采用循环结构，流水机器多数采取特殊措施以加快循环程序的处理，３．流水线的中断处理中断会引起流水线断流，但出现概率比条件转移要低得多，且又是随机发生的。所以，流水机器中断主要是如何处理好断点现场的保存和恢复，而不是如何缩短流水线的断流时间。1.预约表拍号n为了能对流水线的任务进行优化调度和控制，1971年E.S.Davidson提出使用一个二维预约表(ReservationTable)来描述一个任务在非线性流水线中各功能段的使用情况。预约表是一张二维表格，其横坐标表示流水线工作的时钟周期，纵坐标表示流水线的功能段，“√”表示该功能段在这一时钟处于工作状态。图4-21所示为某单功能非线性流水线的预约表。4.2.6非线性流水线调度（1）禁止表根据预约表可得出一个任务使用各段所需的间隔拍数(也称为延迟)。（2）冲突向量冲突向量（CollisionVector）是一个n－1为的向量，用它来表示已进入流水线中的任务对尚未进入流水线的后续任务流入流水线的时间间隔的约束。（3）状态转移图初始冲突向量表示刚流入流水线的第一个任务对后续任务流入流水线的时间间隔的限制。（4）列出无冲突调度方案根据流水线状态图由初始状态出发，凡是间隔拍数呈周期性重复的环路，都构成一个无冲突调度方案。表4-2给出本例中各种调度方案，并计算出每种调度方案的平均建个拍数，从而得到不同类型的调度方案。4.3向量处理技术1.水平（横向）处理法如果采用逐个求d[i]的方式，则d[1]=a[1]*(b[1]+c[1])d[2]=a[2]*(b[2]+c[2])…d[i]=a[i]*(b[i]+c[i])…d[N]=a[N]*(b[N]+c[N])这种方法的每次循环中至少要用两条指令：k[i]=b[i]+c[i]d[i]=k[i]*a[i]显然在流水处理中，不仅有操作数相关（“先读后写”相关），而且每次循环中又有功能部件的切换（+、*、…），这就使流