计算机系统结构 第5章

1、第第 5 5 章章 重叠、重叠、 流水和向量处理机流水和向量处理机 5.1 重叠解释方式重叠解释方式 5.2 流水方式流水方式 5.3 向量的流水处理与向量流水处理机向量的流水处理与向量流水处理机 5.4 指令级高度并行的超级处理机指令级高度并行的超级处理机 设计处理机的基本任务之一时要缩短解释指令的时间,即提高处理机指令执行的速度.途径:提高处理机的工作主频采用更好的算法和设计更好的功能部件.多条指令并行执行(指令级并行技术)u采用流水线技术u在一个处理机中设置多个独立的功能部件u超长指令字技术5.1 重叠解释方式重叠解释方式 5.1.1 基本思想和一次重叠基本思想和一次重叠 图图 5.1

2、对一条机器指令的解释对一条机器指令的解释 取指令分析执行t取指令:按指令计数器的内容访问主存,取出该指令送指令寄存器.指令的分析:对指令的操作码进行译码,按寻址方式和地址字段形成操作数物理地址,并取出操作数,形成下一条指令的地址.指令的执行:对操作数进行运算,处理,或存储运算结果(可能要访问主存)当有多条指令要在处理机中执行时,可以采用多种执行方式:1.顺序执行方式niiiitttT1)(执分取若各阶段执行时间相等，则共需若各阶段执行时间相等，则共需3 n t t 优点：优点：控制简单；控制简单； 缺点：缺点：速度慢，机器各部件的利用率很低。速度慢，机器各部件的利用率很低。 2.重叠执行方式:

3、取第k+1条指令与分析第k条指令同时进行,分析第k+1条指令与执行第k条指令同时进行.如果执行一条指令的三过程的时间相等,则 T=(2+n)t为了能够实现理想的指令重叠执行方式,处理机的结构要作比较大的改变,必须采用先行控制方式.要使指令能够正确地重叠执行,必须解决如下两个问题:1.独立的取指令部件,指令分析部件和指令执行部件集中的指令控制器分解:存储控制器 指令控制器 运算控制器2.要解决访问主存的冲突问题1)把主存分成两个独立编址的存储器指存 和 数存 解决了取指令和读操作数的冲突运算结果只写通用寄存器,不写主存.2)低位交叉存取方式3)解决访问存储器冲突的根本方法是采用先行控制技术.先行

4、控制技术的关键是缓冲技术和预处理技术.缓冲技术:在工作速度不固定的两个功能部件之间设置缓冲栈先行指令缓冲栈先行操作栈先行读数栈后行写数栈预处理技术:把进入运算器的指令都处理成RR型指令.可大幅度提高指令的执行速度.图 5.2 指令的顺序解释与重叠解释 图 5.3 一次重叠工作方式 如果指令分析器每次取指令都能在先行指令缓冲栈中得到, 则取指令只需要很短的时间. 把取指令和分析指令指令合并.实现分析k+1和执行k的一次重叠,待解决的问题:u分析和执行所时间差很大u如果分析k+1所要读取的操作数正好数执行k的结果,那它们不能重叠执行-数据相关,另外还有控制相关,指令相关等.u当出现转移或转子程序指

5、令时,程序的执行过程就不是顺序的,在先行指令缓冲栈中预取的指令和已经分析完成的下一条指令等都可能要作废.图 5.4 当第k条指令是条件转移时 例一、数据相关。 第K+1条指令的源操作数正好是第K条指令结果地址，顺序解释没问题，而重叠解释时，在“执行K”和“分析K+1”重叠时就出现问题 相关：因程序相邻指令之间出现了关联，为防止出错他们不能同时解释。这种现象称发生了”相关“，有数据相关和指令相关。 指令相关。指令相关是因为机器指令允许修改引起的。 如果采用Von Neumann型机器上指令可修改的办法经第k条指令的执行来形成第k+1条指令，如 k： 存 通用寄存器， k+1； (通用寄存器)k+

6、1 k+1: 由于在“执行k”的末尾才形成第k+1条指令，按照一次重叠的时间关系，“分析k+1”所分析的是早已取进指缓的第k+1条指令的旧内容，这就会出错。为了避免出错，第k、k+1条指令就不能同时解释，我们称此时这两条指令之间发生了“指令相关”。 特别是当指令缓冲器可缓冲存放n条指令情况下，执行到第k条指令时，与已预取进指缓的第k+1到第k+n条指令都有可能发生指令相关。指缓容量越大，或者说指令预处理能力愈强的机器发生指令相关的概率就愈高。 5.1.2 相关处理相关处理 1. 指令相关的处理指令相关的处理 要判断是否发生了指令相关,要把每一条指令的执行结果地址与先行操作栈中,指令分析器和先行

