第五章重叠、流水和向量处理机1

第五章重叠、流水和向量处理机

§1重叠方式通常提高指令执行速度的途径有如下三种：提高处理机的工作主频。采用更好的算法和设计更好的功能部件。多条指令并行执行，称为指令级并行技术。

可以从两个方面来开发处理机内部的并行性：空间并行性：即在一个处理机内设置多个独立的操作部件，并让这些操作部件并行工作，这种处理机称为多操作部件处理机或超标量处理机;时间并行性：就是采用流水线技术。流水线技术是一种非常经济、对提高处理机的运算速度非常有效的技术。采用流水线技术可以不增加硬件或只需要增加少量硬件就能够把处理机的运算速度提高几倍它是目前使用非常普遍的一种并行处理方式。

本章学习标量计算机上使用的流水加速技术。主要内容有流水技术的分类、流水线性能指标计算、非线性流水线的调度算法。标量计算机指只能直接进行标量运算的计算机，与能够直接进行向量运算的向量计算机相对应。流水处理方式的特征，是让多个依次启动的任务，尽量同时使用系统的不同部件，通过时间重叠来提高处理速率。这种技术理论上不增加成本。标量计算机上使用的流水加速技术属于指令级并行技术。

每条指令的处理过程，可以划分为取指、译码、取数、运算、送结果5个子过程，也可以分得更细或更粗一些。划分的原则是各部分时间长度大致相等、并使用CPU中不同的部件，这样才有利于多任务重叠处理。基本名词术语标量处理机，超标量处理机：标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；指令级并行技术：指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；流水线处理机，超流水线处理机：流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；超长指令字技术VLIW：指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。

一．重叠解释方式1.一条指令的几个过程段1）取指令：根据PC（指令计数器）从M（存储器）取出指令送到IR（指令寄存器）2）译码分析：译出指令的操作性质，准备好所需数据3）执行：将准备好的数按译出性质进行处理，主要涉及ALU（算术逻辑运算部件）2.对指令执行的几种方式1）顺序执行(传统机采用)只有在前一条指令的各过程段全部完成后，才从存储器取出下一条指令2)仅两条指令重叠：第i条指令的执行与第i+1条的取指重叠。3)三条指令重叠：第i条指令的执行与第i+1条的译码及第i+2条的取指重叠。

取

译

执

取

译

执

i条

i+1条

i条取译执i+1条取译执i+2条取译执i条取译执取译执i+1条

若一条指令的过程段划分更多时，重叠组合方式更多。重叠解释并不能加快一条指令的实现，但能加快一段程序的解释。3.重叠方式中所需时间表达式及所需时间计算1）条件：设一条指令分为三个过程段，各过程段分别用t取、t译、t执表示。执行K条指令，分别采用顺序执行、两条重叠、三条重叠。假设:各个功能段时间相同,公式见教材P231各个功能段时间不相同,公式见顺序执行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取=3Δt，t译=4Δt，t执=5Δt，时，分别计算上述三种执行方式的时间。顺序执行：200×(3+4+5)=2400Δt两条重叠：3+200×4+(200-1)×5+5=1803Δt三条重叠：3+4+(200-2)×5+5+5=1007Δt4重叠方式需要解决的问题1）对存储器的频繁访问①有哪些访问：取指令、取操作数、存放执行结果,I/O通道访问.②希望存储器为多体结构，以适应多种访问源的需要。③当存储器为单体结构时，需要将访问源排队，先后顺序为：取指令、取数据、I/O通道访问、存结果先行控制（look-ahead）技术最早在IBM公司研制的STRETCH机器中采用。目前，许多处理机中都已经采用了这种技术，包括超流水处理机和超标量处理机等。先行控制技术的关键是缓冲技术和预处理技术，以及两者的结合。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作。预处理技术是把进入运算器的指令都处理成寄存器－寄存器（RR型）指令，为进入运算器的指令准备好所需要的全部操作数。5.1先行控制技术采用先行控制方式的处理机结构2）应具有先行控制部件①

先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。②先行控制部件的主要包括

Ⅰ）先行地址站，包括先行指令地址站和先行操作数地址站；

Ⅱ）先行指令站，用来存放多条指令；

Ⅲ）先行操作数站，用来存放多个操作数；

Ⅳ）先行地址形成部件，用来形成先行指令地址以及先行操作数地址；

Ⅴ）先行操作码译码站，用来完成对多条指令的译码并保留译码输出状态。也应具有后行部件

