计算机系统结构课件详解

计算机系统结构课件详解演示文稿第1页，共138页。优选计算机系统结构课件第2页，共138页。5.1重叠解释方式5.1.1基本思想和一次重叠图5.1对一条机器指令的解释取指令分析执行t第3页，共138页。取指令:按指令计数器的内容访问主存,取出该指令送指令寄存器.指令的分析:对指令的操作码进行译码,按寻址方式和地址字段形成操作数物理地址,并取出操作数,形成下一条指令的地址.指令的执行:对操作数进行运算,处理,或存储运算结果(可能要访问主存)第4页，共138页。当有多条指令要在处理机中执行时,可以采用多种执行方式:1.顺序执行方式若各阶段执行时间相等，则共需3n

t优点：控制简单；缺点：速度慢，机器各部件的利用率很低。第5页，共138页。2.重叠执行方式:取第k+1条指令与分析第k条指令同时进行,分析第k+1条指令与执行第k条指令同时进行.如果执行一条指令的三过程的时间相等,则T=(2+n)t为了能够实现理想的指令重叠执行方式,处理机的结构要作比较大的改变,必须采用先行控制方式.要使指令能够正确地重叠执行,必须解决如下两个问题:1.独立的取指令部件,指令分析部件和指令执行部件集中的指令控制器分解:存储控制器指令控制器运算控制器2.要解决访问主存的冲突问题第6页，共138页。1)把主存分成两个独立编址的存储器指存和数存解决了取指令和读操作数的冲突运算结果只写通用寄存器,不写主存.2)低位交叉存取方式3)解决访问存储器冲突的根本方法是采用先行控制技术.先行控制技术的关键是缓冲技术和预处理技术.缓冲技术:在工作速度不固定的两个功能部件之间设置缓冲栈先行指令缓冲栈先行操作栈先行读数栈后行写数栈第7页，共138页。预处理技术:把进入运算器的指令都处理成RR型指令.可大幅度提高指令的执行速度.第8页，共138页。图5.2指令的顺序解释与重叠解释第9页，共138页。图5.3一次重叠工作方式如果指令分析器每次取指令都能在先行指令缓冲栈中得到,则取指令只需要很短的时间.把取指令和分析指令指令合并.第10页，共138页。实现分析k+1和执行k的一次重叠,待解决的问题:分析和执行所时间差很大如果分析k+1所要读取的操作数正好数执行k的结果,那它们不能重叠执行------数据相关,另外还有控制相关,指令相关等.当出现转移或转子程序指令时,程序的执行过程就不是顺序的,在先行指令缓冲栈中预取的指令和已经分析完成的下一条指令等都可能要作废.第11页，共138页。图5.4当第k条指令是条件转移时第12页，共138页。例一、数据相关。第K+1条指令的源操作数正好是第K条指令结果地址，顺序解释没问题，而重叠解释时，在“执行K”和“分析K+1”重叠时就出现问题相关：因程序相邻指令之间出现了关联，为防止出错他们不能同时解释。这种现象称发生了”相关“，有数据相关和指令相关。指令相关。指令相关是因为机器指令允许修改引起的。第13页，共138页。如果采用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条指令都有可能发生指令相关。指缓容量越大，或者说指令预处理能力愈强的机器发生指令相关的概率就愈高。第14页，共138页。5.1.2相关处理1.指令相关的处理要判断是否发生了指令相关,要把每一条指令的执行结果地址与先行操作栈中,指令分析器和先行指令缓冲栈中的所有指令地址进行比较.如果发现相关,则在修改主存相关单元的同时,也要修改先行操作栈或指令分析器或先行指令缓冲栈中的相关指令.解决指令相关的根本办法:在程序设计中不允许修改指令.第15页，共138页。IBM370机器中,有一条”执行”指令能够解决指令相关,又允许在程序执行过程中修改指令.

“执行”指令是IBM370机器为此设置的一条指令，其形式为执行R1X2B2D2当执行到“执行”指令时，按第二操作数(X2)+(B2)+D2地址取出操作数区中单元的内容作为指令来执行，参见图5.5。第16页，共138页。图5.5IBM370“执行”指令的执行第17页，共138页。2.主存空间数相关的处理相邻两条指令之间出现要求对主存同一单元先写入而后再读出的关联.在大多数处理机中,运算结果一般都写入通用寄存器,而不写入主存.主存操作数相关出现的概率比较小.解决办法:推后处理法.在设置有存储控制器的处理机中,把”写结果”的优先级安排得高于”读操作数”的优先级.由于存控响应访问请求是定时进行的,它在一个周期的最末尾处对这一个周期这的所有访问源进行排队.第18页，共138页。图5.6主存数相关的处理第19页，共138页。3.通用寄存器组相关的处理