7、指令缓冲栈中的所有指令地址进行比较.如果发现相关,则在修改主存相关单元的同时,也要修改先行操作栈或指令分析器或先行指令缓冲栈中的相关指令.解决指令相关的根本办法:在程序设计中不允许修改指令.IBM370机器中,有一条”执行”指令能够解决指令相关,又允许在程序执行过程中修改指令. “执行”指令是IBM 370机器为此设置的一条指令，其形式为 执行R1X2B2D2当执行到“执行”指令时，按第二操作数(X2)+(B2)+D2地址取出操作数区中单元的内容作为指令来执行，参见图5.5。 图 5.5 IBM 370“执行”指令的执行 2. 主存空间数相关的处理主存空间数相关的处理 相邻两条指令之间出现要求

8、对主存同一单元先写入而后再读出的关联.在大多数处理机中,运算结果一般都写入通用寄存器,而不写入主存. 主存操作数相关出现的概率比较小.解决办法:推后处理法.在设置有存储控制器的处理机中,把”写结果”的优先级安排得高于”读操作数”的优先级.由于存控响应访问请求是定时进行的,它在一个周期的最末尾处对这一个周期这的所有访问源进行排队.图图 5.6 主存数相关的处理主存数相关的处理 3. 3. 通用寄存器组相关的处理通用寄存器组相关的处理 通用寄存器存放操作数,也存放变址,基址.存放在通用寄存器中的基址或变址一般总是在”分析”周期的前半段就要取出; 而操作数则是在”分析”周期的末尾的后半段取出,到”执

9、行”周期的前半段才真正用上; 运算结果在”执行”周期的末尾才形成,并送入通用寄存器. 通用寄存器数相关的情况和处理办法设机器的基本指令格式为 操作码L1L3B2d2或 操作码L1L3L2图图 5.7 指令解释过程中与通用寄存器内容有关的微操作时间关系指令解释过程中与通用寄存器内容有关的微操作时间关系图图 5.8 “执行执行k”、 “分析分析k+1”重叠时，访问通用寄存器组的时间关系重叠时，访问通用寄存器组的时间关系 解决办法:1)分析周期推后一个周期执行.顺序串行 实现简单 运算速度的损失较大2)分析指令仅仅推后一个节拍3)设置专用数据通路.图 5.9 用相关专用通路解决通 用寄存器组的数相关