后行部件：对指令执行后的结果进行处理的器件，称

后行部件。包括：

①后行数地址站，提供后行数存放地址。

②后行数站，存放运行的结果，并且，这些结果需送存

储器。5.2.1基本思想5.2流水处理的概念5.2.2流水技术

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

流水方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目；

重叠方式是一种简单的流水方式，它把指令分成2个子过程每条指令只与下一条指令相重叠。

重叠方式流水线当分析部件完成上一条指令的“分析”后，就立即将之送入执行部件，同时分析部件可以开始处理下一条指令。虽然从执行一条指令的全过程来看，仍需要2∆t的时间，但从机器的输出端来看，却是每隔一个∆t就能给出一条指令的执行结果。

流水线结构图

流水线工作时空图

5.2.4流水线的特点流水过程由多个相联系的子过程组成，每个子过程称为流水线的级或段，段的数目称为流水线的深度。在流水线中处理的必须是连续任务，只有不断的提供任务才能充分发挥流水线的效率。把一个任务分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。在流水线的每一个功能部件的后面都要有一个缓冲器，用于保存本段的执行结果。各个功能段所需时间应尽量相等，否则时间长的功能段将成为流水线的“瓶颈”，会造成流水线的“堵塞”和“断流”。这个时间一般为一个时钟周期（节拍）。流水线需要有“装入时间”和“排空时间”。5.3流水技术的分类1）按各过程段用时是否全等划分①均匀流水线：各过程段用时全等②非均匀流水线：各过程段用时不全等（如上图）Ⅰ）时间匹配的均匀流水线。Ⅱ）时间不匹配的非均匀流水线。2）按处理的数据类型①标量流水线：用于对标量数据进行流水处理。②向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理）3）按流水线的规模①操作流水线：如将一条指令划分为多个过程段进行流水处理。规模最小②指令流水线：以指令为单位进行处理，用于多进程、多任务。规模较大③宏流水线：以程序的逻辑功能段为单位进行流水处理。规模最大4）按流水线具有功能的多少①单功能流水线：各过程段之间固定连接，不能重新构成其它流水线——固定流水线②多功能流水线分：静态流水线：各过程段之间可重新连接，但不同时刻只能重构成一种不同的流水线。动态流水线：各过程段之间可重新连接，不同时刻可重构成多种流水线。5）按部件在同一时刻送出支路数的多少来分。①一维流水线：在同一时刻，部件只能向一个地方传送结果。②阵列流水线：在同一时刻，部件可同时向多个地方传送结果。5.4.5“瓶颈”问题及其解决方法瓶颈：瓶颈就是Δti最大的段，它使流水线“流速”减慢。 S1 S2 S3 S4

Δt 3Δt Δt Δt方法1：再细分──将瓶颈设备再细分为下一级流水线 S1 S2a S2b S2c S3 S4

Δt Δt Δt Δt Δt Δt方法2：并行设置──将瓶颈设备重复设置多套。

衡量流水线的主要指标有吞吐率，加速比和效率。5.4.1吞吐率TP吞吐率（TP──ThroughPut）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。其中k表示流水线划分的段数。当满足 条件时，有 。5.4线性流水线性能分析S41234……N-1NS31234……N-1NS21234……N-1NS11234……N-1N时间K×T(N-1)×TN×T(K-1)×TTk

流水线产生n个结果所需要的时间：

实际吞吐率：

最大吞吐率：最大吞吐率与实际吞吐率的关系：（1） 流水线各段的执行时间相等

实际吞吐率：

最大吞吐率：

（2） 流水线各段的执行时间不等5.4.2加速比（即吞吐率之比，）不使用流水线所用的时间与使用流水线所用的时间之比一般表示：s=T0/TK其中实际加速比：最大加速比：段效率： ， 各段平均效率：其中表示第i段设备量占整条流水线全部设备量的百分比当满足 条件（即"等长"、"等权"）时，有：5.4.3效率（设备利用率）上式指出，S=E×k，就是说当效率达到100%时，流水方式（一个任务/Δt）吞吐率为顺序方式（一个任务/(k×Δt)）的k倍。实际效率：最大效率：瓶颈问题用两种方法改进后的效率和吞吐率静态双功能流水线的效率与吞吐率教材P241非线性流水线的吞吐率和效率教材P291

