第5章 流水和指令级高度并行的超级机.ppt

1、第5章 流水和指令级高度并行的超级机,1计算机组成设计的基本任务： 加快机器语言的解释。,2从两方面实现： 一方面，通过选用更高速的器件、采取更好的运算方法、提高指令内各微操作的并行程度、减少解释过程所需要的拍数等多项措施来加快每条机器指令的解释。,第5章 流水和指令级高度并行的超级机,1计算机组成设计的基本任务： 加快机器语言的解释。,2从两方面实现：,另一方面，通过控制机构采用同时解释两条、多条以至整段程序的控制方式来加快整个机器语言程序的解释。重叠和流水是其中常用的控制方式。,5.1重叠方式,5.1.1重叠原理和一次重叠 1指令的顺序解释方式： 各条机器指令之间顺序串行地执行，执行完一条

2、指令后才取出下条指令来执行，而且每条机器指令内部的各个微操作也是顺序串行地执行。,5.1重叠方式,5.1.1重叠原理和一次重叠 1指令的顺序解释方式：,解释一条机器指令的为操作归并成：取指令、分析、执行。如图5-1所示。,取指令：指按指令计数器的内容访问主存，取出该指令送 到指令寄存器。,5.1重叠方式,5.1.1重叠原理和一次重叠 1指令的顺序解释方式：,解释一条机器指令的为操作归并成：取指令、分析、执行。如图5-1所示。,分析指令：指对指令的操作码进行译码，按寻址方式和地址字段形成操作数真地址，并用此真地址去取操作数（可能访存，也可能访寄存器），还要为准备取下条指令提前形成下条指令的地址等

3、。,5.1重叠方式,5.1.1重叠原理和一次重叠 1指令的顺序解释方式：,解释一条机器指令的为操作归并成：取指令、分析、执行。如图5-1所示。,执行指令：指对操作数进行运算、处理，或存储运算结果（可能要访主存）。,5.1重叠方式,5.1.1重叠原理和一次重叠 1指令的顺序解释方式：,指令的顺序解释如图5.2（a）。,顺序执行的优点：控制简单。 缺点：速度上不去，机器各部件利用率低。,所以，提出让不同机器指令的解释在时间上能重叠进行的重叠解释方式。,5.1重叠方式,5.1.1重叠原理和一次重叠 2指令的重叠解释方式： 指令的重叠解释方式是中小型计算机及高档微型计算机组成中常用的一种控制方式，它使

4、机器语言程序的执行速度比采用顺序解释方式的有较大提高。,5.1重叠方式,5.1.1重叠原理和一次重叠 2指令的重叠解释方式：,5.1重叠方式,5.1.1重叠原理和一次重叠,3重叠解释对计算机组成提出的要求,一般机器，操作数和指令混合存储于同一主存体内，而且主存同时只能访问一个单元。,访主存,分析中取操作数也可能访主存,5.1重叠方式,5.1.1重叠原理和一次重叠,3重叠解释对计算机组成提出的要求,所以要求在硬件上花费一定代价解决访主存的冲突。,访主存,分析中取操作数也可能访主存,5.1重叠方式,5.1.1重叠原理和一次重叠,3重叠解释对计算机组成提出的要求,在硬件上解决访主存冲突的方法：,方法

5、一：让操作数和指令分别存放于两个独立编址且可同时访问的存储器中。 有利于实现指令的保护；但增加了主存总线控制的复杂性及软件设计的麻烦。,5.1重叠方式,5.1.1重叠原理和一次重叠,3重叠解释对计算机组成提出的要求,在硬件上解决访主存冲突的方法：,方法二：仍然维持指令和操作数混存，但采用多体交叉主存结构。 解决有局限。,5.1重叠方式,5.1.1重叠原理和一次重叠,3重叠解释对计算机组成提出的要求,在硬件上解决访主存冲突的方法：,方法三：增设指令缓冲寄存器（指缓）。可以乘主存有空时，预先把下一条或下几条指令取出来放在指缓中，这样“分析k”和“取指k+1”重叠。,5.1重叠方式,5.1.1重叠原

6、理和一次重叠,4一次重叠解释方式,由于从指缓中取指令，使得“取指k+1”时间很短，完全可以把这个微操作合并到“分析k+1”中，那么重叠变成了“分析k+1”和“执行k”的重叠。如图5-3。,5.1重叠方式,5.1.1重叠原理和一次重叠,4一次重叠解释方式,称这种指令分析部件和指令执行部件任何时候都只有相邻两条指令在重叠解释的方式为“一次重叠”。,5.1重叠方式,5.1.1重叠原理和一次重叠,4一次重叠解释方式,为实现一次重叠要求：,（1）在硬件上保证有独立的指令分析部件和指令的执行部件。,5.1重叠方式,5.1.1重叠原理和一次重叠,4一次重叠解释方式,为实现一次重叠要求：,（2）在硬件上解决好

