利用堆栈技术模拟
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条的取指重叠 。
取 译 执 取 译 执
i 条 i +1 条
i 条 取 译 执
取 译 执 i+1 条
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取 =3Δ t,t译 =4Δ t,t执 =5Δ t,时,
分别计算上述三种执行方式的时间。
顺序执行,200× (3+4+5)=2400Δ t
两条重叠,3+200× 4+(200-1)× 5+5=1803Δ t
三条重叠,3+4+(200-2)× 5+5+5=1007Δ t
4 重叠方式需要解决的问题
1) 对存储器的频繁访问
① 有哪些访问,取指令, 取操作数, 存放执行结
果,I/O通道访问,
② 希望存储器为多体结构, 以适应多种访问源的
需要 。
③ 当存储器为单体结构时, 需要将访问源排队,
先后顺序为,
取指令, 取数据, I/O通道访问, 存结果
2) 应具有先行控制部件
① 先行:在重叠操作中, 当前一条指令在执行过程
中就需要提前取出后面的指令进行相应处理, 这
种提前取出后继指令进行相应处理, 称为先行 。
② 先行控制部件的主要包括
Ⅰ ) 先行地址站, 包括先行指令地址站和先行操作
数地址站;
Ⅱ ) 先行指令站, 用来存放多条指令;
Ⅲ ) 先行操作数站, 用来存放多个操作数;
Ⅳ ) 先行地址形成部件, 用来形成先行指令地址
以及先行操作数地址;
Ⅴ ) 先行操作码译码站, 用来完成对多条指令的
译码并保留译码输出状态 。
2)也应具有后行部件
后行部件:对指令执行后的结果进行处理的器件,称
后行部件。包括,
① 后行数地址站,提供后行数存放地址。
② 后行数站,存放运行的结果,并且,这些结果需送存
储器。
1ó D
êy μ×
?·??
?è D
2? ×÷
êy μ×
?·??
?è D
?· á?
μ× ?·
??
?è D
2? ×÷
êy ??
?è D
?· á?
??
′? ′¢ ?÷
μ× ?·D? 3é 2? ?t
?è D 2? ×÷? ? ò? ?? ??
OP×? ??
ALU
1ó D êy ??
μ× ?·
×? ??
?? ê? ?? ?- ?? ?? 2?
?t ?ù ?′ D ?×?? íê
3é ·÷? ? ?? ??
二, 相关问题
1 何谓相关:在重叠方式的指令执行过程中, 由于
发生了某种关联, 使正在被解释的指令无法再继
续下去的现象, 称相关 。
2 相关类型
1) 从性质上分
① 指令 相关:重新修改了正在被解释的指令
② 数 相关:因等待前面指令执行的结果, 使后
面指令等待而不能连续解释 。
如,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
2) 按影响面大小分
① 局部相关:相关发生时只能影响邻近几条指令的执
行, 这种相关影响面不大 。 如等待结果的数相关 。
② 全局相关:相关发生时影响面很大 ——全局 。 如条
件转移指令, 当条件具备时, 就转到其他地方去执行
程序, 而转移指令之后的几条语句已先后被解释了部
分功能, 但此时全部废弃 。
i-1
j
i
j + 1
i + 1
j + 2
i + 2
.,,
.,,
Y e s
No
成 功 支 路
不 成 功 支 路
条 转 指 令
3 解决指令相关
1) 尽可能避免指令相关
2) 用分支程序代替被修改的指令
4 解决条件转移的全局相关
1) 猜测法
① 按成功支路猜测:凡是条件转移指令都将成功
支路指令提前取到指令站中, 此时将不成功支
路指令取到后援寄存器组 。
② 按不成功支路猜测:做法与 ① 正好相反 。
2) 分支预测,
允许 CPU对分支以后的指令进行译码, 如 P6系列
CPU中, 取指 /译码单元使用一种优化的分支预测算
法, 用来在多级分支, 过程调用和返回时预测指令
的流向 。
如 计算 A=B﹡ C
if A< 0 GoTo n
在进行 B﹡ C之前, 可先对 SB⊕ SC=? 进行判断,
决定流向 。
3) 尽可能作成短转移, 短循环:使转去的指令都
在指令站中 。
4) 增加指令站容量
( P6体系中称为指令池 ——重排序缓冲器, 是
一个按内容寻址的存储器阵列 。 可存放 40个等待
执行的微操作, 执行单元能够以任意顺序执行重
排序缓冲器中的指令 。 )
5 解决等待结果的数相关
1) 推迟法:包括推迟译码分析, 推迟执行 。
适用范围宽, 但不利于速度的提高 。
2) 相关专用通路法
当上一条的运算结果
需作下一条的源操作
数时, 如,
LD R,A
ADD R,B
SUB R,C
可建一个相关专用比
常规通路提前 1τ 获取
源操作数 。
ALU
A B
registers










