LRU在不同n条件下页面变化时空图及命中率

1、LRU在不同n条件下页面变化时空 图及命中率 利用堆栈技术模拟利用堆栈技术模拟 LRU在不同在不同n条件下页面变化时空图及命中率。条件下页面变化时空图及命中率。 LRU算法的实现方法算法的实现方法 堆栈法、比较对法堆栈法、比较对法 虚拟存贮器的简单工作过程虚拟存贮器的简单工作过程 Cache主存体系与虚拟存储器相同之处主存体系与虚拟存储器相同之处 Cache主存体系与虚拟存储器不同之处主存体系与虚拟存储器不同之处 内部定向原理的和的绘制内部定向原理的和的绘制 组相联映象的的两个例子组相联映象的的两个例子 页面替换时空图页面替换时空图 主存地址到主存地址到Cache地址的变换地址的变换 LRU在

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

3、取指重叠。 取 译 执 取 译 执 i条 i +1条 i 条 取译执 取译执 i+1条 i条 取译执 i+1条 取译执 i+2 条取译执 LRU在不同n条件下页面变化时空 图及命中率 若一条指令的过程段划分更多时，重叠组合方式更多。 重叠解释并不能加快一条指令的实现，但能加快一段程重叠解释并不能加快一条指令的实现，但能加快一段程 序的解释。序的解释。 1）条件：设一条指令分为三个过程段，各过程段分别 用t取、t译、t执表示。 执行K条指令，分别采用顺序执行、两条重叠、 三条重叠。 2）分别列出上述三种执行方式所需时间表达式 顺序执行顺序执行 k* *（t取 取+t译译+t执执） ） 两条重叠两

4、条重叠 t取 取+ k* * t译译+(k-1) * *( ( t取取, ,t执执)max+ )max+ t执 执 三条重叠三条重叠 t取 取+( ( t译译, , t取取)max+(k-2) )max+(k-2) * *（t取 取,t译译,t执执） ） max+( ( t执 执, , t译译)max+ )max+ t执 执 LRU在不同n条件下页面变化时空 图及命中率 3) 例子例子 当当k=200，t取 取=3 t，t译 译= =4 t，t执 执=5 =5t，时，时， 分别计算上述三种执行方式的时间。分别计算上述三种执行方式的时间。 顺序执行：顺序执行：200(3+4+5)=2400t 两

5、条重叠：两条重叠：3+2004+(200- -1)5+5=1803t 三条重叠：三条重叠：3+4+(200- -2)5+5+5=1007t 4 重叠方式需要解决的问题重叠方式需要解决的问题 1）对存储器的频繁访问）对存储器的频繁访问 有哪些访问：取指令、取操作数、存放执行结有哪些访问：取指令、取操作数、存放执行结 果果, I/O, I/O通道访问通道访问. . 希望存储器为多体结构，以适应多种访问源的希望存储器为多体结构，以适应多种访问源的 需要。需要。 当存储器为单体结构时，需要将访问源排队，当存储器为单体结构时，需要将访问源排队， 先后顺序为：先后顺序为： 取指令、取数据、取指令、取数据、

6、I/O通道访问、存结果通道访问、存结果 LRU在不同n条件下页面变化时空 图及命中率 2）应具有先行控制部件）应具有先行控制部件 先行：在重叠操作中，当前一条指令在执行过先行：在重叠操作中，当前一条指令在执行过 程中就需要提前取出后面的指令进行相应处理，程中就需要提前取出后面的指令进行相应处理， 这种提前取出后继指令进行相应处理，称为先行。这种提前取出后继指令进行相应处理，称为先行。 先行控制部件的主要包括先行控制部件的主要包括 ）先行地址站，包括先行指令地址站和先行操）先行地址站，包括先行指令地址站和先行操 作数地址站；作数地址站； ）先行指令站，用来存放多条指令；先行指令站，用来存放多条指