7、控制上的同步，保证任何时候都只是“执行k”和“分析k+1”一次重叠。,5.1重叠方式,5.1.1重叠原理和一次重叠,4一次重叠解释方式,由于多次重叠不仅要设置多套指令分析和指令执行部件，控制还相当复杂，所以重叠方式的机器大多数采用一次重叠。如果仍达不到速度要求，宁可采用流水方式。,5.1重叠方式,5.1.1重叠原理和一次重叠,4一次重叠解释方式,为实现一次重叠要解决控制上的问题：,（1）当遇到条件转移并且转移成功时，重叠方式变成了顺序方式，如图5-4。,图5-4 当K条指令是条件转移指令时,5.1重叠方式,5.1.1重叠原理和一次重叠,4一次重叠解释方式,为实现一次重叠要解决控制上的问题：,（

8、1）当遇到条件转移并且转移成功时，重叠方式变成了顺序方式，如图5-4。,图5-4 当K条指令是条件转移指令时,5.1重叠方式,5.1.1重叠原理和一次重叠,4一次重叠解释方式,为实现一次重叠要解决控制上的问题：,（1）当遇到条件转移并且转移成功时，重叠方式变成了顺序方式，如图5-4。,图5-4 当K条指令是条件转移指令时,5.1重叠方式,5.1.1重叠原理和一次重叠,4一次重叠解释方式,为实现一次重叠要解决控制上的问题：,（1）当遇到条件转移并且转移成功时，重叠方式变成了顺序方式，因此采用重叠方式的机器应尽量减少程序中条件转移指令的使用。可采用延迟转移技术。,（2）解决好邻近指令之间有可能出现

9、的某种关联。,5.1重叠方式,5.1.2相关处理,1转移指令的处理,采用延迟转移技术：,将转移指令与其前面的一条或多条指令对换位置（由编译程序生成时调整），让成功转移总是在紧跟的指令被执行之后发生，从而使预取的指令不作废，就可省了一个机器周期。,指令地址 指令 功能 210 取X,Rd (X)Rd 211 加Rd,#1,Rd (Rd)+1Rd 212 条转,215 条件满足转215 213 加Rd,R0,Rd (Rd)+(R0)Rd 214 减Rb,Rc,Rb (Rb)-(Rc)Rb 215 存Rd,Y (Rd)Y 216 ,指令地址 指令 功能 210 取X,Rd (X)Rd 211 条转,

10、215 条件满足转215 212 加Rd,#1,Rd (Rd)+1Rd 213 加Rd,R0,Rd (Rd)+(R0)Rd 214 减Rb,Rc,Rb (Rb)-(Rc)Rb 215 存Rd,Y (Rd)Y 216 ,5.1重叠方式,5.1.2相关处理,2指令相关的处理,出现指令相关的原因是冯诺依曼机器的指令允许修改。所以若规定在程序运行过程中不准修改指令，就不会出现指令相关。,5.1重叠方式,5.1.2相关处理,2指令相关的处理,如果需要在程序运行中修改指令，可通过设置“执行”指令来解决，例如IBM370的“执行”指令，被修改的指令是以“执行”指令的操作数形式出现的，将指令相关转换成了数相关

11、，所以只需统一按数相关处理就可以了。,IBM370的“执行”指令,形式为： 执行到“执行”指令时， 按第二操作数 (X2)+(B2)+D2地址取 出操作数区中单元的 内容作为指令来执行， 参见图5-6。,5.1重叠方式,5.1.2相关处理,3主存空间数相关的处理,主存空间数相关就是相邻两条指令之间出现要求对主存同一单元先写入而后再读出的关联。如图5-7(a),5.1重叠方式,5.1.2相关处理,3主存空间数相关的处理,要想避免出错，只有推后“分析k+1”的读。 如图5-7(b),5.1重叠方式,5.1.2相关处理,4通用寄存器组相关的处理,设机器的基本指令格式：,第一操作数寄存器号,运算结果寄

