计算机组成原理第6章流水线原理.ppt

《计算机组成原理第6章流水线原理.ppt》由会员分享，可在线阅读，更多相关《计算机组成原理第6章流水线原理.ppt（87页珍藏版）》请在三一办公上搜索。

1、第6章 流水线原理及其1 重叠方式,通常提高指令执行速度的途径有如下三种：提高处理机的工作主频。采用更好的算法和设计更好的功能部件。多条指令并行执行，称为指令级并行技术。,可以从两个方面来开发处理机内部的并行性：空间并行性：即在一个处理机内设置多个独立的操作部件，并让这些操作部件并行工作，这种处理机称为多操作部件处理机或超标量处理机;时间并行性：就是采用流水线技术。流水线技术是一种非常经济、对提高处理机的运算速度非常有效的技 术。采用流水线技术可以不增加硬件或只需要增加少量硬件就能够把处理机的运算速度提高几倍 它是目前使用非常普遍的一种并行处理方式。,本章学习标量计算机上使用的流水加速技术。主

2、要内容有流水技术的分类、流水线性能指标计算、非线性流水线的调度算法。标量计算机指只能直接进行标量运算的计算机，与能够直接进行向量运算的向量计算机相对应。流水处理方式的特征，是让多个依次启动的任务，尽量同时使用系统的不同部件，通过时间重叠来提高处理速率。这种技术理论上不增加成本。标量计算机上使用的流水加速技术属于指令级并行技术。每条指令的处理过程，可以划分为取指、译码、取数、运算、送结果5个子过程，也可以分得更细或更粗一些。划分的原则是各部分时间长度大致相等、并使用CPU中不同的部件，这样才有利于多任务重叠处理。,基本名词术语标量处理机，超标量处理机：标量处理机指只能进行标量运算的处理机，超标量

3、处理机指能在一个时钟周期内同时发射多条指令的处理机；指令级并行技术：指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；流水线处理机，超流水线处理机：流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；超长指令字技术VLIW：指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。,一重叠解释方式1.一条指令的几个过程段 1）取指令：根据PC（指令计数器）从M（存储器）取出指令送到IR（指令寄存器）2）译码分析：译出指令的操作性质，准备好所需数据 3）执行：将准备好的数按译出性质进行处理，

4、主要涉及ALU（算术逻辑运算部件）2.对指令执行的几种方式,1）顺序执行(传统机采用)只有在前一条指令的各过程段全部完成后，才从存储器取出下一条指令 2)仅两条指令重叠：第i条指令的执行与第i+1条的取指重叠。3)三条指令重叠：第i条指令的执行与第i+1条的译码及第i+2条的取指重叠。,若一条指令的过程段划分更多时，重叠组合方式更多。重叠解释并不能加快一条指令的实现，但能加快一段程序的解释。3.重叠方式中所需时间表达式及所需时间计算1）条件：设一条指令分为三个过程段，各过程段分别用t取、t译、t执表示。执行K条指令，分别采用顺序执行、两条重叠、三条重叠。假设:各个功能段时间相同,公式见教材P2

5、85,各个功能段时间不相同,公式见顺序执行 k*（t取+t译+t执）两条重叠 t取+k*t译+(k-1)*(t取,t执)max+t执三条重叠 t取+(t译,t取)max+(k-2)*（t取,t译,t 执）max+(t执,t译)max+t执,3)例子 当k=200，t取=3t，t译=4t，t执=5t，时，分别计算上述三种执行方式的时间。顺序执行：200(3+4+5)=2400t 两条重叠：3+2004+(200-1)5+5=1803t 三条重叠：3+4+(200-2)5+5+5=1007t,4 重叠方式需要解决的问题1）对存储器的频繁访问 有哪些访问：取指令、取操作数、存放执行结果,I/O通道访

6、问.希望存储器为多体结构，以适应多种访问源的需要。当存储器为单体结构时，需要将访问源排队，先后顺序为：取指令、取数据、I/O通道访问、存结果,先行控制（look-ahead）技术最早在IBM公司研制的STRETCH机器中采用。目前，许多处理机中都已经采用了这种技术，包括超流水处理机和超标量处理机等。先行控制技术的关键是缓冲技术和预处理技术，以及两者的结合。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作。预处理技术是把进入运算器的指令都处理成寄存器寄存器（RR型）指令，为进入运算器的指令准备好所需要的全部操作数。,6.1 先行控制技术,采用先行控制方式的处理机结构,2