7、令； ）先行操作数站先行操作数站，用来存放多个操作数；用来存放多个操作数； ）先行地址形成部件，用来形成先行指令地址先行地址形成部件，用来形成先行指令地址 以及先行操作数地址；以及先行操作数地址； ）先行操作码译码站，用来完成对多条指令的先行操作码译码站，用来完成对多条指令的 译码并保留译码输出状态。译码并保留译码输出状态。 LRU在不同n条件下页面变化时空 图及命中率 LRU在不同n条件下页面变化时空 图及命中率 后行 数地 址站 先行 操作 数地 址站 先行 指令 地址 站 先行 操作 数站 先行 指令 站 存储器 地址形成部件 先行操作码译码站 OP字段 ALU 后行数站 地址 字段 算

8、术逻辑运算部 件在执行阶段完 成各种运算 LRU在不同n条件下页面变化时空 图及命中率 二、相关问题二、相关问题 1 何谓相关：在重叠方式的指令执行过程中，由于何谓相关：在重叠方式的指令执行过程中，由于 发生了某种关联，使正在被解释的指令无法再继发生了某种关联，使正在被解释的指令无法再继 续下去的现象，称相关。续下去的现象，称相关。 2 相关类型相关类型 1）从性质上分）从性质上分 指令指令相关：重新修改了正在被解释的指令相关：重新修改了正在被解释的指令 数数相关：因等待前面指令执行的结果，使后相关：因等待前面指令执行的结果，使后 面指令等待而不能连续解释。面指令等待而不能连续解释。 如：如：

9、S=a/b+c LD R , A DIV R , B ADD R , C；要等；要等DIV结果结果 ST R , S；存结果；存结果 A B C S a b c s LRU在不同n条件下页面变化时空 图及命中率 2）按影响面大小分）按影响面大小分 局部相关：相关发生时只能影响邻近几条指令的执局部相关：相关发生时只能影响邻近几条指令的执 行，这种相关影响面不大。如等待结果的数相关。行，这种相关影响面不大。如等待结果的数相关。 全局相关：相关发生时影响面很大全局相关：相关发生时影响面很大全局。如条全局。如条 件转移指令，当条件具备时，就转到其他地方去执行件转移指令，当条件具备时，就转到其他地方去执

10、行 程序，而转移指令之后的几条语句已先后被解释了部程序，而转移指令之后的几条语句已先后被解释了部 分功能，但此时全部废弃。分功能，但此时全部废弃。 i-1 j i j+1 i+1 j+2 i+2 . . Yes No 成功支路 不成功支路 条转指令 LRU在不同n条件下页面变化时空 图及命中率 3 解决指令相关解决指令相关 1）尽可能避免指令相关）尽可能避免指令相关 2）用分支程序代替被修改的指令）用分支程序代替被修改的指令 4 解决条件转移的全局相关解决条件转移的全局相关 1）猜测法）猜测法 按成功支路猜测：凡是条件转移指令都将成功按成功支路猜测：凡是条件转移指令都将成功 支路指令提前取到指

11、令站中，此时将不成功支支路指令提前取到指令站中，此时将不成功支 路指令取到后援寄存器组。路指令取到后援寄存器组。 按不成功支路猜测：做法与按不成功支路猜测：做法与正好相反。正好相反。 2）分支预测：）分支预测： 允许允许CPU对分支以后的指令进行译码，如对分支以后的指令进行译码，如P6系列系列 CPU中，取指中，取指/译码单元使用一种优化的分支预测算译码单元使用一种优化的分支预测算 法，用来在多级分支、过程调用和返回时预测指令法，用来在多级分支、过程调用和返回时预测指令 的流向。的流向。 LRU在不同n条件下页面变化时空 图及命中率 如如 计算计算 A=BC if A0 GoTo n 在进行在

12、进行BC之前，可先对之前，可先对SBSC=？进行判断，？进行判断， 决定流向。决定流向。 3）尽可能作成短转移，短循环：使转去的指令都）尽可能作成短转移，短循环：使转去的指令都 在指令站中。在指令站中。 4）增加指令站容量）增加指令站容量 （P6体系中称为指令池体系中称为指令池重排序缓冲器，是重排序缓冲器，是 一个按内容寻址的存储器阵列。可存放一个按内容寻址的存储器阵列。可存放40个等待个等待 执行的微操作，执行单元能够以任意顺序执行重执行的微操作，执行单元能够以任意顺序执行重 排序缓冲器中的指令。）排序缓冲器中的指令。） 5 解决等待结果的数相关解决等待结果的数相关 1）推迟法：包括推迟译码