10、 变址相关因为计算有效地址是在指令分析的一开始进行的,因此,变址相关造成的后果要比数相关更为严重.设操作数的有效地址 222)0000()()(dBBXd由分析器内的地址加法器形成。由于通常情况下，“分析”周期等于主存周期，所以，从时间关系上要求在“分析”周期的前半段，就能由通用寄存器输出总线取得(B2)，送入地址加法器。由于运算结果是在“执行”周期的末尾才送入通用寄存器组的，它当然不能立即出现在通用寄存器输出总线上。也就是说，在“执行k”得到的、送入通用寄存器的运算结果来不及作为“分析k+2”的基址值用，更不用说作为“分析k+1”的基址值用。因此，虽然是一次重叠，但基址值相关(B相关)就不止

11、会出现一次相关，还会出现二次相关。即当出现B(k+1)=L3 (k)时，称为发生了B一次相关；而当出现B(k+2)=L3(k)时，称为发生了B二次相关，如图5.10所示。 解决变址相关的办法:推后分析和设置相关专用通路推后分析法 对于二次变址相关, “分析k+2”推后 1周期(1节拍) 一 “分析k+1” 2 (1周期+1节拍)变址相关专用通路 运算结果送入通用寄存器的同时,直接送到地址加法器中.图 5.10 B一次相关与二次相关 图 5.11 B一次、 二次相关的推后处理 图 5.12 B相关专用通路法 5.2 流流 水水 方方 式式 5.2.1 基本概念基本概念 流水是重叠的引申：流水是重

12、叠的引申：一次重叠：把一条指令的解释分为两个子过程，同时解释两一次重叠：把一条指令的解释分为两个子过程，同时解释两条指令。条指令。流水：把一条指令的解释分为多个子过程，同时解释多条指流水：把一条指令的解释分为多个子过程，同时解释多条指令。令。取指取指访存访存执行执行译码译码写回写回IFIDEXMEMWBS1S2S3S4S5输入输入输出输出指令的流水处理指令的流水处理S1S2Sk输入输入 输出输出流水线的基本结构流水线的基本结构.时钟时钟.12345.n-1 n.12345.n-1 n.12345.n-1 n.12345.n-1 n1234t t0 0 t t0 0 t t0 0 t t0 0T

13、 T0=m 0=m t t0 0n n t t0 0T T(m-1) (m-1) t t0 0(n-1) (n-1) t t0 0填入填入 正常正常 排空排空 流水时空图流水时空图空间空间时间时间2、流水线特点、流水线特点： 1）流水一定重叠，比重叠更苛刻。）流水一定重叠，比重叠更苛刻。 2）一条流水线通常有多个流水段组成。）一条流水线通常有多个流水段组成。 3）每段有专用功能部件，各部件顺序连接，不断流。）每段有专用功能部件，各部件顺序连接，不断流。 4）流水线有建立时间、满载时间、排空时间，）流水线有建立时间、满载时间、排空时间， 5）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。）各段

14、时间尽量短、一致；不一致时最慢子过程为瓶颈。 6）给出指标如最大吞吐率，为满负载最佳指标。）给出指标如最大吞吐率，为满负载最佳指标。建立时间：建立时间：在流水线开始时有一段流水线填入时间，使得流在流水线开始时有一段流水线填入时间，使得流水线填满。水线填满。正常流动时间：正常流动时间：流水线正常工作，各功能段源源不断满载工流水线正常工作，各功能段源源不断满载工作。作。排空时间：排空时间：在流水线第一条指令结束时，其他指令还需要一在流水线第一条指令结束时，其他指令还需要一段释放时间。段释放时间。分级分级：（处理的级别分类）：（处理的级别分类）部件级流水：构成部件内的各个子件之间的流水，如运算器内的

15、“浮点加”流 处理机级流水：构成处理机的各部件间的流水，如取指，分析，执行的流水。系统级流水：构成计算机系统的多个处理机间的流水。2. 流水线的分类流水线的分类 其他分类：其他分类： 功能：单功能流水线（如功能：单功能流水线（如CRAY-1CRAY-1）、多功能流水线）、多功能流水线 （如（如TI-ASCTI-ASC） 工作方式：静态流水线、动态流水线工作方式：静态流水线、动态流水线 连接方式：线性、非线性连接方式：线性、非线性 处理数据：标量流水、向量流水处理数据：标量流水、向量流水1234出出入入非线性流水线非线性流水线图 5.15 处理机间的流水处理 单功能流水线: 只能实现一种功能的流

16、水处理.多功能流水线: 同一流水线的各个段之间可以有多种不同的连接方式以实现多种不同的运算或功能.图 5.16 ASC机运算器的流水线 按多功能流水线的各段是否允许同时用于多种不同功能连接流水,流水线分为静态流水线和动态流水线静态流水线: 在某个时间内各段只能按一种功能连接流水,只有等流水线全部流空后才能切换成按另一种功能来连接. 就指令级流水而言,仅当进入的是一串相同运算的指令时,才能发挥出静态流水线的效能.动态流水线 : 各功能段在同一时间内可按不同的运算或功能连接. 图 5.17 静、 动态多功能流水线时-空图举例以机器所具有的数据表示分类标量流水处理机: 没有向量数据表示,只能用标量循

17、环方式对向量,数组进行处理.向量流水处理机: 机器具有向量数据表示,设置有向量指令和向量运算硬件,能对向量,数组中的各元素流水地处理.是向量数据表示和流水技术的结合. 从流水线中各功能段之间是否有反馈回路来分类线性流水非线性流水图 5.18 非线性流水线举例 5.2.2 流水线处理机的主要性能流水线处理机的主要性能 衡量流水线性能的主要指标 吞吐率 加速比 效率吞吐率吞吐率 吞吐率是流水线单位时间里能流出的任务数或结果数。 在图5.14的流水线例子中，各个子过程经过的时间都是t2，满负荷后，流水线每隔t2解释完一条指令，其最大吞吐率TPmax为1/t2。实际上，各个子过程进行的工作不相同，所经

18、过的时间也就不一定相同，所以前述在子过程间设置了接口锁存器， 让各锁存器都受同一时钟脉冲同步。时钟脉冲周期直接影响流水线的最大吞吐率，总希望它越小越好。如果各个子过程所需的时间分别为t1、t2、t3、t4，时钟周期应当为maxt1, t2, t3, t4，即流水线的最大吞吐率 ,max14321maxttttTP 它受限于流水线中最慢子过程所需要的时间。称流水线中经过时间最长的子过程为瓶颈子过程。 图 5.19 最大吞吐率取决于瓶颈段的时间 图 5.20 瓶颈子过程再细分 图 5.21 瓶颈子过程并联 设一m段流水线的各段经过时间均为t0，则第1条指令从流入到流出需要T0=mt0的流水建立时间

19、，之后每隔t0就可以流出一条指令，其时空图如图5.22所示(这里设m=4)。这样，完成n个任务的解释共需时间T=mt0+(n-1)t0。在这段时间里， 流水线的实际吞吐率 nmTPnmttntmnTP11)11 (1) 1(max000图 5.22 从时空图分析实际的吞吐率 不仅实际的吞吐率总是小于最大的吞吐率，而且只有当nm时，才能使实际的吞吐率接近于理想的最大吞吐率。 加速比(Speedup Ratio, Sp):表示流水线方式相对非流水线顺序串行方式速度提高的比值.非流水线顺序串行方式工作，连续完成n个任务需要nmt0的时间 . 流水线方式工作的加速比 nmmtntmtmnSp11) 1