数据总线
§ 2流水方式
一, 流水方式的出现
1 重叠方式的两种等待
1) 等待译码
当 ti译 > ti+1取 时, 即,
2) 等待执行
ti执 > ti+1译 时, 即,
i+1
i
等待译码
时间
取 译 执
取 译 执
取 译 执 i
i+1 执 取 译
等待执行时间
2 产生等待的原因
重迭方式未按时间单位来划分过程段,比较粗
糙。
3 流水线上对各过程段进行时间匹配的办法。
1)将一条指令分为以 Δ t为单位的多个 Δ t过程段。
如某指令用时 5Δ t,可分为 5个过程段,(均匀流
水线 )
1
Δ t
2
Δ t
3
Δ t
4
Δ t
5
Δ t
2) 当某过程段用时较长, 又不便于细分时, 可用多套
相同设备来实现时间匹配 。 如第 3个过程段用时 2Δ t,
其余 1,2,4用时均为 Δ t,( 非均匀流水线 )
4 流水线的分类
1) 按各过程段用时是否全等划分
① 均匀流水线:各过程段用时全等
② 非均匀流水线:各过程段用时不全等 ( 如上图 )
Ⅰ ) 时间匹配的非均匀流水线 。
Ⅱ ) 时间不匹配的非均匀流水线 。
1
Δ t
2
Δ t
4
Δ t 3 2Δ t
3
2
1
2) 按处理的数据类型
① 标量流水线:用于对标量数据进行流水处理 。
② 向量流水线:用于对向量数据进行流水处理 。
( 向量很适合流水处理 )
3) 按流水线的规模
① 操作流水线:如将一条指令划分为多个过程段
进行流水处理 。 规模最小
② 指令流水线:以指令为单位进行处理, 用于多
进程, 多任务 。 规模较大
③ 宏流水线:以程序的逻辑功能段为单位进行流
水处理 。 规模最大
1
|¤t
2
|¤t
3
2 |¤t
4
|¤t
4) 按流水线具有功能的多少
① 单功能流水线:各过程段之间固定连接, 不能重
新构成其它流水线 ——固定流水线
② 多功能流水线分,
静态流水线:各过程段之间可重新连接, 但不同
时刻只能重构成一种不同的流水线 。
动态流水线:各过程段之间可重新连接, 不同时
刻可重构成多种流水线 。
5) 按部件在同一时刻送出支路数的多少来分 。
① 一维 流水线:在同一时刻, 部件只能向一个地方
传送结果 。
② 阵列流水线:在同一时刻, 部件可同时向多个地

传送结果 。
二.流水线的执行过程及性能评价
1 均匀流水线
加法流水线,
1
|¤t
2
|¤t
3
|¤t
4
|¤t
5
|¤t
1) 不相关算式
计算,Si = ai + bi (i=0~ 7) 共有 8个算式
① S0=a0+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)
性能计算,
吞吐率 ( 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 ) /( 18Δ t*5) =7/18
结论,相关发生时, 对单条流水线而言会降低流水线性
能 。
S 0 S 1 S 2 S 3 S 4 S 5 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)
2 时间匹配的非均匀流水线
右图所示乘法流水线
完成计算,Mi=ai*bi (i=0~7)
( 也是不相关式子 )
1) ① M0=a0*b0 …
⑧ M7=a7*b7
1
|¤t
2
|¤t
4
|¤t
3
3| ¤t
3
3
1
3 2
2)画出各算式在流水线上执行过程示意图
M 0 M 1 M 2 M 3 M 4 M 5 M 6 M 7
过程段
① ② ③ ④ ⑤ ⑥ ⑦ ⑧
③ ⑥
② ⑤ ⑧
① ④ ⑦
① ② ③ ④ ⑤ ⑥ ⑦ ⑧
4
33
3 2
31
2
1
① ② ③ ④ ⑤ ⑥ ⑦ ⑧
1 2 3 4 5 6 7 8 9 10 11 12 13 t( Δ t)
3) 性能, TP=8/13 ( 个 /Δ t)
η =( 8*6 Δ t ) /( 13Δ t*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)