12、存器号,相对位移量,形成第二操作数地址的基址值所在通用寄存器,5.1重叠方式,5.1.2相关处理,4通用寄存器组相关的处理,微操作时间关系：,在指令解释过程中，使用通用寄存器作为不同用途所需的有关微操作的时间要求是不同的。,5.1重叠方式,5.1.2相关处理,4通用寄存器组相关的处理,微操作时间关系：,-8,（1）通用寄存器组数相关的情况和处理办法（如图5.8）,L1相关： L3（k）=L1（k+1） L2相关： L3（k）=L2（k+1）,解决通用寄存器组数相关的办法,1）推后读（牺牲速度）的办法： 办法一：推后“分析k+1”的读到“执行k”结束时开始。 此办法，只要发生数相关就使得一次重叠

13、变成了完全的顺序串行，速度明显下降。,办法二：把“分析k+1”推后到“执行k”把结果送入L3时，保证“分析k+1”在取（L1）或（L2）时能取到所需要的。,此办法，发生数相关时，相邻两条指令的解释仍有部分重叠，与办法一比较，可以减少速度损失，但控制复杂。,2）不降低速度的办法： 办法三：设置相关专用通路的办法。 如果在运算器的输出到B、C输入之间增设一条“相关专用通路”（硬件），如图5.9所示，在发生L1或L2相关时，让相关专用通路接通，就可以在“执行k”时将运算结果送入通用寄存器以在完成其应用的功能的同时，直接将运算结果送回到B或C寄存器，从而大大缩短了期间的传送时间，并能保证“执行k+1”

14、需要此操作数时，它已经在B或C寄存器中准备好了,解决通用寄存器组数相关的办法,3）两种办法比较：,推后“分析k+1”和设置“相关专用通路”是解决重叠方式相关的两种基本方法。 前者以降低速度为代价，使设备基本不增加。 后者以增加设备为代价，使重叠效率不下降。,（2）通用寄存器组基址或变址值相关的情况及处理办法：,（以基址值相关为例）设操作数的有效地址 （Xd）+（B2）+d2相关的发生如图5.10,解决通用寄存器组基址值相关的办法：,1）推后分析法： 对于B二次相关，只需推后“分析k+2”的始点，使“执行k”送入通用寄存器的运算结果，在“分析k+2”开始时已经出现在通用寄存器的输出总线上。图5.

15、11（a） 对于B一次相关，则除此之外，还要推后一个“执行”周期。如图5.11（b）,图5.11,2）设置相关专用通路： 办法与图5.9类似，如图5.12所示 由于B一次、二次相关的概率并不低，所以设置专用通路是值 得的。二次相关时，用专用通路，一次相关时用推后分析法。,解决通用寄存器组基址值相关的办法：,5.2 流水方式,5.2.1 基本概念 1工作原理 “流水”在概念上与“重叠”没什么差别，可以看成是“重叠”的进一步引申。差别在于“一次重叠”只是把一条指令的解释分解为两个子过程，而“流水”分解成更多个子过程。 “重叠”同时解释两条指令，“流水”同时解释多条指令。如图5-15,图5-15,流

16、水线的吞吐率：流水线单位时间内能流出的任务数或结果数。 如果能把一条指令的解释分解成时间相等的m个子过程，则每隔T/m就可以处理一条指令。这意味着，流水的最大吞吐率取决于子过程所经过的时间，这个时间越小，流水线的吞吐率越高。 流水的最大吞吐率指的是当流水线满负荷流动时所达到的吞吐率。,2流水的分类,（1）按流水处理的级别不同可分为： 部件级：指构成部件内的各个子部件之间的流水。 处理机级：构成处理机的各个部件之间的流水。 系统级：构成计算机系统得多个处理机之间的流水，也称为宏流水。,（2）按流水线具有的功能多少分为： 单功能流水线：只能实现一种功能的流水处理。 多功能流水线：同一流水线的各个段

17、之间可以有多种不同的联接方式以实现多种不同的运算或功能。 （如图5-17所示，TI-ASC计算机流水线就是多功能的）,2流水的分类,图5-17,（3）按多功能流水线各段能否允许同时用于多种不同功能连接流水分为： 静态流水线：在某一时间内各段只能按一种功能连接流水，只有等流水线全部流空后才能切换成按另一种功能来连接流水。 动态流水线：各功能段在同一时间内可按不同运算或功能连接。（如图5-18所示）,2流水的分类,（4）以机器所具有的数据表示流水线处理机可分为： 标量流水处理机：没有向量数据表示，只能用标量循环方式来对向量、数组进行处理。 向量流水处理机：机器具有向量数据表示，设置有向量指令和向量