通用寄存器存放操作数,也存放变址,基址.存放在通用寄存器中的基址或变址一般总是在”分析”周期的前半段就要取出;而操作数则是在”分析”周期的末尾的后半段取出,到”执行”周期的前半段才真正用上;运算结果在”执行”周期的末尾才形成,并送入通用寄存器.通用寄存器数相关的情况和处理办法第20页，共138页。设机器的基本指令格式为操作码L1L3B2d2或操作码L1L3L2第21页，共138页。图5.7指令解释过程中与通用寄存器内容有关的微操作时间关系第22页，共138页。图5.8“执行k”、“分析k+1”重叠时，访问通用寄存器组的时间关系第23页，共138页。解决办法:1)分析周期推后一个周期执行.顺序串行实现简单运算速度的损失较大2)分析指令仅仅推后一个节拍3)设置专用数据通路.第24页，共138页。图5.9用相关专用通路解决通用寄存器组的数相关第25页，共138页。变址相关因为计算有效地址是在指令分析的一开始进行的,因此,变址相关造成的后果要比数相关更为严重.第26页，共138页。设操作数的有效地址由分析器内的地址加法器形成。由于通常情况下，“分析”周期等于主存周期，所以，从时间关系上要求在“分析”周期的前半段，就能由通用寄存器输出总线取得(B2)，送入地址加法器。由于运算结果是在“执行”周期的末尾才送入通用寄存器组的，它当然不能立即出现在通用寄存器输出总线上。也就是说，在“执行k”得到的、送入通用寄存器的运算结果来不及作为“分析k+2”的基址值用，更不用说作为“分析k+1”的基址值用。因此，虽然是一次重叠，但基址值相关(B相关)就不止会出现一次相关，还会出现二次相关。即当出现B(k+1)=L3(k)时，称为发生了B一次相关；而当出现B(k+2)=L3(k)时，称为发生了B二次相关，如图5.10所示。第27页，共138页。解决变址相关的办法:推后分析和设置相关专用通路推后分析法对于二次变址相关,“分析k+2”推后1周期(1节拍)一“分析k+1”2(1周期+1节拍)变址相关专用通路运算结果送入通用寄存器的同时,直接送到地址加法器中.第28页，共138页。图5.10B一次相关与二次相关第29页，共138页。图5.11B一次、二次相关的推后处理第30页，共138页。图5.12B相关专用通路法第31页，共138页。5.2流水方式5.2.1基本概念流水是重叠的引申：一次重叠：把一条指令的解释分为两个子过程，同时解释两条指令。流水：把一条指令的解释分为多个子过程，同时解释多条指令。第32页，共138页。取指访存执行译码写回IFIDEXMEMWBS1S2S3S4S5输入输出指令的流水处理第33页，共138页。S1S2Sk输入输出流水线的基本结构.….…..时钟第34页，共138页。...12345......n-1n...12345......n-1n...12345......n-1n...12345......n-1n1234△t0△t0

△t0△t0T0=m△t0n△t0T(m-1)△t0(n-1)△t0填入正常排空流水时空图空间时间第35页，共138页。2、流水线特点：1）流水一定重叠，比重叠更苛刻。2）一条流水线通常有多个流水段组成。3）每段有专用功能部件，各部件顺序连接，不断流。4）流水线有建立时间、满载时间、排空时间，5）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。6）给出指标如最大吞吐率，为满负载最佳指标。建立时间：在流水线开始时有一段流水线填入时间，使得流水线填满。正常流动时间：流水线正常工作，各功能段源源不断满载工作。排空时间：在流水线第一条指令结束时，其他指令还需要一段释放时间。第36页，共138页。分级：（处理的级别分类）部件级流水：构成部件内的各个子件之间的流水，如运算器内的“浮点加”流处理机级流水：构成处理机的各部件间的流水，如取指，分析，执行的流水。系统级流水：构成计算机系统的多个处理机间的流水。2.流水线的分类第37页，共138页。其他分类：功能：单功能流水线（如CRAY-1）、多功能流水线（如TI-ASC）工作方式：静态流水线、动态流水线连接方式：线性、非线性处理数据：标量流水、向量流水1234出入非线性流水线第38页，共138页。图5.15处理机间的流水处理第39页，共138页。单功能流水线:只能实现一种功能的流水处理.多功能流水线:同一流水线的各个段之间可以有多种不同的连接方式以实现多种不同的运算或功能.第40页，共138页。图5.16ASC机运算器的流水线第41页，共138页。按多功能流水线的各段是否允许同时用于多种不同功能连接流水,流水线分为静态流水线和动态流水线静态流水线:在某个时间内各段只能按一种功能连接流水,只有等流水线全部流空后才能切换成按另一种功能来连接.就指令级流水而言,仅当进入的是一串相同运算的指令时,才能发挥出静态流水线的效能.动态流水线:各功能段在同一时间内可按不同的运算或功能连接.第42页，共138页。图5.17静、动态多功能流水线时-空图举例第43页，共138页。第44页，共138页。以机器所具有的数据表示分类标量流水处理机:没有向量数据表示,只能用标量循环方式对向量,数组进行处理.向量流水处理机:机器具有向量数据表示,设置有向量指令和向量运算硬件,能对向量,数组中的各元素流水地处理.是向量数据表示和流水技术的结合.