3) 性能,
TP=7/27 ( 个 /Δ t)
η =( 7*6 Δ t ) /( 27Δ t*4) =7/18
§ 1 重叠方式
重叠方式中所需时间表达式及所需时间计算
解决条件转移的全局相关
解决等待结果的数相关
§ 2流水方式
重叠方式的两种等待
流水线的分类
均匀流水线, 非均匀流水线
流水线的执行过程及性能评价
均匀流水线
时间匹配的非均匀流水线
时间不匹配的非均匀流水线
三, 向量流水处理
1,向量的处理方式
计算,fi=ai*bi+ci ( i=0~99)
设各向量分别放在大写字母单元中,
a1
a0
a99
...
A0
A1
A99
c99
...
C0
C1
C99
c1
c0
b1
b0
b99
...
B0
B1
B99
f1
f0
f99
...
F0
F1
F99
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
优点:解决了相关问题, 将原来条条发生相关
改为条条不相关 。
缺点:在向量数据较多时, 所用的寄存器数目
多 。
如本例共用了一百个寄存器 ( R0~R99),
因而在向量数据不多时, 可用纵向处理, 而向量
数据较多时, 可用纵横处理 。
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个向量寄存器组
( V0~ V7), 每个组可存
放 64个长度为 64位的二进
制数的向量数据 。
V0.0
:
V0.63
V1.0
63
V7.0
63
3) 多功能部件
每个部件都以 1τ (=10ns=10-8S)为单位的流水线结构 。
① 逻辑运算,② 定点加,
③ 移位, ④ 浮点加,
⑤ 访存 储器, ⑥ 浮点乘,
⑦ 除法,
此外, 在功能部件和向量寄存器组之间相互传送也用
1τ 。
4) 独立总线结构
每个向量寄存器组到每个功能部件之间都有单独总线连
接, 在不冲突条件下, 可实现功能部件之间并行运行 。
2|ó
4|ó
6|ó
14| ó
3 |ó
6 |ó
7 |ó
3,向量指令的执行过程及性能计算
已知向量指令,V2← V1 + V0 ( 浮点加 )
向量长度为 64,实际上是 64组向量数据求和 。
1) 写出 64组算式
① V2.0←V 1.0 + V0.0
② V2.1←V 1.1 + V0.1

64 V2.63← V1.63 + V0.63
2) 画出向量指令结构图 ( 如右上图所示 )
3) 画出各算式执行过程示意图
送数 1τ, 加法 6τ, 输出结果 1τ, 共 8τ 。
6 |ó
V0 V1 V2
1 |ó
1 |ó

