计算机体系结构金星第五章重叠流水与向量之一

1、第五章第五章 重叠、流水与向量处理机重叠、流水与向量处理机加速机器语言解释的两种方式加速机器语言解释的两种方式 选用更高速的器件，加快每条指令解释选用更高速的器件，加快每条指令解释 通过控制机构同时解释两条或多条指令通过控制机构同时解释两条或多条指令，加快整个程序的解释，加快整个程序的解释 1重叠基本思想重叠基本思想处理机解释程序的方式有处理机解释程序的方式有顺序方式顺序方式、重叠方式重叠方式、流流水方式水方式等。等。顺序方式：顺序方式：解释完一条指令再开始解释下一条；解释完一条指令再开始解释下一条；重叠方式：重叠方式：k条指令还未完成，条指令还未完成，k+1条指令就开条指令就开始始一、重叠方

2、式一、重叠方式2 重叠中要解决的问题及解决办法重叠中要解决的问题及解决办法(1)重叠引起重叠引起(取指与分析取指与分析)访存冲突访存冲突解决方式：解决方式：最好的解决方式是设置指令缓冲器最好的解决方式是设置指令缓冲器取指与分析两个微操作合并取指与分析两个微操作合并一次重叠方式一次重叠方式分析k执行k分析k+1 执行k+1分析k+2 执行k+2(2)转移指令对重叠的影响转移指令对重叠的影响 转移不成功，对重叠没有影响转移不成功，对重叠没有影响 转移成功，则此部分重叠变成了顺序转移成功，则此部分重叠变成了顺序 解决方式：延迟转移技术（解决方式：延迟转移技术（p163）(3)指令相关指令相关 k：s

3、tore r1, k+1 k+1: 重叠使得第重叠使得第k条指令执行与第条指令执行与第k+1条指令分条指令分析同时进行，而第析同时进行，而第k+1条指令本身的内容取条指令本身的内容取决于第决于第k条指令的执行结果条指令的执行结果 解决方式：不允许修改指令解决方式：不允许修改指令(4)主存空间数相关主存空间数相关 相邻两条指令要求对同一存储单元先写后相邻两条指令要求对同一存储单元先写后读，而重叠使得读先于写，如：读，而重叠使得读先于写，如：store r1，aadd r2，a 解决方法：推后读解决方法：推后读 实现方式：用存储控制器将写级别高于读实现方式：用存储控制器将写级别高于读，从而推后读，

4、从而推后读(5)通用寄存器组相关通用寄存器组相关 数相关：数相关：相邻两条指令要求对同一寄存器相邻两条指令要求对同一寄存器先写后读，而重叠使得读先于写先写后读，而重叠使得读先于写 load r1, aadd r1, b推后读：设备不变，效率降低推后读：设备不变，效率降低设置相关专用通路：增加设备，效率不设置相关专用通路：增加设备，效率不变变 变变(基基)址值相关址值相关二、流水方式线的基本概念二、流水方式线的基本概念1 1 流水线的基本概念流水线的基本概念 (1) (1)流水的定义流水的定义 流水是重叠的引申，多次重叠流水是重叠的引申，多次重叠 流水技术流水技术是指：将一个重复的时序过程分是指

5、：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执效地在其专用功能段上与其他子过程同时执行。行。(2)(2)流水的表示流水的表示时空图时空图 时空图从时间和空间两个方面描述了时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。表时间，纵坐标代表流水线的各个段。(3)(3)流水技术的特点流水技术的特点把一个任务分解为几个有联系的子任务，每个子把一个任务分解为几个有联系的子任务，每个子过程由专用的功能段实现，依靠多个功能段的并