18、运算硬件，能对向量、数组中的各个元素流水地处理。,2流水的分类,（5）从流水线各功能段之间是否有反馈回路，流水线分为： 线性流水线：流水线各段串行联接，没有反馈回路，各段只经过一次。 非线性流水线：流水线中除有串行联接通路，还有某种反馈回路，一个任务流经流水线时，需多次经过某个段或越过某个段。如图5-19。,2流水的分类,图5-19,5.2.2 标量流水线的主要性能,流水线处理机 性能主要指标,吞吐率TP： 流水线单位时间里能流出的任务数或结果数,效率： 流水线中的设备实际使用时间占整个运行 时间之比，也称流水线设备的时间利用率。,1吞吐率和加速比,吞吐率：流水线单位时间里能流出的任务数或结果

19、数 最大吞吐率 实际吞吐率,5.2.2 流水线处理机的主要性能,（1）最大吞吐率,a）流水线各段经过的时间相等时：,（1）最大吞吐率,b）流水线各段经过的时间不相等时：,瓶颈子过程,最大吞吐率：,（1）最大吞吐率,b）流水线各段经过的时间不相等时：,办法一：将瓶颈子过程再细分 办法二：重复设置多套瓶颈段并联,（2）消除瓶颈,（2）消除瓶颈,a)将瓶颈子过程再细分,（2）消除瓶颈,a)将瓶颈子过程再细分,（2）消除瓶颈,b)重复设置 多套瓶颈段并联,（2）消除瓶颈,（3）实际吞吐率 a）各段时间相等,TP=,n,mt0+(n-1) t0,（3）实际吞吐率 a）各段时间相等,TP=,n,mt0+(

20、n-1) t0,实际吞吐率总是小于最大吞吐率,且只有当nm时，才能使TP接近于TPmax,加速比Sp：用来表示流水方式相对非流水线串行 方式速度提高的比值。,（3）实际吞吐率 a）各段时间相等加速比,（3）实际吞吐率 a）各段时间相等加速比,mt0,n,(m+n-1) t0,加速比:,（3）实际吞吐率 a）各段时间相等加速比,mt0,n,(m+n-1) t0,线性流水线且各段时间相同时，仅当nm时， 加速比才能趋于最大值，为流水线的段数m。,加速比:,n,（3）实际吞吐率 b）各段时间不相等,tj：瓶颈段时间,ti：第i段时间, i=1,2,m,n,（3）实际吞吐率 b）各段时间不相等,tj：

21、瓶颈段时间,ti：第i段时间,i=1,2,m,加速比:,2效率,流水线的效率： 指流水线中的设备实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。,a）线性流水线，且各段经过时间相同,2效率,对于线性流水且每段经过时间相等时，流水线的效率是正比于吞吐率的。,对于非线性流水或线性流水但各段经过的时间不等时，这种正比关系不存在，需要通过画出实际工作时的时空图分别求吞吐率和效率。,a）线性流水线，且各段经过时间相同,2效率,b）线性流水线，且各段经过时间不相同,2效率,b）线性流水线，且各段经过时间不相同,2效率,tj：瓶颈段时间,ti：第i段时间, i=1,2,m,b）线性流水线，且各段

22、经过时间不相同,2效率,tj：瓶颈段时间,ti：第i段时间, i=1,2,m,ti：第i段时间, ai： 第i段权值， i=1,2,m tj：瓶颈段时间,c）线性流水线，各段加权,2效率,c）线性流水线，各段加权,2效率,ti：第i段时间, ai： 第i段权值， i=1,2,m tj：瓶颈段时间,实际吞吐率和效率要画出时-空图，用下式求：,3复杂的非线性流水,4标量流水机的性能举例1,设有两个向量A和B，各有4个元素，要在如图所示的静态双功能流水线上，计算向量点积AB=a1b1+a2b2+a3b3+a4b4。其中，1235组成加法流水线，145组成乘法流水线。设每个流水线所经过的时间均为t，而

23、且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间和功能切换所需的时间都可以忽略不计。请求出流水线从开始流入到结果流出这段时间的实际吞吐率TP和效率。,x y,静态流水线：在某一时间内各段只能按一种功能连接流水，只有等流水线全部流空后才能切换成按另一种功能来连接流水。,4流水线工作举例1,设有两个向量A和B，各有4个元素，要在如图所示的静态双功能流水线上，计算向量点积AB=a1b1+a2b2+a3b3+a4b4。其中，1235组成加法流水线，145组成乘法流水线。设每个流水线所经过的时间均为t，而且流水线的输出结果可以直接返回到输入或暂存于相应的缓冲寄存器中，其延迟时间

