资源预览内容
第1页 / 共70页
第2页 / 共70页
第3页 / 共70页
第4页 / 共70页
第5页 / 共70页
第6页 / 共70页
第7页 / 共70页
第8页 / 共70页
第9页 / 共70页
第10页 / 共70页
亲,该文档总共70页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
本资料来源,利用堆栈技术模拟 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=1007t 4 重叠方式需要解决的问题 1)对存储器的频繁访问 有哪些访问:取指令、取操作数、存放执行结果, I/O通道访问. 希望存储器为多体结构,以适应多种访问源的需要。 当存储器为单体结构时,需要将访问源排队,先后顺序为: 取指令、取数据、I/O通道访问、存结果,2)应具有先行控制部件 先行:在重叠操作中,当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理,这种提前取出后继指令进行相应处理,称为先行。 先行控制部件的主要包括 )先行地址站,包括先行指令地址站和先行操作数地址站; )先行指令站,用来存放多条指令; )先行操作数站,用来存放多个操作数; )先行地址形成部件,用来形成先行指令地址 以及先行操作数地址; )先行操作码译码站,用来完成对多条指令的 译码并保留译码输出状态。,2)也应具有后行部件 后行部件:对指令执行后的结果进行处理的器件,称 后行部件。包括:后行数地址站,提供后行数存放地址。后行数站,存放运行的结果,并且,这些结果需送存 储器。,二、相关问题 1 何谓相关:在重叠方式的指令执行过程中,由于发生了某种关联,使正在被解释的指令无法再继续下去的现象,称相关。 2 相关类型 1)从性质上分 指令相关:重新修改了正在被解释的指令 数相关:因等待前面指令执行的结果,使后面指令等待而不能连续解释。 如:S=a/b+c LD R , A DIV R , B ADD R , C;要等DIV结果 ST R , 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)按流水线具有功能的多少 单功能流水线:各过程段之间固定连接,不能重新构成其它流水线固定流水线 多功能流水线分: 静态流水线:各过程段之间可重新连接,但不同时刻只能重构成一种不同的流水线。 动态流水线:各过程段之间可重新连接,不同时刻可重构成多种流水线。 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*a7 1)合理分解算式 M0=a0*a1 M1=a2*a3 M2=a4*a5 M3=a6*a7 M4=M0*M1 M5=M2*M3 M=M4*M5,2) 画出时空图:,过程段 M0 M1 M2 M3 M4 M5 M,1 2 3 5 6 8 9 10 12 16 20 22 27t(t),3)性能: TP=7/27 (个 /t) =(7*6 t )/(27t*4)=7/18,1 重叠方式 重叠方式中所需时间表达式及所需时间计算 解决条件转移的全局相关 解决等待结果的数相关 2流水方式 重叠方式的两种等待 流水线的分类 均匀流水线 、非均匀流水线 流水线的执行过程及性能评价 均匀流水线 时间匹配的非均匀流水线 时间不匹配的非均匀流水线,三、向量流水处理 1. 向量的处理方式 计算:fi=ai*bi+ci (i=099) 设各向量分别放在大写字母单元中:,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) 缺点:条条指令发生相关。,2)纵向处理 将所有算式列出后,按列进行计算。如对f0 f99可分为四大步完成。 第一大步:取向量 LD R0 , A0 : LD R99 , A99 第二大步:向量乘 MUL R0 , B0 : MUL R99 , B99 第三大步:向量加 ADD R0 , C0 : ADD R99 , C99,第四大步:送结果 ST R0 , F0 : ST R99 , F99 优点:解决了相关问题,将原来条条发生相关改为条条不相关。 缺点:在向量数据较多时,所用的寄存器数目多。 如本例共用了一百个寄存器(R0R99),因而在向量数据不多时,可用纵向处理,而向量数据较多时,可用纵横处理。,3)纵横处理 基本思想:将所有算式分为若干组进行如f0 f99 可分为10组: 第一组:,第二组,第十组。 组内采用纵向处理,组间采用横向处理。 如第一组:取向量 LD R0 , A0 : LD R9 , A9 向量乘 MUL R0 , B0 : MUL R9 , B9,向量加 ADD R0 , C0 : ADD R9 , C9 送结果 ST R0 , F0 : ST R9 , F9 其余各组与第一组类似,因而总共用了10个寄存器(R0 R9) 2. CRAY-1机有关问题 1)向量指令类型 取向量: Vi存储器 存向量: 存储器Vi,向量与向量运算: Vi Vj OP Vk 向量与数据运算: Vi Vj OP B 2)向量寄存器组结构 共有8个向量寄存器组(V0V7),每个组可存放64个长度为64位的二进制数的向量数据
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号