第5章重叠、流水和向量处理机.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,5,章 重叠、流水和向量处理机,5.1,重叠方式,5.2,流水方式,5.3,向量的流水处理与向量流水处理机,5.4,指令级高度并行的超级处理机,本章重点：,流水的性能分析及时空图,相关处理、流水线调度、向量指令流水的并行与链接。,本章难点：,针对所要求的重叠关系，计算全部指令完成的时间。根据题目要求画出功能静态流水时空图，计算吞吐率、效率和加速比。单功能非线性流水线的调度。向量指令间的并行、链接、串行的判断及所需拍数的计算。,5.1,重叠方式,5.1.1,基本思想和一次重叠,一条指令的执行过程可以分为多个阶段，,如：,取指,分析,执行,可以有多种处理方式：顺序执行、一次重叠、,二次重叠,。,1,、顺序解释：,各条指令之间顺序串行地进行；每条指令内部的各个微操作也顺序串行地进行。,2,、,解释一条机器指令的微操作可归并成,取指令，分析和执行,三个部份,执行,n,条指令所用的时间为：,如果每段时间都为,t,，,则执行,n,条指令所用的时间为：,T=3nt,对一条机器指令的解释,优点：,控制简单，节省设备。,缺点：,执行指令的速度慢，功能部件的利用率,很低。,3,、指令的重叠：,是在解释第,K,条指令的操作完成之前，就可开始解释第,K+1,条指令。,取指令,k,分析,k,执行,k,取指令,k+1,分析,k+1,执行,k+1,取指,k+2,分析,k+2,执行,k+2,取指,k+1,分析,k+1,执行,k+1,取指,k,分析,k,执行,k,重叠解释的一种方式（二次重叠）,4,、重叠方式对计算机组成的要求,解决主存冲突问题（在同一时刻同时访问第,K,条指令的操作数和第,K+1,条指令的指令码）：,一是把操作数和指令分别存放在两个独立的存储器；二是采用多体交叉主存系统；三是增设采用先进先出方式工作的指令缓冲寄存器。,5,、一次重叠：,指令分析部件和指令执行部件任何时候只有相邻两条指令在重叠解释的方法。,分析,k,执行,k,分析,k+1,分析,k+2,执行,k+1,执行,k+2,一次重叠工作方式一次重叠,”,解释的优点,:,省硬件,简化控制,指令的执行时间缩短,功能部件的利用率明显提高。,（,1,）为了实现“执行,k,”,与,“,分析,k+1,”,，,硬件还应有独立,的指令分析部件和指令执行部件；,以增加某些硬件为代价的。,（,2,）要解决因条件转移指令带来的重叠效率下降问题；,采取延迟转移技术。,（,3,）要解决“相关”问题。,5.1.2,相关处理,1,、基本概念,“相关”：,邻近指令之间出现关联，为了防出错,让它们不能同时解释的现象；,“数相关”：,邻近两条指令的数据地址有了关联；,“指令相关”：,采用机器指令可修改的方法在第,K,条指令执行后才产生第,K+1,条指令的现象即：为了避免出错，第,k,、第,k+1,条指令就不能同时,解释。,2,、,指令相关的处理：,禁止指令修改，还可另设置一条执行指令来解决程序设计灵活性。,3,、,主存空间数相关的处理：,推后读。,推后读是指若出现相邻两条指令之间出现对主存同一单元要求先写后读的关联。,4,、,通用寄存器组相关的处理,通用寄存器组数相关的处理方法：,推后“分析,k+1”,和设置“相关专用通路”，前面降低速度为代价，后者增加硬件成本为代价。,设置“相关专用通路”,是指第,K,条指令的运算结果直接通有硬件专用通道回送到寄存器。,通用寄存器组基址值或变址值相关的处理：,方法同上类拟，只不推后分析的推后时间不同及设置“相关专用通路”回写是到访存操作数地址形成机构。,5.2,流水方式,5.2.1,基本概念,1.,流水是重叠的引申,流水,是重叠的引申：把指令的解释过程分为,更多子过程；,取指令,指令译码,取操作数,入,出,执行,指令解释的流水处理,1,时间,空间,0,t,1,t,2,t,3,t,4,t,5,2,3,4,5,1,2,3,4,5,1,2,3,4,5,1,2,3,4,5,t,6,t,7,t,8,取指令,指令译码,取操作数,执行,流水处理的时空图,流水的最大吞吐率,：指流水线满负荷每隔,t,流出一个结果时所达到的吞吐率；,流水的最大吞吐率是取决于,子过程的经过时间,t,，,t,越小，流水线的最大吞吐率就越高。,时钟信号周期不得低于速度最慢子部件的经过时间与锁存器的存取时间之和；,子过程的细分会因锁存器数增多而增大任务或指令流过流水线的时间，这在一定程度上会抵消子过程细分使吞吐率提高的好处。,2.,流水线的分类,计算机系统在不同等级上的流水线,（处理的级别）,（,1,）流水的向下扩展指的是把子过程进一步细分，让每个子过程经过的时间都同等程度地减少，吞吐率就会进一步提高；,部件级流水线（操作流水线）,。,（,2,）流水的向上扩展可理解为在多个处理机之间的流水。,系统级流水是指构成计算机系统的多个处理机之间的流水，也称为宏流水。,处理机级流水线,又称为指令流水线,(Instruction Pipelining),。,处理机,1,处理机,2,处理机,n,数据集,处理机间的流水处理,从流水线的功能的多少来分，可分为单功能流水线和多功能流水线,（流水线具有的功能）,（,1,）单功能流水线只能实现单一功能的流水。,（,2,）多功能流水线指的是同一流水线的各个段之间可以有多种不同的联接方式以实现多种不同的运算或功能。,输 入,减 阶,对阶移位,相 加,规格化,相 乘,累 加,输 出,2,1,5,4,3,6,7,8,输 入,减 阶,对阶移位,相 加,规格化,输 出,2,1,5,4,3,6,7,8,输 入,相 乘,累 加,输 出,2,1,5,4,3,6,7,8,（,a,）流水线的,功能段,（,b,）浮点加减法运,算时的联接,（,c,）定点乘法,时的联接,ASC,机器运算器的流水线,按多功能流水线的各段能否允许同时用于多种不同功能联接流水，可把流水线分为静态流水线和动态流水线,（,1,）静态流水线在某一时间内各段只能按一种功能联接流水，只有等流水线全部流空后，才能切换成按另一种功能联接流水。,（,2,）动态流水线的各功能段在同一时间内可按不同运算或功能联接。,1,时间,空间,0,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,4,1,2,3,1,2,1,输入,求阶差,对阶,尾数加,规格化,尾数乘,累加,输出,静态流水线时空图,浮点加法定点乘法,1,时间,空间,0,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,1,2,3,n,输入,求阶差,对阶,尾数加,规格化,尾数乘,累加,输出,动态流水线时空图,1,2,3,5,4,6,1,2,3,5,4,1,2,3,4,1,2,3,浮点加法,定点乘法,以机器所具有的数据表示可以把流水线处理机分为标量流水机和向量流水机,（,1,）标量流水机没有向量数据表示，只能用标量循环方式来处理向量和数组。,（,2,）向量流水机指的是机器有向量数据表示，设置有向量指令和向量运算硬件，能流水地处理向量和数组中的各个元素。,从流水线中各功能段之间是否有反馈回路，可把流水线分为线性流水和非线性流水,（,1,）流水线各段串行联接，各段只经过一次，没有反馈回路的，称为线性流水线。,每个流水段都流过一次，且仅流过一次。线性流水线能够用流水线连接图唯一表示。,（,2,）流水线除有串行联接的通路，还有反馈回路，使任务流经流水线需多次经过某个段或越过某些段，则称为非线性流水线。,在流水线的某些流水段之间有反馈回路或前馈回路。,S,1,输入,S,2,S,3,输出,前馈回路,反馈回路,一种简单的非线性流水线,流水线的其他分类方法,（,1,）按照控制方式：,同步流水线和,异步流水线。,（,2,）,顺序流水线与乱序流水线,：,乱序流水线又称为无序流水线、错序流水线或异步流水线等。,5.2.2,流水线处理机的主要性能,衡量流水线处理机的性能主要使吞吐率,（,Through Put,Rate,TP,）,和效率,（,Efficiency,）,和,加速比,。,1.,吞吐率,吞吐率使流水线单位时间里能流出的任务数或结果数。,求流水线吞吐率的最基本公式：,TP,=,n,/,T,k,n,为任务数,T,k,为完成,n,个任务所用时间,各段执行时间相等，输入连续任务情况下完成,n,个连续任务需要的总时间为：,T,k,=(,k,+,n,-1),D,t,k,为流水线的段数，,D,t,为时钟周期,1,时间,空间,S,1,2,3,n,-1,n,S,2,S,3,S,4,1,2,3,n,-1,n,1,23,n,-1,n,1,2,3,n,-1,n,k,D,t,(,n,-1),D,t,n,D,t,(,k,-1),D,t,T,吞吐率：最大吞吐率为：,各段执行时间不相等、输入连续任务情况下：,吞吐率为：,最大吞吐率为：,瓶颈子过程,：流水线中经过时间最长的子过程。,消除瓶颈的两种方法：,细化与并联；,最大吞吐率：,流水线各段执行时间不相等的解决办法,S,1,输,入,D,t,1,=,D,t,S,2,D,t,2,=3,D,t,S,3,D,t,3,=,D,t,S,4,D,t,4,=,D,t,输,出,1,时间,空间,S,1,S,2,S,3,S,4,S,D,t,i,(,n,-1),D,t,2,T,k,2,3n,1,2,3,n,1,2,3,n,1,2,3,n,一是将“瓶颈”流水段细分,(,如果可分的话,),：,二是将“瓶颈”流水段重复设置（并联）：,S,1,输入,输出,D,t,S,2-1,D,t,S,2-2,D,t,S,2-3,D,t,S,3,D,t,S,4,D,t,S,2,(3,D,t),S,1,输入,输出,D,t,1,=,D,t,S,2-1,S,2-1,S,2-1,S,3,S,4,D,t,3,=,D,t,D,t,4,=,D,t,D,t,2,=3,D,t,1,时间,空间,2,3,n,S,1,S,2-1,4,5,6,1,4,-2,-1,n,-2,2,5,n,-1,3,6,n,1,2,3,n,4,5,6,-2,-1,1,2,3,n,4,5,6,-2,-1,S,2-2,S,2-3,S,3,S,4,流水段重复设置的流水线,设一,m,段流水线各段经过的时间均为,t,0,，,则第,1,条指令从流入到流出需要,T,0,=m,t,0,的流水建立时间，之后每隔,t,0,就可流出一条指令，这样，完成,n,个任务共需时间,T=m,t,0,+(n-1),t,0,流水线在这段时间里的实际吞吐率为：,TP=n/(,m,t,0,+(n-1),t,0,)=1/,t,0,(,1+(m-1)/n),=,TP,max,/(1+(m-1)/n),不仅实际吞吐率总是小于最大吞吐率，而且只有当,nm,时，才能使实际吞吐率接近于最大吞吐率。,加速比（,Speedup,）,计算流水线加速比的基本公式：,S,=,顺序执行时间,T,0,/,流水线执行时间,T,m,（,1,）各段执行时间相等，输入连续任务情况下,加速比为：,（,2,）最大加速比为：,（,3,）,各段执行时间不等，输入连续任务情况下,实际加速比为：,如果线性流水线每段经过的时间 不等，其中瓶颈段的时间为 ，则完成,n,隔任务所能达到的,实际吞吐率为：,其加速比为：,2.,效率,流水线的效率,是指,流水线中设备的实际使用时间占整个运行时间之比，,也称流水线设备的时间利用率。,如果是线性流水线且各段经过的时间相同，则在,T,时间里，流水线各段的效率都相同，均为,0,。,即：,整个流水线的效率：,从上式可以看出，只有当,nm,时，,才趋近于,1,。对于线性流水且每段经过的时间相等时，,流水线的效率是正比于吞吐率的，即,如果流水线各段经过的时间不等，各段的效率就会不等，可以得出整个流水线的效率：,3.,流水线工作举例,设向量,A,和,B,各有,4,个元素，在下图所示的静态双功能流,水线上计算向量点积,其中，,1 2 3 5,组成加法流水线，,1 4 5,组成乘法流水线。又设每个流水线所经过的时间均为 ，流水线输出可直接返回输入或暂存于相应缓冲寄存器中，其延迟时间和功能切换时间都可忽略。请求出流水线从开始流入到结果流出这段时间的实际吞吐率,TP,和效率,。1,2,3,4,5,X,Y,Z,时间,(,t,),空间,1,2,3,4,5,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,a1,b1,a2,b2,a3,b3,a4,b4,Z,Y,输入,a1b1,a2b2,a3b3,a4b4,a1b1,a2b2,a3b3,a4b4,a1b1+a2b2,a3b3+a4b4,a1b1+a2b2,a3b3+a4b4,输出,X,流水线工作的时空图,由上图可以看出，在,15,个 时间内流出,7,个结果，其实际吞吐率,TP,为,7/,（,15,），而顺序方式所需时间为,4 3 +3 4 =24,，因此，加速比为,S,p,=24 /(15 )=1.6,该流水线的效率可用阴影区面积和全部,5,个段的总时空区面积之比求得，即,影响效率提高的因素有：,1,、静态多功能流水线按某种功能流水时，总有一些本功能用不到得段处于空闲；,2,、流水建立时，本功能要用到的某些段也有部分处于空闲；,3,、功能切换时，增加了前一功能流水的排空时间及后一功能流水的建立时间；,4,、经常需要等待把上一步计算的结果输出回授到输入，才能开始下一步的计算。,5.2.3,流水机器的相关处理和控制机构,流水机器在遇到转移指令尤其是条件转移指令时，效率也会显著下降。,转移指令和其后的指令之间存在关联，使之不能同时解释，称为,全局性相关,。,指令相关、主存操作数相关和通用寄存器组相关及基址或变址值相关，只影响相关的两条或几条指令，最多影响流水线某些段工作的推后，不会改动指缓中预取到的指令，影响是局部的，称为,局部性相关,。,1.,局部性相关的处理,重叠机器处理局部相关的方法：,（,1,）推后后续指令对相关单元的读，直至在先的指令写入完成。,（,2,）设置相关直接通路，将运算结果经相关直接通路直接送入所需部件。,任务在流水线中流动顺序的安排和控制可以有两种方式：,（,1,）,同步流动方式：,让任务（指令）流出流水线的顺序保持与流入流水线的顺序一致。,（,2,）,异步流动方式：,让流出流水线的任务（指令）顺序可以和流入流水线的顺序步同。,异步流动方式带来的新的相关：,（,1,）“写,-,写”相关,对同一单元要求在先的指令先写入，在后的指令才能写入的关联称为“写,写”相关。,（,2,）“先读后写”相关,对同一单元要求在先的指令先读出，在后的指令才写入的关联称为“先读后写”相关。,（,3,）“先写后读”相关,对同一单元要求在先的指令先写入，在后的指令才读出的关联称为“先写后读”相关。,解决方法：,推后后续指令和设置相关直接通路。,举例：,第,142,页,IBM 360/91,浮点执行部件。,2.,全局性相关的处理,全局性相关,指的是已进入流水线的转移指令（尤其是条件转移指令）和后续指令之间的相关。,（,1,）猜测法,根据历史猜测出现概率大的分支装入指缓当转移的两个分支概率不均等时，宜猜高概率分支。,采用猜测法时应能保证猜错时可恢复分支点的处原先的现场，一般有三种方法：,在机器沿猜测分支解释时，应当与正常情况下的指令解释不同。,IBM360/91,采取对指令只译码和准备好操作数，在转移条件码出现之前不运算。,另一种方法时让它运算完但不送回运算结果。,（早期使用的这两种方法都不方便）,采用后援寄存器法。,一旦猜错，就取出后援寄存器的内容来恢复分支点的现场。,（,2,）加快和提前形成条件码,不等指令执行完成提前形成条件码。,尽快、尽早获得条件码，以便提前知道流向哪个分支，会有利于流水机器简化对条件转移的处理。,两个方面的措施：,加快单条指令内部条件码的形成，不等指令执行完就提前形成反映运算结果的条件码。,在一段程序内提前形成条件码，这特别适合于循环型程序在判断循环是否继续时的转移情况。,（,3,）采取延迟转移,用软件方法将转移指令与其前面不相关的指令交换位置。,这是用软件方法进行静态指令调度的技术。,（,4,）加快短循环程序的处理,将长度小于指缓的循环程序一次性放入指缓，并暂停预取指令，,避免执行循环时由于指令预取导致指缓中需循环执行的指令被冲掉，减少了访主存重复取指的次数；,或者让循环出口端条件转移指令恒猜循环分支，,减少因条件分支造成流水线断流的机会。,3.,流水机器的中断处理,流水机器处理中断主要是如何处理好断点现场的保护和恢复，而不是如何缩短流水线的断流时间。,“不精确断点”法：,不论指令,i,在流水线的哪一段发生中断，未进入流水线的后续指令不再进入，已在流水线的指令仍继续流完，然后才转入中断处理程序。“不精确断点”法不利于编程和程序的排错。,“精确断点”法：,不论指令,i,是在流水线中哪一段响应中断，给中断处理程序的现场全都是对应,i,的，,i,之后流入流水线的指令的原有现场都能恢复。,“精确断点”法,需设置很多后援寄存器，以保证流水线内各条指令的原有现场都能保存和恢复。,4.,流水线调度,（,1,）如果每拍向流水线送入一个新的任务，非线性流水线会出现多个任务争用同一功能段的使用冲突现象。,流水线调度要解决的问题：,究竟间隔几拍送入下一个任务，才既不发生功能段使用冲突，又能使流水线有较高的吞吐率和效率。,为了对流水线的任务进行优化调度和控制，,1971,年,E.S.Davidson,等人提出使用一个,二维的预约表（,Reservation Table),。,如果有一个由,K,段组成的单功能非线性流水线，每个任务通过流水线需要,N,拍。利用类似画时空图的方法可以得到该任务使用流水线各段的时间关系表（即预约表）。,其中拍号,n,为任务经过流水线的时钟节拍号。如果任务再第,n,拍要用到第,k,段就在相应第,n,列和第,k,行的交点处用表示。现设流水线由,5,段组成，段号,k,分别为,15,，任务经过流水线总共需,9,拍，其预约表如下图所示：,1,2,3,4,5,6,7,8,9,1,2,3,4,5,拍号,n,段号,k,（,a,）单功能流水线预约表举例,7,10110001,10110111,10111101,10111011,10111111,初始状态,7,2,7,2,4,3,7,4,3,7,（,b,）单功能流水线,的状态转移图,图,5.27,流水线预约表及状态图举例,数格子的游戏，如上图,5.27,（,a,），分别数出每行中两个打勾之间的间隔数，然后把所有行的间隔数构成一个间隔集合，就是,延迟禁止表,了。,冲突向量（,C,N-1,C,i,C,2,C,1,),中第,i,位的状态表示与当时相隔,i,拍给流水线送入后续任务是否会发生功能段冲突。,如果不会发生冲突，令该位为“,0”,，表示允许送入；否则让该位为“,1”,，表示禁止送入。,冲突向量取,N-1,位是因为经,N,拍后，任务已流出流水线不会与后续的任务争用流水线功能段了。,只要按流水线状态图中由初始状态出发，能构成一种间隔拍数呈周期性重复的方案来进行流水线的调度，都不会发生功能段使用冲突。要想找出一种最佳的调度方案使流水线的吞吐率最高，只要计算出每种调度方案的平均间隔拍数，从中找出最小者即可。,由下表可见，采用先隔,3,拍后隔,4,拍轮流给流水线送入任务的调度方案使最佳的，平均每隔,3.5,拍即可流入一个任务，吞吐率最高。尽管（4,，,3,）调度方案平均间隔拍数也是,3.5,拍，但若实际流入任务数不是循环所需任务数的整数倍时，其实际吞吐率相对会低一些，所以不作为最佳调度方案。,这是一种不等间隔的调度策略，比起相等间隔的调度策略在控制上要复杂一些。,调度方案,平均间隔拍数,（,2,，,2,，,7,）,3.67,（,2,，,7,）,4.50,（,3,，,4,）,3.50,（,4,，,3,）,3.50,（,3,，,4,，,7,）,4.67,（,3,，,7,）,5.00,（,4,，,3,，,7,）,4.67,（,4,，,7,）,5.50,（,7,）,7.00,各种调度方案的平均间隔拍数的例子,（,2,）预约表及流水线调度过程,根据预约表写出延迟禁止表,F,；,由延迟禁止表形成冲突向量,C,；,由所有的向量图画出状态图；,由状态图形成最佳调度方案,。,练习：,P158,习题,5.9,延迟禁止表,F=1,，,3,，,4,，,8,（第一行间隔,8,，第二行间隔,1,，第三行间隔,1,，,3,，,4,，然后间隔都为,1,，合并）,冲突向量为,C,：,10001101,（写一个,8,位两进制数，根据禁止表倒着写）,画出状态图,（如图，当第二个任务在第二拍进入时，冲突向量,C1,为,10101111,，又分为两种情况：当第三个任务在第,5,拍进入时，冲突向量,C2,等于,C0,，当第三个任务在第,7,拍进入时，冲突向量,C2,也等于,C0,），这时你就可以画出最右边的三条线。以此类推，画出所有连线，这题倒也简单，一共有两个冲突向量，比例子好多了。）,写出各种方案的平均延迟表：,（,2,，,7,）,4.5 (2,5)3.5 (6,7)6.5 (6,5)5.5 (5)5 (7)7,从第一个向量出发，找出所有回路，把回路上的拍数按顺序写下来，并求出这些拍数的平均数,最小延迟调度方案为（,2,，,5,）,根据方案画出时空图，求效率和吞吐量（这是上节的内容了，大家自己做做吧）,5.3,向量的流水处理与向量流水处理机,5.3.1,向量的流水处理,不同的向量处理方式会对流水处理机的结构、组成提出不同的要求，而结构和组成不同的向量处理机反过来也会要求采用不同的向量流水处理方式。,举例：,计算,D=A*(B+C),，其中,A,、,B,、,C,、,D,都是有,N,个元素的向量。,横向（水平）处理方式：,先求,K=B+C,再求,A*K,，然后重复；,采用逐个求,D,向量元素的方法，即访存取,a,i,、,b,i,、,c,i,元素求,d,i,再取,a,i+1,、,b,i+1,、,c,i+1,求,d,i+1,然后重复。,宜于在标量处理机上用循环程序实现，但却难以使流水线连续流动。,纵向（垂直）处理方式：,先求所有的,K=,（,B+C,），再求所有的,A*K,。,即按,bi+ci,ki,（,i,从,1,到,N,），然后再,ki,ai,di,（,i,从,1,到,N),。,在,ASC,流水机上，将上述向量运算由横向处理改为纵向处理，就是向量的流水处理，流水线就能每拍流出一个结果元素。,分组纵横处理方式：,把该向量分割成若干个组，使每个组都能装入向量寄存器中，每组内均按纵向方式处理，组间采用软件方法编制循环程序的方式依次循环处理。,这种分组纵横处理的方式，就可以对向量的长度,N,大小不加限制。,CRAY-1,就是采用这种方式来进行向量的流水处理的。,以一个简单的,C,语言编写的程序为例，说明向量的三种处理方式的工作原理。,for(i=1,；,i=n,；,i+),yi,=,ai,(,bi,+,ci,);,（,1,）,横向处理方式,也称为水平处理方式，横向加工方式等。,逐个分量进行处理：假设中间结果为,T(I),计算第,1,个分量：,T(1),B(1),C(1)Y(1),A(1),T(1),计算第,2,个分量：,T(2),B(2),C(2)Y(2),A(2),T(2),计算最后一个分量：,T(N),B(N),C(N)Y(N),A(N),T(N),存在两个问题：,在计算向量的每个分量时，都发生写读数据相关。流水线效率低。如果采用多功能流水线，必须频繁进行流水线切换。,横向处理方式对向量处理机不适合,即使在标量处理机中，也经常通过编译器进行指令流调度。,（,2,）纵向处理方式,也称为垂直处理方式，纵向加工方式等。,T(1)=B(1)+C(1)T(2)=B(2)+C(2),T(n,)=,B(n,)+,C(n,)Y(1)=A(1)T(1)Y(2)=A(2)T(2)Y(N)=A(N)T(N),采用向量指令只需要,2,条：,VADDB,，,C,，,T VMULA,，,T,，,Y,这种处理方式适用于向量处理机,数据相关不影响流水线连续工作。不同的运算操作只需要切换,1,次。,（,3,）纵横处理方式,用于寄存器,-,寄存器结构的向量处理机中,向量寄存器的长度是有限的，,例如,，每个向量寄存器有,64,个寄存器。当向量长度,N,大于向量寄存器长度,n,时，需要分组处理。,分组方法：,，其中：为余数，共分组。,组内采用纵向处理方式，组间采用横向处理方式。因此，也称为分组处理方式，纵横向加工方式等。,运算过程为：,第组：,T(1,n)=B(1,n)+C(1,n)Y(1,n)=A(1,n)T(1,n),第组：,T(n+1,2n)=B(n+1,2n),C(n+1,2n)Y(n+1,2n)=A(n+1,2n)T(n+1,2n),最后第,k+1,组：,T(kn+1,N)=B(kn+1,N)+C(kn+1,N)Y(kn+1,N)=A(kn+1,N)+T(kn+1,N),每组用两条向量指令，每组发生数据相关两次，,其中组内发生数据相关一次，组间切换时发生数据相关一次。,优点：减少访问主存储器的次数,例如：中间变量,T,不写入主存储器。,5.3.2,向量流水处理机,以,CRAY-1,机为例，说明面向寄存器,-,寄存器型向量流水处理的一些结构特点。,（,1,）组成,CRAY-1,是由中央处理机、诊断维护控制处理机、大容量磁盘存储子系统、前端处理机组成的功能分布异构型多处理机。中央处理机的控制部分里有总容量为,256,个,16,位的指令缓冲器，分成,4,组，每组,64,个。,中央处理机的运算部件有,12,条可并行工作的单功能流水线，可分别流水地进行地址、向量、标量的各种运算。另外还有可为流水线功能部件直接访问的向量寄存器组,V,0,-V,7,、标量寄存器,S,0,-S,7,及地址寄存器,A,0,-A,7,。,（,2流水线单功能部件,6,个流水线单功能部件：,整数加、逻辑运算、移位、浮点加、浮点乘和浮点迭代求倒数，,其流水经过的时间分别为,3,、,2,、,4,、,6,、,7,和,14,拍。一拍为,12.5ns,。任何一条流水线，只要满负荷流动，都可以每拍流出一个结果分量。,（,3,）,向量寄存器,向量寄存器部分由,512,个,64,位的寄存器组成，分成,8,组，编号为,V,0,V,7,。每个向量寄存器组,v,i,可存放最多含,64,个分量（元素）的一个向量。因此向量寄存器组部分同时可存放,8,个向量。对于长度超过,64,个分量的长向量可以由软件加以分段处理，每段,64,个分量。,为处理长向量而形成的程序结构称为向量循环。每经过一次循环，处理一段。分段中，余下不足,64,个分量的段作为向量循环的首次循环，最先处理。,（,4,）,V,i,冲突,并行工作的各向量指令的源向量或结果向量使用了相同的,V,i,。,除了相关情况之外，就是出现源向量冲突，,例如：,V,4,V,1,+V,2,V,5,V,1,V,3,（,5,）,功能部件冲突,同一个功能部件被要求并行工作的多条向量指令所使用。,例如：,V,4,V,2,*V,3,V,5,V,1,*V,6,（,6,）,四个向量指令,CRAY-1,有标量类和向量类指令共,128,条。其中有,4,种向量指令如下图所示：,V,i,访存,第,I,种,V,j,V,k,n,3,2,1,S,j,V,k,V,i,n,3,2,1,主存,主存,6,5,4,3,2,1,6,5,4,3,2,1,访存,第,II,种,第,III,种,第,种,CRAY-1,的,4,种向量指令,功能部件,功能部件,以,CRAY-1,向量处理机为例，,有四类指令，两种指令格式,(1),向量与向量操作，,Vi,Vj,OP,Vk,(2),向量与标量操作，,Vi,Sj,OP,Vk,(3),向量取，,Vi,存储器,(4),向量存，存储器,Vi,CRAY,向量处理机的指令格式,g,h,i,j,k,4,位,3,位,3,位,3,位,3,位,g,h,为操作码，,i,为目的寄存器编号,j,k,为源寄存器编号,g,h,i,j,k,g,为操作码，,h,为变址寄存器,A,的编号,i,为目的寄存器编号，,j,k,m,为形式地址,m,4,位,3,位,3,位,3,位,3,位,16,位,（,7,）通过链接技术实现向量指令之间大部,分时间并行,（以,D=A*,（,B+C,）为例）,链接技术：,利用向量指令间存在的,先写后读,的数据相关性,则可以使结果寄存器成为后继指令的操作数寄存器，通过两条有数据相关的向量指令并行执行来加快向量指令序列执行速度的技术。,基本规则：,只要操作数向量中的第一个元素可用，而且功能部件有空，向量运算可立即开始,只要不发生功能部件冲突和操作数寄存器冲突都可以通过全链接机构使数据相关指令功能并行处理适用情况：,即第,1,条指令的结果，是第,2,条指令的操作数，这时，所得到的第,1,条指令的中间结果不必要等待全部向量元素都执行完才进行第二条指令的操作，可以将从一个流水线部件得到的结果直接送入下一个功能流水线部件的向量寄存器，形成两条指令的链接。,实现链接的条件：,(1),没有向量寄存器冲突和运算部件冲突。,(2),只有第一个结果送入向量寄存器的那一,个周期可以链接。,(3),先行的两条指令产生运算结果的时间必,须相等。,(4),两条向量指令的向量长度必须相等。,例如：,有如下,3,条向量指令：,V3,AV2,V0,V1V4,V2V3,第一、二条指令没有数据相关和功能部件冲突，可以同时开始执行。第三条指令与第一、二条指令均存在写读数据相关，可以链接执行。,LD V3,，,A,；访主存,读,ADDV V2,，,V0,，,V1,；浮点加,MULTV V4,，,V2,，,V3,；浮点乘,V0,V4,V1,V2,V3,1,3,2,4,5,6,1,3,2,4,5,6,1,3,2,4,5,6,浮点加,浮点乘,D,B,C,访存,存储器,A,7,访存与浮点加并行，,再与浮点乘链接,LD V3,，,A,ADDV V2,，,V0,，,V1,MULTV V4,，,V2,，,V3,并行和链接操作图,掌握根据,P152,三条向量指令画出图,P153,图,5.30,的方法，,注意两个条件，,一是向量长度限制，二是,Vi,冲突的解决方法。,如果每一个时钟周期的延迟称为,1,拍，在,Cray-1,机中,LD,指令需要,6,拍，浮点加为,6,拍，浮点乘为,7,拍，假若向量寄存器的存与取的传送各为,1,拍，内存的传送为,1,拍，,分别计算上述三条指令不同的执行方式所需的时间。,（假设向量长度为,N,）,若三条指令串行执行，,即每次只有前条指令结束，才执行后继指令，那么三条指令执行的总时间为：,(1+6+1)+N-1+(1+6+1)+N-1+(1+7+1)+,N-1=3N+22(,拍,),若第一、二条指令并行与第三条串行：,(1+6+1)+N-1+(1+7+1)+N-1=2N+15(,拍,),若第一，二条指令并行与第三条链接：,(1+6+1)+(1+7+1)+(N-1)=N+16(,拍,),可以看出采用并行与链接后，可以很有效的改善性能。,5.4,指令级高度并行的超级处理机,5.4.1,超标量,(Superscalar),处理机,资源重复，配置多套部件，按组（一组,m,条指令）执行指令。,超标量处理机采用多指令流水线，每个,t,同时流出,m,条指令（称为度,m,）。,度为,m=3,的超标量流水处理机的流水时空图如下图所示，每三条指令为一组，执行完,12,条指令需要,7t,。,时间,（,t,）,部件,0,1,2,3,4,5,度,m=3,的超标量处理机时空图,6,7,取指,译码,存结果,执行,7,10,4,1,8,11,5,2,9,12,6,3,7,10,4,1,8,11,2,9,12,6,3,7,10,4,1,8,11,2,9,12,6,3,7,10,4,1,8,11,5,2,9,12,6,3,5,5,1,2,3,1,2,3,1,2,3,1,2,3,在超标量流水线处理机中配置多套功能部件、指令译码电路和多组总线，寄存器也备有多个端口和多组总线。,超级标量流水处理机非常适合于求解像稀疏向量或矩阵这类标量计算问题，因为它们用向量流水线处理机求解很不方便。,典型的超标量流水线处理机有,IBM RS/6000,、,DEC21064,、,Intel i960CA,、,Tandem Cyclone,等。,5.4.2,超长指令字,(VLIW),处理机,编译程序找出指令间潜在并行性，将多个能并行执行的指令或无关操作先行压缩组合在一起，形成一条多个操作段的超长指令。,VLIW,结构是将水平型微码和超标量处理两者相结合。指令字长可达数百位，多个功能部件并发工作，共享大容量寄存器堆。,每个操作段控制其中的一个功能部件，相当于同时在执行多条指令。因此硬件结构和指令系统简单，是一种单指令多操作码多数据的系统结构,(SIMOMD),，不同于,SIMD,计算机。,寄存器堆,主存,存,/,取部件,浮点加法部件,定点算逻部件,转移部件,转移,定点算逻,.,浮点乘,浮点加,存,/,取,VLIW,处理机组成和指令格式,时间,（,t,）,部件,0,1,2,3,4,5,度,m=3,时的执行时空图,6,7,取指,译码,存结果,执行,3,4,2,1,3,4,2,1,3,4,2,1,3,4,2,1,1,2,3,3,4,2,1,3,4,2,1,超长指令字处理机每条指令所需拍数比超标量处理机的少，指令译码容易，开发标量操作间的随机并行性更方便，从而可使指令级并行性较高。,但,VLIW,处理机能否成功，很大程度取决于代码压缩的效率，其结构的目标码与一般的计算机不兼容，而且指令字很长而操作段格式固定，经常使指令字中的许多字段没有操作，白白浪费了存储空间。所以,VLIW,结构思想是好的，却难以成为计算机的主流。,5.4.3,超流水线（,Superpipelining,）,处理机,时间并行性,在公共硬件上采用较短时钟周期，深度流水来提高速度。,超流水线处理机不同于超标量和,VLIW,处理机，每个,t,仍只流出一条指令，但它的,t,值很小，一台度为,m,的超流水线处理机的,t,只是基本机器周期,t,的,1/m,。所以此一条指令需花,k*m*t,的时间，,k,为一条指令所含的基本机器周期数。下图是度,m=3,的超流水线处理机工作的时空图。,时间,（,t,）,部件,0,1,2,3,4,5,每,t,流出一条指令且,度,m=3,的超流水线处理机,时空图,6,7,取指,译码,存结果,执行,7,10,4,1,8,112,9,12,5,6,3,1,2,3,1,2,3,1,2,3,1,2,3,7,10,4,1,8,11,2,9,12,5,6,3,7,10,4,1,8,11,2,9,12,5,6,3,7,10,4,1,8,11,2,9,12,5,6,3,t,t,超标量处理机利用资源重复，设置多个执行部件寄存器堆端口。超流水线处理机则着重开发时间并行性，在公共的硬件上采用较短的时钟周期，深度流水来提高速度，需使用多时钟，时钟频率高达,100MHz500MHz,。,如果一台有,k,段流水线的,m,度超流水线处理机，执行完,N,条指令的时间为,如上图所示，所需时间为：,相对常规流水线处理机加速比为：,当,N,趋于无穷大时，加速比,S,p,趋近于,m,。,第,5,章 小结,1.,重叠方式，要求达到简单应用层次。,1.1,顺序方式习重叠方式的定义和特点，重叠方式解决,访存冲突的办法。,1.2“,一次重叠”的含义及好处。,1.3,条件转移指令与后续指令之间的相关及其处理办,法。,1.4,指令相关、主存数相关、通用寄存器组的数相关和,变（基）址值相关的定义及处理相关的办法，设置,相关专用通路的作用。,1.5,给出指令间微操作重叠的时间要求，计算出执行完,若干条指令所需要的时间。,2.,流水方式，要求达到综合应用层次。,2.1,流水是重叠进一步引申的概念，流水的向上扩展与向下扩展，指令级、处理机级、系统级流水的含