第45页，共138页。从流水线中各功能段之间是否有反馈回路来分类线性流水非线性流水第46页，共138页。图5.18非线性流水线举例第47页，共138页。5.2.2流水线处理机的主要性能衡量流水线性能的主要指标吞吐率加速比效率第48页，共138页。吞吐率吞吐率是流水线单位时间里能流出的任务数或结果数。在图5.14的流水线例子中，各个子过程经过的时间都是Δt2，满负荷后，流水线每隔Δt2解释完一条指令，其最大吞吐率TPmax为1/Δt2。实际上，各个子过程进行的工作不相同，所经过的时间也就不一定相同，所以前述在子过程间设置了接口锁存器，让各锁存器都受同一时钟脉冲同步。时钟脉冲周期直接影响流水线的最大吞吐率，总希望它越小越好。如果各个子过程所需的时间分别为Δt1、Δt2、Δt3、Δt4，时钟周期应当为max｛Δt1,Δt2,Δt3,Δt4｝，即流水线的最大吞吐率第49页，共138页。它受限于流水线中最慢子过程所需要的时间。称流水线中经过时间最长的子过程为瓶颈子过程。第50页，共138页。图5.19最大吞吐率取决于瓶颈段的时间第51页，共138页。图5.20瓶颈子过程再细分第52页，共138页。图5.21瓶颈子过程并联第53页，共138页。设一m段流水线的各段经过时间均为Δt0，则第1条指令从流入到流出需要T0=mΔt0的流水建立时间，之后每隔Δt0就可以流出一条指令，其时—空图如图5.22所示(这里设m=4)。这样，完成n个任务的解释共需时间T=m·Δt0+(n-1)Δt0。在这段时间里，流水线的实际吞吐率第54页，共138页。图5.22从时—空图分析实际的吞吐率第55页，共138页。不仅实际的吞吐率总是小于最大的吞吐率，而且只有当n>>m时，才能使实际的吞吐率接近于理想的最大吞吐率。加速比(SpeedupRatio,Sp):表示流水线方式相对非流水线顺序串行方式速度提高的比值.非流水线顺序串行方式工作，连续完成n个任务需要n·m·Δt0的时间.流水线方式工作的加速比第56页，共138页。如果线性流水线各段经过的时间Δti不等，其中瓶颈段的时间为Δtj，则完成n个任务所能达到的实际吞吐率其加速比第57页，共138页。

2.效率

流水线的效率是指流水线中的设备实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。由于流水线存在有建立时间和排空时间(最后一个任务流入到流出的时间)，在连续完成n个任务的时间里，各段并不总是满负荷工作的。如果是线性流水线，且各段经过时间相同，如图5.22那样，则在T时间里，流水线各段的效率都相同，均为η0，即整个流水线的效率第58页，共138页。式中，分母m·T是时—空图中m个段和流水总时间T所围成的总面积，分子m·nΔt0则是时—空图中n个任务实际占用的总面积。因此，从时—空图上看，效率实际上就是n个任务占用的时—空区面积和m个段总的时—空区面积之比。显然，与吞吐率类似，只有当n>>m时，η才趋近于1。同时还可看出，对于线性流水且每段经过时间相等时，流水线的效率是正比于吞吐率的，即第59页，共138页。如果流水线各段经过的时间不等，各段的效率就会不等，但是，参照图5.22，不难得出整个流水线的效率第60页，共138页。其中，分母为m个段的总的加权时—空区，分子为n个任务总的加权时—空区。当时，有第61页，共138页。对于复杂的非线性流水线，实际的吞吐率TP和效率η需要通过画出实际工作时的时—空图，才能分别用下列两个式子求得：第62页，共138页。图5.23流水线工作举例3.流水线工作举例第63页，共138页。TP=7/(15△t)顺序方式时间：4*3△t+3*4△t=24△t加速比：Sp=24△t/15△t=1.6效率（用面积比方法）：

η=（3*4△t+4*3△t）/(5*15△t)=32%第64页，共138页。3实例分析:性能分析（实测法,分析法,时空图法）.例1.四段流水线,△t1=△t3=△t4=△t,△t2=3△t,4个任务、10个任务时TP，η、SP。η=N个任务实际占用的时-空区M各段总的时-空区n=10，η=6*10△t4*6△t+9*3*4△t=6024+108=115TP=106*△t+3*9*△t