24、和功能切换所需的时间都可以忽略不计。请求出流水线从开始流入到结果流出这段时间的实际吞吐率TP和效率。,x y,a1b1+a2b2+a3b3+a4b4,加法：1235 乘法：145,7,15t,34 t+43 t,515 t,=32%,5标量流水机的性能举例2,用一条5个功能段的浮点加法器流水线计算 每个功能段的延迟时间均相等设为t，流水线的输出端与输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，计算流水线的实际吞吐率和效率。,改为 重新计算,A1+A2+A3+A4+A5+A6+A7+A8,A1+A2+A3+A4+A5+A6+A7+A8+A9

25、+A10,5.2.3 标量流水机的相关处理和控制机构,流水线只有不断流动，不出现断流，才能获得高效率。,断流原因：,目的程序不能发挥流水结构的作用 存储系统供不上为连续流动所需的指令和操作数 出现了相关和中断,全局相关：转移指令和其后的指令之间存在关联。,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,局部相关原因： 在机器同时解释的多条指令之间出现了对同一主存单元或寄存器要求“先写后读”而产生的。,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,局部相关的处理方法：,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,局部相关控制机构要解决的问题： 如何

26、判定流入流水线的多条指令之间是否相关； 如何控制推后对相关单元的读； 如何设置相关专用通路并控制其连通和断开。,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,顺序流动方式：让任务流出流水线的顺序保持与流入流水线的顺序一致。,异步流动方式：让流出流水线的任务顺序可以和流入流水线的顺序不同。,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,任务在流水线中流动顺序,指令串：h、i、j、k、l、m、n、,指令j的源操作数与指令h的目的操作数同一地址,5.2.3 标量流水机的相关处理和控制机构,任务在流水线中顺序

27、流动,1局部相关的处理,h与j发生 “先写后读”相关,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,任务在流水线中异步流动,5.2.3 标量流水机的相关处理和控制机构,如果让j之后的指令，只要与j没有相关，就越过j继续向前流动，就可以使指令在流水线内部顺序流动。,任务在流水线中异步流动发生其它相关：,1局部相关的处理,对同一单元，要求在先的指令先写入，在后的指令后写入的关联。,对同一单元，要求在先的指令先读出，在后的指令才写入的关联。,5.2.3 标量流水机的相关处理和控制机构,h:R0=R1R4 i：R6=R5+1 j:R2=R0R3 k:R3=R4-1 l:R2=R5 m:

28、,1局部相关的处理,任务在流水线中异步流动发生其它相关：,h与j：先写后读相关,j与k：先读后写相关,j与l：写写相关,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,在流水线的读操作数段设置一个相联比较器，在指令读操作数之前，把源操作数地址与已经在流水线中的、从读操作数功能段到写结果功能段之间的所有指令的目标地址进行比较，若发现有一个地址是相等的，则表明发生“先写后读”相关。,数据相关的测试 “先写后读”相关：,5.2.3 标量流水机的相关处理和控制机构,先写后读相关测试,空间,时间,j源操作数地址,读段设置相联比较器,相联比较,数据相关的测试 “先读后写”“写写”相关：,1局

29、部相关的处理,在流水线的写功能段设置一个相联比较器，把自己的目标操作数地址分别与已经进入流水线的、指令序号比自己小的源操作数地址和目标操作数地址比较，若发现与某一条指令的源操作数地址相等，说明发生了“先读后写”相关，若发现与某一条指令的目标地址相等，则说明发生了“写写”相关。,5.2.3 标量流水机的相关处理和控制机构,1局部相关的处理,采用异步流动方式，控制机构应能同时处理好三种相关：,主要采用“推后执行”和设置“相关直接通路”两种基本方法。,参考： 郑伟民，汤志忠，计算机系统结构，清华大学出版社,5.2.3 标量流水机的相关处理和控制机构,指已进入流水线的转移指令（尤其是条件转移指令）和其

30、后续指令之间的相关。,2全局相关的处理,5.2.3 标量流水机的相关处理和控制机构,处理方法1：猜测法,2全局相关的处理,5.2.3 标量流水机的相关处理和控制机构,处理方法1：猜测法,2全局相关的处理,5.2.3 标量流水机的相关处理和控制机构,2全局相关的处理,分支选择：,处理方法1：猜测法,两个分支概率相近时，宜选不成功分支,5.2.3 标量流水机的相关处理和控制机构,2全局相关的处理,分支选择：,处理方法1：猜测法,两个分支概率相近时，宜选不成功分支,两分支概率不均等时，宜选高概率分支,转移概率统计：静态根据转移指令类型预测（需事先统计）、或根据执行期间转移的历史状况预测（准确度可达9