4) 完成运算时间
第一个结果时间 +( 长度 -1) τ =(1+6+1) τ +(64-1) τ =71τ
5) 向量数据处理速度计算
( 向量指令条数 *长度 ) /( 完成运算用时 )
=( 1*64) /( 71*10-8S) =90MFLOPS (每秒处理的浮点数个数 )
V 2, 0 V 2, 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 70 71t ( τ )
注:图中⊙ = 64
4.多条向量指令的执行过程
若有多条向量指令, 且可并行
执行时, 完成运算用时, 可选
用时最多的那条向量指令 。 如,
V0← 存储器 可并行执行,
V3← V2× V1 向量长度为 64
V6← V5÷V4
由于除法用时最长, 以它为准 。
1+14+1+(64-1)=79(τ )
3*64/(79*10-8S)≈ 244MFLOPS
7 |ó
V1 V2 V3
1 |ó
1 |ó
3?
1 4 |ó
V4 V5 V6
1 |ó
1 |ó
3y
6 |óV0
·? ′?
1 |ó
1 |ó
四,向量的链接特性
1,链接:将多条相关的向量指令链接起来组成
更大规模的流水线,从而进一步提高向量数据
处理速度,这种链接称为向量链接。
2,向量指令之间的几种情况
1) 既不相关,又无冲突
不能链接,但可并行执行(执行时间以最长向
量指令时间为准)
2) 条条指令相关,且无冲突
可顺利链接
3) 条条指令相关,但有冲突不能顺利链接,执行
时间往往需要推迟。
3.可顺利链接的情况
有如下向量指令,
V0← 存储器 ; V2←V 0+V1; V3←V 2位移 ;
V5← V3× V4; V7← V5÷V6
向量长度 64
相关:上一条向量指令的结果作下一条指令的一个源操作数 。
1) 画出向量链接特性图
6 |óV0
·? ′?
1 |ó1 |ó
7 |ó
V4 V5
1 |ó
1 |ó
3?
6 |ó
V1 V2
1 |ó
1 |ó

4 |ó
V3
1 |ó
1 |ó ?o ò?
1 4 |ó
V6 V7
1 |ó
1 |ó
3y
2) 完成运算有时
6+2+6+2+4+2+7+2+14+2+( 64-1) =110(τ )
3) 计算向量数据处理速度,
5*64/(110*10-8S)≈ 291MFLOPS
此处结论:相关在向量链接中有利于向量
据处理速度的提高 。
4.不能顺利链接的情况
有如下向量指令,
V0← 存储器 ; V2←V 0× V1;
V4←V 2+V3; V5←V 4位移 ;
V7←V 5÷V6; V0←V 7× V1
故不能顺利链接
1) 不能顺利链接时, 对画向量链接特
性图的影响 。
① 源冲突:第一次送出画实线, 第二
次送出画虚线
② 目冲突:第一次接收画实线, 第二
次接收画虚线
③ 功能部件冲突:第一次出现画实线,
第二次出现画虚线
V 0 ?a ?? ?? ′? ?÷ 3? ío
V 1 ?a ?′ ?? ′? ?÷ 3? ío
* ?a ?| ?ü 2? ?t 3? ío
3? ío
V 0 ← 存 储 器 实 线
V 0 ← V 7 × V 1 虚 线
V 0 + V 1 → V 2 实 线
V 7 × V 1 → V 0 虚 线
向量长度 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(τ )
6 τ
V0
访存
1 τ1 τ
6 τ
V5
1 τ

7 τ
V1
V2
1 τ
1 τ
乘 V3
1 τ
14 τ
V6 V7
1 τ
1 τ

V4
4 τ
1 τ
位移
7 τ

1 τ
1 τ
1 τ
说明:乘法功能部件冲突最严重, 上述三个时间以最短
时间为准 ( 仅适用本例 ) 。
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
P224 17题,在 CRAY-1机上, 在下列指令组中, 组内哪些指
令可以链接? 哪些不可以链接? 不能链接的原因是什么?
完成各指令所需的拍数 ( 设向量长度均为 64,打入寄存
器及启动功能部件各需 1τ ) 。
( 1 ) V0← 存 储 器
(6τ );V1←V 2+V3(6τ );V4←V 5× V6(7τ )
( 2) V2←V 0× V1; V3← 存储器 ; V4←V 2+V3
( 3) V0← 存储器 ;V2←V 0× V1;V3←V 2+V0;V6←V 3+V4
( 4) V0← 存储器 ;V1← 1/V0(14τ );V3←V 1× V2;V5←V 3+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) 条条指令相关, 但有冲突 —— 不能顺利链接
6| ó
V0
·? ′?
1| ó
1| ó
6| ó
V3
V4
1| ó

7| ó
V1 V2
1| ó
1| ó
3?
6| óV0
·? ′?
1| ó1| ó
6| ó
V3
1| ó

7| ó
V1 V2
1| ó
1| ó
3? 1| ó
6| ó
V4 V5
1| ó
1| ó