=1033*△t

≈45%

（1）分析法:各段时间不等=Sp=n*Σ△timi=1Σ△ti+(N-1)*△tjmI=110*6△t(6+3*9)△t=2011=1.8TP=nΣ△ti+(n-1)△tjmi=1第65页，共138页。时间12343111223234123123123444443△t3△t空间(2)时空图法:Tp=4/((6+3*3)△t)=4/(15△t)=0.267(1/△t)

=24△t

/(4*15△t)=2/5=40%Sp=4*6△t

/15△t=8/5=1.6n=4时;n=10时;同上.第66页，共138页。例2.以浮点加法运算为例（四段流水线）各段时间相等，如何求吞吐率、效率。求Z=A+B+C+D+E+F+G+H，TP、η、Sp注意有相关时间空间Z=A+B+C+D+E+F+G+H1234567TP=7/15△t,η=7*4/(15*4)=7/15解：Sp=4*7/15=28/15=1.871111222233334444555566667777第67页，共138页。例3.ASC计算机功能算术运算流水线各段时间相等，6次浮点加、5次定点乘的吞吐率,效率,加速比M=8,N=11.分析：T加=6+(6-1)*1=11(△t)T乘=4+(5-1)*1=8(△t)则TP=11/(11+8)△t=11/19△tSp=56△t/19△t=2.94η=(6*6+5*4)△t/(19*8△t)=6/52=7/1912345612345612345612345612345867123456123456时间浮加定点乘一二三四五一二三四五一二三四五一二三四五第68页，共138页。5.2.3流水机器的相关处理和控制机构要使流水线充分发挥效率,不发生或少发生断流,需要硬件和软件两方面的共同努力.软件方面:编译器生成的目标程序要能够适合流水线结构,要尽量把有数据相关和控制相关的指令安排得相隔远一些,把相同的操作尽量安排在一起.硬件方面:要解决存储系统的频带平衡问题,能够为流水线提供足够的指令和数据.另外,要处理好流水线的局部相关和全局相关.第69页，共138页。流水机器的全局性相关指的是转移指令与其后指令之间的相关联,不仅不能同时解释,还会使指令缓冲器所预取的指令要全部作废,重新花较长的时间再去访存取出指令.流水机器的局部性相关：指令相关,主存数相关,通用寄存器组的数相关,基(变)址相关等对流水性能下降的影响要严重得多.(只影响到相关的指令在某些功能段上停等一段时间,不会影响到流水线需要等待,去重新访存指令任务在流水线中流动顺序的安排和控制方式:同步流动方式(顺序流动方式):让任务(指令)流出流水线的顺序保持与流入的顺序一致.异步流动方式(乱序):让流出流水线的任务顺序可以和流入流水线的顺序不同.第70页，共138页。局部性数据相关例：有i和j两条指令，i指令在前，j指令在后，则三种不同类型的数据相关的含义为：RAW读写(先写后读)-指令j试图在指令i写入寄存器前就读出该寄存器内容，这样，指令j就会错误地读出该寄存器旧的内容。（改用相关）i:R1+R2->R3j:R3*R4->R5WAR写读(先读后写)-指令j试图在指令i读出寄存器之前就写入该寄存器，这样，指令i就错误地读得该寄存器新的内容。（用改相关）i:R3*R4->R5j:R1+R2->R3WAW写写(先写后写)-指令j试图在指令i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令i写入的值成为该寄存器内容。（改改相关）i:R1*R2->R3j:R4+R5->R3顺序流动不按顺序流动不按顺序流动第71页，共138页。解决办法主要用软件和硬件技术：时间推后法旁路技术或相关专用通路技术第72页，共138页。图5.24顺序流动和异步流动第73页，共138页。对IBM360/91机是通过给FLR设置一个“忙”标志来判别指令间所用的数据是否发生相关,另外还有一个标志（即站号）表示数据由何处来，用站号位控制相关通路连接，采用公共数据总线CDB来实现内部数据专用通路的连接。IBM360/91的浮点运算器部分包括了以下主要部件：（1）

运算部件：一个加法部件和一个乘除部件。（2）保存站：加法部件中有A1~A3三个保存站，乘除部件有M1和M2两个保存站，用来保存当前参加运算的数据。（3）

指令操作缓冲栈：存放经分析后由指令部件送来的指令，译码后，产生相应的控制信号送到各个部件。（4）浮点操作数寄存器（FLB）：存放由主存预取来的操作数。（5）浮点寄存器（FLR）：存放操作数的寄存器。（6）

存储数据缓冲站（SDB）：存放将写入存储器的结果数据，也有站号。（7）

公共数据总线（CDB）：以上各部件间的连接总线。第74页，共138页。图5.25IBM360/91的浮点执行部件结构框图Tomasulo算法第75页，共138页。浮点操作站FLOS(FloatingPointOperandStack)缓冲的浮点操作命令的格式为操作源1(目的)，源2操作可以是浮点加、减、乘、除。源1指明存放源操作数的浮点寄存器FLR的号，并兼作存放中间结果的目的寄存器的号。源2指明存放经存贮器总线送来的浮点操作数的缓冲器FLB的号。它们分别经FLR总线和FLB总线将数据送入浮点加法流水线或浮点乘/除法流水线输入端的保存站。浮点加法器流水线的输入端设有3个保存站A1至A3，浮点乘/除法器流水线的输入端设有两个保存站M1和M2，分别用规定的站号标记。保存站由控制部分控制，只要任意一个保存站的两个源操作数都到齐，且流水段空闲时就可以进入流水线向前流动，因此是采用异步流动方式工作的。第76页，共138页。由于操作命令中源1兼作目的，因此同时进入两条流水线的操作命令之间发生操作数相关的概率是较高的。设k+i表示k之后同时在两条流水线流动的第i条指令，则只要k+i的源1与k的目的一样，就会发生“先写后读”相关，k+i的目的与k的目的一样，就会发生“写—写”相关，k+i的目的与k的源1一样，就会发生“先读后写”相关。也就是说，只要同时进入流水线的各个操作命令中使用了同一个浮点寄存器FLR的号就会发生相关。第77页，共138页。现在，以FLOS依次送出ADDF2,FLB1;(F2)+(FLB1)→F2MDF2,FLB2;(F2)*(FLB2)→F2两条操作命令为例，来说明是怎样判出发生相关以及怎样控制推后和相关直接通路的联接的。很明显，这两条命令异步流动时，“先写后读”、“写—写”、“先读后写”三种相关都会发生。当FLOS送出ADDF2,FLB1第78页，共138页。操作命令时，它控制由FLR取得(F2)，由FLB取得(FLB1)送往加法器保存站，例如送往A1，同时立即将F2的“忙位”置“１”，以指明该寄存器的内容已送往保存站等待运算，这样F2的内容再不能被其他操作命令作源操作数读出用。由于F2这时已成为“目的”寄存器，准备接收由加法器来的运算结果，因此将F2的“站号”字段置成是A1的站号“1010”，以便控制把站号为1010的保存站A1在加法流水线流出的运算结果经CDB总线送回F2。一旦结果送回后，立即将F2的“忙位”和“站号”都置成“０”，以释放出F2为别的操作命令使用。第79页，共138页。问题在于，当F2的“忙位”为“１”，而加法结果并未流出加法流水线时，FLOS又送出操作命令MDF2,FLB2由译码控制去访问F2取源1操作数时，由于其“忙位”为“１”，表明出现了F2相关，此时就不能直接将(F2)送往乘法器保存站，而改成为把原存在F2的“站号”字段中的站号A1(即1010，指明F2应有内容的来源)送往M1的“源1站号”，并把F2内的站号由A1(1010)改为M1(1000)以指明应改为从M1接收运算结果。第80页，共138页。特点：（1）由于为加法器和乘法部件分别设置了3个和2个保存站，从而减小了资源使用冲突的机会。仅当这些保存站读都处于忙碌状态时，才有可能发生资源使用冲突。（2）调度算法使用保存站，通过对寄存器重新命名（改写站号）自然地消除了WAR和WAW数据相关可能性。（3）通过对FLR寄存器忙位状态的判别，来检测是否存在RAW数据相关。（4）借助CDB公共数据总线作为专用相关通路，将有关数据直接送往所有需要它的功能部件，而不必先写入寄存器，然后再从此寄存器读出。第81页，共138页。2.全局性相关(控制相关)由条件转移或程序中断引起的相关-----全局相关关键问题:1)确保流水线能够正常工作2)减少因断流引起的吞吐率和效率的下降一般情况下要在转移指令执行到流水线的最后功能段时,转移条件才能建立.因此,在条件转移指令进入流水线之后,到形成转移条件之前,后续指令不能进入流水线.

