重叠、流水和向量处理机 课件.ppt

《重叠、流水和向量处理机 课件.ppt》由会员分享，可在线阅读，更多相关《重叠、流水和向量处理机 课件.ppt（96页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章第五章重叠、流水和向量处理机重叠、流水和向量处理机1重叠方式重叠方式一重叠解释方式1.一条指令的几个过程段1）取指令：根据PC（指令计数器）从M（存储器）取出指令送到IR（指令寄存器）2）译码分析：译出指令的操作性质，准备好所需数据3）执行：将准备好的数按译出性质进行处理，主要涉及ALU（算术逻辑运算部件）12.对指令执行的几种方式1）顺序执行(传统机采用)l只有在前一条指令的各过程段全部完成后，才从存储器取出下一条指令取取译译执执取取译译执执i条条i+1条条22)仅两条指令重叠：第i条指令的执行与第i+1条的取指重叠。3)三条指令重叠：第i条指令的执行与第i+1条的译码及第i+2条的取

2、指重叠。i条取译执取译执i+1条i条取译执i+1条取译执i+2条取译执3若一条指令的过程段划分更多时，重叠组合方式更多。重叠解释并不能加快一条指令的实现，但能加快一段程序的解释。2.重重叠叠方方式式中中所所需需时时间间表表达达式式及及所所需需时时间间计计算算1）条件：设一条指令分为三个过程段，各过程段分别用t取、t译、t执表示。执行K条指令，分别采用顺序执行、两条重叠、三条重叠。42）分别列出上述三种执行方式所需时间表达式顺序执行顺序执行k*（t取取+t译译+t执执）两条重叠两条重叠t取取+k*t译译+(k-1)*(*(t取取,t执执)max+max+t执执三条重叠三条重叠t取取+(t译译,t

3、取取)max+(k-2)*max+(k-2)*（t取取,t译译,t执执）max+(t执执,t译译)max+max+t执执53)例子当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=1007t64重叠方式需要解决的问题1）对存储器的频繁访问 有哪些访问：取指令、取操作数、存放执行结果,I/O通道访问.希望存储器为多体结构，以适应多种访问源的需要。当存储器为单体结构时，需要将访问源排队，先后顺序为：取指令、取数据、I/O通

4、道访问、存结果72）应具有先行控制部件）应具有先行控制部件先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。82）先行控制部件的主要内容先行控制部件的主要内容）先行地址站，包括先行指令地址站和先行操作数地址站；）先行指令站，用来存放多条指令；）先行操作数站，用来存放多个操作数；）先行地址形成部件，用来形成先行指令地址以及先行操作数地址；）先行操作数译码站，用来完成对多条指令的译码并保留译码输出状态。93）也应具有后行部件 后行部件：对指令执行后的结果进行处理的器件，称后行部件。包括：后行数地址站，提供后行数存放地址。后

5、行数站，存放运行的结果，并且，这些结果需送存储器。1011二、二、相关问题1何谓相关：在重叠方式的指令执行过程中，由于发生了某种关联，使正在被解释的指令无法再继续下去的现象，称相关。122相关类型1）从性质上分指令相关：重新修改了正在被解释的指令数相关：因等待前面指令执行的结果，使后面指令等待不能连续解释。如：S=a/b+cLDR,ADIVR,BADDR,C；要等DIV结果STR,S；存结果ABCSabcs132）按影响面大小分）按影响面大小分局部相关：相关发生时只能影响邻近几条指令的执行，这种相关影响面不大。如等待结果的数相关。全局相关：相关发生时影响面很大全局。如条件转移指令，当条件具备时

6、，就转到其他地方去执行程序，而转移指令之后的几条语句已先后被解释了部分功能，但此时全部废弃。14153解决指令相关解决指令相关1）尽可能避免指令相关2）用分支程序代替被修改的指令4.解决条件转移的全局相关1）猜测法按成功支路猜测：凡是条件转移指令都将成功支路指令提前取到指令站中，此时将不成功支路指令取到后援寄存器组。按不成功支路猜测：做法与正好相反。162）分支预测：允许CPU对分支以后的指令进行译码，如P6系列CPU中，取指/译码单元使用一种优化的分支预测算法，用来在多级分支、过程调用和返回时预测指令的流向。17如计算A=BCifA0GoTon在进行BC之前，可先对SBSC=？进行判断，决定