7、）应具有先行控制部件 先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。先行控制部件的主要包括）先行地址站，包括先行指令地址站和先行操作数地址站；）先行指令站，用来存放多条指令；）先行操作数站，用来存放多个操作数；）先行地址形成部件，用来形成先行指令地址 以及先行操作数地址；）先行操作码译码站，用来完成对多条指令的 译码并保留译码输出状态。,也应具有后行部件 后行部件：对指令执行后的结果进行处理的器件，称 后行部件。包括：后行数地址站，提供后行数存放地址。后行数站，存放运行的结果，并且，这些结果需送存 储器。,6.2.

8、1 基本思想,6.2 流水处理的概念,6.2.2 流水技术,流水技术：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。时空图:从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。CPU中的各个部件按流水处理顺序连接起来，就称为一条流水线。,6.2.3 流水线工作原理流水线方式是把一个复杂的过程分解为若干个子过程，每个子过程与其他子过程同时进行。处理机解释程序的方式有顺序方式、重叠方式、流水方式等 顺序方式是解释完一条指令再开始解释下一条；流水方式是把一个重复的过程分解为若干个子过程，每个子过程可以

9、与其它子过程同时进行，以此提高单位时间内解释指令的数目；重叠方式是一种简单的流水方式，它把指令分成2个子过程 每条指令只与下一条指令相重叠。,重叠方式流水线,当分析部件完成上一条指令的“分析”后，就立即将之送入执行部件，同时分析部件可以开始处理下一条指令。虽然从执行一条指令的全过程来看，仍需要2t的时间，但从机器的输出端来看，却是每隔一个t就能给出一条指令的执行结果。,流水线结构图,流水线工作时空图,6.2.4 流水线的特点,流水过程由多个相联系的子过程组成，每个子过程称为流水线的级或段，段的数目称为流水线的深度。在流水线中处理的必须是连续任务，只有不断的提供任务才能充分发挥流水线的效率。把一

10、个任务分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。在流水线的每一个功能部件的后面都要有一个缓冲器，用于保存本段的执行结果。各个功能段所需时间应尽量相等，否则时间长的功能段将成为流水线的“瓶颈”，会造成流水线的“堵塞”和“断流”。这个时间一般为一个时钟周期（节拍）。流水线需要有“装入时间”和“排空时间”。,6.3 流水技术的分类,1）按各过程段用时是否全等划分 均匀流水线：各过程段用时全等 非均匀流水线：各过程段用时不全等（如上图）时间匹配的均匀流水线。）时间不匹配的非均匀流水线。,2）按处理的数据类型标量流水线：用于对标量数据进行流水处理。向量流水线：用于对向量数据进行流水

11、处理。（向量很适合流水处理）3）按流水线的规模操作流水线：如将一条指令划分为多个过程段进行流水处理。规模最小指令流水线：以指令为单位进行处理，用于多进程、多任务。规模较大 宏流水线：以程序的逻辑功能段为单位进行流水处理。规模最大,4）按流水线具有功能的多少 单功能流水线：各过程段之间固定连接，不能重新构成其它流水线固定流水线 多功能流水线分：静态流水线：各过程段之间可重新连接，但不同时刻只能重构成一种不同的流水线。动态流水线：各过程段之间可重新连接，不同时刻可重构成多种流水线。5）按部件在同一时刻送出支路数的多少来分。一维流水线：在同一时刻，部件只能向一个地方传送结果。阵列流水线：在同一时刻，

12、部件可同时向多个地方传送结果。,5.4.5“瓶颈”问题及其解决方法,瓶颈：瓶颈就是ti最大的段，它使流水线“流速”减慢。S1S2S3S4t3ttt方法1：再细分 将瓶颈设备再细分为下一级流水线S1S2aS2bS2cS3S4tttttt方法2：并行设置 将瓶颈设备重复设置多套。,衡量流水线的主要指标有吞吐率，加速比和效率。6.4.1 吞吐率TP吞吐率（TP ThroughPut）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。其中k表示流水线划分的段数。当满足 条件时，有。,6.4 线性流水线性能分析,S4 1 2 3 4 N-1 N S3 1 2 3 4 N-1 N S2