第82页，共138页。1)猜测法图5.26用猜测法处理条件转移第83页，共138页。采用猜测法时,应能保证猜错时可恢复分支点处原先的现场.方法:只进行指令译码和准备好运算所需要的操作数,在转移条件没有形成之前不执行运算一直执行到运算完成,但不送回结果.把可能被破坏的原始状态都用后援寄存器保存起来.第84页，共138页。2)加快和提前形成条件码:有的指令的条件码并不一定要等执行完毕得到运算结果后才能形成；3)采取延迟转移:

a.将转移指令前的那条指令调度到延迟槽中；b.将转移目标处的那条指令调度到延迟槽中；c.将转移不发生时该执行的那条指令调度到延迟槽中。4)设置特殊循环指令，加快短循环处理:第85页，共138页。

3.流水机器的中断处理中断会引起流水线断流。然而，其出现概率比条件转移的概率要低得多，且又是随机发生的。所以，流水机器处理中断主要是如何处理好断点现场的保存和恢复，而不是如何缩短流水线的断流时间。

第86页，共138页。不精确断点法(同外部设备中断处理一样)：不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入

精确断点法：不论第i条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第i条的，在第i条之后进入流水线的指令的原有现场都能恢复(增加设备，加许多缓冲器，各功能段状态保留）第87页，共138页。4.流水线调度

非线性流水线：由于段间有前馈和反馈通路任务，执行过程中可能会多次通过同一流水段，发生几个任务同时争用同一流水段的现象，这就是功能段的使用冲突。流水线调度常借助于二维预约表和状态转换图来进行分析根据预约表可较容易地推算出一个任务执行时，各段所需的间隔周期拍数。解决方法：间隔恰当的拍数后再向流水线送入下一个任务。这就需要对流水线作适当的调度。第88页，共138页。S/t1234567891XX2XXX3X4XX5XX二维预约表图中每一行代表P的一个段，每一列表示相应的时钟周期。若某个任务在周期ti需要使用Sj段进行处理，则在行Sj和列ti的相交处以“

”表示。条件：非线性、单功能流水线P，由K段组成，每个任务流过流水线需N个时钟周期（t1,t2,…,tn），段为纵坐标，时间为横坐标禁止表F={1，5，6，8}第89页，共138页。1011000110110111101111011011111110111011一个n位的位向量C=(Cn、Cn-1、...、C2、C1)称为冲突向量。其中第i位状态表示于当时相隔i拍时间时，是否允许输入新任务。如允许输入，则Ci=0,否则Ci=1。非线性流水线预约表相应状态图42>=7>=734>=7>=7>=7原始冲突向量23第90页，共138页。过程:1.按给出的预约表写出允许表和禁止表F={1，5，6，8}；2.写出n位初始冲突向量（10110001）；3.按禁止表约束条件列出新的冲突向量，直到不再生成新的冲突向量为止（当前冲突向量和初始冲突向量按位“或”）；4.画出用冲突向量表示的流水线状态转移图（两个冲突向量之间用有向弧连接，并用数字表示引入后继任务用的间隔节拍，写出各种可能的状态转换）；5.列出各种调度方法平均间隔拍数；6.求出最佳等间隔和非等间隔调度拍数；本例子中非等间隔调度为3拍，4拍…….平均间隔为3.5拍，而等间隔调度为7拍。第91页，共138页。图5.27流水线预约表及状态图举例第92页，共138页。表5.1各种调度方案的平均间隔拍数的例子第93页，共138页。调度方案：间隔拍数周期性重复（只有重复才能循环）最佳策略：平均间隔拍数最少（吞吐率，效率高）吞吐率TP=任务数M/总时间T调度方案产生办法：1）从初始状态出发，沿箭头方向，每走一个闭环，即为一个方案2）若中间遇到小闭环，每个小闭环也可作为一个方案3）遍历初始状态中的每一个Ci=0的回路。第94页，共138页。状态转移图的生成方法：1）从初始冲突向量出发，对每一个ci=0产生一个新的冲突向量2）箭头由原冲突向量指向新的冲突向量，线弧上写上i,表示间隔i拍送入流水线产生冲突向量。3）对新的冲突向量中的ci=0重复进行1)2)4)图中全部ci=0的位全有目标冲突向量。第95页，共138页。图5.28多功能流水线预约表及状态图举例第96页，共138页。使用交叉冲突向量(CrosscollisionVector)来反映有A、B两种功能的动态流水线各个后继任务流入流水线所禁止使用的间隔拍数。这样，对于本例就应有4个交叉冲突向量，即VAB=(1011)，VBA=(1010),VAA=(0110),VBB=(0110)。其中，VAA和VBB分别表示同按A功能和B功能流水时，后继任务流入流水线的冲突向量；而VAB表示先前按B功能流水流入的任务与后继按A功能流水流入的任务之间的冲突向量，VBA则表示先前按A功能流水流入的任务与后继按B功能流水流入的任务之间的冲突向量。第97页，共138页。就一般情况而言，一个有P个功能的流水线将有P2个交叉冲突向量，它们可以分别归类写成P个冲突矩阵Mp，其中p分别为1至P。冲突矩阵Mp表示按p功能流水线进入一个任务后与按各种功能流水线流入后继任务所产生的全部冲突向量的集合。对本例来说有两个初始冲突矩阵，分别为第98页，共138页。例如，按A功能刚流入一个任务后，根据VAA的(0110)，知道可隔1拍或4拍流入一个A功能的新任务。将MA初始冲突矩阵各行同时右移1位，再与A功能的初始冲突矩阵MA对应行按位“或”，形成新的冲突矩阵。根据此时VAA的(0111)，知道只有隔4拍流入一个A功能的新任务才能不发生冲突，从而形成在此基础上的新的冲突矩阵。第99页，共138页。再如，根据初始冲突矩阵中的VBA为(1010)，知道可在第一拍或第三拍进行B功能的新任务的送入而不发生冲突。于是将MA初始冲突矩阵均右移1位或3位，再与MA的初始冲突矩阵对应行按位“或”，形成新的冲突矩阵，它们恰好都为。据此可知，或者是隔3拍流入A功能的新任务，或者是隔4拍流入B功能的新任务，又将分别产生不同的新的冲突矩阵。第100页，共138页。5.3向量的流水处理与向量流水处理机5.3.1向量的流水处理向量中的各个元素在运算时很少相关,而且都是进行相同的运算或处理,相比标量运算,应当更能发挥出流水线的效能.选择对向量,数组如何处理,才能最充分地发挥出流水线的效能,是向量流水处理要解决的问题.是与所要解的具体题目及计算机的结构密切相关的.第101页，共138页。例如：向量计算：A*(B+C)的