6、行过程由专用的功能段实现，依靠多个功能段的并行工作来缩短程序的执行时间。每个子过程称为流水工作来缩短程序的执行时间。每个子过程称为流水线的线的“级级”或或“段段”。“段段”的数目称为流水线的的数目称为流水线的“深度深度”。流水线需要有流水线需要有“通过时间通过时间”( (也叫装入时间也叫装入时间) )、充、充满时间与排空时间满时间与排空时间 各个功能段所需时间应尽量相等；理想状态下，各个功能段所需时间应尽量相等；理想状态下，流水线充满后每隔时间流水线充满后每隔时间t t就流出一个结果；只有输入就流出一个结果；只有输入端能连续地提供任务端能连续地提供任务, ,流水线的效率才能充分发挥。流水线的效

7、率才能充分发挥。2 流水线的分类流水线的分类流水线可按不同的观点进行分类，一般来说流水线可按不同的观点进行分类，一般来说流水线可以分为如下几种类型：流水线可以分为如下几种类型：(1) 按功能分按功能分l l 单功能流水单功能流水(unifunction pipelines) 只能完成固定功能。例如，浮点加法流水线只能完成固定功能。例如，浮点加法流水线，浮点乘法流水线。，浮点乘法流水线。l l 多功能流水线多功能流水线(multifunction) 流水线的各段可以进行不同的连接，从而流水线的各段可以进行不同的连接，从而使流水线在不同的时间或同一时间内完成不同的使流水线在不同的时间或同一时间内完

8、成不同的功能。功能。(2)同一时间内各段之间的连接方式来分类同一时间内各段之间的连接方式来分类l静态流水线静态流水线 在同一时间内，流水线的各段只能按同一种功在同一时间内，流水线的各段只能按同一种功能的连接方式工作，只有程序中连续出现同一种运能的连接方式工作，只有程序中连续出现同一种运算时，流水线的效率才能得到充分的发挥。算时，流水线的效率才能得到充分的发挥。l l 动态流水线动态流水线 在同一时间内，多功能流水线中的各段可以按在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。照不同的方式连接，同时执行多种功能。 优点：能提高流水线的效率。优点：能提高流水线的效率。

9、缺点：会使流水线的控制变得复杂缺点：会使流水线的控制变得复杂(3)按流水线的级别按流水线的级别 部件级流水线部件级流水线 处理机级流水线处理机级流水线 处理机间流水线处理机间流水线部件级流水线部件级流水线也叫运算操作流水线也叫运算操作流水线(arithmetic pipelines)。就是把处理机的算术逻辑部件。就是把处理机的算术逻辑部件分段，以便为各种数据类型进行流水操作。分段，以便为各种数据类型进行流水操作。浮点加法流水线就是一种典型的功能部件级浮点加法流水线就是一种典型的功能部件级流水线。流水线。处理机级流水线处理机级流水线也叫指令流水线也叫指令流水线(instruction pipel

10、ines)，它把一条指令的执行过程分解为多个子过，它把一条指令的执行过程分解为多个子过程，每个子过程在一个独立的功能部件中完程，每个子过程在一个独立的功能部件中完成。成。处理机间流水线处理机间流水线(宏流水线宏流水线macro pipelines)这种流水线由两个或两个以上处理机通过存这种流水线由两个或两个以上处理机通过存储器串行连接起来，每个处理机对同一个数据流储器串行连接起来，每个处理机对同一个数据流的不同部分分别进行处理。前一个处理机的输出的不同部分分别进行处理。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入，结果存入存储器中，作为后一个处理机的输入，每个处理机完成整个任务的

11、一部分。每个处理机完成整个任务的一部分。(4) 按数据表示来进行分类按数据表示来进行分类 标量流水处理机标量流水处理机(scalar pipelines processor)(scalar pipelines processor)处理机不具有向量数据表示，仅对标量数据进处理机不具有向量数据表示，仅对标量数据进行处理行处理 例如：例如：ibm360/91,amdah1 470v/6ibm360/91,amdah1 470v/6等等 向量流水处理机向量流水处理机(vector pipelines processor)(vector pipelines processor) 处理机具有向量数据表示，

