单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,可以从两个方面来开发处理机内部的并行性：,空间并行性：即在一个处理机内设置多个独立的操作部件，并让这些操作部件并行工作，这种处理机称为多操作部件处理机或超标量处理机,;,时间并行性：就是采用流水线技术。流水线技术是一种非常经济、对提高处理机的运算速度非常有效的技 术。采用流水线技术可以不增加硬件或只需要增加少量硬件就能够把处理机的运算速度提高几倍,它是目前使用非常普遍的一种并行处理方式。,本章学习标量计算机上使用的流水加速技术。主要内容有流水技术的分类、流水线性能指标计算、非线性流水线的调度算法。,标量计算机指只能直接进行标量运算的计算机，与能够直接进行向量运算的向量计算机相对应。,流水处理方式的特征，是让多个依次启动的任务，尽量同时使用系统的不同部件，通过时间重叠来提高处理速率。这种技术理论上不增加成本。,标量计算机上使用的流水加速技术属于指令级并行技术。,每条指令的处理过程，可以划分为取指、译码、取数、运算、送结果,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,取,=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,通道访问,.,希望存储器为多体结构，以适应多种访问源的需要。,当存储器为单体结构时，需要将访问源排队，先后顺序为：,取指令、取数据、,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,最大的段，它使流水线“流速”减慢。,S1S2S3S4,t3ttt,方法,1,：再细分,将瓶颈设备再细分为下一级流水线,S1S2aS2bS2cS3S4,tttttt,方法,2,：并行设置,将瓶颈设备重复设置多套。,衡量流水线的主要指标有吞吐率，加速比和效率。,5.4.1,吞吐率,TP,吞吐率（,TP ThroughPut,）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。,其中,k,表示流水线划分的段数。,当满足 条件时，有 。,5.4,线性流水线性能分析,S4 1 2 3 4 N-1 N,S3 1 2 3 4 N-1 N,S2 1 2 3 4 N-1 N,S1 1 2 3 4 N-1 N,时间,KT (N-1)T,NT (K-1)T,T,k,流水线产生,n,个结果所需要的时间：,实际吞吐率,：,最大吞吐率：,最大吞吐率与实际吞吐率的关系：,（,1,）流水线各段的执行时间相等,实际吞吐率：,最大吞吐率：,（,2,）流水线各段的执行时间不等,5.4.2,加速比（即吞吐率之比，）,不使用流水线所用的时间与使用流水线所用的时间之比,一般表示：,s=T,0,/T,K,其中,实际加速比：,最大加速比：,段效率：，各段平均效率：,其中 表示第,i,段设备量占整条流水线全部设备量的百分比,当满足 条件,（即,等长,、,等权,）,时，有：,5.4.3,效率（设备利用率）,上式指出，,S=Ek,，就是说当效率达到,100%,时，流水方式（一个任务,/,t,）,吞吐率,为顺序方式（一个任务,/,(kt),）的,k,倍。,实际效率：,最大效率：,瓶颈问题用两种方法改进后的效率和吞吐率,静态双功能流水线的效率与吞吐率,教材,P241,非线性流水线的吞吐率和效率,教材,P291,5.5,流水线中的相关,相关的定义：,流水线中的相关是指相邻或相近的指令因存在某种关联，后面的指令不能在原指定的时钟周期开始执行。,一般来说，流水线中的相关主要分为如下三种类型：,结构相关：当硬件资源满足不了指令重叠执行的要求，而发生资源冲突时，就发生了结构相关。,数据相关：当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就可能引起数据相关。,3.,控制相关：当流水线遇到分支指令和其它能够改变,PC,值的指令时，就会发生控制相关。,一旦流水线中出现相关，必然会给指令在流水线中的顺利执行带来许多问题，如果不能很好地解决相关问题，轻则影响流水线的性能，重则导致错误的执行结果。消除相关的基本方法是让流水线暂停执行某些指令，而继续执行其它一些指令。 在后面的讨论中，我们约定：当一条指令被暂停时，在该暂停指令之后发射的所有指令都要被暂停，而在该暂停之前发射的指令则可继续进行，在暂停期间，流水线不会取新的指令,。,5.5.1,结构相关,如果某些指令组合在流水线中重叠执行时，产生资源冲突，则称该流水线有结构相关。为了能够在流水线中顺利执行指令的所有可能组合，而不发生结构相关，通常需要采用流水化功能单元的方法或资源重复的方法。,许多流水线机器都是将数据和指令保存在同一存储器中。如果在某个时钟周期内，流水线既要完成某条指令对数据的存储器访问操作，又要完成取指令的操作，那么将会发生存储器访问冲突问题 产生结构相关。为了解决这个问题，可以让流水线完成前一条指令对数据的存储器访问时，暂停取后一条指令的操作。该周期称为流水线的一个暂停周期。暂停周期一般也称为流水线气泡，或简称为,“,气泡,”,。在流水线中插入暂停周期可以消除这种结构相关。,结构相关举例访存冲突,为,消除结构相关插入流水气泡,时空图来表示暂停情况,分析,为消除结构相关而引入的暂停将影响流水线的性能。为了避免结构相关，可以考虑采用资源重复的方法。比如，在流水线机器中设置相互独立的指令存储器和数据存储器；也可以将,Cache,分割成指令,Cache,和数据,Cache,。,假设不考虑流水线其它因素对流水线性能的影响，显然如果流水线机器没有结构相关，那么其,CPI,也较小。然而，为什么有时流水线设计者却允许结构相关的存在呢？主要有两个原因：一是为了减少硬件代价，二是为了减少功能单元的延迟。如果为了避免结构相关而将流水线中的所有功能单元完全流水化，或者设置足够的硬件资源，那么所带来的硬件代价必定很大。,5.5.2,数据相关,当指令在流水线中重叠执行时，流水线有可能改变指令读,/,写操作数的顺序，使得读,/,写操作顺序不同于它们非流水实现的顺序，这将导致数据相关。,ADD,R1,，,R2,，,R3,SUB,R4,，,R5,，,R1,AND,R6,，,R1,，,R7,OR,R8,，,R1,，,R9,XOR,R10,，,R1,，,R11,ADD,指令后的所有指令都要用到,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,之前进入流水线，由此可能带来的数据相关有：,写后读相关（,Read After Write,，,RAW,）：,j,的执行要用到,i,的计算结果，当它们在流水线中重叠执行时，,j,可能在,i,写入其计算结果之前就先行对保存该结果的寄存器进行读操作，从而得到错误的值。这是最常见的一种数据相关，采用定向技术消除的数据相关就属于这种类型。,写后写相关（,Write After Write,，,WAW,）：,j,和,i,的目的寄存器相同，当它们在流水线中重叠执行时，,j,可能在,i,写入其计算结果之前就先行对该结果寄存器进行写操作，从而导致写入顺序错误，在目的寄存器中留下的是,i,写入的值，而不是,j,写入的值。如果在流水线中不只一个段可以进行写操作，或者当流水线暂停某条指令时，允许该指令之后的指令继续前进，就可能会产生这种类型的数据相关。,读后写相关（,Write After Read,，,WAR,）：,j,可能在,i,读取某个源寄存器的内容之前就先对该寄存器进行写操作，导致,i,后来读取到的值是错误的。,需要暂停的数据相关,前面我们讨论了如何利用定向技术消除由于数据相关带来的暂停。但是，并不是所有数据相关带来的暂停都可以通过定向技术消除。,对数据相关的编译器调度方法,流水线常常会遇到许多种类型的暂停。比如，采用典型的代码生成方法对,A=B,C,这种常用的表达式进行处理，可以得到如图所示的指令序列。从图中可以看出，在,ADD,指令的流水过程中必须插入一个暂停时钟周期，以保证变量,C,的读入值有效。既然定向无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？,指令级调度,实际上，编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技术为流水线调度（,pipeline scheduling,）或指令调度（,instruction scheduling,）。,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.,延迟分支（,delayed branch,）方法,为降低流水线分支损失而采用的第四种方法就是延迟分支方法。其主要思想是从逻辑上,“,延长,”,分支指令的执行时间。延迟长度为,n,的分支指令的执行顺序是： 分支指令 顺序后继指令,1,顺序后继指令,n,如果分支成功，分支目标处指令 所有顺序后继指令都处于分支延迟槽（,branch-delay slots,）中，无论分支成功与否，流水线都会执行这些指令。,基于延迟分支方法，无论分支成功与否，其流水线时空图所描述的流水线的行为是类似的，流水线中均没有插入暂停周期，从而极大地降低了流水线分支损失。从图中可以看出，实际上是处于分支延迟槽中的指令“掩盖”了流水线原来所必需插入的暂停周期。,5.6,非线性流水线调度技术,调度问题的提出：,一个任务在通过非线性流水线时对有些功能段要通过多次（非线性定义），所以容易与紧跟而来的后继任务发生设备争用。,调度机构的作用就是合理安排前后任务进入流水线的相差时间，既要避免争用，又要使相差时间尽可能少，以提高吞吐率。,1,.,非线性流水线的表示,一条非线性流水线一般需要一个各功能段间的连接图和一张预约表共同表示。,下图是一条,4,个功能段组成的非线性流水线，它有从,S1,到,S4,的单方向传输线。但它有两条反馈线和一条前馈线；输出端不一定在最后一个功能段，而可能从任意一个功能段输出。,输出,输入,S1,S2,S3,S4,2.,非线性流水线的预约表,S4,S3,S2,S1,7,6,5,4,3,2,1,时,功能段,3.,对于非线性流水线的表示,预约表的横坐标表示流水线的时钟周期，纵坐标表示流水线的功能,段，中间有“, ”,的表示该功能段在这一个时钟周期处于工作状态，即在这个时钟周期有任务通过这个功能段；空白的表示该功能段在这一个时钟周期不处于工作状态。,预约表行数是非线性流水线的段数；而列数是一个任务从进入流水,线到从流水线中输出所经历的时钟周期数。,一张非线性流水线的预约表可能与多个非线性流水线连接图相对,应；同样，一个非线性流水线的连接图也可能对应有多张预约表。,4.,非线性流水线的冲突,非线性流水线的启动距离：向一条非线性流水线的输入端连续输入两个任务之间的时间间隔。,非线性流水线的冲突：当以某一个启动距离向一条非线性流水线连续输入任务时，可能在某一个功能段或某几个功能段中发生有几个任务同时争用同一个功能 段的情况。,5.,无冲突调度方法,目标：找出具有最小平均启动时间的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有功能段在任何时间都没有冲突。,算法：共,5,个步骤,第,1,步,.,分析预约表,R,描述非线性流水线有,2,种图形：,(a),连接图，仅给出各段之间的静态空间连接关系；,(b),预约表，就是一个任务通过流水线的时空图，能全面反映该流水线的动态特性,。,要检验2个任务相距,k,拍是否冲突，可将它们的预约表错位,k,列重叠（,如,图）。,5.6.1,不改变流水线结构的调度方法,第,2,步,.,作禁止表,F,F,是,1-N,之间可冲突拍数的集合，,N,是预约表的列数减1。,具体操作是将同一行中任意,2,个标记之间的拍数差记下来，再将各行的这类数字汇成一个集合，即为禁止表。本例中,F = 3,，,4,，,6 ,第,3,步,.,作,原始,冲突向量,C,为了设计调度机构，需将禁止表转化为原始冲突向量,C,（,Collision,）。,C,是含,N,个分量的布尔向量，一般形式为,C = (c,N,.c,1,),，其中,N,是预约表的列数减1，也可以是,禁止表中的最大元素。第,i,个分量取值原则为：,本例中,C = (101100),动态冲突向量,（初值,000000,）,右移寄存器：0 010110右移出,0,“或”运算器： 按位“或” 0接通,1,断开,常量发生器： 101100,原始冲突向量,时钟输入,流水线任务排队,1.,每个时钟脉冲使流水线中现有任务前进一步，也使右移寄存器移出一位；,2.,如果新任务进入，则用它的原始冲突向量与,右移寄存器内容相“或”。,使用,冲突向量,C,实现调度的原理图,第,4,步,.,作状态转移图,这是为了研究无穷多个任务时任务之间可能存在的合法间隔情况。从表达方便考虑，用动态冲突向量作为状态变量。,具体作图方法是：,(1),先画“根结点”，它就是第一个任务进入后的,右移寄存器状态,，数值等于原始冲突向量；,(2),分析当前结点的,各位,，如果,c,i,=0,则,发出一个旁标,i,值的箭头，,c,i,=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,时允许进入流水线。,时间,功能段,1,S1,S2,S3,S4,2,3,4,5,6,7,8,9,10,11,1,1,1,1,1,2,1,2,1,1,2,3,2,2,2,2,2,3,3,3,3,3,4,4,4,5.6.2,改变流水线结构的优化调度方法 预留算法,目的：等间隔的最小延迟调度方案,方法：插入延迟器件,第,1,步，确定,相邻任务间隔拍数：因为最小间隔拍数是一行内“,”,的最大数目（第,11,行），取最小间隔拍数。,第,2,步，确定插入延迟器件位置的原则（,P302,第,2,行,）：从第一个,“,”,开始，凡是相距,最小间隔,拍数整倍数位置的,“,”,都要向后推迟。,实例（,P301,倒数第,7,行）：,1.,确定间隔拍数（最多,3,个,“,”,，所以是,3,拍,）；,2.,插入延迟器件（使各行,“,”,的间距不为,3,的倍数,）；,3.,修改预约表（,P,302,图,5.53(a),）；,4.,写调度方案（,3,）（示意图见下页）,5.7,超标量,/,超流水,/,超长指令字技术,本节学习其它指令级并行技术。主要内容有超标量技术、超流水技术、 多操作部件技术、超长指令字技术。,下面是一些相关的名词术语,标量处理机，超标量处理机：标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；,指令级并行技术：指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；,流水线处理机，超流水线处理机：流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；,超长指令字技术,VLIW,：指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术,。,5.7.1,超标量技术,一个时钟节拍内,同时,发射多条指令,通常，把一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机。超标量处理机最基本的要求是必须有,两套或两条,以上完整的指令执行部件。上图是典型超标量处理机的指令流水线，为了能够在一个时钟周期内同时发射多条指令，超标量处理机必须有两条或两条以上能够同时工作的指令流水线。,目前，在多数超标量处理机中，每个时钟周期发射,两条指令,，通常不超过,4,条,。由于存在有数据相关和条件转移等问题，采用一般的指令调度技术，理论上的最佳情况是每个时钟周期发射,3,条指令。对大量程序的模拟统计结果也表明，每个时钟周期发射,2,至,4,条指令比较合理。例如，,Intel,公司的,i860,、,i960,、,Pentium,处理机，,Motolora,公司的,MC88110,处理机，,IBM,公司的,Power 6000,处理机等每个时钟周期都发射两条指令；美国德州仪器公司（,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 ) / ( nK + N - 1 ),1.,超标量超流水线处理机,超标量超流水线处理机在一个时钟周期内要发射指令,n,次，每次发射指令,m,条，因此，超标量超流水线处理机每个时钟周期总共要发射指令,mn,条。,在下图中，每一个时钟周期分为,3,个流水线周期，每一个流水线周期发射,3,条指令。从图中可以看出，每个时钟周期能够发射并执行完成,9,条指令。因此，在理想情况下，超标量超流水线处理机执行程序的速度应该是超标量处理机和超流水线处理机执行程序速度的乘积。,5.7.3,超标量超流水技术,2.,超标量超流水线处理机的性能,（,1,）性能,在一台指令级并行度为（,m,，,n,）的超标量超流水线处理机上，连续执行,N,条没有资源冲突、没有数据相关和控制相关的指令所需要的时间为：,其中，,k,是指令流水线的时钟周期数，而不是流水线级数。,t,是一个时钟周期的时间长度。上式中的第一项是开始,m,条指令通过指令流水线所需要的时间，第二项是执行其余,N - m,条指令所需要的时间；这时，每一个时钟周期平均执行完成,mn,条指令，也就是每一个流水线周期平均执行完成,n,条指令。,（,2,）性能比较,（,3,）结论：,超标量处理机的相对性能最高，其次是超标量超流水线处理机，超流水线处理机的相对性能最低，主要原因如下：,超标量处理机在每个时钟周期的一开始就同时发射多条指令，而超流水线处理机则要把一个时钟周期平均分成多个流水线周期，每个流水线周期发射一条指令。因此，超流水线处理机的启动延迟比超标量处理机大。,条件转移造成的损失，超流水线处理机要比超标量处理机大。,在指令执行过程中的每一个功能段，超标量处理机都重复设置有多个相同的指令执行部件，而超流水线处理机只是把同一个指令执行部件分解为多个流水级。,因此，超标量处理机指令执行部件的冲突要比超流水线处理机小。,当横坐标给出的设计指令级并行度比较低时，处理机实际指令级并行度的提高比较快。但是，当设计指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。因此，在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当；否则，有可能造成花费了大量的硬件，但实际上处理机所能达到的指令级并行度并不高。目前，一般认为,m,和,n,都不要超过,4,。,一个特定程序由于受到本身的数据相关和控制相关的限制，它的指令级并行度的最大值是确定的。这个最大值主要由程序自身的语义来决定，与这个程序运行在那一种处理机上无关。因此，上图中的三条曲线，对于某一个特定的程序，最终都要收拢到同一个点上。当然，对于各个不同程序，这个收拢点的位置也是不同的。,一个程序能够达到的实际指令级并行度还与所采用的调度算法有关。目前，国际上已经提出了多种开发指令级并行性的优化调度算法。对于没有条件转移操作，没有输入输出，没有程序调用和程序中断，单入口单出口的基本块程序，实现最优调度并不十分困难。但是，对于一般程序，要充分开发程序中的指令级并行性，实现最优调度非常复杂，已经证明，这是一个,NP,完全问题。,另外，实现最优调度所需要的代价很大，包括硬件代价和软件代价，通常需要编译器和硬件的结合才能获得比较好的调度效果。目前，开发程序指令级并行性的许多优化调度算法及编译技术还在进一步研究中。,5.7.4,超长指令字（,VLIW,）技术,把多条无相关关系的常规指令储存在一个超长的指令字中，让它们同时被处理，分别控制多个功能部件并行工作的技术。,这种技术的实质，是把超标量技术中的相关性识别任务，由,CPU,硬件转移给程序员或编译程序去实现。,5.7.5,超线程技术,“,Hyper-Threading Technology,（超线程技术，以下简称,HTT,技术）,”,。,对于计算机微处理器而言，程序只是一组编译过的机器代码，可以执行相关的数据计算与操作，这些代码由一条条的指令组成，每一个代码组就是一条线程。,单,CPU,系统中，在执行指令的时候，,CPU,先找出相应指令所在的内存位置，执行下一条指令，再转换到另一个位置，在同一时间内,CPU,只能对应一个指令。线程可以中断，并把中间结果暂存在另一个特殊位置（堆栈），不同的线程可以交叉运行，实现多任务，但每次运行的线程仍然仅有一条，千万不要把多任务和多线程混淆了。,既然一个,CPU,是单线程，那么两个,CPU,自然就可以双线程啦，如此类推，就会出现四路、八路系统。但双处理器系统的性能并不能达到单处理器的两倍，通常只有,33%,的性能增益,。,为了提高,CPU,的性能，厂商通常采用增加工作频率和缓存容量的方法来提升速度，但这是治标不治本的方法，,CPU,只提高了速度，其内在潜力依然未能完全发挥，,CPU,的执行单元没有被充分利用，于是设计者就在,CPU,中加入两个逻辑处理单元，同时管理,CPU,的全部资源，直接提高,CPU,内核的工作效率。,简而言之：超线程技术就是利用特殊的硬件指令，把两个逻辑内核模拟成两个物理芯片，让单个处理器都能使用线程级并行计算。从而兼容多线程操作系统和软件，提高处理器的性能。,操作系统或者应用软件的多线程可以同时运行于一个,HTT,处理器上，两个逻辑处理器共享一组处理器执行单元，并行完成加、乘、负载等操作。这样就可以使得运行性能提高,30%,，这是因为在同一时间里，应用程序可以使用芯片的不同部分。,虽然单线程芯片每秒钟能够处理成千上万条指令，但是在任一时刻只能够对一条指令进行操作。而,“,超线程,”,技术可以使芯片同时进行多线程处理，使芯片性能得到提升。,例如：,Office,等商业软件主要使用整数运算单元和读写,/,存储单元，几乎不涉及浮点运算单元，,3D,渲染软件主要使用浮点运算单元，很少涉及整数运算单元，很明显，这种设计造成了很大的浪费。如,P4,处理器内部有,7,个执行单元，每个时钟周期内，约有,2,个执行单元工作，它们共执行两次操作，那么，其它,5,个单元完全没有用到。,超线程技术对商用和家用电脑而言，除了全面提升系统性能以外，还增加系统平台所能支持用户的数量，大幅降低系统的反应潜伏时间（因为任务能被分为几个隔离的线程来同时执行），增加系统的指令执行数量，还有一点很关键的是，即使对于现有的,IA-32,体系软件它也能很好地兼容。因为，,HTT,处理器还提供一个中断指令，在执行适合单处理器的任务时，暂停其中一个逻辑内核，让操作系统识别为单处理器，在执行适合多处理器的任务时，重新打开逻辑内核，利用,HTT,来增加整体效率。,支持超线程技术需软硬件的支持，硬件方面需要主板北桥芯片的支持。,超线程技术还需要主板对,CPU,的电源支持，需要主板能提供给处理器高达,70A,的电流，否则系统可能不能长期稳定工作。除此之处还需要主板,BIOS,的支持，需要,BIOS,加入特定的支持,HTT,处理器的代码。当,BIOS,检测到是超线程处理器时，在,BIOS,设置菜单中出现,CPU Hyper-Threading,（,Enabled or Disabled,）的选项,超线程技术还需要操作系统的支持。目前支持超线程技术的有,Windows XP,和,Linux 2.4.X,。这不同于传统的处理器安装的,Windows XP,，使用超线程技术的处理器安装完,Windows XP,后在设备管理器中能显示有两个处理器和,ACPI Multiprocessor PC,。,