循环程序用C语言为for(i=1;i<=n;i++)di=ai*(bi+ci)水平处理法(横向)d1=a1*(b1+c1)d2=a2*(b2+c2)

·

·dn=an*(bn+cn)垂直处理法（纵向）B+C

E(1到n)A*E

D(1到n)向量处理方式适合于流水处理分组纵横处理法分成k组,每组长度为m，组内垂直处理，组间水平处理。n=k*m+r(r为第k+1组剩余分量)Bi+Ci

Ei(1到m)Bi+Ci

Ei(m+1到2m)Ei*Ai

Di(1到m)Ei*Ai

Di(m+1到2m)……第102页，共138页。向量处理机的结构存储器——存储器结构参加运算的向量数据在存储器中，运算的结果也送到存储器中，其结构与数据流的示意图如下图所示。如果以向量加法为例子C=A+B存储器ABC流水线运算部件一种能实现两个向量相加的流水结构的加法器第103页，共138页。AB1234C=A+B加法流水线部件M1M2M3M4M5M6M7M8多模块存储器系统的向量处理机A、B、C的向量长度为8，加法流水线分为4个功能段，主存储器采取了8个存储体第104页，共138页。寄存器——寄存器型（如CRAY_1机）主存储器8个向量寄存器组8个标量寄存器8个地址寄存器256个指令缓冲寄存器整数加3位移4逻辑2向量部件浮点部件浮点加6浮点乘7浮点倒数14整数加3整数乘6地址运算部件整数加3逻辑1位移2-3计数3-4标量部件Cray_1向量计算机结构第105页，共138页。5.3.2向量流水处理机1.向量处理机的指令系统