13、1 2 3 4 N-1 N S1 1 2 3 4 N-1 N 时间 KT(N-1)T NT(K-1)T Tk,流水线产生n个结果所需要的时间：实际吞吐率：最大吞吐率：最大吞吐率与实际吞吐率的关系：,（1）流水线各段的执行时间相等,实际吞吐率：最大吞吐率：,（2）流水线各段的执行时间不等,6.4.2 加速比（即吞吐率之比，）,不使用流水线所用的时间与使用流水线所用的时间之比一般表示：s=T0/TK其中 实际加速比：最大加速比：,段效率：，各段平均效率：其中 表示第i段设备量占整条流水线全部设备量的百分比当满足 条件（即等长、等权）时，有：,6.4.3 效率（设备利用率）,上式指出，S=Ek，就是

14、说当效率达到100%时，流水方式（一个任务/t）吞吐率为顺序方式（一个任务/(kt)）的k倍。,实际效率：最大效率：,瓶颈问题用两种方法改进后的效率和吞吐率,P295,6.5 流水线中的相关,相关的定义：流水线中的相关是指相邻或相近的指令因存在某种关联，后面的指令不能在原指定的时钟周期开始执行。一般来说，流水线中的相关主要分为如下三种类型：结构相关：当硬件资源满足不了指令重叠执行的要求，而发生资源冲突时，就发生了结构相关。数据相关：当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就可能引起数据相关。3.控制相关：当流水线遇到分支指令和其它能够改变 PC 值的指令时，就会

15、发生控制相关。,一旦流水线中出现相关，必然会给指令在流水线中的顺利执行带来许多问题，如果不能很好地解决相关问题，轻则影响流水线的性能，重则导致错误的执行结果。消除相关的基本方法是让流水线暂停执行某些指令，而继续执行其它一些指令。在后面的讨论中，我们约定：当一条指令被暂停时，在该暂停指令之后发射的所有指令都要被暂停，而在该暂停之前发射的指令则可继续进行，在暂停期间，流水线不会取新的指令。,5.6.1 结构相关,如果某些指令组合在流水线中重叠执行时，产生资源冲突，则称该流水线有结构相关。为了能够在流水线中顺利执行指令的所有可能组合，而不发生结构相关，通常需要采用流水化功能单元的方法或资源重复的方法

16、。,许多流水线机器都是将数据和指令保存在同一存储器中。如果在某个时钟周期内，流水线既要完成某条指令对数据的存储器访问操作，又要完成取指令的操作，那么将会发生存储器访问冲突问题 产生结构相关。为了解决这个问题，可以让流水线完成前一条指令对数据的存储器访问时，暂停取后一条指令的操作。该周期称为流水线的一个暂停周期。暂停周期一般也称为流水线气泡，或简称为“气泡”。在流水线中插入暂停周期可以消除这种结构相关。,结构相关举例访存冲突,为消除结构相关插入流水气泡,时空图来表示暂停情况,分析,为消除结构相关而引入的暂停将影响流水线的性能。为了避免结构相关，可以考虑采用资源重复的方法。比如，在流水线机器中设置

17、相互独立的指令存储器和数据存储器；也可以将 Cache 分割成指令 Cache 和数据 Cache。,假设不考虑流水线其它因素对流水线性能的影响，显然如果流水线机器没有结构相关，那么其 CPI 也较小。然而，为什么有时流水线设计者却允许结构相关的存在呢？主要有两个原因：一是为了减少硬件代价，二是为了减少功能单元的延迟。如果为了避免结构相关而将流水线中的所有功能单元完全流水化，或者设置足够的硬件资源，那么所带来的硬件代价必定很大。,6.6.2 数据相关,当指令在流水线中重叠执行时，流水线有可能改变指令读/写操作数的顺序，使得读/写操作顺序不同于它们非流水实现的顺序，这将导致数据相关。,ADD指令

18、后的所有指令都要用到ADD指令的计算结果，ADD 指令在 WB 段才将计算结果写入寄存器 R1 中，但是 SUB 指令在其 ID 段就要从寄存器 R1 中读取该计算结果，这种情况就叫做数据相关。除非有措施防止这一情况出现，否则 SUB 指令读到的是错误的值。所以，为了保证上述指令序列的正确执行，流水线只好暂停 ADD 指令之后的所有指令，直到 ADD 指令将计算结果写入寄存器 R1 之后，再启动 ADD 指令之后的指令继续执行。,数据相关举例,例子分析,从上图还可以看到，AND 指令同样也将受到这种相关关系的影响。ADD 指令只有到第五个时钟周期末尾才能结束对寄存器 R1 的写操作，所以 AN