源冲突 ( 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) 条条相关, 且无冲突 —— 可顺利链接
6| óV0
·? ′?
1| ó1| ó
7| ó
V3
1| ó
3?
14| ó
V1
1| ó
1| ó
μ? êy
1| ó
6| ó
V4 V5
1| ó
1| ó

1
V2
1+6+2+14+2+7+2+6+1+( 64-1) =104(τ )
4*64/( 104*10 -8S ) ≈ 246MFLOPS
三, 向量流水处理
向量的处理方式
向量指令的执行过程及性能计算
四, 向量的链接特性
冲突,邻近向量指令使用了同一个部件
冲突又分为表面冲突与实际冲突
向量链接特性图的绘制
完成运算用时计算:顺利连接时间 +推迟时间
有关时间, 推迟时间的计算
五, 加速比的概念
流水线方式相对于非流水线顺序串行方式
速度提高的比值称加速比 ( Sp) 。
设,流水线段数 m,指令有 n条, 各段经过的时间
均为 Δt
则,
n * m * Δ t
m* Δ t + ( n - 1 ) * Δ t
S p =
此外,还有某种流水处理机相对于另一种流
水处理机的加速比。如超标量流水处理机相对于
常规标量流水处理机的加速比。
六, 非线性流水线的概念
线性流水线中各个段之间串行地链接, 既无反
馈也无跳跃, 每个任务流经流水线中各个段均只
有一次, 反之就是非线性流水线 。
S1 S4S3S2
输出
输入
前馈线
反馈线
非线性流水线的连接图
1 2 3 4 5 6 7
S1 × ×
×
S2
×
×
S3 ×
S4 × ×
时间 流水线
非线性流水线的预约表
延迟禁止表为,F={2,4,6}
初始冲突向量为,C=( 101010)
S1 S4S3S2
输出
输入
前馈线
反馈线
非线性流水线的连接图
101010
111111
101011
101111
初始
7
1
3 7
5
7
7
5
5
3
状态转移图
调度方案 平均延 迟
( 1,7) 4
( 3,5) 4
( 5,3) 4
( 5,7) 6
( 5) 5
( 7) 7
如上例中,
延迟禁止表为,F={2,4,6}
初始冲突向量为,C=( 101010)
状态转移图,各种调度方案及其相应的平均延迟表:由状
态转移图, 从初始状态开始延箭头走向, 构成调度意义
上延迟拍数成周期性重复出现的拍数循环 。 按此方案进
行任务调度, 必然无冲突 。
七, 指令级高级并行超级处理机
超标量处理机, 超长指令字处理机和超流水线处理
机是指令级高度并行的三种不同的超级处理机 。 让单处理
机在每个时钟周期里可同时解释 m( m>1) 条指令, 称处
理机并行的度为 m。
1,超标量处理机 是采用设置 m条指令流水线同时并行, 来
实现度为 m的 。
2,超长指令字处理机 是将水平型微码和超标量处理相结合 。
在编译时, 将多个能并行执行的不相关或无关的操作组合
在一起, 形成一条有多个操作码字段的超长指令字 。 运行
时, 直接控制机器中多个相互独立的功能部件并行操作,
来实现同时执行多条指令 。
3,超流水线处理机,一台度为 m的超流水线处理机的时钟
只是基本机器周期的 1/m。
[解 ] 过程
执行
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (Δt)
图 1 常规标量流水处理机的时空图
[例 1] 指令由取指, 译码和执行三个过程组成 。 每
个过程经过的时间为 Δt连续执行 12条指令 。 请分别
画出在常规标量流水处理机及度 m均为 4的超标量
处理机, 超长指令字处理机, 超流水线处理机上
工作的时空图, 分别计算出它们相对常规标量流
水处理机的加速比 Sp。
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12
译码
取指
过程
4
8
12
3
7
11
2
6
10
1
5
9
4
8
12
3
7
11
2
6
10
1
5
9
4
8
12
3
7
11
2
6
10
1
5
9
0 1 2 3 4 5 时间( Δt)
图 2 超标量处理机的时空图
取指
译码
执行
Sp=14Δt/5Δt=2.8
过程
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
1
2
3
执行
(m=4)
取指
译码
图 3 超长指令字处理机的时空图
Sp=14Δt/5Δt=2.8
0 1 2 3 4 5 时间( Δt)
图 4 超流水线处理机的时空图
4 8 12
3 7 11
2 6 10
1 5 9
4 8 12
3 7 11
2 6 10
1 5 9
4 8 12
3 7 11
2 6 10
1 5 9
5 5.75时间 (Δt) 0 1 2 3 4
Sp=14Δt/5.75Δt≈2.43
执行
译码
取指
过程
[例 2] 现有长度为 4向量 A和 B,请分别画出在下列 4种结构
的处理器上求点积 A·B的时空图, 并求完成全部结果的最
少时钟拍数 。 设处理器中每个部件的输出均可直接送到
任何部件的输入端或存入缓冲器, 其间的传送延时不计,
指令和源操作数均能连续提供 。
(1)处理器有一个乘法部件和一个加法部件, 不能同时工
作, 部件内也只能顺序方式工作, 完成一次加法或乘法
均只需 5拍;
(2)与 (1)基本相同, 只是乘法部件和加法部件可并行;
(3)处理器有一个乘, 加双功能静态流水线, 乘, 加均由
5个流水段构成, 各段经过时间要 1拍;
(4)处理器有乘, 加两条流水线, 可同时工作, 各由 5段
构成, 每段经过时间为 1拍 。
[解答 ] 长度为 4向量 A和 B的点积为
A·B= a1*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= A·B
(1)乘法部件和加法部件不能同时工作, 部件内也只能顺序
方式工作如下图所示 。
由向量点积 A·B运算的时空图可知, 完成全部运算最少为
4× 5十 3 × 5= 35(拍 )
部件
0 5 10 15 20 25 30 35 拍
c4
d1
d2
d3
c1
c2
c3