向量处理机的指令系统一般应包含有向量型和标量型两类指令。向量型运算类指令一般又可以有如下几种：向量V1运算得向量V2，如V2=SIN(V1)；向量V运算得标量S，如 ；向量V1与向量V2运算得向量V3，如V3=V1∧V2；向量V1与标量S运算得向量V2，如V2=S*V1。第106页，共138页。2.向量流水处理机的结构CRAY—1是由中央处理机、诊断维护控制处理机、大容量磁盘存贮子系统、前端处理机组成的功能分布异构型多处理机系统。中央处理机的控制部分里有总容量为256个16位的指令缓冲器，分成4组，每组为64个。中央处理机的运算部分有12条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算。另外，还有可由流水线功能部件直接访问的向量寄存器组V0~V7、标量寄存器S0~S7及地址寄存器A0~A7。第107页，共138页。图5.29CRAY—1的向量流水处理部分简图第108页，共138页。向量寄存器组Vi在同一时钟周期可接受一个结果分量，并为下次操作再提供一个源分量。这种把寄存器组既作为结果寄存器组又作为源寄存器组的用法，可以实现将2条以上向量指令链接成一条链来提高向量操作的并行程度和功能部件流水的效能。第109页，共138页。为了能充分发挥向量寄存器和可并行工作的6个流水线功能部件的作用，加快对向量的处理，将CRAY—1设计成每个Vi组都有连到6个功能部件的单独总线，而每个功能部件也都有把运算结果送回向量寄存器组的输出总线。这样，只要不出现Vi冲突和功能部件冲突，各个Vi之间和各个功能部件之间都能并行工作，大大加快了向量指令的处理，这是CRAY—1向量处理的一个显著特点。第110页，共138页。