19、D 指令在第四个时钟周期从寄存器 R1 中读出的值也是错误的。而 XOR 指令则可以正常操作，因为它是在第六个时钟周期读寄存器 R1 的内容。另外，利用流水线的一种简单技术，可以使流水线顺利执行 OR 指令。这种技术就是：在流水线中，约定在时钟周期的后半部分进行寄存器文件的读操作，而在时钟周期的前半部分进行寄存器文件的写操作。在图中，我们将寄存器文件的边框适当地画成虚线来表示这种技术。,通过定向技术减少数据相关带来的暂停,数据相关问题可以采用一种称为定向（也称为旁路或短路）的简单技术来解决。定向技术的主要思想是：在某条指令（如图中的 ADD 指令）产生一个计算结果之前，其它指令（如图中的 SU

20、B 和 AND 指令）并不真正需要该计算结果，如果能够将该计算结果从其产生的地方（寄存器文件 EX/MEM）直接送到其它指令需要它的地方（ALU 的输入寄存器），那么就可以避免暂停.,基于这种考虑，定向技术的要点可以归纳为：寄存器文件 EX/MEM 中的 ALU 的运算结果总是回送到 ALU 的输入寄存器；当定向硬件检测到前一个 ALU 运算结果的写入寄存器就是当前 ALU 操作的源寄存器时，那么控制逻辑将前一个 ALU 运算结果定向到 ALU 的输入端，后一个 ALU 操作就不必从源寄存器中读取操作数。流水线中的指令所需要的定向结果可能并不仅仅是前一条指令的计算结果，而且还有可能是前面与其不

21、相邻指令的计算结果,采用定向技术消除数据相关,定向技术的推广,上述定向技术可以推广到更一般的情况，可以将一个结果直接传送到所有需要它的功能单元。也就是说，一个结果不仅可以从某一功能单元的输出定向到其自身的输入，而且还可以从某一功能单元的输出定向到其它功能单元的输入。前面的一些数据相关的实例均是有关寄存器操作数的，但是数据相关也有可能发生在一对指令对存储器同一单元进行读写的时候。不过，本章仅讨论有关寄存器的数据相关。,到数据存储器和ALU的定向路径,数据相关分类,根据指令对寄存器的读写顺序，可以将数据相关分为三类。习惯上，这些相关是根据流水线所必须保持的访问顺序来命名的。考虑流水线中的两条指令

22、i 和 j，且 i 在 j 之前进入流水线，由此可能带来的数据相关有：,写后读相关（Read After Write，RAW）：j 的执行要用到 i 的计算结果，当它们在流水线中重叠执行时，j 可能在 i 写入其计算结果之前就先行对保存该结果的寄存器进行读操作，从而得到错误的值。这是最常见的一种数据相关，采用定向技术消除的数据相关就属于这种类型。,写后写相关（Write After Write，WAW）：j 和 i 的目的寄存器相同，当它们在流水线中重叠执行时，j 可能在 i 写入其计算结果之前就先行对该结果寄存器进行写操作，从而导致写入顺序错误，在目的寄存器中留下的是 i 写入的值，而不是

23、j 写入的值。如果在流水线中不只一个段可以进行写操作，或者当流水线暂停某条指令时，允许该指令之后的指令继续前进，就可能会产生这种类型的数据相关。读后写相关（Write After Read，WAR）：j 可能在 i 读取某个源寄存器的内容之前就先对该寄存器进行写操作，导致 i 后来读取到的值是错误的。,需要暂停的数据相关,前面我们讨论了如何利用定向技术消除由于数据相关带来的暂停。但是，并不是所有数据相关带来的暂停都可以通过定向技术消除。,对数据相关的编译器调度方法,流水线常常会遇到许多种类型的暂停。比如，采用典型的代码生成方法对A=BC这种常用的表达式进行处理，可以得到如图所示的指令序列。从图

24、中可以看出，在 ADD 指令的流水过程中必须插入一个暂停时钟周期，以保证变量C的读入值有效。既然定向无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？,指令级调度,实际上，编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技术为流水线调度（pipeline scheduling）或指令调度（instruction scheduling）。,6.6.3 控制相关,在流水线上执行分支指令时，PC 值有两种可能的变化情况。一种是 PC 值发生改变（为分支转移的目标地址）；一种是 PC 值保持正常。如果一条分支指令将PC值改