20、(000 如果线性流水线各段经过的时间ti不等，其中瓶颈段的时间为tj，则完成n个任务所能达到的实际吞吐率 jmiimiipjmiitnttnStntnTP) 1() 1(111其加速比 2. 效率效率 流水线的效率是指流水线中的设备实际使用时间占整个运行时间之比，也称流水线设备的时间利用率时间利用率。由于流水线存在有建立时间和排空时间(最后一个任务流入到流出的时间)，在连续完成n个任务的时间里，各段并不总是满负荷工作的。 如果是线性流水线，且各段经过时间相同，如图5.22那样， 则在T时间里，流水线各段的效率都相同，均为0，即 TmtnmmmmnmnTtnmm002100211整个流水线的效

21、率 式中，分母mT是时空图中m个段和流水总时间T所围成的总面积，分子mnt0则是时空图中n个任务实际占用的总面积。因此，从时空图上看，效率实际上就是n个任务占用的时空区面积和m个段总的时空区面积之比。显然，与吞吐率类似，只有当nm时，才趋近于1。 同时还可看出，对于线性流水且每段经过时间相等时， 流水线的效率是正比于吞吐率的， 即 00) 1(tTPmnnTtn 如果流水线各段经过的时间不等，各段的效率就会不等，但是，参照图5.22，不难得出整个流水线的效率 jmiimiitntmtnmn) 1(11空区个段总的时空白个任务实际占用的时jmiimiimiiitntatan) 1(111其中，分

22、母为m个段的总的加权时空区，分子为n个任务总的加权时空区。当 时， 有 miia11mijimiiitnttan11) 1( 对于复杂的非线性流水线，实际的吞吐率TP和效率需要通过画出实际工作时的时空图，才能分别用下列两个式子求得： 空区个段的总的加权时空区个任务的总的加权时个任务全部流出的时间从开始流入到任务数mnnTP图 5.23 流水线工作举例 3. 流水线工作举例流水线工作举例 TP=7/(15t) t) 顺序方式时间：顺序方式时间：4 4* *3 3t+3t+3* *4 4t=24t=24t t 加速比：加速比： Sp=24t/15 t/15 t=1.6t=1.6 效率（用面积比方法

23、）：效率（用面积比方法）： =（3 3* *4 4 t+4t+4* *3 3 t t）/(5/(5* *15 15 t) t) =32% =32%3 实例分析实例分析:性能分析（实测法性能分析（实测法, 分析法分析法, 时空图法）时空图法）.例例1. 四段流水线四段流水线, t t1 1= =t t3 3= =t t4 4= =t, t, t t2 2=3=3t,4t,4个任务、个任务、1010个任务时个任务时T TP P，、S SP P 。=N N个任务实际占用的时个任务实际占用的时- -空区空区M M各段总的时各段总的时- -空区空区n=10，=6 6* *1010t t4 4* *6 6

24、t+9t+9* *3 3* *4 4t t=6024+108= 115TP=106*t t+3*9* t t =1033*t t 45%45% （1）分析法）分析法: 各段时间不等各段时间不等=Sp=n *t ti imi=1t ti i+ +(N-1)(N-1)* *t tj jmI=110*6 t t(6+3*9) t t=202011=1.8TP=TP=nt ti i+(n-1)+(n-1)tjtjmi=1时间时间12343111223234123123123444443 3t t3 3t t空间空间(2) 时空图法时空图法:Tp=4/(6+3*3) t)=4/(15t)=4/(15t)

25、=0.267(1/t)=0.267(1/t)t) =24 t t /(4/(4* *1515t)=2/5=40%t)=2/5=40%Sp=4*6 t t /15/15t=8/5=1.6t=8/5=1.6n=4n=4时时; ;n=10n=10时时; ;同上同上. .例例2. 以浮点加法运算为例（四段流水线）各段时间相等，如何求以浮点加法运算为例（四段流水线）各段时间相等，如何求吞吐率、效率。吞吐率、效率。 求求Z=A+B+C+D+E+F+G+H，TP、Sp 注意有相关注意有相关时间时间空间空间Z=A+B+C+D+E+F+G+H1234567TP=7/15t t, =7*4/(15*4)=7/15

26、解：解：Sp=4*7/15=28/15=1.871111222233334444555566667777例例3. ASC计算机功能算术运算流水线各段时间相等，计算机功能算术运算流水线各段时间相等，6次浮点加、次浮点加、 5次定点乘的吞吐率次定点乘的吞吐率,效率效率,加速比加速比 M=8,N=11.分析：分析：T T加加=6+(6-1)=6+(6-1)* *1=11 (1=11 (t) Tt) T乘乘=4+(5-1)=4+(5-1)* *1=8 (1=8 (t)t)则则 TP= 11/(11+8)TP= 11/(11+8)t =11/19 t =11/19 t t Sp= 56 Sp= 56 t

27、 /19 t /19 t =2.94t =2.94 = (6 = (6* *6+56+5* *4) 4) t /(19t /(19* *8 8t)=6/52=7/19t)=6/52=7/1912345612345612345612345612345867123456123456时间时间浮加浮加定点乘定点乘一一二二三三 四四 五五一一二二三三 四四 五五一一二二三三 四四五五一一二二三三 四四五五5.2.3 流水机器的相关处理和控制机构流水机器的相关处理和控制机构 要使流水线充分发挥效率,不发生或少发生断流,需要硬件和软件两方面的共同努力.软件方面: 编译器生成的目标程序要能够适合流水线结构,要