(2)乘法部件和加法部件可并行的时空图
其中, e1=d1+c3,e2=e1+c4= A·B
d1 e1 e2
c1 c2 c3 c4
部件


0 5 10 15 20 25 拍
( d1=c1+c2)
(3)处理器有一个乘, 加双功能静态流水线时的时
空图
d1 d2 d3
d1 d2 d3
d1 d2 d3
d1 d2 d3
d1 d2 d3
c1 c2 c3 c4
c1 c2 c3 c4
c1 c2 c3 c4
c1 c2 c3 c4
c1 c2 c3 c4


部件
0 5 8 10 15 19拍
5
4
3
2
1
5
4
3
2
1
(4)处理器有乘, 加两条流水线, 可同时工作时的
时空图
d1 d2 d3
d1 d2 d3
d1 d2 d3
d1 d2 d3
d1 d2 d3
c1 c2 c3 c4
c1 c2 c3 c4
c1 c2 c3 c4
c1 c2 c3 c4
c1 c2 c3 c4


部件
0 5 8 10 15 18 拍
5
4
3
2
1
5
4
3
2
1
2,在下述流水线上完成
算式 M=Πai (i=1~ 8)
( 1) 合理分解算式;
( 2) 画出各算式执行过
程时空图;
( 3)计算吞吐率和效率。
1
3 1
2 4
3 3
3 2
3 Δ t
Δ tΔ t Δ t
1 设将指令划分为三个时间段 t取 t译 t执来完成。分别采
用顺序执行,有两条指令重叠,有三条指令重叠。都
执行 K条指令,分别写出三种执行方式所需时间表达式;
若 K=300,t取 =4Δt,t译 =5Δt,t执 =6Δt,分别计算三种
执行方式所需时间
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+300× 5+(300-1)× 6+6=3304( Δt)
3) 三条重叠,
t = t取 +( t译,t取 )max +(k-2)*(t取,t译,t执 )max+( t执,t译 )max+ t执
= 4+5+(300-2)× 6+6+6=1809( Δ t)
M 0 M 1 M 2 M 3 M 4 M 5 M
过程段
① ② ③ ④ ⑤ ⑥ ⑦