12、并通过向量指令对处理机具有向量数据表示，并通过向量指令对向量的各元素进行处理。向量的各元素进行处理。例如：例如：ti asc, cray-iti asc, cray-i等。等。(5) 按流水线是否有反馈回路按流水线是否有反馈回路l 线性流水线线性流水线(linear pipelines)(linear pipelines)s1s2s3输输入入输输出出l非线性流水线非线性流水线(nonlinear pipelines)(nonlinear pipelines)(6) 按流水线中，流水线输出端流出的任务与按流水线中，流水线输出端流出的任务与流水线输入的任务顺序是否相同流水线输入的任务顺序是否相同

13、顺序流水线顺序流水线 任务输入的顺序与输出的顺序是相同的，也任务输入的顺序与输出的顺序是相同的，也就是先进先出就是先进先出(fifo)(fifo)s 1s 2s 3输输入入输输出出s 1s 2s 3输输入入输输出出乱序流水线乱序流水线( (无序流水线，错序流水线，异步流水无序流水线，错序流水线，异步流水线线) )流水线输出端流出任务的与输入端流入任务流水线输出端流出任务的与输入端流入任务的顺序可以不一样。的顺序可以不一样。3 流水线性能分析流水线性能分析(1) 吞吐率（吞吐率（throughput rate) 流水线的吞吐率（流水线的吞吐率（throughput rate,tp）是指在单位时间

14、内）是指在单位时间内流流水线所完成的任水线所完成的任务数量或输出的结果数量。务数量或输出的结果数量。(2) 加速比加速比(speedup radio) 完成一批任务，不使用流水线所用的时完成一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为水线间与使用流水线所用的时间之比称为水线的加速比的加速比(speedup radio)。 (3) 效率效率(efficiency) 流水线的效率是指流水线的设备利用率流水线的效率是指流水线的设备利用率。 3.1 吞吐率（吞吐率（throughput rate)单位时间内单位时间内流流水线所完成的任务数量或水线所完成的任务数量或输出的结果数量。输出