31、0%）。,5.2.3 标量流水机的相关处理和控制机构,2全局相关的处理,猜错时分支点现场的恢复：,处理方法1：猜测法,办法1：对指令只译码和准备好操作数，在转移条件码出现之前不进行运算。,（不方便）,办法2：运算完，但不送回运算结果。,5.2.3 标量流水机的相关处理和控制机构,2全局相关的处理,猜错时分支点现场的恢复：,处理方法1：猜测法,办法3：后援寄存器法。,与正常情况一样，不加区别地全部解释完，把可能被破坏的原始状态都用后援寄存器保存起来，一旦猜错就取出后援寄存器的内容来恢复分支点的现场。,（效率高）,5.2.3 标量流水机的相关处理和控制机构,2全局相关的处理,猜错时分支的转移：,处

32、理方法1：猜测法,为猜错时尽快回复到原分支点，转入另一分支： 在沿猜测（转移不成功）路径向前流动的同时，预取转移成功分支指令放入转移目标指缓中。,猜错时，不必访存取p，减少流水线等待时间。,5.2.3 标量流水机的相关处理和控制机构,2全局相关的处理,处理方法2：加快和提前形成条件码,措施1：加快加快单条指令内部条件码的形成。不等指令执行完，就提前形成反映运算结果的条件码。,措施2：在一段程序内提前形成条件码。 适合于循环型程序在判断是否继续时的转移情况。,5.2.3 标量流水机的相关处理和控制机构,2全局相关的处理,处理方法3：采取延迟转移,在编译生成目标指令程序时，将转移指令与其前面不相关

33、的一条或几条指令交换位置。,5.2.3 标量流水机的相关处理和控制机构,2全局相关的处理,处理方法4：加快短循环程序的处理,1：可将长度小于指令缓冲器容量的短循环程序整个一次性放入指缓，并暂停预取指令，减少访主存重复取指次数。,2：由于循环分支概率高，因此让循环出口端的条件转移指令恒猜循环分支，减少因条件分支流水断流的机会。,5.2.3 标量流水机的相关处理和控制机构,3流水机器的中断处理,中断会引起流水线断流，但概率比条件转移低得多，且随机发生。,流水机器处理中断 主要是如何处理好断点现场的保存和恢复，而不是如何缩短流水线的断流时间。,5.2.3 标量流水机的相关处理和控制机构,3流水机器的

34、中断处理,顺序解释方式断点特点：,执行指令 i时有中断,顺序解释方式,5.2.3 标量流水机的相关处理和控制机构,断点,3流水机器的中断处理,流水机器断点特点：,流水线解释方式,5.2.3 标量流水机的相关处理和控制机构,3流水机器的中断处理,流水机器断点处理方法：,早期不精确断点法：,不利于编程和程序排错。,禁止未进入流水的指令进入,转入中断处理程序,仅当指令i在第1段响应中断时，断点是精确的。,无论i在流水 线哪一段 发生中 断,5.2.3 标量流水机的相关处理和控制机构,3流水机器的中断处理,流水机器断点处理方法：,后来精确断点法：,不论指令i是在流水线的哪一段响应中断，给中断处理程序的

35、现场都是对应i的，i之后流入流水线的指令的原有现场都能保存和恢复（需要设置很多后援寄存器来保证）。,中断现场,存入后援寄存器,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,非线性流水线需要调度，线性流水线不需要。,(1)单功能流水线调度,预约表表示任务使用流水线各段的时间关系。,延迟禁止表表示相邻两个任务进入流水线禁止的间隔拍数。,形成初始冲突向量,构成流水线状态图,得到流水线调度方案,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度预约表,设流水线由K段组成，任务经流水线共需要N拍。,5.2.3 标量流水机的相关处理和控制机构,5.2.3 标量流水

36、机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔1拍,F= ,1，,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔5拍,F= ,1，,5，,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔6拍,F= ,1，,5，,6，,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔其它拍（2拍）,5.2.3 标量流水机的相关处理和控制机构,4流水线调

37、度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔其它拍（3拍）,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔其它拍（4拍）,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔其它拍（7拍）,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔其它拍（8拍）,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 延迟禁止表（F）,以第二段为例：间隔

38、其它拍（9拍）,4流水线调度,(1)单功能流水线调度延迟禁止表（F）,F= 1，5，6，8 ,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度冲突向量（C）,设流水线由K段组成，任务经流水线共需要N拍。,用一个有N-1位的位向量表示后继新任务间隔各种不同拍数送入流水线时，是否会发生功能段使用的冲突。,5.2.3 标量流水机的相关处理和控制机构,冲突向量：（CN-1，CN-2，C1）,4流水线调度,(1)单功能流水线调度冲突向量（C）,设流水线由K段组成，任务经流水线共需要N拍。,Ci：表示与当时相隔i拍给流水线送入后继任务是否会发生功能段的使用冲突。,Ci=“0