13、分析，推迟执行。）推迟法：包括推迟译码分析，推迟执行。 适用范围宽，但不利于速度的提高。适用范围宽，但不利于速度的提高。 LRU在不同n条件下页面变化时空 图及命中率 2）相关专用通路法）相关专用通路法 当上一条的运算结果当上一条的运算结果 需作下一条的源操作需作下一条的源操作 数时，如：数时，如： LD R，A ADD R，B SUB R，C 可建一个相关专用比可建一个相关专用比 常规通路提前常规通路提前1获取获取 源操作数。源操作数。 ALU A B registers 相 关 专 用 通 路 常 规 通 路 数据总线 LRU在不同n条件下页面变化时空 图及命中率 一、流水方式的出现一、流

14、水方式的出现 1 重叠方式的两种等待重叠方式的两种等待 1）等待译码）等待译码 当当ti译 译 ti+1取 取时，即： 时，即： 2）等待执行）等待执行 ti执 执 ti+1译 译时，即： 时，即： i+1 i 等待译码 时间 取译执 取 译 执 取译 执 i i+1 执取译 等待执行时间 LRU在不同n条件下页面变化时空 图及命中率 1 t 2 t 3 t 4 t 5 t LRU在不同n条件下页面变化时空 图及命中率 2）当某过程段用时较长，又不便于细分时，可用多套）当某过程段用时较长，又不便于细分时，可用多套 相同设备来实现时间匹配。如第相同设备来实现时间匹配。如第3个过程段用时个过程段用

15、时2t， 其余其余1，2，4用时均为用时均为t：（非均匀流水线）：（非均匀流水线） 4 流水线的分类流水线的分类 1）按各过程段用时是否全等划分）按各过程段用时是否全等划分 均匀流水线：各过程段用时全等均匀流水线：各过程段用时全等 非均匀流水线：各过程段用时不全等（如上图）非均匀流水线：各过程段用时不全等（如上图） ）时间匹配的非均匀流水线。）时间匹配的非均匀流水线。 ）时间不匹配的非均匀流水线。时间不匹配的非均匀流水线。 1 t 2 t 4 t 3 2t 3 2 1 LRU在不同n条件下页面变化时空 图及命中率 2）按处理的数据类型）按处理的数据类型 标量流水线：用于对标量数据进行流水处理。

16、标量流水线：用于对标量数据进行流水处理。 向量流水线：用于对向量数据进行流水处理。向量流水线：用于对向量数据进行流水处理。 （向量很适合流水处理）（向量很适合流水处理） 3）按流水线的规模）按流水线的规模 操作流水线：如将一条指令划分为多个过程段操作流水线：如将一条指令划分为多个过程段 进行流水处理。规模最小进行流水处理。规模最小 指令流水线：以指令为单位进行处理，用于多指令流水线：以指令为单位进行处理，用于多 进程、多任务。规模较大进程、多任务。规模较大 宏流水线：以程序的逻辑功能段为单位进行流宏流水线：以程序的逻辑功能段为单位进行流 水处理。规模最大水处理。规模最大 1 t 2 t 3 2

17、t 4 t LRU在不同n条件下页面变化时空 图及命中率 4）按流水线具有功能的多少）按流水线具有功能的多少 单功能流水线：各过程段之间固定连接，不能重单功能流水线：各过程段之间固定连接，不能重 新构成其它流水线新构成其它流水线固定流水线固定流水线 多功能流水线分：多功能流水线分： 静态流水线：各过程段之间可重新连接，但不同静态流水线：各过程段之间可重新连接，但不同 时刻只能重构成一种不同的流水线。时刻只能重构成一种不同的流水线。 动态流水线：各过程段之间可重新连接，不同时动态流水线：各过程段之间可重新连接，不同时 刻可重构成多种流水线。刻可重构成多种流水线。 5）按部件在同一时刻送出支路数的