5.5流水线中的相关相关的定义：流水线中的相关是指相邻或相近的指令因存在某种关联，后面的指令不能在原指定的时钟周期开始执行。一般来说，流水线中的相关主要分为如下三种类型：结构相关：当硬件资源满足不了指令重叠执行的要求，而发生资源冲突时，就发生了结构相关。数据相关：当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就可能引起数据相关。

3.控制相关：当流水线遇到分支指令和其它能够改变PC值的指令时，就会发生控制相关。

一旦流水线中出现相关，必然会给指令在流水线中的顺利执行带来许多问题，如果不能很好地解决相关问题，轻则影响流水线的性能，重则导致错误的执行结果。消除相关的基本方法是让流水线暂停执行某些指令，而继续执行其它一些指令。

在后面的讨论中，我们约定：当一条指令被暂停时，在该暂停指令之后发射的所有指令都要被暂停，而在该暂停之前发射的指令则可继续进行，在暂停期间，流水线不会取新的指令。

5.5.1结构相关如果某些指令组合在流水线中重叠执行时，产生资源冲突，则称该流水线有结构相关。为了能够在流水线中顺利执行指令的所有可能组合，而不发生结构相关，通常需要采用流水化功能单元的方法或资源重复的方法。

许多流水线机器都是将数据和指令保存在同一存储器中。如果在某个时钟周期内，流水线既要完成某条指令对数据的存储器访问操作，又要完成取指令的操作，那么将会发生存储器访问冲突问题产生结构相关。为了解决这个问题，可以让流水线完成前一条指令对数据的存储器访问时，暂停取后一条指令的操作。该周期称为流水线的一个暂停周期。暂停周期一般也称为流水线气泡，或简称为“气泡”。在流水线中插入暂停周期可以消除这种结构相关。

结构相关举例－－访存冲突

为消除结构相关插入流水气泡

时空图来表示暂停情况分析

为消除结构相关而引入的暂停将影响流水线的性能。为了避免结构相关，可以考虑采用资源重复的方法。比如，在流水线机器中设置相互独立的指令存储器和数据存储器；也可以将Cache分割成指令Cache和数据Cache。

假设不考虑流水线其它因素对流水线性能的影响，显然如果流水线机器没有结构相关，那么其CPI也较小。然而，为什么有时流水线设计者却允许结构相关的存在呢？主要有两个原因：一是为了减少硬件代价，二是为了减少功能单元的延迟。如果为了避免结构相关而将流水线中的所有功能单元完全流水化，或者设置足够的硬件资源，那么所带来的硬件代价必定很大。

5.5.2数据相关当指令在流水线中重叠执行时，流水线有可能改变指令读/写操作数的顺序，使得读/写操作顺序不同于它们非流水实现的顺序，这将导致数据相关。

ADDR1，R2，R3SUBR4，R5，R1ANDR6，R1，R7ORR8，R1，R9XORR10，R1，R11ADD指令后的所有指令都要用到ADD指令的计算结果，ADD指令在WB段才将计算结果写入寄存器R1中，但是SUB指令在其ID段就要从寄存器R1中读取该计算结果，这种情况就叫做数据相关。除非有措施防止这一情况出现，否则SUB指令读到的是错误的值。所以，为了保证上述指令序列的正确执行，流水线只好暂停ADD指令之后的所有指令，直到ADD指令将计算结果写入寄存器R1之后，再启动ADD指令之后的指令继续执行。

数据相关举例例子分析

从上图还可以看到，AND指令同样也将受到这种相关关系的影响。ADD指令只有到第五个时钟周期末尾才能结束对寄存器R1的写操作，所以AND指令在第四个时钟周期从寄存器R1中读出的值也是错误的。而XOR指令则可以正常操作，因为它是在第六个时钟周期读寄存器R1的内容。