7、流向。3）尽可能作成短转移，短循环：使转去的指令都在指令站中。184）增加指令站容量（P6体系中称为指令池重排序缓冲器，是一个按内容寻址的存储器阵列。可存放40个等待执行的微操作，执行单元能够以任意顺序执行重排序缓冲器中的指令。）5解决等待结果的数相关1）推迟法：包括推迟译码分析，推迟执行。适用范围宽，但不利于速度的提高。192）相关专用通路法当上一条的运算结果需作下一条的源操作数时，如：LDR，AADDR，BSUBR，C20可建一个相关专用通路，比常规通路提前1获取源操作数。通用寄存器组通用寄存器组AB1相关专用通路常规通路1212 2流水方式流水方式一、流水方式的出现1重叠方式的两种等待1

8、）等待译码当ti译ti+1取时，即：2）等待执行ti执ti+1译时，即：i+1i等待译码时间取译执取译执取译执ii+1执取译等待执行时间222产生等待的原因重迭方式未按时间单位来划分过程段，比较粗糙。3流水线上对各过程段进行时间匹配的办法。1）将一条指令分为以t为单位的多个t过程段。如某指令用时5t，可分为5个过程段：(均匀流水线）1t2t3t4t5t232）当某过程段用时较长，又不便于细分时，可用多套相同设备来实现时间匹配。如第3个过程段用时2t，其余1，2，4用时均为t：（非均匀流水线）1t2t4t32t321244流水线的分类1）按各过程段用时是否全等划分均匀流水线：各过程段用时全等非均

9、匀流水线：各过程段用时不全等（如上图）时间匹配的非均匀流水线。）时间不匹配的非均匀流水线。252）按处理的数据类型标量流水线：用于对标量数据进行流水处理。向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理）3）按流水线的规模操作流水线：如将一条指令划分为多个过程段进行流水处理。规模最小指令流水线：以指令为单位进行处理，用于多进程、多任务。规模较大宏流水线：以程序的逻辑功能段为单位进行流水处理。规模最大264）按流水线上各过程部件之间的连接方式）按流水线上各过程部件之间的连接方式固定流水线：各过程段之间固定连接，不能重新构成其它流水线单单功功能能流流水水线线半动态流水线：各过程段之间可

10、重新连接，但不同时刻只只能能重重构构成成一一种种不不同同的流水线。的流水线。动态流水线：各过程段之间可重新连接，不同时刻可重构成多种流水线。可重构成多种流水线。275）按部件在同一时刻送出支路数的多少来分。一维流水线：在同一时刻，部件只能向一个地方传送结果。阵列流水线：在同一时刻，部件可同时向多个地方传送结果。二流水线的执行过程及性能评价1均匀流水线加法流水线：281）不相关算式计算：Si=ai+bi(i=07)共有8个算式S0=a0+b0 S1=a1+b1 S7=a7+b7 画出各算式在流水线上执行过程时空图 S0 S1S2S3S4 S5S6S7 过程段 1 2 3 4 5 6 7 8 9

11、10 11 12 54321 t(t)29性能计算：吞吐率（TP）：单位时间输出的结果数。完成完成n n个连续任务需要的总时间为：个连续任务需要的总时间为：T Tk k（k kn n1 1）t t 其中：其中：k k 为为流水流水线线的段数，的段数，t t为时钟为时钟周期。周期。最大吞吐率为：最大吞吐率为：TP=(输出结果数输出结果数)/（完成算式总用时）（完成算式总用时）=8/12=2/3（1/t）而无流水时（顺序）：TP=1/5（1/t）30一个浮点加法器流水线的时空图由求阶差、对阶、尾数加和规格化4个流水段组成。31规规格格化化尾尾数数加加对对阶阶求求阶阶差差求阶求阶差差1求阶求阶差差2

12、求阶求阶差差3求阶求阶差差4求阶求阶差差50t1t2t3t4t5t6t7t8时时间间规格规格化化1规格规格化化2规格规格化化3规格规格化化4规格规格化化5尾数尾数加加1尾数尾数加加2尾数尾数加加3尾数尾数加加4尾数尾数加加5对阶对阶1对阶对阶2对阶对阶3对阶对阶4对阶对阶5空空间间322）相关算式计算：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+a73334TP=7/18（1/t）效率（）：即流水线上部件的利用率=（作作用用

13、区区域域面面积积）/（完完成成运运算算所所需需时时间间矩矩形面积）形面积）=（7t*5）/（18t*5）=7/18结结论论：相关发生时，对单条流水线而言会降低流水线性能。354时间匹配的非均匀流水线右图所示乘法流水线完 成 计 算:Mi=ai*bi(i=07)（也是不相关式子）1）M0=a0*b0 M7=a7*b7362）画出各算式在流水线上执行过程示意图373）性能:TP=8/13（1/t）=（8t*6）/（13t*6）=8/133时间不匹配的非均匀流水线按上图所示乘法流水线完成算式:M=a0*a1*a2*a3*a4*a5*a6*a71）合理分解算式M0=a0*a1 M1=a2*a3 M2=

14、a4*a5 M3=a6*a7M4=M0*M1 M5=M2*M3 M6=M4*M51t2t4t33t382)画出时空图:M0M1M2M3M4M5M 过程段 4 3 2 1 1 2 3 4 6 8 9 10 12 16 20 22 27 t(t)393）性能:TP=7/27（1/t）=（7t*6）/（27t*4）=7/1840三、向量流水处理1向量的处理方式计算：fi=ai*bi+ci设各向量分别放在大写字母单元中:411）横向处理按照算式一个一个地进行计算，即按行计算第一步计算：f0=a0*b0+c0LDR,A0MULR,B0ADDR,C0STR,F0第二步计算：f1=a1*b1+c1即将第一步