18、多少来分。）按部件在同一时刻送出支路数的多少来分。 一维一维流水线：在同一时刻，部件只能向一个地方流水线：在同一时刻，部件只能向一个地方 传送结果。传送结果。 阵列流水线：在同一时刻，部件可同时向多个地阵列流水线：在同一时刻，部件可同时向多个地 方方 传送结果。传送结果。 LRU在不同n条件下页面变化时空 图及命中率 二流水线的执行过程及性能评价二流水线的执行过程及性能评价 1 均匀流水线均匀流水线 加法流水线：加法流水线： 1 t 2 t 3 t 4 t 5 t LRU在不同n条件下页面变化时空 图及命中率 1）不相关算式 计算：Si = ai + bi (i=07) 共有8个算式 S0=a

19、0+b0 S1=a1+b1 S7=a7+b7 画出各算式在流水线上执行过程时空图 S0 S1 S2 S3 S4 S5 S6 S7 过程段 1 2 3 4 5 6 7 8 9 10 11 12 5 4 3 2 1 t(t) LRU在不同n条件下页面变化时空 图及命中率 性能计算： 吞吐率（TP）：单位时间输出的结果数。 TP=(输出结果数输出结果数)/（完成算式总用时）（完成算式总用时） =8/12=2/3（条/t） 而无流水时：TP=1/5 （条/t） 2）相关算式 计算：S=a0+a1+a2+a3+a4+a5+a6+a7 对相关算式要合理分解算式尽量分解为少相关算 式： S0=a0+a1 S

20、4=S0+S1 S1=a2+a3 S5=S2+S3 S2=a4+a5 S6=S4+S5 S3=a6+a7 LRU在不同n条件下页面变化时空 图及命中率 TP=7/18 （条 /t） 效率（）：即流水线上部件的利用率 =（作用区域面积）（作用区域面积）/（完成运算所需时间矩形面积）（完成运算所需时间矩形面积） =（7*5 t ）/（18t*5）=7/18 结论：结论：相关发生时，对单条流水线而言会降低流水线性 能。 S0 S1 S2 S3 S4 S5 S 过程段 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 t(t) LRU在不同n

21、条件下页面变化时空 图及命中率 2 时间匹配的非均匀流水线时间匹配的非均匀流水线 右图所示乘法流水线右图所示乘法流水线 完成计算完成计算:Mi=ai*bi (i=07) （也是不相关式子）（也是不相关式子） 1） M0=a0*b0 M7=a7*b7 1 t 2 t 4 t 3 3t 3 3 1 32 2）画出各算式在流水线上执行过程示意图）画出各算式在流水线上执行过程示意图 M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7 过程段 4 33 32 31 2 1 1 2 3 4 5 6 7 8 9 10 11 12 13 t(t) LRU在不同n条件下页面变化时空 图及命中率 3）

22、性能）性能: 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 1 t 2 t 4 t 3 3 t 2) 画出时空图: 过程段 M0 M1 M2 M3 M4 M5 M 4 3 2 1 1 2 3 5 6 8 9 10 12 16 20 22 27t(t) LRU在不同n条件下页面变化时空

23、图及命中率 3）性能: TP=7/27 （个 /t） =（7*6 t ）/（27t*4）=7/18 LRU在不同n条件下页面变化时空 图及命中率 解决条件转移的全局相关解决条件转移的全局相关 解决等待结果的数相关解决等待结果的数相关 重叠方式的两种等待重叠方式的两种等待 流水线的分类流水线的分类 均匀流水线均匀流水线 、非均匀流水线、非均匀流水线 流水线的执行过程及性能评价流水线的执行过程及性能评价 均匀流水线均匀流水线 时间匹配的非均匀流水线时间匹配的非均匀流水线 时间不匹配的非均匀流水线时间不匹配的非均匀流水线 LRU在不同n条件下页面变化时空 图及命中率 三、向量流水处理三、向量流水处理

24、 1. 向量的处理方式 计算：fi=ai*bi+ci （i=099） 设各向量分别放在大写字母单元中: a1 a0 a99 . A0 A1 A99 c99 . C0 C1 C99 c1 c0 . b1 b0 b99 . B0 B1 B99 f1 f0 f99 . F0 F1 F99 LRU在不同n条件下页面变化时空 图及命中率 1）横向处理 按照算式一个一个地进行计算，即按行计算 第一步计算：f0=a0*b0+c0 LD R , A0 MUL R , B0 ADD R , C0 ST R , F0 第二步计算：f1=a1*b1+c1 即将第一步中的脚标0改为1，同样用上述四条指令。 直到第一百