28、尽量把有数据相关和控制相关的指令安排得相隔远一些,把相同的操作尽量安排在一起.硬件方面: 要解决存储系统的频带平衡问题,能够为流水线提供足够的指令和数据.另外,要处理好流水线的局部相关和全局相关.流水机器的全局性相关指的是转移指令与其后指令之间的相关联,不仅不能同时解释,还会使指令缓冲器所预取的指令要全部作废,重新花较长的时间再去访存取出指令. 流水机器的局部性相关：指令相关,主存数相关,通用寄存器组的数相关,基(变)址相关等对流水性能下降的影响要严重得多.(只影响到相关的指令在某些功能段上停等一段时间,不会影响到流水线需要等待,去重新访存指令任务在流水线中流动顺序的安排和控制方式:同步流动方

29、式(顺序流动方式):让任务(指令)流出流水线的顺序保持与流入的顺序一致.异步流动方式(乱序):让流出流水线的任务顺序可以和流入流水线的顺序不同.局部性数据相关局部性数据相关例：有例：有i 和和j两条指令，两条指令，i指令在前，指令在前，j指令在后，则三种不同类指令在后，则三种不同类型的数据相关的含义为：型的数据相关的含义为：RAW读写读写(先写后读先写后读) - 指令指令 j 试图在指令试图在指令 i 写入寄存器前就写入寄存器前就读出该寄存器内容，这样，指令读出该寄存器内容，这样，指令j就会错误地读出该寄存器旧就会错误地读出该寄存器旧的内容。的内容。 （改用相关）（改用相关） i: R1+R2

30、-R3 j: R3*R4-R5WAR写读写读(先读后写先读后写) - 指令指令 j 试图在指令试图在指令 i读出寄存器之前读出寄存器之前就写入该寄存器，这样，指令就写入该寄存器，这样，指令i就错误地读得该寄存器新的内就错误地读得该寄存器新的内容。容。 （用改相关）（用改相关）i: R3*R4-R5 j: R1+R2-R3WAW写写写写(先写后写先写后写) - 指令指令j试图在指令试图在指令i写寄存器之前就写写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令使由指令i写入的值成为该寄存器内容。写入的值成为该寄存器内容。

31、 （改改相关）（改改相关） i: R1*R2-R3 j: R4+R5-R3顺序顺序流动流动不按顺不按顺序流动序流动不按顺不按顺序流动序流动解决办法主要用软件和硬件技术：解决办法主要用软件和硬件技术：v时间推后法时间推后法v旁路技术或相关专用通路技术旁路技术或相关专用通路技术图 5.24 顺序流动和异步流动 对对IBM360/91机是通过给机是通过给FLR设置一个设置一个“忙忙”标志来判别指令标志来判别指令间所用的数据是否发生相关间所用的数据是否发生相关,另外还有一个标志（即站号）表示另外还有一个标志（即站号）表示数据由何处来，用站号位控制相关通路连接，采用公共数据总数据由何处来，用站号位控制相

32、关通路连接，采用公共数据总线线CDB来实现内部数据专用通路的连接。来实现内部数据专用通路的连接。IBM360/91的浮点运算器部分包括了以下主要部件：的浮点运算器部分包括了以下主要部件： （1） 运算部件：运算部件：一个加法部件和一个乘除部件。一个加法部件和一个乘除部件。（2）保存站：）保存站：加法部件中有加法部件中有A1A3三个保存站，乘除部件有三个保存站，乘除部件有M1和和M2两个保两个保存站，用来保存当前参加运算的数据。存站，用来保存当前参加运算的数据。（3） 指令操作缓冲栈：指令操作缓冲栈：存放经分析后由指令部件送来的指令，译码后，存放经分析后由指令部件送来的指令，译码后， 产生相应的

33、控制信号送到各个部件。产生相应的控制信号送到各个部件。（4）浮点操作数寄存器（）浮点操作数寄存器（FLB）：）：存放由主存预取来的操作数。存放由主存预取来的操作数。（5）浮点寄存器（）浮点寄存器（FLR）：）：存放操作数的寄存器。存放操作数的寄存器。（6） 存储数据缓冲站（存储数据缓冲站（SDB）：）：存放将写入存储器的结果数据，也有站号。存放将写入存储器的结果数据，也有站号。（7） 公共数据总线（公共数据总线（CDB）：）：以上各部件间的连接总线。以上各部件间的连接总线。图5.25 IBM 360/91的浮点执行部件结构框图Tomasulo算法 浮点操作站FLOS(Floating Poin

34、t Operand Stack)缓冲的浮点操作命令的格式为 操作 源1 (目的)， 源2 操作可以是浮点加、减、乘、除。源1指明存放源操作数的浮点寄存器FLR的号，并兼作存放中间结果的目的寄存器的号。 源2指明存放经存贮器总线送来的浮点操作数的缓冲器FLB的号。 它们分别经FLR总线和FLB总线将数据送入浮点加法流水线或浮点乘/除法流水线输入端的保存站。浮点加法器流水线的输入端设有3个保存站A1至A3，浮点乘/除法器流水线的输入端设有两个保存站M1和M2，分别用规定的站号标记。保存站由控制部分控制，只要任意一个保存站的两个源操作数都到齐，且流水段空闲时就可以进入流水线向前流动，因此是采用异步流

35、动方式工作的。 由于操作命令中源1兼作目的，因此同时进入两条流水线的操作命令之间发生操作数相关的概率是较高的。设k+i表示k之后同时在两条流水线流动的第i条指令，则只要k+i 的源1与k的目的一样，就会发生“先写后读”相关，k+i的目的与k的目的一样，就会发生“写写”相关， k+i的目的与k的源1一样，就会发生“先读后写”相关。也就是说，只要同时进入流水线的各个操作命令中使用了同一个浮点寄存器FLR的号就会发生相关。 现在，以FLOS依次送出 ADD F2, FLB1; (F2)+(FLB1)F2 MD F2, FLB2; (F2)*(FLB2)F2两条操作命令为例，来说明是怎样判出发生相关以

36、及怎样控制推后和相关直接通路的联接的。很明显，这两条命令异步流动时，“先写后读”、“写写”、“先读后写”三种相关都会发生。 当FLOS送出 ADD F2, FLB1 操作命令时，它控制由FLR取得(F2)，由FLB取得(FLB1)送往加法器保存站，例如送往A1，同时立即将F2的“忙位”置“”， 以指明该寄存器的内容已送往保存站等待运算，这样F2的内容再不能被其他操作命令作源操作数读出用。由于F2这时已成为“目的”寄存器，准备接收由加法器来的运算结果，因此将F2的“站号”字段置成是A1的站号“1010” ，以便控制把站号为1010的保存站A1在加法流水线流出的运算结果经CDB总线送回F2。一旦结

37、果送回后，立即将F2的“忙位”和“站号”都置成“”，以释放出F2为别的操作命令使用。 问题在于，当F2的“忙位”为“”，而加法结果并未流出加法流水线时，FLOS又送出操作命令 MD F2, FLB2由译码控制去访问F2取源1操作数时，由于其“忙位”为“”， 表明出现了F2相关，此时就不能直接将(F2)送往乘法器保存站， 而改成为把原存在F2的“站号”字段中的站号A1(即1010， 指明F2应有内容的来源)送往M1的“源1站号”，并把F2内的站号由A1(1010)改为M1(1000)以指明应改为从M1接收运算结果。 特点：特点：（1）由于为加法器和乘法部件分别设置了）由于为加法器和乘法部件分别设

38、置了3个和个和2个保存站，个保存站，从而减小了资源使用冲突的机会。仅当这些保存站读都处于从而减小了资源使用冲突的机会。仅当这些保存站读都处于忙碌状态时，才有可能发生资源使用冲突。忙碌状态时，才有可能发生资源使用冲突。（2）调度算法使用保存站，通过对寄存器重新命名（改写站）调度算法使用保存站，通过对寄存器重新命名（改写站号）自然地消除了号）自然地消除了WAR和和WAW数据相关可能性。数据相关可能性。（3）通过对）通过对FLR寄存器忙位状态的判别，来检测是否存在寄存器忙位状态的判别，来检测是否存在RAW数据相关。数据相关。（4）借助）借助CDB公共数据总线作为专用相关通路，将有关数公共数据总线作为

39、专用相关通路，将有关数据直接送往所有需要它的功能部件，而不必先写入寄存器，据直接送往所有需要它的功能部件，而不必先写入寄存器，然后再从此寄存器读出。然后再从此寄存器读出。2. 全局性相关全局性相关(控制相关控制相关)由条件转移或程序中断引起的相关由条件转移或程序中断引起的相关-全局相关全局相关关键问题关键问题: 1)确保流水线能够正常工作确保流水线能够正常工作 2)减少因断流引起的吞吐率和效率的下降减少因断流引起的吞吐率和效率的下降一般情况下要在转移指令执行到流水线的最后功能段时一般情况下要在转移指令执行到流水线的最后功能段时,转移转移条件才能建立条件才能建立.因此因此,在条件转移指令进入流水

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