39、”：不发生冲突，允许送入； Ci=“1”：发生冲突，禁止送入。,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度冲突向量（C）,设流水线由5段组成，任务经流水线共需要9拍。,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度冲突向量（C）,F= 1，5，6，8 ,N=9,C=（10110001）,设流水线由5段组成，任务经流水线共需要9拍。,（初始冲突向量）,第二个任务可以距第一个任务2、3、4、7拍流入流水线,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度冲突向量（C）,初始冲突向量C=（1011

40、0001）,间隔 2 拍流水线状态,C1=（00101100）,C2=（10110001）,C =（10111101）,按位或,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度冲突向量（C）,2拍后冲突向量C=（10111101）,再间隔 2 拍流水线状态,C =（00101111）,C3=（10110001）,C =（10111111）,按位或,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度状态转移图,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度状态转移图,10110001,00010110

41、,按位或,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度状态转移图,00001011,10110001,按位或,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度状态转移图,00010111,10110001,按位或,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度状态转移图,5.2.3 标量流水机的相关处理和控制机构,00000001,10110001,按位或,4流水线调度,(1)单功能流水线调度状态转移图,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 调度方案

42、,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 最佳调度方案,平均间隔拍数最小 吞吐率最高,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(1)单功能流水线调度 最佳调度方案,（3，4）是最佳方案， （4，3）不是最佳方案。,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(2)多功能流水线调度预约表,将对应每种功能的预约表都重叠在一起,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(2)多功能流水线调度冲突向量,本例对应有4个交叉冲突向量：,VAA，VBB，VAB，VBA,5.2.3 标量流水机的相关处理和控制机构,4流水

43、线调度,(2)多功能流水线调度延迟禁止表,FBB=2，3,FAA=2，3,FAB=1，2，4,FBA=2，4,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(2)多功能流水线调度冲突向量,FBB=2，3,FAA=2，3,FAB=1，2，4,FBA=2，4,VBB=（0110）,VAA=（0110）,VAB=（1011）,VBA=（1010）,5.2.3 标量流水机的相关处理和控制机构,VAB=（1011）,VAA=（0110）,VBB=（0110）,VBA=（1010）,4流水线调度,(2)多功能流水线调度冲突矩阵,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(2)多

44、功能流水线调度状态转移图,5.2.3 标量流水机的相关处理和控制机构,0011 0101,0110 1010,0111 1111,A1,0110 1010,1011 0110,MA,MB,0000 0000,0110 1010,A4,0110 1010,1011 0110,0111 1111,MA,MB,A1,1011 0111,0011 0101,1011 0110,B1,0110 1010,1011 0110,0111 1111,MA,A4,MB,A1,0111 1010,A3,0001 0000,0110 1010,0110 1010,1011 0110,0111 1111,MA,A4,

45、B1,1011 0111,MB,A1,B1,0011 0101,1011 0110,0110 1010,1011 0110,0111 1111,MA,A4,B1,MB,A3,A1,B1,0110 1010,1011 0110,0111 1111,MA,A4,B1,MB,A3,A1,A3,0001 0000,0110 1010,B1,0110 1010,1011 0110,0111 1111,MA,A4,B1,MB,A3,A1,A3,B1,11110111,0101 0011,1011 0110,0111 1111,0110 1010,1011 0110,MA,MB,B3,B3,A4,B1,B1

46、,A3,A1,B1,A3,11110111,4流水线调度,(2)多功能流水线调度调度方案,根据状态图找出平均拍数最小的最佳调度方案,5.2.3 标量流水机的相关处理和控制机构,4流水线调度,(2)多功能流水线调度交叉冲突向量数量,一般，有P个功能的流水线将有P2个交叉冲突向量，它们可以分别归类写成P个冲突矩阵Mp，其中p分别为1至P。,5.2.3 标量流水机的相关处理和控制机构,5.3向量的流水处理与向量流水处理机,向量内： 各个元素之间很少相关， 且对这些元素一般执行同一种操作， 较容易发挥流水线效能，,所以 一般将向量数据表示和流水线技术结合起来，构成向量流水处理机，简称向量处理机。,目的