15、中的脚标0改为1，同样用上述四条指令。直到第一百步，f99优点：作为工作单元的通用寄存器少（本例仅用一个R）缺点：条条指令发生相关，因而无人采用。422）纵向处理将所有算式列出后，按列进行计算。如对f0f99可分为四大步完成。第一大步：取向量LDR0,A0：LDR99,A99第二大步：向量乘MULR0,B0：MULR99,B99第三大步：向量加ADDR0,C0：ADDR99,C9943第四大步：送结果STR0,F0：STR99,F99优点：解决了相关问题，将原来条条发生相关改为条条不相关。缺点：在向量数据较多时，所用的寄存器数目多。如本例共用了一百个寄存器（R0R99），因而在向量数据不多时，

16、可用纵向处理，而向量数据较多时，可用纵横处理。443）纵横处理基本思想：将所有算式分为若干组进行如f0f99可分为10组：第一组：，第二组，第十组。组内采用纵向处理，组间采用横向处理。如第一组：取向量 LDR0,A0：LDR9,A9 向量乘 MULR0,B0：MULR9,B945 向量加ADDR0,C0：ADDR9,C9 送结果STR0,F0：STR9,F9 其余各组与第一组类似，因而总共用了10个寄存器（R0R9）462 2 CRAY-1CRAY-1机有关问题机有关问题 1）向量指令类型 取向量：Vi存储器 存向量：存储器Vi 向量与向量运算：Vi Vj OP Vk 向量与数据运算：Vi V

17、j OP B472）多向量寄存器组结构 共有8个向量寄存器组（V0V7），每个组可存放64个长度为64位的二进制数的向量数据。3）多功能部件 每个部件都以1=10ns=10-8S为单位的流水线结构。48 逻辑运算：定点加：移位：浮点加：访存储器：浮点乘：除法：此外，在功能部件和向量寄存器组之间相互传送也用1。494）独立总线结构 每个向量寄存器组到每个功能部件之间都有单独总线连接，在不冲突条件下，可实现功能部件之间并行运行。503 向量指令的执行过程及性能计算 已知向量指令：V2 V1+V0（浮点加）向量长度为64，实际上是64组向量数据求和。1）写出64组算式 V2.0V1.0+V0.0 V

