计算机体系--重叠、流水和向量处理机讲义.ppt

本资料来源,利用堆栈技术模拟LRU在不同n条件下页面变化时空图及命中率。LRU算法的实现方法堆栈法、比较对法4存贮体系的两个分支虚拟存贮器的简单工作过程Cache主存体系与虚拟存储器相同之处Cache主存体系与虚拟存储器不同之处内部定向原理的有向图和有向简图的绘制组相联映象的的两个例子页面替换时空图主存地址到Cache地址的变换,第五章重叠、流水和向量处理机1重叠方式,一重叠解释方式1.一条指令的几个过程段1）取指令：根据PC（指令计数器）从M（存储器）取出指令送到IR（指令寄存器）2）译码分析：译出指令的操作性质，准备好所需数据3）执行：将准备好的数按译出性质进行处理，主要涉及ALU（算术逻辑运算部件）2.对指令执行的几种方式,1）顺序执行(传统机采用)只有在前一条指令的各过程段全部完成后，才从存储器取出下一条指令2)仅两条指令重叠：第i条指令的执行与第i+1条的取指重叠。3)三条指令重叠：第i条指令的执行与第i+1条的译码及第i+2条的取指重叠。,若一条指令的过程段划分更多时，重叠组合方式更多。重叠解释并不能加快一条指令的实现，但能加快一段程序的解释。3.重叠方式中所需时间表达式及所需时间计算1）条件：设一条指令分为三个过程段，各过程段分别用t取、t译、t执表示。执行K条指令，分别采用顺序执行、两条重叠、三条重叠。2）分别列出上述三种执行方式所需时间表达式顺序执行k*（t取+t译+t执）两条重叠t取+k*t译+(k-1)*(t取,t执)max+t执三条重叠t取+(t译,t取)max+(k-2)*（t取,t译,t执）max+(t执,t译)max+t执,3)例子当k=200，t取=3t，t译=4t，t执=5t，时，分别计算上述三种执行方式的时间。顺序执行：200(3+4+5)=2400t两条重叠：3+2004+(200-1)5+5=1803t三条重叠：3+4+(200-2)5+5+5=1007t4重叠方式需要解决的问题1）对存储器的频繁访问有哪些访问：取指令、取操作数、存放执行结果,I/O通道访问.希望存储器为多体结构，以适应多种访问源的需要。当存储器为单体结构时，需要将访问源排队，先后顺序为：取指令、取数据、I/O通道访问、存结果,2）应具有先行控制部件先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。先行控制部件的主要包括）先行地址站，包括先行指令地址站和先行操作数地址站；）先行指令站，用来存放多条指令；）先行操作数站，用来存放多个操作数；）先行地址形成部件，用来形成先行指令地址以及先行操作数地址；）先行操作码译码站，用来完成对多条指令的译码并保留译码输出状态。,2）也应具有后行部件后行部件：对指令执行后的结果进行处理的器件，称后行部件。包括：后行数地址站，提供后行数存放地址。后行数站，存放运行的结果，并且，这些结果需送存储器。,二、相关问题1何谓相关：在重叠方式的指令执行过程中，由于发生了某种关联，使正在被解释的指令无法再继续下去的现象，称相关。2相关类型1）从性质上分指令相关：重新修改了正在被解释的指令数相关：因等待前面指令执行的结果，使后面指令等待而不能连续解释。如：S=a/b+cLDR,ADIVR,BADDR,C；要等DIV结果STR,S；存结果,2）按影响面大小分局部相关：相关发生时只能影响邻近几条指令的执行，这种相关影响面不大。如等待结果的数相关。全局相关：相关发生时影响面很大全局。如条件转移指令，当条件具备时，就转到其他地方去执行程序，而转移指令之后的几条语句已先后被解释了部分功能，但此时全部废弃。,3解决指令相关1）尽可能避免指令相关2）用分支程序代替被修改的指令4解决条件转移的全局相关1）猜测法按成功支路猜测：凡是条件转移指令都将成功支路指令提前取到指令站中，此时将不成功支路指令取到后援寄存器组。按不成功支路猜测：做法与正好相反。2）分支预测：允许CPU对分支以后的指令进行译码，如P6系列CPU中，取指/译码单元使用一种优化的分支预测算法，用来在多级分支、过程调用和返回时预测指令的流向。,如计算A=BCifA0GoTon在进行BC之前，可先对SBSC=？进行判断，决定流向。3）尽可能作成短转移，短循环：使转去的指令都在指令站中。4）增加指令站容量（P6体系中称为指令池重排序缓冲器，是一个按内容寻址的存储器阵列。可存放40个等待执行的微操作，执行单元能够以任意顺序执行重排序缓冲器中的指令。）5解决等待结果的数相关1）推迟法：包括推迟译码分析，推迟执行。适用范围宽，但不利于速度的提高。,2）相关专用通路法当上一条的运算结果需作下一条的源操作数时，如：LDR，AADDR，BSUBR，C可建一个相关专用比常规通路提前1获取源操作数。,2流水方式一、流水方式的出现1重叠方式的两种等待1）等待译码当ti译ti+1取时，即：2）等待执行ti执ti+1译时，即：,取,译,执,i,i+1,执,取,译,等待执行时间,2产生等待的原因重迭方式未按时间单位来划分过程段，比较粗糙。3流水线上对各过程段进行时间匹配的办法。1）将一条指令分为以t为单位的多个t过程段。如某指令用时5t，可分为5个过程段：(均匀流水线）,2）当某过程段用时较长，又不便于细分时，可用多套相同设备来实现时间匹配。如第3个过程段用时2t，其余1，2，4用时均为t：（非均匀流水线）4流水线的分类1）按各过程段用时是否全等划分均匀流水线：各过程段用时全等非均匀流水线：各过程段用时不全等（如上图）时间匹配的非均匀流水线。）时间不匹配的非均匀流水线。,2）按处理的数据类型标量流水线：用于对标量数据进行流水处理。向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理）3）按流水线的规模操作流水线：如将一条指令划分为多个过程段进行流水处理。规模最小指令流水线：以指令为单位进行处理，用于多进程、多任务。规模较大宏流水线：以程序的逻辑功能段为单位进行流水处理。规模最大,4）按流水线具有功能的多少单功能流水线：各过程段之间固定连接，不能重新构成其它流水线固定流水线多功能流水线分：静态流水线：各过程段之间可重新连接，但不同时刻只能重构成一种不同的流水线。动态流水线：各过程段之间可重新连接，不同时刻可重构成多种流水线。5）按部件在同一时刻送出支路数的多少来分。一维流水线：在同一时刻，部件只能向一个地方传送结果。阵列流水线：在同一时刻，部件可同时向多个地方传送结果。,二流水线的执行过程及性能评价1均匀流水线加法流水线：,1）不相关算式计算：Si=ai+bi(i=07)共有8个算式S0=a0+b0S1=a1+b1S7=a7+b7画出各算式在流水线上执行过程时空图,性能计算：吞吐率（TP）：单位时间输出的结果数。TP=(输出结果数)/（完成算式总用时）=8/12=2/3（条/t）而无流水时：TP=1/5（条/t）2）相关算式计算：S=a0+a1+a2+a3+a4+a5+a6+a7对相关算式要合理分解算式尽量分解为少相关算式：S0=a0+a1S4=S0+S1S1=a2+a3S5=S2+S3S2=a4+a5S6=S4+S5S3=a6+a7,TP=7/18（条/t）效率（）：即流水线上部件的利用率=（作用区域面积）/（完成运算所需时间矩形面积）=（7*5t）/（18t*5）=7/18结论：相关发生时，对单条流水线而言会降低流水线性能。,2时间匹配的非均匀流水线右图所示乘法流水线完成计算:Mi=ai*bi(i=07)（也是不相关式子）1）M0=a0*b0M7=a7*b7,2）画出各算式在流水线上执行过程示意图,3）性能:TP=8/13（个/t）=（8*6t）/（13t*6）=8/13,3时间不匹配的非均匀流水线按右图所示乘法流水线完成算式:M=a0*a1*a2*a3*a4*a5*a6*a71）合理分解算式M0=a0*a1M1=a2*a3M2=a4*a5M3=a6*a7M4=M0*M1M5=M2*M3M=M4*M5,2)画出时空图:,过程段M0M1M2M3M4M5M,1235689101216202227t(t),3）性能:TP=7/27（个/t）=（7*6t）/（27t*4）=7/18,1重叠方式重叠方式中所需时间表达式及所需时间计算解决条件转移的全局相关解决等待结果的数相关2流水方式重叠方式的两种等待流水线的分类均匀流水线、非均匀流水线流水线的执行过程及性能评价均匀流水线时间匹配的非均匀流水线时间不匹配的非均匀流水线,三、向量流水处理1.向量的处理方式计算：fi=ai*bi+ci（i=099）设各向量分别放在大写字母单元中:,1）横向处理按照算式一个一个地进行计算，即按行计算第一步计算：f0=a0*b0+c0LDR,A0MULR,B0ADDR,C0STR,F0第二步计算：f1=a1*b1+c1即将第一步中的脚标0改为1，同样用上述四条指令。直到第一百步，f99优点：作为工作单元的通用寄存器少（本例仅用一个R）缺点：条条指令发生相关。,2）纵向处理将所有算式列出后，按列进行计算。如对f0f99可分为四大步完成。第一大步：取向量LDR0,A0：LDR99,A99第二大步：向量乘MULR0,B0：MULR99,B99第三大步：向量加ADDR0,C0：ADDR99,C99,第四大步：送结果STR0,F0：STR99,F99优点：解决了相关问题，将原来条条发生相关改为条条不相关。缺点：在向量数据较多时，所用的寄存器数目多。如本例共用了一百个寄存器（R0R99），因而在向量数据不多时，可用纵向处理，而向量数据较多时，可用纵横处理。,3）纵横处理基本思想：将所有算式分为若干组进行如f0f99可分为10组：第一组：，第二组，第十组。组内采用纵向处理，组间采用横向处理。如第一组：取向量LDR0,A0：LDR9,A9向量乘MULR0,B0：MULR9,B9,向量加ADDR0,C0：ADDR9,C9送结果STR0,F0：STR9,F9其余各组与第一组类似，因而总共用了10个寄存器（R0R9）2.CRAY-1机有关问题1）向量指令类型取向量：Vi存储器存向量：存储器Vi,向量与向量运算：ViVjOPVk向量与数据运算：ViVjOPB2）向量寄存器组结构共有8个向量寄存器组（V0V7），每个组可存放64个长度为64位的二进制数的向量数据。,3）多功能部件每个部件都以1(=10ns=10-8S)为单位的流水线结构。逻辑运算：定点加：移位：浮点加：访存储器：浮点乘：除法：此外，在功能部件和向量寄存器组之间相互传送也用1。4）独立总线结构每个向量寄存器组到每个功能部件之间都有单独总线连接，在不冲突条件下，可实现功能部件之间并行运行。,3.向量指令的执行过程及性能计算已知向量指令：V2V1+V0（浮点加）向量长度为64，实际上是64组向量数据求和。1）写出64组算式V2.0V1.0+V0.0V2.1V1.1+V0.164V2.63V1.63+V0.632）画出向量指令结构图（如右上图所示）3）画出各算式执行过程示意图送数1，加法6，输出结果1，共8。,4）完成运算时间第一个结果时间+（长度-1）=(1+6+1)+(64-1)=715）向量数据处理速度计算（向量指令条数*长度）/（完成运算用时）=（1*64）/（71*10-8S）=90MFLOPS(每秒处理的浮点数个数),4.多条向量指令的执行过程若有多条向量指令，且可并行执行时，完成运算用时，可选用时最多的那条向量指令。如:V0存储器可并行执行，V3V2V1向量长度为64V6V5V4由于除法用时最长，以它为准。1+14+1+(64-1)=79()3*64/(79*10-8S)244MFLOPS,四、向量的链接特性1.链接：将多条相关的向量指令链接起来组成更大规模的流水线，从而进一步提高向量数据处理速度，这种链接称为向量链接。2.向量指令之间的几种情况1）既不相关，又无冲突不能链接，但可并行执行（执行时间以最长向量指令时间为准）2）条条指令相关，且无冲突可顺利链接3）条条指令相关，但有冲突不能顺利链接，执行时间往往需要推迟。,3.可顺利链接的情况有如下向量指令：V0存储器;V2V0+V1;V3V2位移;V5V3V4;V7V5V6向量长度64相关：上一条向量指令的结果作下一条指令的一个源操作数。1）画出向量链接特性图,2）完成运算有时6+2+6+2+4+2+7+2+14+2+（64-1）=110()3）计算向量数据处理速度：5*64/(110*10-8S)291MFLOPS此处结论：相关在向量链接中有利于向量据处理速度的提高。4.不能顺利链接的情况有如下向量指令：V0存储器;V2V0V1;V4V2+V3;V5V4位移;V7V5V6;V0V7V1,故不能顺利链接1）不能顺利链接时，对画向量链接特性图的影响。源冲突：第一次送出画实线，第二次送出画虚线目冲突：第一次接收画实线，第二次接收画虚线功能部件冲突：第一次出现画实线，第二次出现画虚线,向量长度64，上述向量指令条条相关，有冲突：,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(),说明：乘法功能部件冲突最严重，上述三个时间以最短时间为准（仅适用本例）。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-8S）253MFLOPS,P22417题:在CRAY-1机上，在下列指令组中，组内哪些指令可以链接？哪些不可以链接？不能链接的原因是什么？完成各指令所需的拍数（设向量长度均为64,打入寄存器及启动功能部件各需1）。（1）V0存储器(6);V1V2+V3(6);V4V5V6(7)（2）V2V0V1;V3存储器;V4V2+V3（3）V0存储器;V2V0V1;V3V2+V0;V6V3+V4（4）V0存储器;V11/V0(14);V3V1V2;V5V3+V4解：（1）即不相关又不冲突并行执行（不可链接）1+7+1+（64-1）=72()3*64/（72*10-8S）267MFLOPS（2）有相关，不冲突可链接1+7+1+1+6+1+（64-1）=80()3*64/（80*10-8S）=240MFLOPS,（3）条条指令相关，但有冲突不能顺利链接,源冲突（V1）:1+7+1=9()推迟64-9=55功能块冲突（加）:1推迟64-1=63总推迟：55+63=118()1+6+2+7+2+6+2+6+1+（64-1）+118=214()4*64/（214*10-8S）120MFLOPS（4）条条相关，且无冲突可顺利链接,1+6+2+14+2+7+2+6+1+（64-1）=104()4*64/（104*10-8S）246MFLOPS,三、向量流水处理向量的处理方式向量指令的执行过程及性能计算四、向量的链接特性冲突:邻近向量指令使用了同一个部件冲突又分为表面冲突与实际冲突向量链接特性图的绘制完成运算用时计算：顺利连接时间+推迟时间有关时间、推迟时间的计算,五加速比的概念流水线方式相对于非流水线顺序串行方式速度提高的比值称加速比（Sp）。设：流水线段数m，指令有n条，各段经过的时间均为t则：,此外，还有某种流水处理机相对于另一种流水处理机的加速比。如超标量流水处理机相对于常规标量流水处理机的加速比。,六非线性流水线的概念线性流水线中各个段之间串行地链接，既无反馈也无跳跃，每个任务流经流水线中各个段均只有一次，反之就是非线性流水线。,时间流水线,非线性流水线的预约表,延迟禁止表为：F=2，4，6初始冲突向量为：C=（101010）,如上例中：延迟禁止表为：F=2，4，6初始冲突向量为：C=（101010）状态转移图：各种调度方案及其相应的平均延迟表：由状态转移图，从初始状态开始延箭头走向，构成调度意义上延迟拍数成周期性重复出现的拍数循环。按此方案进行任务调度，必然无冲突。,七、指令级高级并行超级处理机超标量处理机、超长指令字处理机和超流水线处理机是指令级高度并行的三种不同的超级处理机。让单处理机在每个时钟周期里可同时解释m（m1）条指令，称处理机并行的度为m。1.超标量处理机是采用设置m条指令流水线同时并行，来实现度为m的。2.超长指令字处理机是将水平型微码和超标量处理相结合。在编译时，将多个能并行执行的不相关或无关的操作组合在一起，形成一条有多个操作码字段的超长指令字。运行时，直接控制机器中多个相互独立的功能部件并行操作，来实现同时执行多条指令。3.超流水线处理机：一台度为m的超流水线处理机的时钟只是基本机器周期的1/m。,解过程执行,01234567891011121314(t)图1常规标量流水处理机的时空图,例1指令由取指、译码和执行三个过程组成。每个过程经过的时间为t连续执行12条指令。请分别画出在常规标量流水处理机及度m均为4的超标量处理机、超长指令字处理机、超流水线处理机上工作的时空图，分别计算出它们相对常规标量流水处理机的加速比Sp。,译码取指,过程,012345时间（t）图2超标量处理机的时空图,取指,译码,执行,Sp=14t/5t=2.8,过程,执行(m=4),取指,译码,图3超长指令字处理机的时空图Sp=14t/5t=2.8,012345时间（t）,图4超流水线处理机的时空图,55.75时间(t),01234,Sp=14t/5.75t2.43,执行,译码,取指,过程,例2现有长度为4向量A和B，请分别画出在下列4种结构的处理器上求点积AB的时空图，并求完成全部结果的最少时钟拍数。设处理器中每个部件的输出均可直接送到任何部件的输入端或存入缓冲器，其间的传送延时不计，指令和源操作数均能连续提供。(1)处理器有一个乘法部件和一个加法部件，不能同时工作，部件内也只能顺序方式工作，完成一次加法或乘法均只需5拍；(2)与(1)基本相同，只是乘法部件和加法部件可并行；(3)处理器有一个乘、加双功能静态流水线，乘、加均由5个流水段构成，各段经过时间要1拍；(4)处理器有乘、加两条流水线，可同时工作，各由5段构成，每段经过时间为1拍。,解答长度为4向量A和B的点积为ABa1*b1+a2*b2+a3*b3+a4*b4共需做4乘法和3加法：c1=a1*b1,c2=a2*b2,c3=a3*b3,c4=a4*b4d1=c1+c2,d2=c3+c4,d3=d1+d2=AB(1)乘法部件和加法部件不能同时工作，部件内也只能顺序方式工作如下图所示。由向量点积AB运算的时空图可知，完成全部运算最少为45十3535(拍)部件05101520253035拍,c4,加乘,(2)乘法部件和加法部件可并行的时空图其中，e1=d1+c3,e2=e1+c4=AB,部件,加乘,0510152025拍,（d1=c1+c2）,(3)处理器有一个乘、加双功能静态流水线时的时空图,加,乘,部件,058101519拍,54321,54321,(4)处理器有乘、加两条流水线，可同时工作时的时空图,加,乘,部件,058101518拍,54321,54321,2在下述流水线上完成算式M=ai(i=18)（1）合理分解算式；（2）画出各算式执行过程时空图；（3）计算吞吐率和效率。,1设将指令划分为三个时间段t取t译t执来完成。分别采用顺序执行，有两条指令重叠，有三条指令重叠。都执行K条指令，分别写出三种执行方式所需时间表达式；若K=300,t取=4t，t译=5t，t执=6t，分别计算三种执行方式所需时间,1.解：1）顺序执行：t=k*（t取+t译+t执）=300(4+5+6)=4500（t）2）两条重叠：t=t取+k*t译+(k-1)*(t取,t执)max+t执=4+3005+(300-1)6+6=3304（t）3）三条重叠：t=t取+(t译,t取)max+(k-2)*(t取,t译,t执)max+(t执,t译)