15、的结果数量。mtntp 式中，式中，n n为任务数，为任务数，m m为流水线的段数，为流水线的段数，t tm m是处理完成是处理完成n n个任务所用的时间。这是计算流个任务所用的时间。这是计算流水线吞吐率的最基本公式。水线吞吐率的最基本公式。连续输入且各段时间相等时连续输入且各段时间相等时1时间空间s123 n-1 ns2s3s4123 n-1 n123 n-1 n123 n-1 nmdt(n-1) dttms1dts2dts3dts4dt输入输入输出输出各段执行时间相等，输入连续任务情况下完成各段执行时间相等，输入连续任务情况下完成n个个连续任务需要的总时间为：连续任务需要的总时间为：=(m

16、+n-1)=(m+n-1)t tt tm m=m=mt+(n-1)t+(n-1)* *t ttnmntpd) 1(ttnmnlimtpndd1) 1(max吞吐率：吞吐率：最大吞吐率为：最大吞吐率为：连续输入但各段时间不相等时：连续输入但各段时间不相等时：1时间空间s1s2s3s4sdti(n-1)dt2tm23n123n123n123ns1dt1=dts2dt2=3dts3dt3=dts4dt4=dt输入输入输出输出t tm m= =流水线完成第一个任务需要的时间流水线完成第一个任务需要的时间+ +完成其余完成其余n-1n-1个任个任务所需要的时间务所需要的时间= =流水线每段时间之和流水线

17、每段时间之和+(n-1)+(n-1)* *m m段中最慢的一段的时间段中最慢的一段的时间ddddmimitttnt111),.,max() 1(ddddmimitttntntp111),.,max() 1(),.,max(121maxmttttpddd吞吐率为：吞吐率为：最大吞吐率为：最大吞吐率为：解决流水线的瓶颈问题解决流水线的瓶颈问题1时间空间s1s2s3s4sdti(n-1)dt2tm23n123n123n123ns1dt1=dts2dt2=3dts3dt3=dts4dt4=dt输入输入输出输出一是将一是将“瓶颈瓶颈”流水段细分流水段细分(如果可分的话如果可分的话)：二是将二是将 “瓶颈

18、瓶颈”流水段重复设置：流水段重复设置：s1输入输入输出输出d dts21d dts22d dts23d dts3d dts4d dts2(3d dt)输入输入输出输出d dts2-as2-bs2-cd dtd dtd dt2=3d dts1s3s4流水段重复设置的流水线流水段重复设置的流水线1时间空间2 3ns1s2-c4 5 614-2 -1n-225n-136n1 2 3n4 5 6-2 -11 2 3n4 5 6-2 -1s2-bs2-cs3s4(2) 加速比加速比(speedup radio) 完成一批任务，不使用流水线所用的时完成一批任务，不使用流水线所用的时间间(t(t0 0) )

19、与使用流水线所用的时间与使用流水线所用的时间(t(tm m) )之比之比称为流水线的加速比称为流水线的加速比(speedup radio)。mtts0 最大加速比为最大加速比为mnmnmlimsn1max) 1() 1(sddnmnmtnmtnm如果流水线各段时间相等如果流水线各段时间相等 tnmd0t如果流水线各段时间不相等如果流水线各段时间不相等顺序执行需要的时间：顺序执行需要的时间：t t0 0= =任务数任务数* *每个任务顺序通过流水线各段所需要每个任务顺序通过流水线各段所需要的时间的时间dmiitn1dddddmimimiitttnttn1211),.,max() 1(s(3)效率

20、效率(efficiency) 流水线的效率是指流水线的设备利用率。流水线的效率是指流水线的设备利用率。定义为设备的使用时间与整个运行时间之比，定义为设备的使用时间与整个运行时间之比，即各设备实际工作时间与各设备被占用即各设备实际工作时间与各设备被占用( (包括包括实际工作时间和等待时间实际工作时间和等待时间) )时间之比。时间之比。之和各设备的整个运行时间之和各设备的实际工作时间s1dt1=dts2dt2=3dts3dt3=dts4dt4=dt输入输入输出输出计算效率计算效率第一种方法：定义法第一种方法：定义法之和各设备的整个运行时间之和各设备的实际工作时间mmiitmtnd1mtmt0流水线

21、的工作时间设备数工作时间之和各设备为一个任务实际任务数*第二种方法：时空区法第二种方法：时空区法1时间空间s1s2s3s4sdti(n-1)dt2tm23n123n123n123n面积个流水段的总的时空区积个任务占用的时空区面mn计算效率第二种方法：时空区法计算效率第二种方法：时空区法面积个流水段的总的时空区积个任务占用的时空区面mnmmiitmtnd1mtmt0流水线的整个工作时间设备数每个任务所占的面积任务数*流水线效率的计算式可以写为流水线效率的计算式可以写为流水线的整个工作时间设备数要的时间所有任务顺序执行所需*mtmt0流水线性能分析总结流水线性能分析总结(1) 吞吐率吞吐率 mtt

22、s0mtntp 流水线的整个工作时间设备数要的时间所有任务顺序执行所需*(3) 效率效率(计算式计算式)(2) 加速比加速比mtmt0四、流水线工作举例四、流水线工作举例 1、连续输入一批不相关的同类任务、连续输入一批不相关的同类任务 2、输入一批不相关的任务，但不是连续的、输入一批不相关的任务，但不是连续的 3、输入一批有相关情况的任务、输入一批有相关情况的任务1、连续输入一批不相关的同类任务、连续输入一批不相关的同类任务：例例1.1：有一条指令流水线由有一条指令流水线由4段组成，其中每当流段组成，其中每当流经第经第3段时，总要在该段循环一次，然后才能流到段时，总要在该段循环一次，然后才能流到第第4段。如果每段经过一次所需要的时间都是段。如果每段经过一次所需要的时间都是t，问，问：(1)当流水线的输入端连续地每隔时间当流水线的输入