25、变为分支转移的目标地址，那么我们称分支转移成功；如果分支转移条件不成立，PC 值保持正常，我们称分支转移失败。,处理分支指令最简单的方法是：一旦在流水线中检测到某条指令是分支指令，就暂停执行该分支指令之后的所有指令，直到分支指令到达流水线的 MEM 段，确定了新的 PC 值为止。我们当然不希望流水线还没有确定某条指令是分支指令之前就暂停执行指令，所以对分支指令而言，当流水线完成其译码操作（ID段）之后才会暂停执行其后继指令。根据上述处理分支指令的方法，可以得到如图所示流水线时空图。从图中可以看出，在流水线中插入了两个暂停周期，当分支指令在 MEM 段确定新的 PC 值后，流水线作废分支直接后继

26、指令的 IF 周期（相当于一个暂停周期），按照新的有效 PC 值取指令。,减少分支暂停时钟周期数,减少流水线处理分支指令时的暂停时钟周期数有如下两种途径：在流水线中尽早判断出分支转移是否成功；尽早计算出分支转移成功时的 PC 值（即分支的目标地址）。为了优化处理分支指令，在流水线中应该同时采用上述两条途径，缺一不可。即使知道分支转移的目标地址，而不知道分支转移是否成功对减少暂停是徒劳的；知道分支转移是否成功，而不知道分支转移的目标地址，同样对降低分支损失毫无帮助。下面让我们看看如何基于这些思想，从硬件上改进流水线，达到降低分支损失的目的。,在流水线中，分支指令通常需要测试分支条件寄存器的值是否

27、为0，所以可以把测试分支条件寄存器的操作移到 ID 段完成，从而使得在 ID 周期末就完成分支转移成功与否的检测。另外，由于要尽早计算出两个 PC 值（分支转移成功和失败时的 PC 值），也可以将计算分支目标地址的操作移到 ID 段完成。为此，需要在 ID 段增设一个加法器（注意，为了避免结构相关，不能用EX段的 ALU 功能部件来计算分支转移目标地址）。下图是对流水线进行上述改进后的流水线数据通路。容易看出，基于上述改进后的流水线数据通路，处理分支指令只需要一个时钟周期的暂停。,减少分支暂停时钟周期数,降低流水线分支损失的方法有许多种。前面论述了改进流水线硬件减少流水线暂停周期的方法。这里主

28、要从编译技术的角度，论述四种降低流水线分支损失的简单方法。首先需要说明的是，这些方法对分支转移成功与否进行的预测都是静态的，并在整个程序的执行过程中保持这种预测结论，即：要么总是认为分支转移成功，要么总是认为分支转移失败。,冻结（freeze）或排空（flush）流水线的方法在流水线中，处理分支最简单的方法是冻结或排空流水线，保持或清除流水线在分支指令之后读入的任何指令，直到知道分支指令的目标地址以及分支转移是否成功为止。这种方法优点在于其对硬件和软件的要求都十分简单，我们前面采用的就是这种方法。,预测分支失败的方法 如果流水线采用预测分支失败的方法处理分支指令，那么当流水线译码到一条分支指令

29、时，流水线继续取指令，并允许该分支指令后的指令继续在流水线中流动。当流水线确定分支转移成功与否以及分支的目标地址之后，如果分支转移成功，流水线必须将在分支指令之后取出的所有指令转化为空操作，并在分支的目标地址处重新取出有效的指令；如果分支转移失败，那么可以将分支指令看作是一条普通指令，流水线正常流动，无需将在分支指令之后取出的所有指令转化为空操作。,预测分支成功的方法另一种降低流水线分支损失的方法便是预测分支成功，一旦流水线译码到一条指令是分支指令，且完成了分支目标地址的计算，我们就假设分支转移成功，并开始在分支目标地址处取指令执行。在某些流水线中，特别是那些具有隐含设置条件码或分支条件更复杂

30、指令的流水线机器中，在确定分支转移成功与否之前，便可以知道分支的目标地址，这时采用这种方法便可以降低这些流水线的分支损失。,4.延迟分支（delayed branch）方法 为降低流水线分支损失而采用的第四种方法就是延迟分支方法。其主要思想是从逻辑上“延长”分支指令的执行时间。延迟长度为 n 的分支指令的执行顺序是：分支指令 顺序后继指令1顺序后继指令 n如果分支成功，分支目标处指令 所有顺序后继指令都处于分支延迟槽（branch-delay slots）中，无论分支成功与否，流水线都会执行这些指令。,基于延迟分支方法，无论分支成功与否，其流水线时空图所描述的流水线的行为是类似的，流水线中均没