18、2.1V1.1+V0.1 64 V2.63 V1.63+V0.63 512）画出向量指令结构图（如图所示）3）画出各算式执行过程示意图送数1，加法6，输出结果1，共8。52534）完成运算时间第一个结果时间+（长度-1）=(1+6+1)+(64-1)=715）向量数据处理速度计算（向量指令条数*长度）/（完成运算用时）=（1*64）/（71*10-8S）=90MFLOPS544 多条向量指令的执行过程 若有多条向量指令，且可并行执行时，完成运算用时，可选用时最多的那条向量指令。如:V0存储器 可并行执行，V3 V2V1 向量长度为64V6 V5V4 由于除法用时最长，以它为准。1+14+1+(

19、64-1)=79()3*64/(79*10S)244MFLOPS55四四向量的链接特性向量的链接特性1 链接：将多条相关的向量指令链接起来组成更大规模的流水线，从而进一步提高向量数据处理速度，这种链接称为向量链接。562 向量指令之间的几种情况1）既不相关，又无冲突 不能链接，但可并行执行（执行时间以最长向量指令时间为准）2）条条指令相关，且无冲突 可顺利链接3）条条指令相关，但有冲突不能顺利链接，执行时间往往需要推迟。573 可顺利链接的情况 有如下向量指令：V0存储器;V2V0+V1;V3V2位移;V5 V3V4;V7 V5V6 向量长度64 相关：上一条向量指令的结果作下一条指令的一个源

20、操作数。581）画出向量链接特性图592）完成运算用时 6+2+6+2+4+2+7+2+14+2+（64-1）=110()3）计算向量数据处理速度：5*64/(110*10S)291MFLOPS此处结论：相相关关在在向向量量链链接接中中有有利利于于向向量量数数据据处处理理速速度的提高。度的提高。604 不能顺利链接的情况 有如下向量指令：V0存储器;V2V0V1;V4V2+V3;V5V4位移;V7V5V6;V0V7V161 故不能顺利链接向量长度64，上述向量指令条条相关，有冲突：62 1）不能顺利链接时，对画向量链接特性图的影响。源冲突源冲突：第一次送出画实线，第二次送出画虚线目冲突目冲突：

21、第一次接收画实线，第二次接收画虚线功功能能部部件件冲冲突突：第一次出现画实线，第二次出现画虚线63642）为了计算是否需要推迟时间，以及推迟多少时间，先计算冲突部件的有关时间。源冲突：从第一次送出到第二次送出之前1目冲突：从第一次接收到第二次接收之前1功能块：从第一次送出到第二次送入之前165 源冲突（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()说明：乘法功能部件冲突最严重，上述三个时间以最短时间为准（仅适用本例）。663）推

22、迟时间计算：当长度大于最短有关时间时，实际需要推迟时间为：向量时间 有关时间 当长度小于等于有关时间时，实际不用推迟，可视为表面冲突。本例推迟时间为：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 67补充：关于向量指令冲突1）源寄存器冲突：邻近向量指令使用了同一源向量寄存器，如上例中的V1。2）目寄存器冲突：邻近向量指令使用了同一目向量寄存器，如上例中的V0。3）功能部件冲突：邻近向量指令使用了同一功能部件，如上

23、例中的乘法功能部件。解决冲突的办法是推迟法。冲突又分为表面冲突与实际冲突如上例中，向量长度为30时，仅表面冲突。68P224 17题:在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+V469解：（1）既不相关又不冲突并行执行（不可链接）

24、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 MFLOPS70（3）条条指令相关，但有冲突不能顺利链接71源冲突（V1）: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 FLOPS72（4）条条相关，且无冲突可顺利链接用时：1+6+2+14+2+7+2+6+1+（64-1）=104()性能：4*64/（

25、104*10-8）246M FLOPS73五、非线性流水线的调度技术 l非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。741、非线性流水线的表示、非线性流水线的表示线性流水线能够用流水线连接图唯一表示流水线连接图不能用唯一表示非线性流水线的工作流程，因此，引入流水线预约表75前馈线反馈线输输入入输出输出S1S2S3S476时时间间功能功能段段1234567S1S2S3S4非线性流水线的连接图和预约表77 一张预约表可能与多个流水线连接图相一张预约表可能与多个流水线连接图相对应对应 一个连接图对应有

