计算机系统结构第3章流水线技术.ppt

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,1,第三章 流水线技术,3.1,流水线的基本概念,3.2,流水线的时空图及性能分析,3.3,流水线的相关,3.4MIPS R4000,流水线计算机,3.5,向量处理机,2,3.1,流水线的基本概念,一指令的重叠执行,1.,一条指令执行的几个过程段,1,）取指令：根据,PC,（指令计数器）从,M,（存储器）取出指令送到,IR,（指令寄存器）,2,）译码分析：译出指令的操作性质，准备好所需数据,3,）执行：将准备好的数按译出性质进行处理，主要涉及,ALU,（算术逻辑运算部件）,3.1.1,有关基本概念,3,2.,对指令执行的几种方式,1,）顺序执行,(,传统机采用,),只有在前一条指令的各过程段全部完成后，才从存储器取出下一条指令,取,译,执,取,译,执,i,条,i,+1,条,4,2),仅两条指令重叠：第,i,条指令的执行与第,i+1,条的取指重叠。,3),三条指令重叠：第,i,条指令的执行与第,i+1,条的译码及第,i+2,条的取指重叠。,i,条,取,译,执,取,译,执,i+1,条,i,条,取,译,执,i+1,条,取,译,执,i+2,条,取,译,执,5,若一条指令的过程段划分更多时，重叠组合方式更多。,重叠解释并不能加快一条指令的实现，但能加快一段程序的解释。,3.,重叠方式中所需时间表达式及所需时间计算,1,）条件：设一条指令分为三个过程段，各过程段分别用,t,取,、,t,译,、,t,执,表示。,执行,n,条指令，分别采用顺序执行、两条重叠、三条重叠。,2,）分别列出上述三种执行方式所需时间表达式,顺序执行,n*,（,t,取,+t,译,+t,执,）,两条重叠,t,取,+n*t,译,+(n-1)*,max,(t,取,t,执,)+t,执,三条重叠,t,取,+,max,(t,译,t,取,)+(n-2)*,max,（,t,取,t,译,t,执,）,+,max,(t,执,t,译,)+t,执,6,3),例子 当,n=200,，,t,取,=3t,，,t,译,=4t,，,t,执,=5t,，时，分别计算上述三种执行方式的时间。,顺序执行：,200,(3+4+5)=2400t,两条重叠：,3+200,4+(200-1),5+5=1803t,三条重叠：,3+4+(200-2),5+5+5=1007t,7,重叠方式需要解决的问题,1,）对存储器的频繁访问,有哪些访问：取指令、取操作数、存放执行结果,I/O,通道访问,.,希望存储器为多体结构，以适应多种访问源的需要。,当存储器为单体结构时，需要将访问源排队，先后顺序为：,取指令、取数据、,I/O,通道访问、存结果,2,）应具有先行控制部件,先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。,8,2,）,先行控制部件的主要内容,）先行地址站，包括先行指令地址站和先行操作数地址站；,）先行指令站，用来存放多条指令；,）先行操作数站，用来存放多个操作数；,）先行地址形成部件，用来形成先行指令地址以及先行操作数地址；,）先行操作数译码站，用来完成对多条指令的译码并保留译码输出状态。,9,3,）也应具有后行部件 后行部件：对指令执行后的结果进行处理的器件，称后行部件。包括：,后行数地址站，提供后行数存放地址。,后行数站，存放运行的结果，并且，这些结果需送存储器。,10,11,二、从重叠到流水,1,、工业生产流水线,下面通过一个例子来说明流水线的好处,:,两种方案,两种方案的工作过程对比,流水线生产过程的抽象描述,这种流水工作方式的主要特点,12,洗衣店的例子,A,B,C,D,均有一些衣物要清洗，甩干，折叠,清洗要花,30,分钟,甩干要用,30,分钟,叠衣物也需要,30,分钟,还要花费,30,分钟的时间,将衣物放在衣柜里,A,B,C,D,13,顺序操作,洗,4,个人的衣物，顺序操作需要,8,个小时,如果使用流水线作业,将需要多少时间呢,?,30,任,务,顺,序,B,C,D,A,时间,30,30,30,30,30,30,30,30,30,30,30,30,30,30,30,6,下午,7,8,9,10,11,12,1,2,上午,14,流水线作业,流水线作业洗,4,个人的衣物只需要,3.5,个小时,!,任,务,顺,序,12,2,上午,6,下午,7,8,9,10,11,1,时间,B,C,D,A,30,30,30,30,30,30,30,15,流水线,流水线无法帮助解决单个任务,的,延迟,有利于减少整个工作,全部时间,多个,任务同时操作需要不同,的资源,流水线的速率受速度,最慢,的流水段的限制,流水线各段长度不均会降低,加速比,6,下午,7,8,9,时间,B,C,D,A,30,30,30,30,30,30,30,任,务,顺,序,16,2,、流水线技术,把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。,把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。,3,、流水线中的每个子过程及其功能部件称为,流水线的级或段,，段与段相互连接形成流水线。流水线的段数称为,流水线的深度,。,17,4,、指令流水线,把指令的解释过程分解为分析和执行两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。理想情况：速度提高一倍,4,段指令流水线,18,5,、浮点加法流水线,把流水线技术应用于运算的执行过程，就形成了运算操作流水线，也称为部件级流水线。,把浮点加法的全过程分解为求阶差、对阶、尾数相加、规格化,4,个子过程。,理想情况：速度提高,3,倍,19,3.1.2,流水线的分类,流水线可按不同的观点进行分类，一般来说流水线可以分为以下几个类型。,1,、按各过程段用时是否相等分类,流水线按各过程段用时是否相等可分为,均匀流水线,和,非均匀流水线,两种。,1,）均匀流水线指的是各过程段用时全相等的流水线,2,）非均匀流水线指的是各过程段用时不全相等的流水线,20,2,、按处理的数据类型,1,）,标量流水线：用于对标量数据进行流水处理。,2,）,向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理）,按处理的数据类型可分为,标量流水处理机,和,向量流水处理机,两种。,21,3.,按流水线的规模,按流水线的规模可分为,操作流水线,、,指令流水线,和,宏流水线,。,1,）,操作流水线,是把处理机的算术逻辑部件分段，使得各种数据类型的操作能够进行流水，规模最小。,2,）,指令流水线,则是把解释指令的过程按照流水方式处理。,3,）,宏流水线,它是指由两个以上的处理机串行地对同一数据流进行处理，每个处理机完成一项任务。,22,4.,按功能分类,按流水线完成的功能是否单一，流水线可分为,单功能流水线,与,多功能流水线,两种。,1,）单功能流水线：只能完成一种固定功能的流水线。,2,）多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能。,例：,ASC,的多功能流水线,23,24,5.,按工作方式分类,流水线按工作方式可分为,静态流水线,和,动态流水线,两种。,1,）,静态流水线：,在同一时间内，多功能流水线中的各段只能按同一种功能的连接方式工作。,对于静态流水线来说，只有当输入的是一串相同的,运算任务时，流水的效率才能得到充分的发挥。,例如：,ASC,的,8,段流水线,25,2,）动态流水线,：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。,优点,灵活，能够提高流水线各段的使用率，从而提高处理速度。,缺点,控制复杂。,26,静、动态流水线时空图对比,27,6.,按连接方式分类,按照流水线的各个功能段之间是否有反馈信号，可将流水线分为,线性流水线,和,非线性流水线,。,1,）线性流水线：,流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。,2,）非线性流水线：,流水线中除了有串行的连接外，还有反馈回路,28,29,例：,在一个,5,段流水线上,9,拍完成一个任务，其预约表为：,分别写出延迟禁止表,F,和冲突向量,C,。,并请给出一种可行的调度方案。,30,7.,其他分类,除上述几种外，流水线分类还有下述几种。,1,）根据控制方式分成,顺序流水线,和,乱序流水线,。,2,）在线性流水线中，根据控制方式还可以分成,同步流水线,和,异步流水线,。,31,3.1.3,流水线的特点,1.,流水线处理的必须是连续任务，只有连续不断的任务才能充分发挥流水线的效率。,2.,流水线依靠多个功能部件并行工作来缩短程序的执行时间，实际上是把一个大的功能部件分解为多个子过程，如前述将浮点数加法器分解为,4,个子过程。,3.,流水线中的每一功能部件后面都要有一个缓冲寄存器，即所谓的锁存器，以便平滑各个功能段延时时间的不一致。,4.,流水线中各段时间应尽量相等，避免段延时过长引起的相互等待。,5.,流水线需要有,“,装入时间,”,和,“,排空时间,”,。,32,3.2,流水线的时空图及性能分析,一、时空图,时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。,4,段指令流水线的时空图,3.2.1,流水线的时空图,33,3.2.2,流水线的性能分析,吞吐率：在单位时间内流水线所完成的任务数量或输出结果的数量。,一、吞吐率,n,：任务数,T,k,：处理完成,n,个任务所用的时间,34,1,、各段时间均相等的流水线,各段时间均相等的流水线,时空图,35,流水线完成,n,个连续任务所需要的总时间为,（假设一条,k,段线性流水线）,Tk,k,t,(,n,-1),t,(,k,n,-1),t,流水线的实际吞吐率,最大吞吐率,36,最大吞吐率与实际吞吐率的关系,流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数,k,以及输入到流水线中的任务数,n,等有关。,只有当,n,k,时，才有,TPTP,max,。,37,2,、各段时间不完全相等的流水线,各段时间不等的流水线及其时空图,举例（,时空图,）,一条,4,段的流水线,S1,，,S3,，,S4,各段的时间：,t,S2,的时间：,3,t,（瓶颈段）,流水线中这种时间最长的段称为流水线的瓶颈段。,38,39,各段时间不等的流水线的实际吞吐率：,（,ti,为第,i,段的时间，共有,k,个段）,流水线的,最大吞吐率,为,40,3,、解决流水线瓶颈问题的常用方法,1,）细分瓶颈段,例如：对前面的,4,段流水线,把瓶颈段,S3,细分为,3,个子流水线段：,S3a,，,S3b,，,S3c,改进后的流水线的吞吐率：,41,2),重复设置瓶颈段,缺点：控制逻辑比较复杂，所需的硬件增加了。,例如：对前面的,4,段流水线,重复设置瓶颈段,S3,：,S3a,，,S3b,，,S3c,42,重复设置瓶颈段后的时空图,43,二、加速比,流水线的加速比（,Speedup,S,）完成某个任务顺序执行所用时间与流水线执行所用时间之比。,假设：不使用流水线（即顺序执行）所用的间为,Ts,，使用流水线后所用的时间为,Tk,，则该流水线的加速比为,44,1,、流水线各段时间相等（都是,t,）,一条,k,段流水线完成,n,个连续任务,所需要的时间为,Tk,=(,k,n,-1),t,顺序执行,n,个任务,所需要的时间：,Ts,=,nk,t,流水线的实际加速比为,45,最大加速比,当,n,k,时，,S,k,思考：,流水线的段数愈多愈好？,46,2,、流水线的各段时间不完全相等时,一条,k,段流水线完成,n,个连续任务的实际加速比为,47,三、效率,流水线效率（,Efficiency,，,E,）是指流水线的设备利用率。在时空图上，流水线的效率定义为,n,个任务占用的时空区与,k,个功能段总的时空区之比，因此流水线的效率包含时间和空间两个方面的因素。,实际上，,n,个任务占用的时空区就是顺序执行,n,个任务的总的时间,T0,；而用一条,k,段流水线完成,n,个任务的总的时空区为,K*,Tk,，,其中,Tk,是流水线完成,n,个任务所使用的总时间，则一条,k,段流水线的效率为：,48,举例,计算：,S=a0+a1+a2+a3+a4+a5+a6+a7,对相关算式要合理分解算式,尽量分解为少相关算式：,S0=a0+a1 S4=S0+S1,S1=a2+a3 S5=S2+S3,S2=a4+a5 S6=S4+S5,S3=a6+a7,49,吞吐率：,TP=7/18,（,1/t,）,效率：,E=,（作用区域面积）,/,（完成运算所需时间矩形面积）,=,（,7*5t,）,/,（,18t*5,）,=7/18,50,3.3,流水线中的相关,3.3.1,什么是流水线相关,如果要执行算式,S=a/b+c,，要通过下列四条指令来执行。,LD R ,A,DIV R ,B,ADD R ,C,；要等,DIV,结果,ST R ,S,；存结果,第,3,条指令,ADD R ,C,执行的前提是第,2,条指令执行完毕、有了结果以后才能执行。换句话说，只有第,2,条指令没有执行完毕，结果没有出来，第,3,条指令就无法执行下去，这就出现了指令因等待前面结果，使后面没指令无法继续下去的现象，即,相关,。,51,流水线中的相关主要分为以下,3,种类型,1.,结构相关,2.,数据相关,3.,控制相关,52,3.3.2,流水线中的结构相关（资源相关）,如果某些指令组合在流水线中重叠执行时产生了资源冲突，那么我们称该流水线有结构相关。,由于访问同一个存储器而引起的结构冲突,53,对于这种冲突，通常有以下两种解决方法,解决办法,(1),：插入暂停周期，即让流水线在完成前一条指令对数据的存储器访问时，暂停取后一条指令的操作,为消除结构冲突而插入的流水线气泡,54,引入暂停后的时空图,55,解决方法,(2),：设置相互独立的指令存储器和数据存储器或设置相互独立的指令,Cache,和数据,Cache,56,3.3.3,流水线中的数据相关,如果下面的条件之一成立，则指令,j,与指令,i,数据相关：,（,1,）指令,j,使用指令,i,产生的结果,（,2,）指令,j,与指令,k,数据相关，指令,k,与指令,i,数据相关，则指令,j,与指令,i,数据相关。,第,2,个条件指出，如果两条指令之间存在类似上述的相关链，则它们之间也是相关的。这条相关链甚至可以贯穿整个程序。,57,例如：下面这一段代码存在数据相关。,Loop,：,L.D,F0,，,0,（,R1,）,/F0,为数组元素,ADD.D,F4,，,F0,，,F2,/,加上,F2,中的值,S.D,F4,，,0,（,R1,）,/,保存结果,DADDIU,R1,，,R1,，,8,/,数组指针递减,8,个字节,BNE,R1,，,R2,，,Loop,/,如果,R1R2,，则分支,58,3.3.4,流水线的控制相关,控制相关是指因为程序的执行方向可能被改变而引起的相关。,典型的程序结构是,“,if-then,”,结构。,请看一个示例：,if p1,S1,；,；,S,；,if p2,S2,；,；,59,控制相关带来了以下两个限制：,（,1,）控制相关于一个分支的指令不能被移到分支之前执行。,if,then,程序中，,then,后面的语句不能移至,if,之前执行。,（,2,）没有控制相关于一个分支的指令不能移至该分支指令之后从而受这个分支控制，如,if,then,程序中，,if,前的指令不能移至,then,部分中执行。,60,3.4 MIPS R4000,流水线计算机,MIPS(Microprocessor without Interlocked Piped Stages),系列处理机属于超流水线处理机。,3.4.1 MIPS R4000,流水线计算机基本结构和工作原理,R4000,处理器是一种流水线处理器，它所实现的,MIPS-3,指令集是一种和,DLX,类似的,64,位指令集。但是和,DLX,流水线不同，,R4000,的流水线特别考虑了流水访问存储器的操作。,61,一、基本结构,62,MIPS R4000,处理机的流水线操作,二、工作原理,由于流水线段数较多，这有利于提高时钟频率（其时钟速率可达,100-200MHz,），所以这种类型的流水又称为是,“,超级流水,”,(superpipelining),。,63,MIPS R4000,正常指令流水工作时序,一条指令的执行过程经历,8,个流水线周期。由于一个主时钟周期包含有两个流水线周期，因此，也可以认为每,4,个主时钟周期执行完一条指令。,64,3.4.2 MIPS R4000,流水线,指令序列在,MIPS R4000,流水线中重叠执行情况如图所示：,65,从上图可以看出，由于从存储器中读入的数据在,DS,段的末尾才会有效，所以其载人延迟是,2,个时钟周期，如下图所示：,66,指令序列在,R4000,流水线中的执行时空图,指令序列,时钟周期,1,2,3,4,5,6,7,8,9,LW R1,IF,IS,RF,EX,DF,DS,TC,WB,ADD R2,R1,IF,IS,RF,stall,stall,EX,DF,DS,SUB R3,R1,IF,IS,stall,stall,RF,EX,DF,OR R4,R1,IF,stall,stall,IS,RF,EX,67,对,R4000,的流水线来说，定向是十分重要的。,在,R4000,的流水线中，,ALU,输入端的定向源有,4,个：,EX/DF,、,DF/DS,、,DS/T,和,TC/WB,，如图所示，所以其对定向的控制也要比,DLX,流水线复杂得多。,68,R4000,流水线的基本分支延迟为,3,个时钟周期,69,指令序列,时钟周期,1,2,3,4,5,6,7,8,9,分支指令,IF,IS,RF,EX,DF,DS,TC,WB,延迟槽,IF,IS,RF,EX,DF,DS,TC,WB,暂停,stall,stall,stall,stall,stall,stall,stall,暂停,stall,stall,stall,stall,Stall,stall,分支目标,IF,IS,RF,EX,DF,指令序列,时钟周期,1,2,3,4,5,6,7,8,9,分支指令,IF,IS,RF,EX,DF,DS,TC,WB,延迟槽（分支指令,+1,）,IF,IS,RF,EX,DF,DS,TC,WB,分支指令,+2,IF,IS,RF,EX,DF,DS,TC,分支指令,+3,IF,IS,RF,EX,DF,DS,基于单周期延迟分支方法，,R4000,流水线处理分支指令的时空图,70,3.5,向量处理机,3.5.1,向量处理的基本概念,在流水线处理机中，设置向量数据表示和相应的向量指令，称为,向量处理机,。,不具有向量数据表示和相应的向量指令的流水线处理机，称为,标量处理机,。,71,一、向量处理方式,计算：,fi=ai*bi+ci,设各向量分别放在大写字母单元中,:,72,1,、横向处理,按照算式一个一个地进行计算，即按行计算,第一步计算：,f0=a0*b0+c0,LD R,A0,MUL R,B0,ADD R,C0,ST R,F0,第二步计算：,f1=a1*b1+c1,即将第一步中的脚标,0,改为,1,，同样用上述四条指令。,直到第一百步，,f99,优点：作为工作单元的通用寄存器少（本例,仅用一个,R,）,缺点：条条指令发生相关，因而无人采用。,73,2,、纵向处理,将所有算式列出后，按列进行计算。如对,f0 f99,可分为四大步完成。,第一大步：取向量,LD R0,A0,：,LD R99,A99,第二大步：向量乘,MUL R0,B0,：,MUL R99,B99,第三大步：向量加,ADD R0,C0,：,ADD R99,C99,74,第四大步：送结果,ST R0,F0,：,ST R99,F99,优点：解决了相关问题，将原来条条发生相关改为条条不相关。,缺点：在向量数据较多时，所用的寄存器数目多。,如本例共用了一百个寄存器（,R0R99,），因而在向量数据不多时，可用纵向处理，而向量数据较多时，可用纵横处理。,75,3,、纵横处理,基本思想：将所有算式分为若干组进行如,f0 f99,可分为,10,组：,第一组：，第二组，,第十组。,组内采用纵向处理，组间采用横向处理。,如第一组：取向量,LD R0,A0,：,LD R9,A9,向量乘,MUL R0,B0,：,MUL R9,B9,76,向量加,ADD R0,C0,：,ADD R9,C9,送结果,ST R0,F0,：,ST R9,F9,其余各组与第一组类似，因而总共用了,10,个寄存器（,R0 R9,）,77,3.5.2,向量处理机的结构,向量处理机最简单的框图,一种能实现两个向量加得流水结构的加法器,78,3.5.3,向量指令的执行过程及简单性能计算,一、,CRAY-1,机有关问题,1,）向量指令类型,取向量：,Vi,存储器,存向量：存储器,Vi,向量与向量运算：,Vi Vj OP Vk,向量与数据运算：,Vi Vj OP B,79,2,）多向量寄存器组结构,共有,8,个向量寄存器组（,V0,V7,），每个组可存放,64,个长度为,64,位的二进制数的向量数据。,80,3,）多功能部件,每个部件都以,1=10ns,为单位的流水线结构。,逻辑运算：,定点加：,移位：,浮点加：,访存储器：,浮点乘：,除法：,此外，在功能部件和向量寄存器组之间相互传送也用,1,。,81,4,）、独立总线结构,每个向量寄存器组到每个功能部件之间都有单独总线连接，在不冲突条件下，可实现功能部件之间并行运行。,82,二、向量指令的执行过程及简单性能计算,衡量向量处理机性能的简单参数有向量指令的,完成时间,和向量,数据处理速度,两个,通过两个例子分别讨论这两个参数的含义和计算方法。,83,例,3-4,单条向量指令的执行过程,已知向量指令：,V2 V1+V0,（浮点加）向量长度为,64,，实际上是,64,组向量数据求和。请计算该向量指令的完成时间和向量数据处理速度。,1,）写出,64,组算式,V2.0V1.0+V0.0,V2.1V1.1+V0.1,64 V2.63 V1.63+V0.63,84,2,）画出向量指令结构图（如图所示）,3,）画出各算式执行过程示意图,送数,1,，加法,6,，输出结果,1,，共,8,。,85,86,4,）完成运算时间,第一个结果时间,+,（长度,-1,）,=(1+6+1)+(64-1),=71,5,）向量数据处理速度计算,（向量指令条数*长度）,/,（完成运算用时）,=,（,1*64,）,/,（,71*10,-8,S,）,=90MFOLPS,87,例,3-6,：多条向量指令的执行过程,已知有多条向量指令：,V0,存储器；,V3 V2,V1,；,V6 V5,V4,；,三条指令可并行执行，向量长度为,64,，请计算该向量指令的完成时间和向量数据处理速度。,88,解：,若有多条向量指令，且可并行执行时，完成运算用时，可选用时最多的那条向量指令。如,:,V0,存储器 可并行执行，,V3 V2,V1,向量长度为,64,V6 V5,V4,由于除法用时最长，以它为准。,1+14+1+(64-1)=79(),3*64/(79*10,-8,S)244MFLOPS,89,一、向量的链接特性,1,链接：将多条相关的向量指令链接起来组成更大规模的流水线，从而进一步提高向量数据处理速度，这种链接称为向量链接。,3.5.4,向量的链接技术,2,向量指令之间的几种情况,1,）既不相关，又无冲突,不能链接，但可并行执行（执行时间以最长向量指令时间为准）,2,）条条指令相关，且无冲突,可顺利链接,3,）条条指令相关，但有冲突不能顺利链接，执行时间往往需要推迟。,90,3,例子,例,3-6,：条条指令相关，可顺利链接的情况有如下向量指令：,V0,存储器,;V2V0+V1;V3V2,位移,;,V5 V3,V4;V7 V5,V6,向量长度,64,，请计算该向量指令的完成时间和向量数据处理速度。,解：分析相关性：每条指令之间，上一条向量指令的结果作下一条指令的一个源操作数。,91,1,）画出向量链接特性图,92,2,）完成运算有时,6+2+6+2+4+2+7+2+14+2+,（,64-1,）,=110(),3,）计算向量数据处理速度：,5*64/(110*10,-8,S)291MFLOPS,此处结论：,相关在向量链接中有利于向量数据处理速度的提高。,93,例,3-7,：条条指令相关，不能顺利链接的情况,有如下向量指令：,V0,存储器；,V2V0,V1,；,V4V2+V3,；,V5V4,位移；,V7V5,V6,；,V0V7,V1,向量长度为,64,，请计算该向量指令的完成时间和向量数据处理速度。,解：分析相关性：上述向量指令条条相关，且有冲突，故不能顺利链接。,94,1,）不能顺利链接时，对画向量链接特性图的影响。,源冲突,：第一次送出画实线，第二次送出画虚线,目冲突,：第一次接收画实线，第二次接收画虚线,功能部件冲突,：第一次出现画实线，第二次出现画虚线,95,96,2,）为了计算是否需要推迟时间，以及推迟多少时间，先计算冲突部件的有关时间。,源冲突：从第一次送出到第二次送出之前,1,目冲突：从第一次接收到第二次接收之前,1,功能块：从第一次送出到第二次送入之前,1,源冲突（,V1,）：,1+7+1+1+6+1+1+4+1+1+14+1=39(),目冲突（,V0,）：,1+1+7+1+1+6+1+1+4+1+1+14+1+1+7=48(),功能块（,）：,1+1+6+1+1+4+1+1+14+1=31(),说明：乘法功能部件冲突最严重，上述三个时间以最短时间为准。,97,3,）推迟时间计算：,当长度大于最短有关时间时，实际需要推迟时间为：,向量时间,有关时间,当长度小于等于有关时间时，实际不用推迟，可视为表面冲突。,本例推迟时间为：,64-31=33,（,）,4,）完成运算用时计算：顺利连接时间,+,推迟时间,1+6+1+1+7+1+1+6+1+1+4+1+1+14+1+1+7+1+,（,64-1,）,+33=152(),5,）性能：,6*64/,（,152*10,-8,）,253M FLOPS,98,补充：关于向量指令冲突,1,）源寄存器冲突：邻近向量指令使用了同一源向量寄存器，如上例中的,V1,。,2,）目寄存器冲突：邻近向量指令使用了同一目向量寄存器，如上例中的,V0,。,3,）功能部件冲突：邻近向量指令使用了同一功能部件，如上例中的乘法功能部件。解决冲突的办法是推迟法。,冲突又分为表面冲突与实际冲突,如上例中，向量长度为,30,时，仅表面冲突。,99,课后习题第,7,题,:,在,CRAY-1,机上，在下列指令组中，组内哪些指令可以链接？哪些不可以链接？不能链接的原因是什么？完成各指令所需的拍数（设向量长度均为,64,打入寄存器及启动功能部件各需,1,）。,（,1,）,V0,存储器,(6);V1V2+V3(6);,V4V5,V6(7),（,2,）,V2V0,V1;V3,存储器,;V4V2+V3,（,3,）,V0,存储器,;,V2V0,V1;V3V2+V0;V6V3+V4,（,4,）,V0,存储器,;,V11/V0(14);V3V1,V2;V5V3+V4,100,解：,（,1,）既不相关又不冲突,并行执行（不可链接）,1+7+1+,（,64-1,）,=72(),3*64/,（,72*10,-8,）,267MFLOPS,（,2,）有相关，不冲突,可链接,1+7+1+1+6+1+,（,64-1,）,=80(),3*64/,（,80*10,-8,）,=240 MFLOPS,101,（,3,）条条指令相关，但有冲突,不能顺利链接,源冲突（,V0,）,:,1+7+1=9(),推迟,64-9=55,功能块冲突（加）,:,1,推迟,64-1=63,用时：,1+6+2+7+2+6+2+6+1+,（,64-1,）,+118,=214(),性能：,4*64/,（,214*10,-8,）,120M FLOPS,102,（,4,）条条相关，且无冲突,可顺利链接,用时：,1+6+2+14+2+7+2+6+1+,（,64-1,）,=104(),性能：,4*64/,（,104*10,-8,）,246M FLOPS,103,3.5.5,提高向量处理机的方法,1.,链接技术,前面已经详细介绍了，这里不再叙述。,2.,向量循环或分段开采技术,如果,向量的长度大于向量寄存器的长度,，该如何处理呢？,当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。,这种技术称为,分段开采技术。,由系统硬件和软件控制完成，对程序员是透明的。,104,例,3-9,设,A,和,B,是长度为,N,的向量，考虑在,Cray-1,向量处理器上实现以下的循环操作：,DO 10 I=1,，,N,10 A,（,I,）,=5.0*B,（,I,）,+1,105,S1 5.0,；将常数,5.0,送入标量寄存器,S1,S2 1.0,；将常数,1.0,送入标量寄存器,S2,VL N,；在向量长度寄存器,VL,中设置向量长度,N,V0 B,；从存储器中将向量,B,读入向量寄存器,V0,V1 S1,V0,；向量,B,中的每个元素分别和常数,S1,相乘,V2 S2+V1,；向量,V1,中的每个元素分别和常数,S2,相加,A V2,；将计算结果从向量寄存器,V2,存入存储,器的向量,A,当,N,64,时，可以用以下指令序列：,106,当,N,64,时，就需要进行分段开采。,循环次数,K,：,余数,L,：,107,S1 5.0,；将常数,5.0,送入标量寄存器,S1,S2 1.0,；将常数,1.0,送入标量寄存器,S2,VL L,；在向量长度寄存器,VL,中设置向量长度,L,V0 B,；从存储器中将向量,B0.L-1,读入向量,；寄存器,V0,V1 S1*V0,；向量,B,中的每个元素分别和常数,S1,相乘,V2 S2+V1,；向量,V1,中的每个元素分别和常数,S2,相加,A V2,；将计算结果从向量寄存器,V2,存入存储,器的向量,A0.L-1,处理余,数部分,计算,L,个元素,108,For(I=0 to K-1),V0 B,；从存储器中将向量,BL+I*64.L+I*64+63,；读入向量寄存器,V0,V1 S1*V0,；向量,B,中的每个元素分别和常数,S1,；相乘；,V2 S2+V1,；向量,V1,中的每个元素分别和常数,S2,；相加,A V2,；将计算结果,V2,存入存储器的向量,；,AL+I*64,L+I*64+63,循环,K,次,分段,处理,109,3,、向量递归技术,在向量操作中，结果通常是不送回到作为源操作数使用的同一个向量寄存器中的。,有一类特殊的向量循环，其流水线功能部件的输出可能要回送到它的一个源向量寄存器。,换句话说，一个向量寄存器用来同时存放源操作数和结果操作数。,在功能流水线上的这种递归操作要求特别小心以避免产生数据阻塞问题。,110,4.,稀疏矩阵的处理技术,一个稀疏向量由两个向量组成。其中一个是短向量，它仅包含向量的非零元素。另一个是位向量，其中,“,1,”,表示对应位置为非零元素，,“,0,”,表示对应位置为零元素。位向量的长度与稀疏向量的长度相等。如果向量元素是,64,位的操作的话，那么现在所需的位数知识原来的,1/64,。,大型的稀疏矩阵往往非常稀疏，,64,：,1,的节省远远不够。稀疏向量这种方法如何进一步改进仍是一个有待研究的问题。,111,3.5.6,向量处理机的性能评价,1.,向量指令的处理时间,Tvp,执行一条向量长度为,n,的向量指令所需的时间为,T,s,：向量流水线的建立时间,Tvf,：向量流水线的流过时间,它是从向量指令开始译码算起，到第一对向量元素流过流水线直到产生第一个结果元素所需的时间。,Tc,：流水线瓶颈段的执行时间,112,如果流水线不存在,“,瓶颈,”,，,每段的执行时间等于一个时钟周期，则上式可以写为：,s,：向量流水线的建立时间所对应的时钟周期数,e,：向量流水线的流过时间所对应的时钟周期数,Tclk,：时钟周期时间,也可以将上式改写为：,Tstart,：向量功能部件启动所需的时钟周期数,113,对于一组向量指令而言，其执行时间主要取决于三个因素：,向量的长度,向量操作之间是否链接,向量功能部件的冲突和数据的冲突性,把几条能在同一个时钟周期内一起开始执行的向量指令集合称为一个编队。,可以看出，同一个编队中的向量指令之间一定不存在流水向量功能部件的冲突和数据的冲突。,114,推论 假设每种向量功能部件只有一个，那么下面的一组向量指令能分成几个编队？,LV V1,，,Rx,MULTSV V2,，,R0,，,V1,LV V3,，,Ry,ADDV V4,，,V2,，,V3,SV Ry,，,V4,解：分为,4,个编队,第一编队：,LV,第二编队：,MULTSV,；,LV,第三编队：,ADDV,第四编队：,SV,115,一个编队内所有向量指令执行完毕所要的时间为：,（假设第,i,个编队中所有向量指令处理的向量元素个数均为,n,）,Tci,：第,i,个编队的执行时间,Tstartij,：第,i,个编队中第,j,条指令所使用向量功能部件的启动时钟周期数,116,编队后的向量指令序列总的执行时间为：,m,：向量指令序列编队的个数,Tstart,：向量指令序列编队总的启动时钟周期数,117,编队并采用分段开采技术后，向量指令序列执行所需的总的时钟周期数为：,Tloop,：分段开采所需的额外的时间开销,MV,L,：向量处理机的向量寄存器长度,m,指令编队数目,118,例,3-10,在某向量处理机上执行,DAXPY,的向量指令序列，也即计算双精度浮点向量表达式。,其中,X,和,Y,是双精度浮点向量，最初保存在外部存储器中，,是一个双精度浮点常数，已存放在浮点寄存器,F0,中。计算该表达式的向量指令序列如下：,LV V1,，,Rx,MULTFV V2,，,F0,，,V1,LV V3,，,Ry,ADDV V4,，,V2,，,V3,SV Ry,，,V4,119,解：可以把上述,5,条向量指令按如下方式进行编队：,第一编队：,LV V1,，,Rx,；,第二编队：,MULTFV V2,，,F0,，,V1,；,LV V3,，,Ry,；,第三编队：,ADDV V4,，,V2,，,V3,；,第四编队：,SV Ry,，,V4,。,假设：,Tloop,15,向量存储部件的启动：,12,个时钟周期,向量乘法部件的启动：,7,个时钟周期,向量加法部件的启动：,6,个时钟周期,向量寄存器长度：,MVL=64,120,对,n,个向量元素进行计算所需的时钟周期数为,采用向量链接技术，那么指令序列可以编队为,第一编队：,LV V1,Rx,；,MULTFV V2,F0,V1,；,第二编队：,LV V3,Ry,；,ADDV V4,V2,V3,；,第三编队：,SV Ry,V4,。,121,第一编队启动需要,12+7=19,个时钟周期,第二个编队启动需要,12+6=18,个时钟周期,第三个编队启动仍然需要,12,个时钟周期,对,n,个向量元素进行计算所需的时钟周期数为,122,2.,向量处理机的峰值性能,R,R,表示当向量长度为无穷大时，向量处理机的最高性能，也称为峰值性能。,对于上述例题,3-10,中 向量指令序列中的操作而言，只有,“,MULTFV V2,F0,V1,”,和,“,ADDV V4,V2,V3,”,两条浮点操作向量指令。,假设该向量处理机的时钟频率为,200 MHz,，那么：,123,124,3.,半性能向量长度,n,1/2,半性能向量长度,n,1/2,是指向量处理机的运行性能达到其峰值性能的一半时所必须满足的向量长度。,对于上面的例子,由于该向量处理机的峰值性能,R,100 MFLOPS,，,所以根据半性能向量长度的定义有：,125,假设 ,64,，那么有：,n,1/2,64,3