另外，利用流水线的一种简单技术，可以使流水线顺利执行OR指令。这种技术就是：在流水线中，约定在时钟周期的后半部分进行寄存器文件的读操作，而在时钟周期的前半部分进行寄存器文件的写操作。在图中，我们将寄存器文件的边框适当地画成虚线来表示这种技术。通过定向技术减少数据相关带来的暂停数据相关问题可以采用一种称为定向（也称为旁路或短路）的简单技术来解决。定向技术的主要思想是：在某条指令（如图中的ADD指令）产生一个计算结果之前，其它指令（如图中的SUB和AND指令）并不真正需要该计算结果，如果能够将该计算结果从其产生的地方（寄存器文件EX/MEM）直接送到其它指令需要它的地方（ALU的输入寄存器），那么就可以避免暂停.基于这种考虑，定向技术的要点可以归纳为：寄存器文件EX/MEM中的ALU的运算结果总是回送到ALU的输入寄存器；当定向硬件检测到前一个ALU运算结果的写入寄存器就是当前ALU操作的源寄存器时，那么控制逻辑将前一个ALU运算结果定向到ALU的输入端，后一个ALU操作就不必从源寄存器中读取操作数。流水线中的指令所需要的定向结果可能并不仅仅是前一条指令的计算结果，而且还有可能是前面与其不相邻指令的计算结果采用定向技术消除数据相关定向技术的推广上述定向技术可以推广到更一般的情况，可以将一个结果直接传送到所有需要它的功能单元。也就是说，一个结果不仅可以从某一功能单元的输出定向到其自身的输入，而且还可以从某一功能单元的输出定向到其它功能单元的输入。前面的一些数据相关的实例均是有关寄存器操作数的，但是数据相关也有可能发生在一对指令对存储器同一单元进行读写的时候。不过，本章仅讨论有关寄存器的数据相关。到数据存储器和ALU的定向路径数据相关分类根据指令对寄存器的读写顺序，可以将数据相关分为三类。习惯上，这些相关是根据流水线所必须保持的访问顺序来命名的。考虑流水线中的两条指令i和j，且i在j之前进入流水线，由此可能带来的数据相关有：写后读相关（ReadAfterWrite，RAW）：j的执行要用到i的计算结果，当它们在流水线中重叠执行时，j可能在i写入其计算结果之前就先行对保存该结果的寄存器进行读操作，从而得到错误的值。这是最常见的一种数据相关，采用定向技术消除的数据相关就属于这种类型。写后写相关（WriteAfterWrite，WAW）：j和i的目的寄存器相同，当它们在流水线中重叠执行时，j可能在i写入其计算结果之前就先行对该结果寄存器进行写操作，从而导致写入顺序错误，在目的寄存器中留下的是i写入的值，而不是j写入的值。

如果在流水线中不只一个段可以进行写操作，或者当流水线暂停某条指令时，允许该指令之后的指令继续前进，就可能会产生这种类型的数据相关。读后写相关（WriteAfterRead，WAR）：j可能在i读取某个源寄存器的内容之前就先对该寄存器进行写操作，导致i后来读取到的值是错误的。需要暂停的数据相关前面我们讨论了如何利用定向技术消除由于数据相关带来的暂停。但是，并不是所有数据相关带来的暂停都可以通过定向技术消除。对数据相关的编译器调度方法流水线常常会遇到许多种类型的暂停。比如，采用典型的代码生成方法对A=B＋C这种常用的表达式进行处理，可以得到如图所示的指令序列。从图中可以看出，在ADD指令的流水过程中必须插入一个暂停时钟周期，以保证变量C的读入值有效。既然定向无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？指令级调度实际上，编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技术为流水线调度（pipelinescheduling）或指令调度（instructionscheduling）。

5.5.3控制相关在流水线上执行分支指令时，PC值有两种可能的变化情况。一种是PC值发生改变（为分支转移的目标地址）；一种是PC值保持正常。如果一条分支指令将PC值改变为分支转移的目标地址，那么我们称分支转移成功；如果分支转移条件不成立，PC值保持正常，我们称分支转移失败。处理分支指令最简单的方法是：一旦在流水线中检测到某条指令是分支指令，就暂停执行该分支指令之后的所有指令，直到分支指令到达流水线的MEM段，确定了新的PC值为止。我们当然不希望流水线还没有确定某条指令是分支指令之前就暂停执行指令，所以对分支指令而言，当流水线完成其译码操作（ID段）之后才会暂停执行其后继指令。

根据上述处理分支指令的方法，可以得到如图所示流水线时空图。从图中可以看出，在流水线中插入了两个暂停周期，当分支指令在MEM段确定新的PC值后，流水线作废分支直接后继指令的IF周期（相当于一个暂停周期），按照新的有效PC值取指令。减少分支暂停时钟周期数减少流水线处理分支指令时的暂停时钟周期数有如下两种途径：在流水线中尽早判断出分支转移是否成功；尽早计算出分支转移成功时的PC值（即分支的目标地址）。