41、将转移指令前的那条指令调度到延迟槽中； b.将转移目标处的那条指令调度到延迟槽中；将转移目标处的那条指令调度到延迟槽中； c.将转移不发生时该执行的那条指令调度到延迟槽中。将转移不发生时该执行的那条指令调度到延迟槽中。4)设置特殊循环指令，加快短循环处理: 3. 流水机器的中断处理流水机器的中断处理 中断会引起流水线断流。然而，其出现概率比条件转移的概率要低得多，且又是随机发生的。所以，流水机器处理中断主要是如何处理好断点现场的保存和恢复，而不是如何缩短流水线的断流时间。 不精确断点法不精确断点法(同外部设备中断处理一样同外部设备中断处理一样)：不论第：不论第i条指令在流条指令在流水线的哪一段

42、发出中断申请，都不再允许那时还未进入流水线水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入的后续指令再进入 精确断点法：精确断点法：不论第不论第i条指令是在流水线中哪一段发的中断申请，条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第给中断处理程序的现场全都是对应第i条的，在第条的，在第i条之后进入条之后进入流水线的指令的原有现场都能恢复流水线的指令的原有现场都能恢复 (增加设备，加许多缓冲器，增加设备，加许多缓冲器，各功能段状态保留）各功能段状态保留）4. 流水线调度流水线调度 非线性流水线：非线性流水线：由于段间有前馈和反馈通路任务，执行过程中由于

43、段间有前馈和反馈通路任务，执行过程中可能会多次通过同一流水段，发生几个任务同时争用同一流可能会多次通过同一流水段，发生几个任务同时争用同一流水段的现象，这就是水段的现象，这就是功能段的使用冲突功能段的使用冲突。流水线调度常借助于二维预约表和状态转换图来进行分析流水线调度常借助于二维预约表和状态转换图来进行分析根据预约表可较容易地推算出一个任务执行时，各段所需的根据预约表可较容易地推算出一个任务执行时，各段所需的间隔周期拍数。间隔周期拍数。解决方法：解决方法：间隔恰当的拍数后再向流水线送入下一个任务。间隔恰当的拍数后再向流水线送入下一个任务。这就需要对流水线作适当的调度。这就需要对流水线作适当的

44、调度。S/t 1 2 3 4 5 6 7 8 91 X X 2 X X X 3 X 4 X X 5 X X 二维预约表二维预约表 图中每一行代表图中每一行代表P的一个段，每一列表示相应的时钟周期。的一个段，每一列表示相应的时钟周期。若某个任务在周期若某个任务在周期ti需要使用需要使用Sj段进行处理，则在行段进行处理，则在行Sj和列和列ti的相交处以的相交处以“ ”表示。表示。条件：条件：非线性、单功能流水线非线性、单功能流水线P，由，由K段组成，每个任务流过流段组成，每个任务流过流水线需水线需N个时钟周期（个时钟周期（t1,t2,tn），段为纵坐标，时间为横坐标），段为纵坐标，时间为横坐标 禁

45、止表禁止表F=1，5，6，8 1011000110110111101111011011111110111011一个一个n位的位向量位的位向量C=(Cn、Cn-1、. 、C2、 C1)称为冲突向量。称为冲突向量。其中第其中第i位状态表示于当时相隔位状态表示于当时相隔 i拍时间时，是否允许输入新拍时间时，是否允许输入新任务。如允许输入，则任务。如允许输入，则Ci=0, 否则否则Ci=1。非线性流水线预约表相应状态图非线性流水线预约表相应状态图 42=7=734=7=7=7原始冲突向量原始冲突向量 23过程过程:1. 按给出的预约表写出允许表和禁止表按给出的预约表写出允许表和禁止表 F=1，5，6，

46、8；2. 写出写出n位初始冲突向量（位初始冲突向量（10110001）；）；3. 按禁止表约束条件列出新的冲突向量，直到不再生成新的冲突按禁止表约束条件列出新的冲突向量，直到不再生成新的冲突向量为止（当前冲突向量和初始冲突向量按位向量为止（当前冲突向量和初始冲突向量按位“或或”）；）；4. 画出用冲突向量表示的流水线状态转移图（两个冲突向量之间画出用冲突向量表示的流水线状态转移图（两个冲突向量之间用有向弧连接，并用数字表示引入后继任务用的间隔节拍，写出用有向弧连接，并用数字表示引入后继任务用的间隔节拍，写出各种可能的状态转换）；各种可能的状态转换）；5. 列出各种调度方法平均间隔拍数；列出各种

47、调度方法平均间隔拍数；6. 求出最佳等间隔和非等间隔调度拍数；求出最佳等间隔和非等间隔调度拍数；本例子中非等间隔调度为本例子中非等间隔调度为3拍，拍，4拍拍.平均间隔为平均间隔为3.5拍，而拍，而等间隔调度为等间隔调度为7拍。拍。图图 5.27 流水线预约表及状态图举例流水线预约表及状态图举例 表表 5.1 各种调度方案的平均间隔拍数的例子各种调度方案的平均间隔拍数的例子 调度方案：间隔拍数周期性重复（只有重复才能循环）最佳策略：平均间隔拍数最少（吞吐率，效率高）吞吐率TP=任务数M/总时间T 调度方案产生办法：1）从初始状态出发，沿箭头方向，每走一个闭环，即为一个方案2）若中间遇到小闭环，每

48、个小闭环也可作为一个方案3）遍历初始状态中的每一个Ci=0的回路。 状态转移图的生成方法： 1）从初始冲突向量出发，对每一个ci=0产生一个新的冲突向量 2）箭头由原冲突向量指向新的冲突向量，线弧上写上i,表示间隔i拍送入流水线产生冲突向量。 3）对新的冲突向量中的ci=0重复进行1)2) 4)图中全部ci=0的位全有目标冲突向量。图 5.28 多功能流水线预约表及状态图举例 使用交叉冲突向量(Crosscollision Vector)来反映有A、B两种功能的动态流水线各个后继任务流入流水线所禁止使用的间隔拍数。 这样， 对于本例就应有4个交叉冲突向量，即 VAB=(1011)，VBA=(1

49、010),VAA=(0110), VBB=(0110)。其中，VAA和VBB分别表示同按A功能和B功能流水时，后继任务流入流水线的冲突向量；而VAB表示先前按B功能流水流入的任务与后继按A功能流水流入的任务之间的冲突向量，VBA则表示先前按A功能流水流入的任务与后继按B功能流水流入的任务之间的冲突向量。 就一般情况而言，一个有P个功能的流水线将有P2个交叉冲突向量，它们可以分别归类写成P个冲突矩阵Mp，其中p分别为1至P。冲突矩阵Mp表示按p功能流水线进入一个任务后与按各种功能流水线流入后继任务所产生的全部冲突向量的集合。 对本例来说有两个初始冲突矩阵，分别为 )(0110)(1011,)(1

50、010)(0110BBABMBBAAAMA 例如，按A功能刚流入一个任务后，根据VAA的(0110)，知道可隔1拍或4拍流入一个A功能的新任务。将MA初始冲突矩阵各行同时右移1位，再与A功能的初始冲突矩阵MA对应行按位“或”，形成新的冲突矩阵 。根据此时VAA的(0111)， 知道只有隔4拍流入一个A功能的新任务才能不发生冲突，从而形成在此基础上的新的冲突矩阵 。 1111011110100110 再如，根据初始冲突矩阵中的VBA为(1010)，知道可在第一拍或第三拍进行B功能的新任务的送入而不发生冲突。于是将MA初始冲突矩阵均右移1位或3位，再与MA的初始冲突矩阵对应行按位“或”，形成新的冲

51、突矩阵，它们恰好都为 。 据此可知，或者是隔3拍流入A功能的新任务， 或者是隔4拍流入B功能的新任务，又将分别产生不同的新的冲突矩阵。 011110115.3 向量的流水处理与向量流水处理机向量的流水处理与向量流水处理机 5.3.1 向量的流水处理向量的流水处理 向量中的各个元素在运算时很少相关,而且都是进行相同的运算或处理,相比标量运算,应当更能发挥出流水线的效能.选择对向量,数组如何处理,才能最充分地发挥出流水线的效能,是向量流水处理要解决的问题. 是与所要解的具体题目及计算机的结构密切相关的. 例如：向量计算：例如：向量计算：A*(B+C) 的的 循环程序循环程序用用C语言为语言为 fo

52、r( i=1;i1)条指令条指令,称处理机并行度为称处理机并行度为m.5.4 指令级高度并行的超级处理机指令级高度并行的超级处理机 5.4.1 超标量处理机超标量处理机 图 5.33 常规(度m=1)的标量流水机时-空图 图 5.34 度m=3的超标量处理机时-空图 每个时钟周期内能启动每个时钟周期内能启动n条指令条指令主要特点：主要特点：（1）配置有多个性能不同的处理部件，采用多条流水线）配置有多个性能不同的处理部件，采用多条流水线并行处理。并行处理。（2）能同时对若干条指令进行译码，将可并行的指令送）能同时对若干条指令进行译码，将可并行的指令送往不同的执行部件，从而达到每个周期启动多条指令

53、。往不同的执行部件，从而达到每个周期启动多条指令。（3）在程序运行期间由硬件（通常是状态记录部件和调）在程序运行期间由硬件（通常是状态记录部件和调度部件）完成指令调度。度部件）完成指令调度。 典型的超标量流水线处理机有IBM RS/6000、DEC 21064、Intel i960CA、TandemCyclone等。1986年的Intel i960CA时钟频率为25 MHz，度m=3, 有7个功能部件可以并发使用。1990年的IBM RS/6000使用1 m CMOS工艺，时钟频率为30 MHz。处理机中有转移处理、定点、浮点 3 种功能部件，它们可并行工作。 转移处理部件每t可执行多达5条指

54、令，度m=4，性能可达34 MIPS和11 MFLOPS。非常适合于在数值计算密集的科学工程上应用及在多用户商用环境下工作。许多基于RS/6000的工作站和服务器都是IBM生产的。如POWER Station 530。1992年的DEC 21064使用0.75 m CMOS， 时钟频率为150 MHz，度m=2，10段流水线， 最高性能可达300 MIPS和150 MFLOPS。Tandem公司的Cyclone(旋风)计算机由4到16台超级标量流水处理机组成。 每个处理机的寄存器组有9个端口(其中5个为读，4个为写)，有两个算术逻辑部件， 度m=2。由于程序中可开发的指令并行性有限，所以超标量流水线处理机的度m比较低。 5.4.2 超长指令字处理机超长指令字处理机 以一条长指令实现多个操作的并行执行，减少存储器访问以一条