25、步，f99 优点：作为工作单元的通用寄存器少（本例 仅用一个R） 缺点：条条指令发生相关。 LRU在不同n条件下页面变化时空 图及命中率 2）纵向处理 将所有算式列出后，按列进行计算。如对f0 f99可 分为四大步完成。 第一大步：取向量 LD R0 , A0 ： LD R99 , A99 第二大步：向量乘 MUL R0 , B0 ： MUL R99 , B99 第三大步：向量加 ADD R0 , C0 ： ADD R99 , C99 LRU在不同n条件下页面变化时空 图及命中率 第四大步：送结果 ST R0 , F0 ： ST R99 , F99 优点：解决了相关问题，将原来条条发生相关 改

26、为条条不相关。 缺点：在向量数据较多时，所用的寄存器数目 多。 如本例共用了一百个寄存器（R0R99）， 因而在向量数据不多时，可用纵向处理，而向量 数据较多时，可用纵横处理。 LRU在不同n条件下页面变化时空 图及命中率 3）纵横处理 基本思想：将所有算式分为若干组进行如f0 f99 可分为10组： 第一组：，第二组，第十组。 组内采用纵向处理，组间采用横向处理。 如第一组：取向量 LD R0 , A0 ： LD R9 , A9 向量乘 MUL R0 , B0 ： MUL R9 , B9 LRU在不同n条件下页面变化时空 图及命中率 向量加 ADD R0 , C0 ： ADD R9 , C9

27、 送结果 ST R0 , F0 ： ST R9 , F9 其余各组与第一组类似，因而总共用了10个寄存 器（R0 R9） 2. CRAY-1机有关问题 1）向量指令类型 取向量： Vi存储器 存向量： 存储器Vi LRU在不同n条件下页面变化时空 图及命中率 向量与向量运算： Vi Vj OP Vk 向量与数据运算： Vi Vj OP B 2）向量寄存器组结构 共有8个向量寄存器组 （V0V7），每个组可存 放64个长度为64位的二进 制数的向量数据。 V0.0 : V0.63 V1.0 63 V7.0 63 LRU在不同n条件下页面变化时空 图及命中率 3）多功能部件 每个部件都以1(=10

28、ns=10-8S)为单位的流水线结构。 逻辑运算： 定点加： 移位 ： 浮点加： 访存储器： 浮点乘： 除法 ： 此外，在功能部件和向量寄存器组之间相互传送也用 1。 4）独立总线结构 每个向量寄存器组到每个功能部件之间都有单独总线连 接，在不冲突条件下，可实现功能部件之间并行运行。 2 4 6 14 3 6 7 LRU在不同n条件下页面变化时空 图及命中率 3. 向量指令的执行过程及性能计算 已知向量指令：V2 V1 + V0 （浮点加） 向量长度为64，实际上是64组向量数据求和。 1）写出64组算式 V2.0V1.0 + V0.0 V2.1V1.1 + V0.1 64 V2.63 V1.

29、63 + V0.63 2）画出向量指令结构图（如右上图所示） 3）画出各算式执行过程示意图 送数1，加法6，输出结果1，共8。 6 V0V1V2 1 1 加 LRU在不同n条件下页面变化时空 图及命中率 4）完成运算时间 第一个结果时间 +（长度-1）=(1+6+1) +(64-1) =71 5）向量数据处理速度计算 （向量指令条数*长度）/（完成运算用时） =（1*64）/（71*10-8S）=90MFLOPS (每秒处理的浮点数个数) V2.0 V2.1 V2.62 V2.63 过程段 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 64 65 66 67 68 69

30、70 71t () 注：图中= 64 LRU在不同n条件下页面变化时空 图及命中率 4.多条向量指令的执行过程 若有多条向量指令，且可并行 执行时，完成运算用时，可选 用时最多的那条向量指令。如: V0存储器 可并行执行， V3 V2V1 向量长度为64 V6 V5V4 由于除法用时最长，以它为准。 1+14+1+(64-1)=79() 3*64/(79*10-8S)244MFLOPS 7 V1V2V3 1 1 乘 14 V4V5V6 1 1 除 6V0 访存 1 1 LRU在不同n条件下页面变化时空 图及命中率 四、向量的链接特性 1. 链接：将多条相关的向量指令链接起来组成 更大规模的流水