为了优化处理分支指令，在流水线中应该同时采用上述两条途径，缺一不可。即使知道分支转移的目标地址，而不知道分支转移是否成功对减少暂停是徒劳的；知道分支转移是否成功，而不知道分支转移的目标地址，同样对降低分支损失毫无帮助。下面让我们看看如何基于这些思想，从硬件上改进流水线，达到降低分支损失的目的。在流水线中，分支指令通常需要测试分支条件寄存器的值是否为0，所以可以把测试分支条件寄存器的操作移到ID段完成，从而使得在ID周期末就完成分支转移成功与否的检测。

另外，由于要尽早计算出两个PC值（分支转移成功和失败时的PC值），也可以将计算分支目标地址的操作移到ID段完成。为此，需要在ID段增设一个加法器（注意，为了避免结构相关，不能用EX段的ALU功能部件来计算分支转移目标地址）。下图是对流水线进行上述改进后的流水线数据通路。容易看出，基于上述改进后的流水线数据通路，处理分支指令只需要一个时钟周期的暂停。减少分支暂停时钟周期数降低流水线分支损失的方法有许多种。前面论述了改进流水线硬件减少流水线暂停周期的方法。这里主要从编译技术的角度，论述四种降低流水线分支损失的简单方法。首先需要说明的是，这些方法对分支转移成功与否进行的预测都是静态的，并在整个程序的执行过程中保持这种预测结论，即：要么总是认为分支转移成功，要么总是认为分支转移失败。冻结（freeze）或排空（flush）流水线的方法

在流水线中，处理分支最简单的方法是冻结或排空流水线，保持或清除流水线在分支指令之后读入的任何指令，直到知道分支指令的目标地址以及分支转移是否成功为止。这种方法优点在于其对硬件和软件的要求都十分简单，我们前面采用的就是这种方法。预测分支失败的方法如果流水线采用预测分支失败的方法处理分支指令，那么当流水线译码到一条分支指令时，流水线继续取指令，并允许该分支指令后的指令继续在流水线中流动。当流水线确定分支转移成功与否以及分支的目标地址之后，如果分支转移成功，流水线必须将在分支指令之后取出的所有指令转化为空操作，并在分支的目标地址处重新取出有效的指令；如果分支转移失败，那么可以将分支指令看作是一条普通指令，流水线正常流动，无需将在分支指令之后取出的所有指令转化为空操作。预测分支成功的方法

另一种降低流水线分支损失的方法便是预测分支成功，一旦流水线译码到一条指令是分支指令，且完成了分支目标地址的计算，我们就假设分支转移成功，并开始在分支目标地址处取指令执行。

在某些流水线中，特别是那些具有隐含设置条件码或分支条件更复杂指令的流水线机器中，在确定分支转移成功与否之前，便可以知道分支的目标地址，这时采用这种方法便可以降低这些流水线的分支损失。

4.延迟分支（delayedbranch）方法为降低流水线分支损失而采用的第四种方法就是延迟分支方法。其主要思想是从逻辑上“延长”分支指令的执行时间。延迟长度为n的分支指令的执行顺序是：

分支指令

顺序后继指令1

……

顺序后继指令n

如果分支成功，分支目标处指令

所有顺序后继指令都处于分支延迟槽（branch-delayslots）中，无论分支成功与否，流水线都会执行这些指令。

基于延迟分支方法，无论分支成功与否，其流水线时空图所描述的流水线的行为是类似的，流水线中均没有插入暂停周期，从而极大地降低了流水线分支损失。从图中可以看出，实际上是处于分支延迟槽中的指令“掩盖”了流水线原来所必需插入的暂停周期。5.6非线性流水线调度技术调度问题的提出：一个任务在通过非线性流水线时对有些功能段要通过多次（非线性定义），所以容易与紧跟而来的后继任务发生设备争用。调度机构的作用就是合理安排前后任务进入流水线的相差时间，既要避免争用，又要使相差时间尽可能少，以提高吞吐率。1.非线性流水线的表示

一条非线性流水线一般需要一个各功能段间的连接图和一张预约表共同表示。下图是一条4个功能段组成的非线性流水线，它有从S1到S4的单方向传输线。但它有两条反馈线和一条前馈线；输出端不一定在最后一个功能段，而可能从任意一个功能段输出。

输出

输入S1S2S3S42.

非线性流水线的预约表×S4××S3××S2×

××S17

6

5

4321时功能段3.对于非线性流水线的表示

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

