《计算机体系结构》第五章.ppt

利用堆栈技术模拟 LRU在不同n条件下页面变化时空图及命中率。LRU算法的实现方法:堆栈法、比较对法4 存贮体系的两个分支 虚拟存贮器的简单工作过程 Cache主存体系与虚拟存储器异同之处5 内部定向原理介绍 内部定向原理的有向图和有向简图的绘制 组相联映象的例子 页面替换时空图 主存地址到Cache地址的变换,3 替换算法及其实现FIFO、LRU、OPT上述算法在给定地址流及主存页面数下页面变化时空图主存页面数n的大小对命中率的影响,6 解：1）,主存,Cache,2）,01234567,主存页号,1位 1位 1位,1位 1位,3)可放入Cache 0组的主存块号:0 1 4 5 可放入Cache 1组的主存块号:2 3 6 74)凡是不命中就是失效;失效而发生替换就是争用。块失效、块争用的时刻 t=6,7,9,10,11,12,14,155)tA=H*tc+(1-H)*tm=0.2*2+0.8*15=12.4(ns),块争用:换出了不该换出的页面.所以:即失效又争用的时刻是:t=10,11,15,t 块流,失 失 失 中 失 失 失 中 失 争 争 失 中 失 争,例 考虑一个920个字的程序，其访问辅存的地址流为20，22，208，214，146，618，370，490，492，868，916，728。若页面大小为200字，主存容量为400字，采用全相联FIFO替换算法，请按访存的各个时刻，写出其虚页地址流，计算主存的命中率；,解 虚页号虚地址页面大小 页面大小为200字，主存容量为400字，可知主存页数为2页。其虚页地址流为 0，0，1，1，0，3，1，2，2，4，4，3 下图给出了采用FIFO替换算法替换时的实际装入和替换过程。其中，“#”标记的是候选替换的虚页页号，下划线表示命中。,t虚地址页面流,H=6/12=0.5,6 交叉访问的存储器,主存储器由多个模块构成。假设主存储器包含m=2a个存储器模块，每个模块包含w=2b个存储单元（字），则总存储容量为,多体交叉存储器的两种组织方式交叉访问的存储器可以分为两种：(1)低位交叉方式（体内断续，体间连续）(2)高位交叉方式（体内连续，体间断续）,1）低位交叉方式存储器地址的低a位用来指明存储器模块，高b位是每个模块内的字地址。低位m路交叉存取如下图：,b位,a位,地址译码器,MAB,0,m,m(w-1),MDB,M0,MAB,1,m+1,mw-m+1,MDB,M1,MAB,m-1,2m-1,mw-1,MDB,Mm-1,WAB,字,模块,地址,a,b,数据总线,存储器数据缓冲器,模块地址缓冲器,字地址缓冲器,2）高位交叉方式存储器地址的高a位作为存储器模块地址，邻接的存储器单元被分配在同一个存储器模块中，在每个存储器周期内，只能对各模块存取一个字。所以不支持邻接单元的成块存取。高位m路交叉存取如下图：,地址译码器,MAB,0,1,w-1,MDB,M0,MAB,w,w+1,2w-1,MDB,M1,MAB,(m-1)w,mw-w-1,mw-1,MDB,Mm-1,WAB,字,模块,地址,a,b,数据总线,存储器数据缓冲器,模块地址缓冲器,字地址缓冲器,3）两种方式的比较（1）低位交叉以流水线方式支持成块存取 将存储器周期称为主周期，细分为m个小周期（m称为交叉存取度），如8路交叉，m=8，w=8，a=b=3，设为主周期，为小周期，则,8路低位交叉存取如下图：,0,8,56,存储器地址寄存器(6位),M0,1,9,57,M1,2,10,58,M2,3,11,59,M3,4,12,60,M4,5,13,61,M5,6,14,62,M6,7,15,63,M7,数据,低位交叉流水线方式示意图：,W0,W7,W6,W5,W4,W3,W2,W1,时间,为主周期，=/m为小周期，m为交叉存取度,（2）如果应用问题很少共享地址空间，把一个进程的几页集中在高位交叉存储器的某个给定的存储器模块中，能有效的减少存储器干扰，即每个存储器模块只和一台处理机有关，可以减少存储器冲突。,将高位与低位交叉存取加以组合。高位交叉时，各存储器模块内的地址是按顺序连续编排的。对8个存储模块，将它们分为2个存储器，体内采用4路低位交叉存取。示意图如下：,4）容错,0,4,28,存储器地址寄存器(6位),M0,1,5,29,M1,2,6,30,M2,3,7,31,M3,32,36,60,M4,33,37,61,M5,34,38,62,M6,35,39,63,M7,体0,体1,体地址,字地址,模块地址,对8个存储模块，将它们分为4个存储器，体内采用2路低位交叉存取。示意图如下：,0,2,14,存储器地址寄存器(6位),M0,1,3,15,M1,16,18,30,M2,17,19,31,M3,32,34,46,M4,33,35,47,M5,48,50,62,M6,49,51,63,M7,体0,体2,体地址,字地址,模块地址,体1,体3,在一个模块发生故障的情况下：8路（1体）交叉存取存储器的最大存储器带宽减少到零；4路2体交叉存储器的最大带宽减少到每周期4个字（只有一个体被废弃）；2路4体交叉存储器中，仍有3个体工作，所以最大带宽为6个字。,习题：假定一个由16个存储器模块构成的主存储器系统有下列三种交叉存储器设计方案。每个模块的容量为1M字节，机器按字节寻址。设计1：用1个存储体16路交叉。设计2：用2个存储体8路交叉。设计3：用4个存储体4路交叉。（a）确定上述存储器组织的地址构成。（b）在上述每种存储器组织中，假定只有一个存储器模块失效，确定能获得的最大存储器带宽。,设计1：1个存储体16路交叉。a)地址构成：存储器地址寄存器(24位)b）带宽为0。,数据,设计2：2个存储体8路交叉。a)地址构成：存储器地址寄存器(24位)b）带宽为50%。,存储器地址寄存器(24位),体地址,模块地址,a)地址构成：存储器地址寄存器(24位)b）带宽为75%。,0,4,222-4,M0,3,7,M3,M12,M15,体0,体3,字地址,222-1,3*222,224-4,3*222+3,224-1,存储器地址寄存器(24位),体地址,模块地址,设计1：1个存储体16路交叉。a)地址构成：存储器地址寄存器(24位)b）带宽为0。,数据,设计2：2个存储体8路交叉。a)地址构成：存储器地址寄存器(24位)b）带宽为50%。c）,存储器地址寄存器(24位),体地址,模块地址,a)地址构成：存储器地址寄存器(24位)b）带宽为75%。,0,4,222-4,M0,3,7,M3,M12,M15,体0,体3,字地址,222-1,3*222,224-4,3*222+3,224-1,存储器地址寄存器(24位),体地址,模块地址,多体交叉存储器的两种组织方式(1)低位交叉方式（体内断续，体间连续）(2)高位交叉方式（体内连续，体间断续）,第五章 重叠、流水和向量处理机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）应具有先行控制部件 先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。先行控制部件主要包括）先行地址站，包括先行指令地址站和先行操作数地址站；）先行指令站，用来存放多条指令；）先行操作数站，用来存放多个操作数；）先行地址形成部件，用来形成先行指令地址 以及先行操作数地址；）先行操作码译码站，用来完成对多条指令的 译码并保留译码输出状态。,3）也应具有后行部件 后行部件：对指令执行后的结果进行处理的器件，称 后行部件。包括：后行数地址站，提供后行数存放地址。后行数站，存放运行的结果，并且，这些结果需送存 储器。,二、相关问题1 何谓相关：在重叠方式的指令执行过程中，由于发生了某种关联，使正在被解释的指令无法再继续下去的现象，称相关。2 相关类型1）从性质上分指令相关：重新修改了正在被解释的指令数相关：因等待前面指令执行的结果，使后面指令等待而不能连续解释。如：S=a/b+c LD R,A DIV R,B ADD R,C；要等DIV结果 ST R,S；存结果,A,B,a,b,c,s,C,S,2）按影响面大小分局部相关：相关发生时只能影响邻近几条指令的执行，这种相关影响面不大。如等待结果的数相关。全局相关：相关发生时影响面很大全局。如条件转移指令，当条件具备时，就转到其他地方去执行程序，而转移指令之后的几条语句已先后被解释了部分功能，但此时全部废弃。,3 解决指令相关1）尽可能避免指令相关,需要修改指令时变指令相关为操作数相关，统一按操作相关去处理。2）用分支程序代替被修改的指令4 解决条件转移的全局相关1）猜测法按成功支路猜测：凡是条件转移指令都将成功支路指令提前取到指令站中，此时将不成功支路指令取到后援寄存器组。按不成功支路猜测：做法与正好相反。2）分支预测：允许CPU对分支以后的指令进行译码，如P6系列CPU中，取指/译码单元使用一种优化的分支预测算法，用来在多级分支、过程调用和返回时预测指令的流向。,如 计算 A=BC if A0 GoTo n 在进行BC之前，可先对SBSC=？进行判断，决定流向。3）尽可能作成短转移，短循环：使转去的指令都在指令站中。4）增加指令站容量（P6体系中称为指令池重排序缓冲器，是一个按内容寻址的存储器阵列。可存放40个等待执行的微操作，执行单元能够以任意顺序执行重排序缓冲器中的指令。）5 解决等待结果的数相关1）推迟法：包括推迟译码分析，推迟执行。适用范围宽，但不利于速度的提高。,2）相关专用通路法 当上一条的运算结果需作下一条的源操作数时，如：LD R，A ADD R，B SUB R，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）按流水线具有功能的多少 单功能流水线：各过程段之间固定连接，不能重新构成其它流水线固定流水线 多功能流水线：流水线的各段可以进行不同的连接，从而实现不同的功能。例：TI ASC运算器 静态流水线：各过程段之间可重新连接，但不同时刻只能重构成一种不同的流水线。动画演示 动态流水线：各过程段之间可重新连接，不同时刻可重构成多种流水线。动画演示5）按部件在同一时刻送出支路数的多少来分。一维流水线：在同一时刻，部件只能向一个地方传送结果。阵列流水线：在同一时刻，部件可同时向多个地方传送结果。,时空图,时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。,二、流水线的执行过程及性能评价,1.均匀流水线加法流水线：,1）不相关算式计算：Si=ai+bi(i=07)共有8个算式S0=a0+b0 S1=a1+b1 S7=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+a1 S4=S0+S1 S1=a2+a3 S5=S2+S3 S2=a4+a5 S6=S4+S5 S3=a6+a7,TP=7/18（条/t）效率（）：即流水线上部件的利用率=（作用区域面积）/（完成运算所需时间矩形面积）=（7*5 t）/（18t*5）=7/18结论：相关发生时，对单条流水线而言会降低流水线性能。,2.时间匹配的非均匀流水线右图所示乘法流水线完成计算:Mi=ai*bi(i=07)（也是不相关式子）1）M0=a0*b0 M7=a7*b7,2）画出各算式在流水线上执行过程示意图,3）性能:TP=8/13（个/t）=（8*6 t）/（13t*6）=8/13,3.时间不匹配的非均匀流水线按右图所示乘法流水线完成算式:M=a0*a1*a2*a3*a4*a5*a6*a71）合理分解算式M0=a0*a1M1=a2*a3 M2=a4*a5 M3=a6*a7M4=M0*M1 M5=M2*M3 M=M4*M5,2)画出时空图,过程段 M0 M1 M2 M3 M4 M5 M,0 5 10 15 20 25 27t,3）性能 TP=7/27（个/t）=（7*6 t）/（27t*4）=7/18,1 重叠方式 重叠方式中所需时间的表达式推导及计算 解决条件转移的全局相关 解决等待结果的数相关2 流水方式一、流水方式 重叠方式的2种等待 流水线的分类用时数据类型规模功能的多少同一时刻送出支路数 均匀流水线、非均匀流水线 二、流水线的执行过程及性能评价 均匀流水线:不相关算式相关算式 时间匹配的非均匀流水线:不相关算式 时间不匹配的非均匀流水线:相关算式,三、向量处理机与向量流水处理 1.向量处理机,向量处理机：具有向量数据表示及指令的流水线处理机。运算速度常用每秒取得多少个浮点运算结果表示机器速度,以MFLOPS(Million of Floating Point Per Second)作为测量单位。,标量处理机:不具有向量数据表示和向量指令的处理机。运算速度通常用每秒执行多少指令表示机器速度，以MIPS(Million Instructions Per Second)作为测量单位。,2.向量的处理方式 计算：fi=ai*bi+ci（i=099）设各向量元素分别放在大写字母单元中:,1）横向（水平）处理 按照算式一个一个地进行计算，即按行计算 第1步计算：f0=a0*b0+c0 LD R,A0 MUL R,B0 ADD R,C0 ST R,F0,第2步计算：f1=a1*b1+c1 即将第一步中的脚标0改为1，同样用上述四条指令。直到第100步计算f99 优点：作为工作单元的通用寄存器少（本例仅用一个R）缺点：条条指令发生相关。,2）纵向（垂直）处理 将所有算式列出后，按列进行计算。如对f0 f99可分为4大步完成。第1大步：取向量 LD R0,A0：LD R99,A99 第2大步：向量乘 MUL R0,B0：MUL R99,B99 第3大步：向量加 ADD R0,C0：ADD R99,C99,LD R,A0MUL R,B0ADD R,C0ST R,F0,第4大步：送结果 ST R0,F0：ST R99,F99优点：解决了相关问题，将原来条条发生相关改为条条不相关。缺点：在向量数据较多时，所用的寄存器数目多。如本例共用了一百个寄存器（R0R99），因而在向量数据不多时，可用纵向处理，而向量数据较多时，可用纵横处理。,第1组，第2组，第10组。组内采用纵向处理，组间采用横向处理。如第1组：取向量 LD R0,A0：LD R9,A9 向量乘 MUL R0,B0：MUL R9,B9,基本思想：将所有向量算式分为若干组，如f0 f99 可分为10个组：,3）纵横（分组）处理,向量加 ADD R0,C0：ADD R9,C9 送结果 ST R0,F0：ST R9,F9 其余各组与第1组类似，因而总共用了10个寄存器（R0 R9）,3.提高向量处理机性能的主要技术,1)CRAY-1简介 美国CRAY公司 1976年 每秒亿次浮点运算 主频：80MHz 字长：64位,3）向量寄存器组结构 共有8个向量寄存器组（V0V7），每个组可存放64个长度为64位的二进制数的向量数据。,2）CRAY-1向量指令类型,CRAY-1有标量类和向量类指令128条，其中有4种向量类指令：,Vk Vi op Vj Vk Si op Vj Vk 主存 主存 Vi,4）CRAY-1的基本结构,5）CRAY-1向量指令 每个部件都以1(=10ns=10-8S)为单位的流水线结构。逻辑运算：定点加：移位：浮点加：访存储器：浮点乘：倒数：此外，在功能部件和向量寄存器组之间相互传送也用1。6）独立总线结构 每个向量寄存器组到每个功能部件之间都有单独总线连接，在不冲突条件下，可实现功能部件之间并行运行。,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 2）画出向量指令结构图（如右上图所示）3）画出各算式执行过程示意图送数1，加法6，输出结果1，共8。,4）完成运算时间第一个结果时间+（长度-1）=(1+6+1)+(64-1)=715）向量数据处理速度计算（向量指令条数*长度）/（完成运算用时）=（1*64）/（71*10-8S）=90MFLOPS(每秒处理的浮点数个数),5.多条向量指令的执行过程 若有多条向量指令，且可并行执行时，完成运算用时，可选用时最多的那条向量指令。如:V0存储器 V3 V2V1V5 1/V4 由于除法用时最长，以它为准。1+14+1+(64-1)=79()3*64/(79*10-8S)244MFLOPS,可并行执行向量长度为64,四、向量的链接特性1.链接：当两条指令出现“写后读”相关时，若它们不存在冲突（源、目、功能部件），就可以通过向量寄存器组把所用的功能部件头尾相接。将多条相关的向量指令链接起来组成更大规模的流水线，从而进一步提高向量数据处理速度，这种链接称为向量链接。2.向量指令之间的几种链接情况1）既不相关，又无冲突 不能链接，但可并行执行（执行时间以最长向量指令时间为准）2）条条指令相关，且无冲突 可顺利链接3）条条指令相关，但有冲突不能顺利链接 执时间往往需要推迟。,3.可顺利链接的情况 有如下向量指令：V0存储器;V2V0+V1;V3V2位移;V5 V3V4;V7 1/V5 向量长度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位移;V71/V5;V0V7V1,故不能顺利链接。1）不能顺利链接时，对画向量链接特性图的影响 源冲突：第一次送出画实线，第二次送出画虚线 目冲突：第一次接收画实线，第二次接收画虚线 功能部件冲突：第一次出现画实线，第二次出现画虚线,向量长度64，上述向量指令条条相关，有冲突：,2）为了计算是否需要推迟时间，以及推迟多少时间，先计算冲突部件的有关时间。源冲突：从第一次送出到第二次送出之间的时间目冲突：从第一次接收到第二次接收之间的时间功能块：从第一次送出到第二次送入之间的时间源冲突（V1）1+7+1+1+6+1+1+4+1+1+14+1=39()目冲突（V0）1+7+1+1+6+1+1+4+1+1+14+1+1+7+1=48()功能部件（）1+1+6+1+1+4+1+1+14+1=31(),V0,冲突又分为表面冲突与实际冲突，如上例中，向量长度为30时，仅表面冲突。,说明：乘法功能部件冲突最严重，上述三个时间以最短时间为准（仅适用本例）。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,三、向量流水处理 向量的处理方式 向量指令的执行过程及性能计算,四、向量的链接特性 冲突:邻近向量指令使用了同一个部件 冲突又分为表面冲突与实际冲突 向量链接特性图的绘制 完成运算用时计算：顺利连接时间+推迟时间 有关时间、推迟时间的计算,P192 13题:在CRAY-1机上，在下列指令组中，组内哪些指令可以链接？哪些不可以链接？不能链接的原因是什么？完成各指令所需的拍数（设向量长度均为64,打入寄存器及启动功能部件各需1）。（1）V0存储器(6);V1V2+V3(6);V4V5V6(7)（2）V2V0V1;V3存储器;V4V2+V3（3）V0存储器;V2V0V1;V3V2+V0;V5V3+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）=240 MFLOPS,（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）,状态转移图及各种调度方案及其相应的平均延迟表建立：由状态转移图，从初始状态开始沿箭头走向，构成调度意义上延迟拍数成周期性重复出现的拍数循环。按此方案进行任务调度，必然无冲突。,（1，7）调度方案,（3，5）调度方案,再看下图所给出的预约表：,l段相隔8拍，那么两个任务相隔8拍流入流水线必将会争用1段；2段相隔1、5、6拍，则相隔1、5或6拍流入流水线必将会争用2段；4段相隔1拍，两个任务相隔1拍流入流水线必将会争用4段；5段相隔1拍，两个任务相隔1拍流入流水线必将会争用5段。由上图的预约表可以得到相应非线性流水线的延迟禁止表F为(1，5，6，8)。即要想不出现争用流水线功能段的现象，相邻两个任务送入流水线的间隔拍数就不能为1、5、6、8拍，这些间隔拍数应当禁止使用。即有：,延迟禁止表为：F=1，5，6，8初始冲突向量为：C=（10110001）状态转移图及调度方案：,3 指令级高级并行超级处理机 超标量处理机、超长指令字处理机和超流水线处理机是指令级高度并行的三种不同的超级处理机。让单处理机在每个时钟周期里可同时解释m（m1）条指令，称处理机并行的度为m。,1.超标量处理机是采用设置m条指令流水线同时并行处理，以实现度m(同时执行m条指令)。,2.超长指令字处理机是将水平型微码和超标量处理相结合。在编译时，将多个能并行执行的不相关或无关的操作组合在一起，形成一条有多个操作码字段的超长指令字。运行时，直接控制机器中多个相互独立的功能部件并行操作，来实现同时执行多条指令。,VLIW中的操作字段：,存/取,浮点加,浮点乘,转移,3.超流水线处理机：一台度为m的超流水线处理机的时钟只是基本机器周期的1/m。,解 过程执行,0 1 2 3 4 5 6 7 8 9 10 11 12 13 14(t)图1 常规标量流水处理机的时空图,例 指令由取指、译码和执行三个过程组成。每个过程经过的时间为t连续执行12条指令。请分别画出在常规标量流水处理机及度m均为4的超标量处理机、超长指令字处理机、超流水线处理机上工作的时空图，分别计算出它们相对常规标量流水处理机的加速比Sp。,译码取指,过程,0 1 2 3 4 5 时间（t）图2 超标量处理机的时空图,取指,译码,执行,Sp=14t/5t=2.8,过程,执行(m=4),取指,译码,图3 超长指令字处理机的时空图Sp=14t/5t=2.8,0 1 2 3 4 5 时间（t）,图4 超流水线处理机的时空图,5 5.75时间(t),0 1 2 3 4,Sp=14t/5.75t2.43,执行,译码,取指,过程,习题3 现有长度为4的向量A和B，请分别画出在下列4种结构的处理器上求点积AB的时空图，并求完成全部结果的最少时钟拍数。设处理器中每个部件的输出均可直接送到任何部件的输入端或存入缓冲器，其间的传送延时不计，指令和源操作数均能连续提供。(1)处理器有一个乘法部件和一个加法部件，不能同时工作，部件内也只能顺序方式工作，完成一次加法或乘法均只需5拍；(2)与(1)基本相同，只是乘法部件和加法部件可并行；(3)处理器有一个乘、加双功能静态流水线，乘、加均由5个流水段构成，各段经过时间要1拍；(4)处理器有乘、加两条流水线，可同时工作，各由5段构成，每段经过时间为1拍。,ABa1*b1+a2*b2+a3*b3+a4*b4,解答 长度为4向量A和B的点积为 ABa1*b1+a2*b2+a3*b3+a4*b4 共需做4乘法和3加法：c1=a1*b1,c2=a2*b2,c3=a3*b3,c4=a4*b4 d1=c1+c2,d2=c3+c4,d3=d1+d2=AB(1)乘法部件和加法部件不能同时工作，部件内也只能顺序方式工作如下图所示。,c4,加乘,由向量点积AB运算的时空图可知，完成全部运算最少为 45+3535(拍),部件,0 5 10 15 20 25 30 35 拍,(2)乘法部件和加法部件可并行的时空图 其中，e1=d1+c3,e2=e1+c4=AB,（d1=c1+c2）,c4,加乘,部件,0 5 10 15 20 25 拍,(3)处理器有一个乘、加双功能静态流水线时的时空图,加,乘,部件,0 5 8 10 15 19拍,54321,54321,(4)处理器有乘、加两条流水线，可同时工作时的时空图,加,乘,部件,0 5 8 10 15 18 拍,54321,54321,