31、线，从而进一步提高向量数据 处理速度，这种链接称为向量链接。 2. 向量指令之间的几种情况 1）既不相关，又无冲突 不能链接，但可并行执行（执行时间以最长向 量指令时间为准） 2）条条指令相关，且无冲突 可顺利链接 3）条条指令相关，但有冲突不能顺利链接，执行 时间往往需要推迟。 LRU在不同n条件下页面变化时空 图及命中率 3.可顺利链接的情况 有如下向量指令： V0存储器; V2V0+V1; V3V2位移; V5 V3V4; V7 V5V6 向量长度64 相关：上一条向量指令的结果作下一条指令的一个源 操作数。 1）画出向量链接特性图 6V0 访存 1 1 7 V4V5 1 1 乘 6 V

32、1V2 1 1 加 4 V3 1 1 位移 14 V6V7 1 1 除 LRU在不同n条件下页面变化时空 图及命中率 2）完成运算有时 6+2+6+2+4+2+7+2+14+2+（64-1）=110() 3）计算向量数据处理速度： 5*64/(110*10-8S)291MFLOPS 此处结论：相关在向量链接中有利于向量 据处理速度的提高。 4.不能顺利链接的情况 有如下向量指令： V0V0存储器; V2V0V1V1; V4V2+V3; V5V4位移; V7V5V6; V0V0V7V1V1 LRU在不同n条件下页面变化时空 图及命中率 故不能顺利链接 1）不能顺利链接时，对画向量链接特 性图的影

33、响。 源冲突：第一次送出画实线，第二 次送出画虚线 目冲突：第一次接收画实线，第二 次接收画虚线 功能部件冲突：第一次出现画实线， 第二次出现画虚线 V0目寄存器冲突 V1源寄存器冲突 * 功能部件冲突 冲突 V0存储器 实线 V0 V7V1 虚线 V0+V1V2 实线 V7V1V0 虚线 向量长度64，上述向量指令条条相关，有冲突： LRU在不同n条件下页面变化时空 图及命中率 2）为了计算是否需要推迟时间，以及推迟多少时间，先 计算冲突部件的有关时间。 源冲突：从第一次送出到第二次送出之前1 目冲突：从第一次接收到第二次接收之前1 功能块：从第一次送出到第二次送入之前1 源冲突（V1）1+

34、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() 6 V0 访存 1 1 6 V5 1 加 7 V1 V2 1 1 乘V3 1 14 V6V7 1 1 除 V4 4 1 位移 7 乘 1 1 1 LRU在不同n条件下页面变化时空 图及命中率 说明：乘法功能部件冲突最严重，上述三个时间以最短 时间为准（仅适用本例）。 3）推迟时间计算： 当长度大于最短有关时间有关时间时，实际需要推迟时间为： 向量时间向量时间 有关时间有关时间 当长度小于等于有

35、关时间时，实际不用推迟，可视 为表面冲突表面冲突。 本例推迟时间为：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 LRU在不同n条件下页面变化时空 图及命中率 P224 17题:在CRAY-1机上，在下列指令组中，组内哪些指 令可以链接？哪些不可以链接？不能链接的原因是什么？ 完成各指令所需的拍数（设向量长度均为64,打入寄存 器及启动功能部件各需1）。 （1）V0存储器 (6);

36、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）= 240 MFLOPS LRU在不同n条件下页面变化时空 图及命中率 （3）条条指令相关，但有冲突不能顺利链接 6 V0 访存

37、1 1 6 V3 V4 1 加 7 V1 V2 1 1 乘 6V0 访存 1 1 6 V3 1 加 7 V1V2 1 1 乘1 6 V4V5 1 1 加 LRU在不同n条件下页面变化时空 图及命中率 源冲突（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）条条相关，且无冲突可顺利链接 6V0 访存 1 1 7 V3 1 乘 14 V1 1 1 倒数 1 6 V4V5 1 1 加 1 V2