26、多张预约表。一个连接图对应有多张预约表。2、非线性流水线的冲突、非线性流水线的冲突流水线的启动距离：流水线的启动距离：向流水线连续输入两个任务之间的时间间隔流水线的冲突：流水线的冲突：几个任务争用同一个流水段78启动距离为启动距离为3 3的流水线冲突情况的流水线冲突情况 时时间间功能功能段段1234567891011S1X1X1X2X1X2X3X2X3X4S2X1X1X2X2X3X3X4S3X1X2X1X3X2X4S4X1X2X379启动距离为启动距离为2的流水线冲突情况的流水线冲突情况时时间间功能功能段段12345678910 11 S1X1X2X1X3X2X1X4X3X2X5X4X3X6S

27、2X1X2X1X3X2X4X3X5X4S3X1X2X1X3X2X4X3X5S4X1X2X3X4X580启动距离为启动距离为5时的流水线不冲突时的流水线不冲突时时间间功能功能段段12345678910 11 S1X1X1X2X1X2X3S2X1X1X2X2S3X1X1X2X2S4X1X2启动周期启动周期重复启动周期重复启动周期81启动距离为启动距离为(1,7)(1,7)循环时的流水线预约表循环时的流水线预约表 时时间间功能功能段段123456789101112 13 14 15 16 S1X1X2X1X2X1X2X3X4X3X4X3X4S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3

28、X4X3X4S4X1X2X3X4启动周期启动周期重复启动周期重复启动周期823、无冲突调度方法、无冲突调度方法 非线性流水线的禁止向量：非线性流水线的禁止向量：预约表中每一行任意两个“”之间的距离都计算出来，去掉重复的。例如，预约表的禁止向量为（3，4，6）。83由禁止向量得到冲突向量：由禁止向量得到冲突向量：C（CmCm-1C2C1）其中：m是禁止向量中的最大值。如果i在禁止向量中，则Ci1，否则Ci0。例如：对于上面的预约表，C（101100）。84 由冲突向量构造状态图：由冲突向量构造状态图：把冲突向量送入一个m位逻辑右移移位器，当移位器移出0时，用移位器中的值与初始冲突向量作“按位或”

29、运算，得到一个新的冲突向量；否则不作任何处理；如此重复m次。对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理。在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，当新形成的冲突向量出现重复时可以合并到一起。85例：例：一条有4个功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下：时间功能段功能段1234567S1XXS2XXS3XXS4X86(1)写出流水线的禁止向量和初始冲突向量。(2)画出调度流水线的状态图。(3)求流水线的最小启动循环和最小平均启动距离。(4)求平均启动距离最小的恒定循环。87解：解：禁止向量为：（2，4，6）初始冲突向量：101010初始

30、冲突向量逻辑右移2、4、6位时，不作任何处理，逻辑右移1、3、5和大于等于7时，要进行处理。887*7*1537*7*53501089初始冲突向量右移1位之后：010101101010111111，初始冲突向量右移3位之后：000101101010101111，初始冲突向量右移5位之后：000001101010101011，初始冲突向量右移7位或大于7位后：还原到它本身。例外：中间冲突向量101111右移5位之后：000001101010101011，中间冲突向量101011右移3位之后：000101101010101111，中间冲突向量101011右移5位之后：000001101010101

31、011。90简单循环：状态图中各种冲突向状态图中各种冲突向量只经过一次的启动循环。量只经过一次的启动循环。简单循环的个数一般是有限的。由简单循环可以计算出平均启动距离。91简单循环简单循环平均启动距离平均启动距离（1，7）4（3，7）5（5，7）6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）792最小的启动循环为（1，7）或（3，5）。其平均启动距离为4。平均启动距离最小的恒定循环为5。93最小启动循环最小启动循环(3,5)的流水线工作状态的流水线工作状态时时间间功能段功能段123456789101112131415S1X1X2X1X3X2X4X3S2X1X2X1X2X3X4X3

32、S3X1X1X2X2X3X3X4S4X1X2X3X4启动周期启动周期重复启动周期重复启动周期94最小启动循环最小启动循环(1,7)(1,7)的流水线工作状态的流水线工作状态时间时间功能段功能段123456789101112 13 14 15S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4启动周期启动周期重复启动周期重复启动周期95恒定启动循环恒定启动循环(5)(5)的流水线工作状态的流水线工作状态时间时间功能段功能段123456789101112131415S1X1X2X1X3X2S2X1X1X2X2X3S3X1X1X2X2X3X3S4X1X2X3启动周期启动周期重复启动周期重复启动周期96