非线性流水线的启动距离：向一条非线性流水线的输入端连续输入两个任务之间的时间间隔。非线性流水线的冲突：当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能段的情况。5.无冲突调度方法目标：找出具有最小平均启动时间的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。

算法：共5个步骤第1步.分析预约表R描述非线性流水线有2种图形：(a)连接图，仅给出各段之间的静态空间连接关系；(b)预约表，就是一个任务通过流水线的时空图，能全面反映该流水线的动态特性。要检验2个任务相距k拍是否冲突，可将它们的预约表错位k列重叠（如图）。5.6.1不改变流水线结构的调度方法第2步.作禁止表FF是1-N之间可冲突拍数的集合，N是预约表的列数减1。具体操作是将同一行中任意2个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，即为禁止表。本例中F={3，4，6}

第3步.作原始冲突向量C为了设计调度机构，需将禁止表转化为原始冲突向量C（Collision）。C是含N个分量的布尔向量，一般形式为C=(cN...c1)，其中N是预约表的列数减1，也可以是禁止表中的最大元素。第i个分量取值原则为：本例中C=(101100)

动态冲突向量

（初值000000）右移寄存器： 0010110 右移出0“或”运算器： 按位“或” 0接通 1断开常量发生器： 101100 原始冲突向量时钟输入 流水线 任务排队1.每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位；2.如果新任务进入，则用它的原始冲突向量与右移寄存器内容相“或”。使用冲突向量C实现调度的原理图第4步.作状态转移图这是为了研究无穷多个任务时任务之间可能存在的合法间隔情况。从表达方便考虑，用动态冲突向量作为状态变量。具体作图方法是：(1)先画“根结点”，它就是第一个任务进入后的右移寄存器状态，数值等于原始冲突向量；(2)分析当前结点的各位，如果ci=0则发出一个旁标i值的箭头，ci=1则不能发出箭头，因为1表示“禁止”。此外还发出一个旁标“N+1*”的箭头，“N+1*”意为“≥N+1”；(3)每个箭头末端产生一个新的结点，其状态等于原结点状态右移i位后与原始冲突向量相“或”；(4)如果新结点状态与已有的结点重复，则取消它，箭头指向已有的那个结点。第5步.作平均延迟拍数表(1)在状态转移图中寻找全部简单循环填入右表第1栏。所谓简单循环是指其中各结点仅通过一次的闭合路径。注意它不一定要通过根结点；(2)计算各简单循环的平均间隔拍数填入右表第2栏。平均间隔拍数等于该简单循环中所有数字之和除以数字个数；(3)取平均延迟拍数最少的方案作为最优方案。本例为(1,1,7)；(4)调度机构实现：计数器加译码电路。本例可用模9计数器，译码条件是计数值等于0、1、2时允许进入流水线。时间功能段1S1S2S3S4234567891011…11111,21,211,2,322222,333,33,4…………,4

45.6.2改变流水线结构的优化调度方法──预留算法

目的：等间隔的最小延迟调度方案方法：插入延迟器件第1步，确定相邻任务间隔拍数：因为最小间隔拍数是一行内“×”的最大数目（第11行），取最小间隔拍数。第2步，确定插入延迟器件位置的原则（P302第2行）：从第一个“×”

开始，凡是相距最小间隔拍数整倍数位置的“×”都要向后推迟。实例（P301倒数第7行）：

1.确定间隔拍数（最多3个“×”，所以是3拍）；

2.插入延迟器件（使各行“×”的间距不为3的倍数）；

3.修改预约表（P302图5.53(a)）；

4.写调度方案（3）（示意图见下页）5.7超标量/超流水/超长指令字技术

本节学习其它指令级并行技术。主要内容有超标量技术、超流水技术、多操作部件技术、超长指令字技术。下面是一些相关的名词术语标量处理机，超标量处理机：标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；指令级并行技术：指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；流水线处理机，超流水线处理机：流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；超长指令字技术VLIW：指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。5.7.1超标量技术

一个时钟节拍内同时发射多条指令

通常，把一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机。超标量处理机最基本的要求是必须有两套或两条以上完整的指令执行部件。上图是典型超标量处理机的指令流水线，为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线。目前，在多数超标量处理机中，每个时钟周期发射两条指令，通常不超过4条。由于存在有数据相关和条件转移等问题，采用一般的指令调度技术，理论上的最佳情况是每个时钟周期发射3条指令。对大量程序的模拟统计结果也表明，每个时钟周期发射2至4条指令比较合理。例如，Intel公司的i860、i960、Pentium处理机，Motolora公司的MC88110处理机，IBM公司的Power6000处理机等每个时钟周期都发射两条指令；美国德州仪器公司（TI）为SUN公司生产SuperSPARC处理机每个时钟周期发射三条指令。超标量处理机指令调度要解决的问题数据相关控制相关功能部件冲突多发射流水线的调度问题（例子说明）