② ⑥
① ④ ⑤ ⑦
① ② ③ ④ ⑤ ⑥ ⑦
4
33
3 2
31
2
1
① ② ③ ④ ⑤ ⑥ ⑦
1 2 3 4 5 6 7 8 9 10 11 12 13 15 18 21 t( Δ t)
2 解,
M=a0*a1*a2*a3*a4*a5*a6*a7
1)合理分解算式
① M=a*a1 ② M1=a2*a3 ③ M2=a4*a5
④ M3=a6*a7 ⑤ M4=M0*M1 ⑥ M5=M2*M3
⑦ M=M4*M5
2)时空图
3) 吞吐率,TP=7/21 =1/3( 个 /Δ t)
效率,η =( 7*6 Δ t ) /( 21Δ t*6) =1/3
3 求向量 D=A*(B+C),向量长度为 N,分解为下列 3条向
量指令,
① V3← 存储器 ( 将 A送 V3,6τ)
② V2←V 0+V1( B+C送 V2,6τ)
③ V4←V 2*V3( A*(B+C)送 V4,7τ)
当采用下列 3种方式工作时, 各需多少时间才能得到全
部结果,
1) ①②③ 串行执行 ;
2) ①② 并行执行完后, 再与 ③ 串行 ;
3) 采用链接技术 ;
4) 画出链接特性图,
3.解
1)串,1+6+1+(N-1)+ 1+6+1+(N-1)+ 1+7+1+(N - 1)
=22+3N(τ)
2) ①② 并 +③ 串, 1+6+1+(N-1)+1+7+1+(N-1)=15+2N(τ)
3)链接,1+6+1+1+7+1+( N-1)=16+N(τ)
4)时空图,
6 τ
V3
访存
1 τ
6 τ
V2
1 τ

V0
1 τ
1 τ
7 τ
V4
1 τ
1 τ

V1
1 τ
例 3 若机器共有 5级中断, 中断响应优先次序为 1-
2-3-4-5,现要求其实际的中断处理次序为 1-4-5-2-
3。
(1)设计各级中断处理程序的中断级屏蔽位 (令
,1”对应于屏蔽,, 0”对应于开放 );
(2)若在运行用户程序时,同时出现第 4,2级中
断请求,而在处理第 2级中断未完成时,又同时出
现第 1,3,5级中断请求,请画出此程序运行过程
示意图。
例 4 某机器有 5级中断, 中断响应次序为 1-2-3-
4— 5,现要求中断处理次序为 2-3-1-5-4。
(1)设计各级中断处理程序的中断级屏蔽位的状
态, 令, 0”为开放,, 1”为屏蔽 。
(2)若在运行用户程序时,同时发生 1,3级中断
请求,而在 1级中断服务未完成时,又发生 2,3、
4,5级中断,请画出处理机执行程序的全过程示
意图。 中断处理
程序级别
中断级屏蔽位
1级
2级
3级
4级
5级
第 1级
第 2级
第 3级
第 4级
第 5级
例 5,设有五级中断, 中断级屏蔽位, 1”对应开放,, 0”对
应屏蔽, 中断响应次序为 1— 2— 3— 4— 5,已知各中断处
理程序的中断级屏蔽位设置如下表所示 。
(1)中断处理次序是什么?
(2)在执行用户程序时, 如出现 4,5级中断请求, 在处理 5
级中断请求未完成时, 又发生 1,2,3级中断请求, 请画
出中断处理过程的示意图 (包括将交换 PSW的时间段也表
示出来 )。
中断处理
程序级别
中断级屏蔽位
1级
2级
3级
4级
5级
第 1级
0
0
0
0
0
第 2级
1
0
1
1
1
第 3级
1
0
0
0
0
第 4级
1
0
1
0
1
第 5级
1
0
1
0
0
补充 1,关于向量指令冲突
1) 源寄存器冲突:邻近向量指令使用了同一源
向量寄存器, 如上例中的 V1。
2) 目寄存器冲突:邻近向量指令使用了同一目
向量寄存器, 如上例中的 V0。
3) 功能部件冲突:邻近向量指令使用了同一功
能部件, 如上例中的乘法功能部件 。 解决冲
突的办法是推迟法 。
冲突又分为表面冲突与实际冲突
如上例中, 向量长度为 30时, 仅表面冲突 。