31、有插入暂停周期，从而极大地降低了流水线分支损失。从图中可以看出，实际上是处于分支延迟槽中的指令“掩盖”了流水线原来所必需插入的暂停周期。,6.6 非线性流水线调度技术,调度问题的提出：一个任务在通过非线性流水线时对有些功能段要通过多次（非线性定义），所以容易与紧跟而来的后继任务发生设备争用。调度机构的作用就是合理安排前后任务进入流水线的相差时间，既要避免争用，又要使相差时间尽可能少，以提高吞吐率。,1.非线性流水线的表示,一条非线性流水线一般需要一个各功能段间的连接图和一张预约表共同表示。下图是一条4个功能段组成的非线性流水线，它有从S1到S4 的单方向传输线。但它有两条反馈线和一条前馈线；输

32、出端不一定在最后一个功能段，而可能从任意一个功能段输出。输出 输入,2.非线性流水线的预约表,3.对于非线性流水线的表示,预约表的横坐标表示流水线的时钟周期，纵坐标表示流水线的功能段，中间有“”的表示该功能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段；空白的表示该功能段在这一个时钟周期不处于工作状态。预约表行数是非线性流水线的段数；而列数是一个任务从进入流水线到从流水线中输出所经历的时钟周期数。一张非线性流水线的预约表可能与多个非线性流水线连接图相对应；同样，一个非线性流水线的连接图也可能对应有多张预约表。,4.非线性流水线的冲突,非线性流水线的启动距离：向一条非线性流

33、水线的输入端连续输入两个任务之间的时间间隔。非线性流水线的冲突：当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能 段的情况。,5.无冲突调度方法,目标：找出具有最小平均启动时间的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。,算法：共5个步骤第1步.分析预约表R描述非线性流水线有2种图形：(a)连接图，仅给出各段之间的静态空间连接关系；(b)预约表，就是一个任务通过流水线的时空图，能全面反映该流水线的动态特性。要检验2个任务相距k拍是否冲突，可将它们的预

34、约表错位k列重叠（如图）。,6.6.1 不改变流水线结构的调度方法,第2步.作禁止表（禁止启动距离）FF是1-N之间可冲突拍数的集合，N是预约表的列数减1。具体操作是将同一行中任意2个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，即为禁止表，由大到小写着。本例中 F=6，4，3,第3步.作原始冲突向量C为了设计调度机构，需将禁止启动距离表转化为原始冲突向量C（Collision）。C是含N个分量的布尔向量，一般形式为C=(cN.c1)，其中N是预约表的列数减1，也可以是禁止表中的最大元素。第i个分量取值原则为：本例中 C=(101100),动态冲突向量（初值000000）右移寄存器：

35、0 010110右移出0“或”运算器：按位“或”0接通1断开常量发生器：101100 原始冲突向量 时钟输入 流水线任务排队1.每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位；2.如果新任务进入，则用它的原始冲突向量与右移寄存器内容相“或”。,使用冲突向量C实现调度的原理图,第4步.作状态转移图这是为了研究无穷多个任务时任务之间可能存在的合法间隔情况。从表达方便考虑，用动态冲突向量作为状态变量。具体作图方法是：(1)先画“根结点”，它就是第一个任务进入后的右移寄存器状态，数值等于原始冲突向量；(2)分析当前结点的各位，如果ci=0则发出一个旁标i值的箭头，ci=1则不能发出箭头

36、，因为1表示“禁止”。此外还发出一个旁标“N+1*”的箭头，“N+1*”意为“N+1”；(3)每个箭头末端产生一个新的结点，其状态等于原结点状态右移i位后与原始冲突向量相“或”；(4)如果新结点状态与已有的结点重复，则取消它，箭头指向已有的那个结点。,第5步.作平均延迟拍数表(1)在状态转移图中寻找全部简单循环填入右表第1栏。所谓简单循环是指其中各结点仅通过一次的闭合路径。注意它不一定要通过根结点；(2)计算各简单循环的平均间隔拍数填入右表第2栏。平均间隔拍数等于该简单循环中所有数字之和除以数字个数；(3)取平均延迟拍数最少的方案作为最优方案。本例为(1,1,7)；(4)调度机构实现：计数器加译码电路。本例可用模9计数器，译码条件是计数值等于0、1、2时允许进入流水线。,