38、1+6+2+14+2+7+2+6+1+（64-1）=104() 4*64/（104*10 -8S ）246MFLOPS LRU在不同n条件下页面变化时空 图及命中率 三、向量流水处理三、向量流水处理 向量的处理方式向量的处理方式 向量指令的执行过程及性能计算向量指令的执行过程及性能计算 四、向量的链接特性四、向量的链接特性 冲突冲突: :邻近向量指令使用了同一个部件邻近向量指令使用了同一个部件 冲突又分为表面冲突与实际冲突冲突又分为表面冲突与实际冲突 向量链接特性图的绘制向量链接特性图的绘制 完成运算用时计算：顺利连接时间完成运算用时计算：顺利连接时间+ +推迟时间推迟时间 有关时间、推迟时间

39、的计算有关时间、推迟时间的计算 LRU在不同n条件下页面变化时空 图及命中率 五加速比的概念五加速比的概念 流水线方式相对于非流水线顺序串行方式 速度提高的比值称加速比（Sp）。 设：流水线段数m，指令有n条，各段经过的时间 均为t 则： n*m*t m*t + (n-1)*t Sp = 此外，还有某种流水处理机相对于另一种流 水处理机的加速比。如超标量流水处理机相对于 常规标量流水处理机的加速比。 LRU在不同n条件下页面变化时空 图及命中率 六非线性流水线的概念六非线性流水线的概念 线性流水线中各个段之间串行地链接，既无反 馈也无跳跃，每个任务流经流水线中各个段均只 有一次，反之就是非线性

40、流水线。 S1S4S3S2 输出 输入 前馈线 反馈线 非线性流水线的连接图 LRU在不同n条件下页面变化时空 图及命中率 1234567 S1 S2 S3 S4 时间 流水线 非线性流水线的预约表 延迟禁止表为：延迟禁止表为： F=2，4，6 初始冲突向量为：初始冲突向量为：C=（101010） S1S4S3S2 输出 输入 前馈线 反馈线 非线性流水线的连接图 LRU在不同n条件下页面变化时空 图及命中率 101010 111111 101011 101111 初始 7 1 3 7 5 7 7 5 5 3 状态转移图 调度方案调度方案 平 均平 均 延延 迟迟 （1，7）4 （3，5）4

41、（5，3）4 （5，7）6 （5）5 （7） 7 如上例中： 延迟禁止表为：延迟禁止表为： F=2，4，6 初始冲突向量为：初始冲突向量为：C=（101010） 状态转移图状态转移图：各种调度方案及其相应的平均延迟表：由状 态转移图，从初始状态开始延箭头走向，构成调度意义 上延迟拍数成周期性重复出现的拍数循环。按此方案进 行任务调度，必然无冲突。 LRU在不同n条件下页面变化时空 图及命中率 七、指令级高级并行超级处理机七、指令级高级并行超级处理机 超标量处理机、超长指令字处理机和超流水线处理 机是指令级高度并行的三种不同的超级处理机。让单处理 机在每个时钟周期里可同时解释m（m1）条指令，称

42、处 理机并行的度为m。 1. 超标量处理机超标量处理机是采用设置m条指令流水线同时并行，来 实现度为m的。 2. 超长指令字处理机超长指令字处理机是将水平型微码和超标量处理相结合。 在编译时在编译时，将多个能并行执行的不相关或无关的操作组合 在一起，形成一条有多个操作码字段的超长指令字。运行 时，直接控制机器中多个相互独立的功能部件并行操作， 来实现同时执行多条指令。 3. 超流水线处理机超流水线处理机：一台度为m的超流水线处理机的时钟 只是基本机器周期的1/m。 LRU在不同n条件下页面变化时空 图及命中率 解 过程 执行 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

43、 (t) 图1 常规标量流水处理机的时空图常规标量流水处理机的时空图 例例1 指令由取指、译码和执行三个过程组成。每指令由取指、译码和执行三个过程组成。每 个过程经过的时间为个过程经过的时间为t连续执行连续执行12条指令。请分条指令。请分 别画出在常规标量流水处理机及度别画出在常规标量流水处理机及度m均为均为4的超标的超标 量处理机、超长指令字处理机、超流水线处理机量处理机、超长指令字处理机、超流水线处理机 上工作的时空图，分别计算出它们相对常规标量上工作的时空图，分别计算出它们相对常规标量 流水处理机的加速比流水处理机的加速比Sp。 123456789 10 11 12 123456789