所谓Vi冲突指的是，并行工作的各向量指令的源向量或结果向量使用了相同的Vi。除了相关情况之外，就是出现源向量冲突，例如V4←V1+V2V5←V1∧V3这两条向量指令不能同时执行，必须在第一条向量指令执行完，释放出V1之后，第二条向量指令才能开始执行。因为虽然这两条向量指令的源向量之一都取自V1，由于二者的首元素下标可能不同，向量长度也可能不同，难以由V1同时提供两条指令所需要的源向量。第111页，共138页。

所谓功能部件冲突指的是，同一个功能部件被一条以上的要求并行工作的向量指令所使用。例如V4←V2*V3V5←V1*V6这两条向量指令都需要使用浮点相乘流水功能部件，那就需在第一条向量指令执行到计算完最后一个结果分量，释放出功能部件之后，第二条向量指令才能开始执行。第112页，共138页。向量的重叠处理全并行V1+V2→V3V4*V5→V6功能冲突V1+V2→V3V4+V5→V6VI冲突V1+V2

→V3V1+V2→V3

V4*V2→V5V4*V5→V3数据相关和功能部件相关V1+V2→V0V1+V5→V3第113页，共138页。图5.30CRAY—1的4种向量指令第114页，共138页。CRAY—1向量处理的另一个显著特点是，只要不出现功能部件冲突和源向量冲突，通过链接机构可使有数据相关的向量指令仍能重叠并行处理。链接技术：利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术。第115页，共138页。

基本规则：只要操作数向量中的第一个元素可用，而且功能部件有空，向量运算可立即开始,只要不发生功能部件冲突和操作数寄存器冲突都可以通过全链接机构使数据相关指令功能并行处理。适用情况：即第1条指令的结果，是第2条指令的操作数，这时，所得到的第1条指令的中间结果不必要等待全部向量元素都执行完才进行第二条指令的操作，可以将从一个流水线部件得到的结果直接送入下一个功能流水线部件的向量寄存器，形成两条指令的链接。第116页，共138页。例如，对前述向量运算D=A*(B+C)若向量长度N≤64，向量为浮点数，则在B、C取到V0、V1后，就可用以下3条向量指令求解：V3←存贮器(访存取A向量)V2←V0+V1(B向量和C向量浮点加)V4←V2*V3(浮点乘，存D向量)第117页，共138页。图5.31通过链接技术实现向量指令之间大部分时间并行第118页，共138页。CRAY—1启动访存，把元素送往功能部件，把结果存入Vi都需要有1拍的传送延迟。由于第一、二条指令之间没有冲突，可以同时执行，并且“访存”拍数正好与“浮加”的一样，因此，从访存开始，直至把第一个结果分量存入V4，所需拍数(亦称为链接流水线的建立时间)为第119页，共138页。此后，每拍就可取得一个结果分量存入V4，一共只需17+(N-1)拍就可以执行完这3条向量指令，获得全部结果分量。显然，这要比第一、二条指令全执行完，所有分量全部送入V2、V3后，才开始执行第三条指令要快得多，因为后者需1+6+1+N-1+1+7+1+N-1=15+2N拍。第120页，共138页。CRAY—1指令可以链接的特点，使得它能灵活地组织各流水线功能部件的并行操作。最多能并行处理6条向量指令，进一步发挥这些流水线功能部件的效能。因此，链接技术是提高机器整体运算速度的一个非常重要的措施。CRAY—1的向量指令还可以通过让源向量和结果向量使用同一个向量寄存器组，并控制分量计数器值的修改，来实现递归操作。CRAY—1的每个向量寄存器组Vi都有一个相应的分量计数器。当一条向量指令开始执行时，它的源向量寄存器和结果向量寄存器相应的分量计数器均置成“０”。第121页，共138页。图5.32递归向量和的部分时间关系第122页，共138页。加法指令在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中各个分量的内容如下：第123页，共138页。第124页，共138页。第125页，共138页。可以看出，第八部分(结果部分)V056到V063中存放的是V1的64个分量的8个部分和。这种递归向量和的运算是很有用的。例如在科学计算中，经常需要计算两个向量A=(a0,a1,…,aN-1)和B=(b0,b1,…,bN-1)的点积第126页，共138页。在STAR—100机中，需用专门处理点积的指令来完成，而在CRAY—1机上，未专门设置处理点积的指令，只需用一个向量循环和一个标量循环即可。在向量循环中，就可以利用这种递归特性组成一个乘—加链：V1←V3*V4(A、B分别放在V3、V4中)V0←V0+V1(递归向量和)如果向量长度N=64，乘—加链执行完毕时，点积的64个部分和就已减少成只有8个，并存放在V056到V063中。这样，下一步的标量循环只需求此8个部分和的和。因此，速度有了显著的提高。第127页，共138页。3.超级向量流水处理机举例美国CRAY研究公司成立于1972年，至今已生产了400台以上安装于世界各地