47、是提高面向向量数组计算类应用的计算机的速度性能。,5.3向量的流水处理与向量流水处理机,5.3.1向量的处理和向量的流水处理,向量的流水处理要研究的问题：,选择使向量运算最能充分发挥出流水线效能的处理方法。,向量流水处理方式的选择常常与所用计算机的结构紧密相连并互相影响。,向量的不同处理方式：,5.3向量的流水处理与向量流水处理机,5.3.1向量的处理和向量的流水处理,向量的不同处理方式横向（水平）处理,5.3向量的流水处理与向量流水处理机,计算：D=A*（B+C） 即：di=ai*（bi+ci）,k= bi+ci,di=ai*k,k= bi+1+ci+1,di+1=ai+1*k,宜于在标量处

48、理机上采用循环实现，难以流水。,先写后读相关,先写后读相关,d1=a1*（b1+c1） d2=a2*（b2+c2） d3=a3*（b3+c3） ,5.3.1向量的处理和向量的流水处理,向量的不同处理方式纵向（垂直）处理,5.3向量的流水处理与向量流水处理机,计算：D=A*（B+C） 即：di=ai*（bi+ci）,ki= bi+ci,di=ai*ki,使流水线发挥效能,流水,ki+1= bi+1+ci+1,ki+2= bi+2+ci+2,di+1=ai+1*ki+1,di+2=ai+2*ki+2,d1=a1*（b1+c1） d2=a2*（b2+c2） d3=a3*（b3+c3） ,5.3.1向

49、量的处理和向量的流水处理,向量的不同处理方式纵向（垂直）处理,5.3向量的流水处理与向量流水处理机,早期：存贮器存贮器结构,向量运算指令的源向量和目的向量放在主存中。,要求必须显著提高主存与流水处理机间的信息流量，才能支持流水线的连续流动。,5.3.1向量的处理和向量的流水处理,向量的不同处理方式纵向（垂直）处理,5.3向量的流水处理与向量流水处理机,早期：存贮器存贮器结构,向量运算指令的源向量和目的向量放在主存中。,要求必须显著提高主存与流水处理机间的信息流量，才能支持流水线的连续流动。,但是主存并非仅供中央处理机使用。,5.3.1向量的处理和向量的流水处理,向量的不同处理方式纵向（垂直）处

50、理,5.3向量的流水处理与向量流水处理机,后来：寄存器寄存器结构,缓解主存流量和流水线的处理速度不匹配的矛盾。,5.3.1向量的处理和向量的流水处理,向量的不同处理方式分组纵横处理方式,5.3向量的流水处理与向量流水处理机,向量长度（N）太长，超出了向量寄存器组中寄存器的个数，可将向量分割成若干个组，使每个组都能装进向量寄存器组中。 这样，每一组内均按纵向方式处理，组间用软件方法编制循环程序依次循环处理。,此方式可对向量长度N不加限制。,5.3.1向量的处理和向量的流水处理,1向量处理机的指令系统,5.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,1向量处理机的指令系统,5

51、.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,向量型运算指令一般如下几种：,向量V1运算得向量V2 向量V运算得标量S 向量V1与向量V2运算得向量V3 向量V1与标量运算得向量V2,其它：,向量比较指令、向量压缩指令、归并指令、向量传送指令等。,1向量处理机的指令系统,5.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,向量指令格式,包括：,操作码、 源或目的操作数地址、 地址偏移量、 地址增量（指明向量中相邻元素间的地址步距）、 向量长度等。,2向量流水处理机的结构,5.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,以CRAY-1

52、为例（寄存器寄存器型结构）,2向量流水处理机的结构,5.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,以CRAY-1为例（寄存器寄存器型结构）,中央处理机控制部分： 256个16位的指缓，分4组，每组64个。,2向量流水处理机的结构,5.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,以CRAY-1为例（寄存器寄存器型结构）,中央处理机运算部分： 12条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算。 可由流水线功能部件直接访问的向量寄存器组V0V7、标量寄存器S0S7及地址寄存器A0A7。,6个流水线单功能部件,向量寄存器组,向量屏

53、蔽寄存器VM（64位）,标量寄存器8个,2向量流水处理机的结构,5.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,以CRAY-1为例（寄存器寄存器型结构）,Vi冲突： 并行工作的各向量指令的源向量或结果向量使用了相同的Vi。,V4V1+V2 V5V1V3,2向量流水处理机的结构,5.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,以CRAY-1为例（寄存器寄存器型结构）,功能部件冲突： 同一个功能部件被一条以上的要求并行工作的向量指令所使用。,V4V2*V3 V5V1*V6,2向量流水处理机的结构,5.3向量的流水处理与向量流水处理机,5.3.2向量流水处理机的结构,以CRAY-1为例（寄存器寄存器型结构）,只要不出现Vi冲突和功能部件冲突，各个Vi之间和各个功能部件之间都能并行工作