资源描述
第五章第五章 重叠、流水与向量处理机重叠、流水与向量处理机加速机器语言解释的两种方式加速机器语言解释的两种方式n选用更高速的器件，加快每条指令解释选用更高速的器件，加快每条指令解释n通过控制机构同时解释两条或多条指令，通过控制机构同时解释两条或多条指令，加快整个程序的解释加快整个程序的解释n1重叠基本思想重叠基本思想n处理机解释程序的方式有顺序方式、重叠处理机解释程序的方式有顺序方式、重叠方式、流水方式等。方式、流水方式等。n顺序方式：解释完一条指令再开始解释下顺序方式：解释完一条指令再开始解释下一条；一条；n重叠方式：重叠方式：K条指令还未完成，条指令还未完成，K+1条指条指令就开始令就开始一、重叠方式一、重叠方式2 重叠中要解决的问题及解决办重叠中要解决的问题及解决办法法(1)重叠引起重叠引起(取指与分析取指与分析)访存冲突访存冲突解决方式：解决方式：最好的解决方式是设置指令缓冲器最好的解决方式是设置指令缓冲器取指与分析两个微操作合并取指与分析两个微操作合并一次重叠方式一次重叠方式(2)转移指令对重叠的影响转移指令对重叠的影响n转移不成功，对重叠没有影响转移不成功，对重叠没有影响n转移成功，则此部分重叠变成了顺序转移成功，则此部分重叠变成了顺序n解决方式：延迟转移技术解决方式：延迟转移技术P163）(3)指令相关指令相关nK：STORE R1,K+1nK+1:n重叠使得第重叠使得第K条指令执行与第条指令执行与第K+1条指条指令分析同时进行，而第令分析同时进行，而第K+1条指令本身条指令本身的内容取决于第的内容取决于第K条指令的执行结果条指令的执行结果n解决方式：不允许修改指令解决方式：不允许修改指令(4)主存空间数相关主存空间数相关n相邻两条指令要求对同一存储单元先写相邻两条指令要求对同一存储单元先写后读，而重叠使得读先于写，如：后读，而重叠使得读先于写，如：nStore R1，AnAdd R2，An解决方法：推后读解决方法：推后读n实现方式：用存储控制器将写级别高于实现方式：用存储控制器将写级别高于读，从而推后读读，从而推后读(5)通用寄存器组相关通用寄存器组相关n数相关：相邻两条指令要求对同一寄存数相关：相邻两条指令要求对同一寄存器先写后读，而重叠使得读先于写器先写后读，而重叠使得读先于写n Load R1,AnAdd R1,Bn推后读：设备不变，效率降低推后读：设备不变，效率降低n设置相关专用通路：增加设备，效率不设置相关专用通路：增加设备，效率不变变n变变(基基)址值相关址值相关二、流水方式线的基本概念二、流水方式线的基本概念1 1 流水线的基本概念流水线的基本概念 (1)(1)流水的定义流水的定义 流水是重叠的引申，多次重叠流水是重叠的引申，多次重叠 流水技术是指：将一个重复的时序过程分流水技术是指：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执效地在其专用功能段上与其他子过程同时执行。行。(2)(2)流水的表示流水的表示时空图时空图 时空图从时间和空间两个方面描述了时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。表时间，纵坐标代表流水线的各个段。(3)(3)流水技术的特点流水技术的特点把一个任务分解为几个有联系的子任务，每个子过把一个任务分解为几个有联系的子任务，每个子过程由专用的功能段实现，依靠多个功能段的并行工程由专用的功能段实现，依靠多个功能段的并行工作来缩短程序的执行时间。每个子过程称为流水线作来缩短程序的执行时间。每个子过程称为流水线的的“级或级或“段段”。“段的数目称为流水线的段的数目称为流水线的“深度深度”。流水线需要有流水线需要有“通过时间通过时间”(也叫装入时间也叫装入时间)、充满时、充满时间与排空时间间与排空时间 各个功能段所需时间应尽量相等；理想状态下，流各个功能段所需时间应尽量相等；理想状态下，流水线充满后每隔时间水线充满后每隔时间t t就流出一个结果；只有输入端就流出一个结果；只有输入端能连续地提供任务能连续地提供任务,流水线的效率才能充分发挥。流水线的效率才能充分发挥。2 流水线的分类流水线的分类流水线可按不同的观点进行分类，一般来说流水线可以分为如下几种类型：(1)按功能分l单功能流水(unifunctionpipelines)只能完成固定功能。例如，浮点加法流水线，浮点乘法流水线。l多功能流水线(multifunction)流水线的各段可以进行不同的连接，从而使流水线在不同的时间或同一时间内完成不同的功能。(2)同一时间内各段之间的连接方式来分类同一时间内各段之间的连接方式来分类l 静态流水线 在同一时间内，流水线的各段只能按同一种功能的连接方式工作，只有程序中连续出现同一种运算时，流水线的效率才能得到充分的发挥。l 动态流水线 在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。优点：能提高流水线的效率。缺陷：会使流水线的控制变得复杂(3)按流水线的级别按流水线的级别 n部件级流水线部件级流水线n处理机级流水线处理机级流水线n处理机间流水线处理机间流水线部件级流水线部件级流水线也叫运算操作流水线也叫运算操作流水线(arithmetic pipelines)。就是把处理机的算术逻辑部件。就是把处理机的算术逻辑部件分段，以便为各种数据类型进行流水操作。分段，以便为各种数据类型进行流水操作。浮点加法流水线就是一种典型的功能部件级浮点加法流水线就是一种典型的功能部件级流水线。流水线。处理机级流水线处理机级流水线也叫指令流水线(instructionpipelines)，它把一条指令的执行过程分解为多个子过程，每个子过程在一个独立的功能部件中完成。处理机间流水线处理机间流水线(宏流水线宏流水线macro pipelines)这种流水线由两个或两个以上处理机通过存储器串行连接起来，每个处理机对同一个数据流的不同部分分别进行处理。前一个处理机的输出结果存入存储器中，作为后一个处理机的输入，每个处理机完成整个任务的一部分。(4)按数据表示来进行分类按数据表示来进行分类n标量流水处理机标量流水处理机(scalar pipelines processor)(scalar pipelines processor)n处理机不具有向量数据表示，仅对标量数处理机不具有向量数据表示，仅对标量数据进行处理据进行处理n 例如：例如：IBM360/91,Amdah1 470V/6IBM360/91,Amdah1 470V/6等等n向量流水处理机向量流水处理机(vector pipelines processor)(vector pipelines processor)n 处理机具有向量数据表示，并通过向量指令处理机具有向量数据表示，并通过向量指令对向量的各元素进行处理。对向量的各元素进行处理。n例如：例如：TI ASC,CRAY-ITI ASC,CRAY-I等。等。(5)按流水线是否有反馈回路按流水线是否有反馈回路l 线 性 流 水 线(l i n e a r pipelines)S1S2S3输输入入输输出出l 非线性流水线(nonlinear pipelines)(6)按流水线中，流水线输出端流出的任务与按流水线中，流水线输出端流出的任务与流水线输入的任务顺序是否相同流水线输入的任务顺序是否相同n顺序流水线顺序流水线n 任务输入的顺序与输出的顺序是相同任务输入的顺序与输出的顺序是相同的，也就是先进先出的，也就是先进先出(FIFO)(FIFO)S1S2S3输输入入输输出出S 1S 2S 3输输入入输输出出 乱序流水线乱序流水线(无序流水线，错序流水线，异步流水无序流水线，错序流水线，异步流水线线)流水线输出端流出任务的与输入端流入流水线输出端流出任务的与输入端流入任务的顺序可以不一样。任务的顺序可以不一样。3 流水线性能分析流水线性能分析(1)吞吐率吞吐率throughput rate)流水线的吞吐率流水线的吞吐率throughput rate,TP是指在单位时间内流水线所完成的任是指在单位时间内流水线所完成的任务数量或输出的结果数量。务数量或输出的结果数量。(2)加速比加速比(speedup radio)完成一批任务，不使用流水线所用的时间完成一批任务，不使用流水线所用的时间与使用流水线所用的时间之比称为水线的与使用流水线所用的时间之比称为水线的加速比加速比(speedup radio)。(3)效率效率(efficiency)流水线的效率是指流水线的设备利用率。流水线的效率是指流水线的设备利用率。3.1 吞吐率吞吐率throughput rate)单位时间内流水线所完成的任务数量或单位时间内流水线所完成的任务数量或输出的结果数量。输出的结果数量。mTnTP 式中，式中，n n为任务数，为任务数，m m为流水线的段数，为流水线的段数，TmTm是处理完成是处理完成n n个任务所用的时间。这是计算个任务所用的时间。这是计算流水线吞吐率的最基本公式。流水线吞吐率的最基本公式。连续输入且各段时间相等时连续输入且各段时间相等时1时间空间S123 n-1 nS2S3S4123 n-1 n123 n-1 n123 n-1 nmDt(n-1)DtTmS1DtS2DtS3DtS4Dt输入输入输出输出各段执行时间相等，输入连续任务情况下完成各段执行时间相等，输入连续任务情况下完成n个连续任务需要的总时间为：个连续任务需要的总时间为：=(m+n-1)=(m+n-1)t tTm=mTm=mt+(n-1)t+(n-1)*t ttnmnTPD)1(ttnmnLimTPnDD1)1(max吞吐率：吞吐率：最大吞吐率为：最大吞吐率为：连续输入但各段时间不相等时：连续输入但各段时间不相等时：1时间空间S1S2S3S4SDti(n-1)Dt2Tm23n123n123n123nS1Dt1DtS2Dt23DtS3Dt3DtS4Dt4Dt输入输入输出输出Tm=Tm=流水线完成第一个任务需要的时间流水线完成第一个任务需要的时间+完成其余完成其余n-1n-1个任个任务所需要的时间务所需要的时间=流水线每段时间之和流水线每段时间之和+(n-1)+(n-1)*m m段中最慢的一段的时间段中最慢的一段的时间DDDDmimitttnt111),.,max()1(DDDDmimitttntnTP111),.,max()1(),.,max(121maxmtttTPDDD吞吐率为：吞吐率为：最大吞吐率为：最大吞吐率为：解决流水线的瓶颈问题解决流水线的瓶颈问题1时间空间S1S2S3S4SDti(n-1)Dt2Tm23n123n123n123nS1Dt1DtS2Dt23DtS3Dt3DtS4Dt4Dt输入输入输出输出n一是将一是将“瓶颈流水段细分瓶颈流水段细分(如果可分的话如果可分的话)：n二是将二是将“瓶颈流水段重复设置：瓶颈流水段重复设置：S1输入输入输出输出DtDtS21DtDtS22DtDtS23DtDtS3DtDtS4DtDtS2(3Dt)输入输入输出输出DtDtS2-aS2-bS2-cDtDtDtDtDt23DtDt23DtS1S3S4流水段重复设置的流水线流水段重复设置的流水线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)完成一批任务，不使用流水线所用的时完成一批任务，不使用流水线所用的时间间(T0)(T0)与使用流水线所用的时间与使用流水线所用的时间(Tm)(Tm)之比之比称为流水线的加速比称为流水线的加速比(speedup radio)(speedup radio)。mTTS0n最大加速比为最大加速比为mnmnmLimSn1max)1()1(SDDnmnmtnmtnm如果流水线各段时间相等如果流水线各段时间相等 tnmD0T如果流水线各段时间不相等如果流水线各段时间不相等顺序执行需要的时间：顺序执行需要的时间：T0=T0=任务数任务数*每个任务顺序通过流水线各段所需要每个任务顺序通过流水线各段所需要的时间的时间Dmiitn1DDDDDmimimiitttnttn1211),.,max()1(S(3)效率效率(efficiency)流水线的效率是指流水线的设备利用率。定义流水线的效率是指流水线的设备利用率。定义为设备的使用时间与整个运行时间之比，即各设备实为设备的使用时间与整个运行时间之比，即各设备实际工作时间与各设备被占用际工作时间与各设备被占用(包括实际工作时间和等包括实际工作时间和等待时间待时间)时间之比。时间之比。之和各设备的整个运行时间之和各设备的实际工作时间S1Dt1DtS2Dt23DtS3Dt3DtS4Dt4Dt输入输入输出输出计算效率第一种方法：定义法计算效率第一种方法：定义法之和各设备的整个运行时间之和各设备的实际工作时间mmiiTmtnD1mTmT0流水线的工作时间设备数工作时间之和各设备为一个任务实际任务数*第二种方法：时空区法第二种方法：时空区法1时间空间S1S2S3S4SDti(n-1)Dt2Tm23n123n123n123n面积个流水段的总的时空区积个任务占用的时空区面mn计算效率第二种方法：时空区法计算效率第二种方法：时空区法面积个流水段的总的时空区积个任务占用的时空区面mnmmiiTmtnD1mTmT0流水线的整个工作时间设备数每个任务所占的面积任务数*流水线效率的计算式可以写为流水线效率的计算式可以写为流水线的整个工作时间设备数要的时间所有任务顺序执行所需*mTmT0流水线性能分析总结流水线性能分析总结(1)吞吐率吞吐率 mTTS0mTnTP 流水线的整个工作时间设备数要的时间所有任务顺序执行所需*(3)效率效率(计算式计算式)(2)加速比加速比mTmT0四、流水线工作举例四、流水线工作举例n1、连续输入一批不相关的同类任务、连续输入一批不相关的同类任务n2、输入一批不相关的任务，但不是连续、输入一批不相关的任务，但不是连续的的n3、输入一批有相关情况的任务、输入一批有相关情况的任务1、连续输入一批不相关的同类任务：、连续输入一批不相关的同类任务：例例1.1：有一条指令流水线由：有一条指令流水线由4段组成，其中每当流段组成，其中每当流经第经第3段时，总要在该段循环一次，然后才能流到段时，总要在该段循环一次，然后才能流到第第4段。如果每段经过一次所需要的时间都是段。如果每段经过一次所需要的时间都是t，问：，问：(1)当流水线的输入端连续地每隔时间当流水线的输入端连续地每隔时间 t输入任务输入任务时，会发生什么情况？时，会发生什么情况？(2)此流水线的最大吞吐率为多少？如果第隔此流水线的最大吞吐率为多少？如果第隔2 t输入一个任务，连续输入输入一个任务，连续输入10个任务的实际吞吐率和个任务的实际吞吐率和效率效率(3)当每段时间不变时，如何提高该流水线的吞吐当每段时间不变时，如何提高该流水线的吞吐率？仍连续处理率？仍连续处理10个任务时，吞吐率提高多少？个任务时，吞吐率提高多少？S1DtS2DtS32DtS4Dt输入输入输出输出S1DtS2DtS3DtS4Dt输入输入输出输出(2)解：此流水线的最大吞吐率为：解：此流水线的最大吞吐率为：tTPD21max4 4段流水线完成段流水线完成1010个任务所需要的时间为：个任务所需要的时间为：DDDDmimimtttntT111),.,max()1(=t+t+2t+t+(10-1)*2t=23t因此，流水线的实际吞吐率为因此，流水线的实际吞吐率为10/(2310/(23t)t)=(t+t+2t+t)*10/(4*23t)=50/92=54.4%流水线的效率为流水线的效率为 mTm0Tn(3)a.重复设备瓶颈段(时空图见P137，图5.21(b)b.b.瓶颈段细分瓶颈段细分(时空图见见时空图见见P137P137，图，图5.20(b)5.20(b)S1S2输输入入输输出出S4t tt tt tt tS3_2S3_1t ttnmnTPD)1(tD)1105(10=5/(7t)所以吞吐率提高的倍数为所以吞吐率提高的倍数为 ttDD231075=1.64 S1S2输输入入输输出出S4t tt t2 2t tt tS3_2S3_12 2t tn再见
展开阅读全文