44、10 11 12 123456789 10 11 12 译码 取指 LRU在不同n条件下页面变化时空 图及命中率 过程 4812 3711 2610 159 4812 3711 2610 159 4812 3711 2610 159 0 1 2 3 4 5 时间（t） 图2 超标量处理机的时空图 取指 译码 执行 Sp=14t/5t=2.8 LRU在不同n条件下页面变化时空 图及命中率 过程 123 123 123 123 123 123 执行 (m=4) 取指 译码 图3 超长指令字处理机的时空图 Sp=14t/5t=2.8 0 1 2 3 4 5 时间（t） LRU在不同n条件下页面变化时

45、空 图及命中率 图4 超流水线处理机的时空图 4812 3711 2610 159 4812 3711 2610 159 4812 3711 2610 159 5 5.75时间(t) 0 1 2 3 4 Sp=14t/5.75t2.43 执行 译码 取指 过程 LRU在不同n条件下页面变化时空 图及命中率 例2 现有长度为4向量A和B，请分别画出在下列4种结构 的处理器上求点积AB的时空图，并求完成全部结果的最 少时钟拍数。设处理器中每个部件的输出均可直接送到 任何部件的输入端或存入缓冲器，其间的传送延时不计， 指令和源操作数均能连续提供。 (1)处理器有一个乘法部件和一个加法部件，不能同时工

46、 作，部件内也只能顺序方式工作，完成一次加法或乘法 均只需5拍； (2)与(1)基本相同，只是乘法部件和加法部件可并行； (3)处理器有一个乘、加双功能静态流水线，乘、加均由 5个流水段构成，各段经过时间要1拍； (4)处理器有乘、加两条流水线，可同时工作，各由5段 构成，每段经过时间为1拍。 LRU在不同n条件下页面变化时空 图及命中率 解答 长度为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

47、)乘法部件和加法部件不能同时工作，部件内也只能顺序 方式工作如下图所示。 由向量点积AB运算的时空图可知，完成全部运算最少为 4 5十3 535(拍) 部件 0 5 10 15 20 25 30 35 拍 c4 d1d2d3 c1c2c3 加 乘 LRU在不同n条件下页面变化时空 图及命中率 (2)乘法部件和加法部件可并行的时空图乘法部件和加法部件可并行的时空图 其中，e1=d1+c3, e2=e1+c4= AB d1e1e2 c1c2c3c4 部件 加 乘 0 5 10 15 20 25 拍 （d1=c1+c2） LRU在不同n条件下页面变化时空 图及命中率 (3)处理器有一个乘、加双功能静

48、态流水线时的时 空图 d1 d2d3 d1 d2d3 d1 d2d3 d1 d2d3 d1 d2d3 c1c2 c3c4 c1c2c3 c4 c1c2c3c4 c1c2c3c4 c1c2c3c4 加 乘 部件 0 5 8 10 15 19拍 5 4 3 2 1 5 4 3 2 1 LRU在不同n条件下页面变化时空 图及命中率 (4)处理器有乘、加两条流水线，可同时工作时的 时空图 d1d2d3 d1d2d3 d1d2d3 d1d2d3 d1d2d3 c1c2 c3c4 c1c2c3 c4 c1c2c3c4 c1c2c3c4 c1c2c3c4 加 乘 部件 0 5 8 10 15 18 拍 5

49、4 3 2 1 5 4 3 2 1 LRU在不同n条件下页面变化时空 图及命中率 2在下述流水线上完成 算式 M=ai (i=18) （1）合理分解算式； （2）画出各算式执行过 程时空图； （3）计算吞吐率和效率。 1 31 24 33 32 3t tt t 1 设将指令划分为三个时间段t取t译t执来完成。分别采 用顺序执行，有两条指令重叠，有三条指令重叠。都 执行K条指令，分别写出三种执行方式所需时间表达式； 若K=300, t取=4t， t译=5t， t执=6t，分别计算三种 执行方式所需时间 LRU在不同n条件下页面变化时空 图及命中率 1.解：解： 1）顺序执行：）顺序执行： t = k* *（t取 取+t译译+t