共需10个周期。有8个空闲周期，其中4个是为了保证指令的顺序发射顺序完成。（1）顺序发射顺序完成（2） 顺序发射乱序完成共需9个周期。仅有3个空闲周期。（3）乱序发射乱序完成共需8个周期，无空闲周期。

超标量处理机性能N条没有资源冲突、数据相关和控制相关的指令在单条流水线普通标量处理机上的执行时间为：

T(1,1)=(K+N-1)×T把相同的N条指令在一台每个时钟周期发射M条的超标量处理机上执行时间为：

T(m,1)=(K+(N-m)/M)×T加速比S(m,1)=T(1,1)/T(m,1)

其中，K是流水线的级数，T是一个时钟周期的时间长度。5.7.2超流水技术

一个时钟节拍内分时发射多条指令

超流水线处理机性能在一台指令级并行度为（1，n）的超流水线处理机上，执行N条没有数据相关和控制相关的指令所需要的时间为：

T(1,n)=(K+(N-1)/n)×T加速比S(1,n)=T(1,1)/T(1,n)=n×(K+N-1)/(n×K+N-1)1.超标量超流水线处理机 超标量超流水线处理机在一个时钟周期内要发射指令n次，每次发射指令m条，因此，超标量超流水线处理机每个时钟周期总共要发射指令m×n条。 在下图中，每一个时钟周期分为3个流水线周期，每一个流水线周期发射3条指令。从图中可以看出，每个时钟周期能够发射并执行完成9条指令。因此，在理想情况下，超标量超流水线处理机执行程序的速度应该是超标量处理机和超流水线处理机执行程序速度的乘积。5.7.3超标量超流水技术2. 超标量超流水线处理机的性能（1）性能 在一台指令级并行度为（m，n）的超标量超流水线处理机上，连续执行N条没有资源冲突、没有数据相关和控制相关的指令所需要的时间为：

其中，k是指令流水线的时钟周期数，而不是流水线级数。△t是一个时钟周期的时间长度。上式中的第一项是开始m条指令通过指令流水线所需要的时间，第二项是执行其余N-m条指令所需要的时间；这时，每一个时钟周期平均执行完成m×n条指令，也就是每一个流水线周期平均执行完成n条指令。（2）性能比较（3）结论：超标量处理机的相对性能最高，其次是超标量超流水线处理机，超流水线处理机的相对性能最低，主要原因如下：超标量处理机在每个时钟周期的一开始就同时发射多条指令，而超流水线处理机则要把一个时钟周期平均分成多个流水线周期，每个流水线周期发射一条指令。因此，超流水线处理机的启动延迟比超标量处理机大。条件转移造成的损失，超流水线处理机要比超标量处理机大。在指令执行过程中的每一个功能段，超标量处理机都重复设置有多个相同的指令执行部件，而超流水线处理机只是把同一个指令执行部件分解为多个流水级。因此，超标量处理机指令执行部件的冲突要比超流水线处理机小。 当横坐标给出的设计指令级并行度比较低时，处理机实际指令级并行度的提高比较快。但是，当设计指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。因此，在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当；否则，有可能造成花费了大量的硬件，但实际上处理机所能达到的指令级并行度并不高。目前，一般认为m和n都不要超过4。一个特定程序由于受到本身的数据相关和控制相关的限制，它的指令级并行度的最大值是确定的。这个最大值主要由程序自身的语义来决定，与这个程序运行在那一种处理机上无关。因此，上图中的三条曲线，对于某一个特定的程序，最终都要收拢到同一个点上。当然，对于各个不同程序，这个收拢点的位置也是不同的。

一个程序能够达到的实际指令级并行度还与所采用的调度算法有关。目前，国际上已经提出了多种开发指令级并行性的优化调度算法。对于没有条件转移操作，没有输入输出，没有程序调用和程序中断，单入口单出口的基本块程序，实现最优调度并不十分困难。但是，对于一般程序，要充分开发程序中的指令级并行性，实现最优调度非