2001.9.1 计算机系统结构 1
计算机系统结构主讲：华中科技大学计算机学院林安
2001.9.1 计算机系统结构 2
教学计划
教材：
《计算机系统结构》（第二版）
郑纬民等清华大学出版社
参考书：
《计算机系统结构复习与考试指导》
郑纬民等高等教育出版社
总学时,40
– 第 1章,4
– 第 2章,4
– 第 3章,10
– 第 4章,4
– 第 5章,6
– 第 6章,2
– 第 7章,6
– 第 8章,2
– 第 9,10章,2
2001.9.1 计算机系统结构 3
第一章 基本概念（ P1）
本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。
定性知识,本课程经常使用的一些名词概念，以及对计算机的定性认识、分析方法。
定量知识,对计算机性能进行定量评价的几个重要公式。
2001.9.1 计算机系统结构 4
1.1 定性知识 ─── 几个基本概念
1.1.1 什么是 计算机系统结构？ （ P4）
英文名称,Computer Architectrue
计算机系统结构（也叫,计算机体系结构,） 课程,传授计算机整机（硬软件统一条件下）设计的重大技术知识 。
Architectrue的英文原义是“建筑学”。
“计算机系统结构”作为 事物名称,使用者必须了解的机器外部特性知识 （广义定义）。在本课程中“使用者”目前特指最低级语言的程序员，“外部特性”特指整个硬件的外部特性（狭义定义）。
透明性概念,使用者可以不了解的知识。
2001.9.1 计算机系统结构 5
“计算机系统结构”狭义定义包含的内容（ P4）
1.数据表示 （ 硬件能够直接识别和处理的数据类型和格式等 ） ；
2.寻址方式 （ 包括最小寻址单位,寻址方式的种类,表示和地址计算等 ） ；
3.寄存器组织 （ 包括各种寄存器的配置数目和功能定义 ） ；
4.指令系统 （ 包括机器指令的操作类型和格式,指令间的排序方式和控制机构等 ） ；
5.存储系统 （ 包括编址方式,存储容量,最大编址空间等 ） ；
6.中断机构 （ 中断源的分类管理和中断服务功能设计 ） ；
7.机器工作状态 （ 如管态,目态等 ） 的定义和切换；
8.输入 /输出 子系统结构与管理；
9.信息保护 手段及其实现 。
2001.9.1 计算机系统结构 6
第 5级 专用应用语言机器 特定应用用户 （ 使用特定应用语言 ）
（ 经应用程序翻译成高级语言 ）
第 4级 通用高级语言机器 高级语言程序员 （ 使用通用高级语言 ）
（ 经编译程序翻译成汇编语言 ）
第 3级 汇编语言机器 汇编语言程序员 （ 使用汇编语言 ）
（ 经汇编程序翻译成机器语言,操作系统原语 ）
第 2级 操作系统语言机器 操作系统用户 （ 使用操作系统原语 ）
（ 经原语解释子程序翻译成机器语言 ）
第 1级 传统机器语言机器 传统机器程序员 （ 使用二进制机器语言 ）
（ 由微程序解释成微指令序列 ）
第 0级 微指令语言机器 微指令程序员 （ 使用微指令语言 ）
（ 由硬件译码器解释成控制信号序列 ）
图 1.1 计算机系统的多级层次模型
1.1.2 计算机系统的多级层次模型（ P3）
2001.9.1 计算机系统结构 7
1.1.3 其他重要名词概念（自学）
[计算机组成 ]计算机系统结构的逻辑实现 。 （ P5）
[计算机实现 ]计算机组成的物理实现 。 （ P5）
[计算机系统设计的 3种主要方法 ]：,由下往上,,,由上往下,,
,由中间开始,。 （ P14）
[系列机 ] （ P23）
[兼容性 ] （ P24）
[模拟 ] （ P24）
[仿真 ] （ P24）
[虚拟机 ] （ P24）
[宿主机 ] （ P24）
[并行性 ] 求解一个问题的若干操作在时间安排上的可重叠性 。
2001.9.1 计算机系统结构 8
1.1.4 冯,诺依曼（ Von Neumann） 型机器的特点（ P22）
传统计算机又称为 冯,诺依曼型机器,它由运算器,控制器,存储器,输入设备和输出设备 5部分组成,并具有如下特点：
1.以运算器为数据流动中枢,以控制器为控制命令中枢；
2.存储程序并且执行,程序象数据一样可以修改；
3.存储器按地址访问,线性顺序编址；
4.程序顺序执行；
5.指令由操作码与操作数两部分组成；
6.数据用二进制编码；
7.机器由硬件与软件组成,硬件功能不能改变 。
2001.9.1 计算机系统结构 9
1.1.5 现代计算机系统的分类（ Flynn分类法,P6）
按照指令流和数据流的多倍性状况把计算机分为：
1.单指令流单数据流 （ SISD---Single Instruction Stream Single
Data Stream）
2,单 指 令 流 多 数 据 流 （ SIMD---Single Instruction Stream
Multiple Data Stream）
3.多 指 令 流 单 数 据 流 （ MISD---Multiple Instruction Stream
Single Data Stream）
4.多 指 令 流 多 数 据 流 （ MIMD---Multiple Instruction Stream
Multiple Data Stream）
例题,P32,题 7，题 8,题 9 。
2001.9.1 计算机系统结构 10
1.2 定量知识 ───3 个性能公式
1.2.1 Amdahl定律 （ 加快经常性事件原理,P9）
e
e
e
n
o
n
S
FFT
TS
)1(
1
其中,Sn ── 全局加速比；
To ── 原执行时间 （ old） ；
Tn ── 新执行时间 （ new） ；
Se ── 被改进部分的局部加速比；
Fe ── 被改进部分原执行时间占原来总时间的百分比 。
2001.9.1 计算机系统结构 11
Amdahl定律的推导
e
e
e
n
o
n
e
e
eon
eeoo
S
F
F
T
T
S
S
F
FTT
FFTT
)1(
1
)1(
)1(
根据加速比定义，有：
：操作加快，总时间降为改进之后由于其中部分
，间可写为：改进之前程序运行总时
2001.9.1 计算机系统结构 12
Amdahl定律的图形
S
n
极限 2 =
2
1
1
e
F?
极限 1 =
1
1
1
e
F?
F e = F
e2
F e = F
e1
1,0
（设 F
e2
> F
e1
）
0,0 1,0 S
e
图 1.2 Amdahl 定律的图形从图 1.2可以看出,增大 Se和 Fe对 Sn都有提升作用；但当 Fe固定时
,一味增大 Se对 Sn的作用会越来越不显著 。
2001.9.1 计算机系统结构 13
1.2.2 CPI与程序执行时间 Te（ P11）
CPI是衡量 CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的 全部执行时间 Te和其中 所有第 i种指令的累计时间 Ti,易知的加权平均值。为所有，它表明）（或者写为
）（
的关系与一式，可以得到比较上面第一式与最后写另一方面，我们又可以
，
i
n
i
i
i
n
i
ii
n
i
ii
n
i
ii
n
i
ie
n
i
i
iii
e
C P IC P IC P I
IC
IC
C P I
C P IICC P IIC
C Y C L EC P IICC Y C L EC P IICTT
ICIC
f
C Y C L E
C Y C L EC P IICT
C Y C L EC P IICT
C P IC P I
)()(
1
其中：
1
1
i
111
1
2001.9.1 计算机系统结构 14
1.2.3 每秒百万指令数 MIPS与每秒百万浮点数 MFLOPS
（ P11）
。，主要用于向量计算机条数每次浮点运算所需指令；，主要用于标量计算机
M I P S
M F LO P S
C P I
f
C Y C LEC P IIC
IC
T
IC
M I P S
e
666 101010
例题,P10,例 1.1~例 1.5。
P33,题 12,题 13,题 14 。
2001.9.1 计算机系统结构 15
例题选讲（ 1）
例 1.1（ P10）
Amdahl定律公式,已知,Fe=0.4,Se=10,求 Sn。
它说明局部（ 40%）的大幅度改进（ 10倍）对全局的作用要小得多（ 1.56倍）。
例 1.2（ P10）
Amdahl定律公式,已知方案 1,Fe1=0.2,Se1=10,求 Sn1；
已知方案 2,Fe2=0.5,Se2=2,求 Sn2 。
它说明大范围的小幅度改进（方案 2）效果可能更好。
2001.9.1 计算机系统结构 16
例题选讲（ 2）
例 1.3（ P11）
CPI公式,注意该公式中的指令数百分比不同于 Amdahl定律中的时间百分比 Fe,避免用错。
已知,ICFP / IC = 25%,IC非 FP / IC = 75%；
IC FPSQR / IC = 2%,IC非 FPSQR / IC = 98%。
改进前,CPI FP = 4.0,CPI非 FP = 1.33；
CPI FPSQR = 20,CPI非 FPSQR =？
改进后,CPI FP = 2.0,CPI非 FP = 老 值；
CPI FPSQR = 2.0,CPI非 FPSQR = 老值 。
求,两种方案改进后的 CPI。
分析,方案 2缺一个条件 CPI非 FPSQR,但改进前用两种方法算出的 CPI应该是相同的，所以由
CPI 老 = CPI FP× ICFP / IC+ CPI非 FP × IC非 FP / IC
= CPI FPSQR× ICFPSQR / IC+ CPI非 FPSQR × IC非 FPSQR / IC
2001.9.1 计算机系统结构 17
例题选讲（ 3）
解出 CPI非 FPSQR = 80 / 49
现在分别用两种方案改进后的参数代入公式，算出新的 CPI为
1.64和 1.5，显然 CPI值较小的方案 2较好。
教材的解法中有两个小公式值得注意，一个是：
iii
ii
i
ICC P IC P IICC P IC P I
C P IC P I
IC
IC
C P IC P I
)()(
)(
__
__
老新老新新老老新时钟周期数总改变量它的实质就是
另一个公式较容易理解：
新老新老
C PI
C PI
T
TS
e
e
n
_
_
2001.9.1 计算机系统结构 18
例题选讲（ 4）
例 1.4（ P12）
Te公式,其中 CPI用相应的公式代换
C Y C LEICICICC P IT
n
i
i
ie
1
)(
对 A机器，已知 CPI转 =2,IC转 /ICA=20%,CPI非转 =1,IC非转 /ICA=80%，
Te_A=1.2× ICA × CYCLEA；
对 B机器，从题义可知,IC比转 = IC转,ICB = ICA × 80%,CYCLEB
=1.25 × CYCLEA,CPI比转 =2，所以 IC比转 /ICB= IC转 /（ ICA × 80% ）
=25%,CPI非比转 =1,IC非 比转 /ICB=75%，
Te_B = 1.25× ICB × CYCLEB
= 1.25× 80%× ICA× 1.25× CYCLEA
= 1.25× ICA× CYCLEA > Te_A
显然 A机器快一些。
2001.9.1 计算机系统结构 19
例题选讲（ 5）
例 1.5（ P12）
Te公式,改动上题中 CYCLEB =1.1 × CYCLEA,则最后
Te_B = 1.25× ICB × CYCLEB
= 1.25× 80%× ICA× 1.1× CYCLEA
= 1.1× ICA× CYCLEA < Te_A
这时 B机器快一些。
题 12 （ P33）
Amdahl定律公式,代入已知量
Se=20变成一元函数
Sn=20/(20-19Fe)
用三点作图法作出关系曲线。
Sn
20
10.5
1.8
1
0 0.5 1 Fe
2001.9.1 计算机系统结构 20
例题选讲（ 6）
题 13 （ P33）
Amdahl定律公式,代入已知量 Se=20,Sn=2,解出 Fe=10/19
题 14 （ P33）
Amdahl定律公式,代入已知量 Se=20,Sn=10,解出 Fe=18/19
2001.9.1 计算机系统结构 21
本章小结本章从定性知识和定量知识两个方面介绍计算机系统结构的基本概念。有关重点如下：
(1) 计算机系统结构的广义定义与狭义定义（ 9项内容），计算机系统结构与计算机组成的主要分工；
(2) 计算机系统的多级层次模型（ 6级），以及基于该模型的透明性判断方法；
(3) 计算机实现、计算机系统设计的主要思路、模拟、仿真、虚拟机、
宿主机、系列机、兼容性、并行性等重要名词的含义；
(4) 冯,诺依曼型机器的 7个特点；
(5) 现代计算机系统分类的 Flynn法（ 4类）；
(6) Amdahl定律；
(7) 平均周期数 CPI公式，程序执行时间 Te公式；
(8) 每秒百万指令数 MIPS公式，每秒百万浮点数 MFLOPS公式。
习题,P33,题 15，题 19 ； P392,题 10，题 11,题 12 。
2001.9.1 计算机系统结构 22
第二章 指令系统（ P36）
本章介绍指令系统设计中 2个最基本的内容：数据表示、操作码优化。
2.1 数据表示
[数据表示 ]就是 计算机硬件能够直接辨认与处理的数据类型 。
人们通常使用的数据类型有整数、实数、逻辑数（布尔数）、字符串、
队列、堆栈、链表、文件等，它们的运算方法各不相同。
所谓,硬件能够直接辨认与处理,,指的是对该数据类型的各种运算操作都有相应的实现硬件电路。
硬件不能直接辨认与处理的数据类型就要根据 数据结构 的知识编制软件 转化 为硬件能处理的数据类型。
下面介绍通用型计算机数据表示集合中的一个基本成员 ── 浮点数据的分析与设计。
2001.9.1 计算机系统结构 23
2.1.1 浮点数据表示（ P38,P39）
浮点数据就是高级语言课程中所说的,实型数,。
2.1.1.1 浮点数的组成浮点数的组成与人们通常所说的,科学记数法,非常相似，唯一不同的是各部分均为有限位数，如下所示
emrmN
它的主要参数有 8个：
m ── 尾数,一般为纯小数，符合 规格化 原则（即最高位的绝对值不为 0），
用 原码 或 补码 表示；
e ── 阶码,整数，常用 移码 表示（见下文解释）；
rm ── 尾数的基值，简称 尾基,常见的有 2进制,8进制,16进制,10进制等，
选定以后不变；
re ── 阶码的基值，简称 阶基,目前都采用 2，也是选定以后不变；
p ── 尾数的位数，未将符号位计入；
q ── 阶码的位数，未将符号位计入。
mf ── 尾数的符号，表示数的正负，简称 数符 ；
ef ── 阶码的符号，表示阶码的正负，简称 阶符 。但对移码表示来说，这仅仅是额外的 1位 2进制数，不决定正负。
2001.9.1 计算机系统结构 24
移码（ P41）
移码是一种 2进制记数方法,它的 真值等于相同编码的无符号数加上一个指定的偏移量 d。 例如,同样是 2进制编码 000000 ～ 111111,看作 6位无符号数时的取值范围是 0
～ 63,而看作 6位移 -10码的取值范围就是 –10 ～ 53。 如下图所示 。
移码是一种有符号数,但它的最高位通常不决定数的正负,不应称为符号位 。 它的独特之处在于其最小取值的 2进制编码是全 0,这给机器零的判断和处理电路设计带来很大方便 。
十进制真值
63
无符号数
53
移 -10 码
0 111111
-10 二进制编码图 2,1 移码与无符号数的比较实例
2001.9.1 计算机系统结构 25
2.1.1.2 浮点数的机内格式（ P39）
一种浮点数中每个数据的尾基 rm,阶基 re都是相同的,在设计运算电路已经作为默认值来使用,各个具体数据在存储时只需要存入如下参数即可：
各字段位数,1 位 1 位 阶码 q 位 尾数 p 位浮点数字段,m
f
e
f
e
q - 1
… … e
0
,,m
1
… … m
p
对应位的权,r
e
q-1
… … r
e
0
r
m
-1
… … r
m
-p
隐含小数点图 2,2 浮点数的机内格式
2001.9.1 计算机系统结构 26
2.1.1.3 浮点数的性能（ P38）
浮点数的性能主要用 表数范围,表数精度 和 表数效率 来刻画,下面分别进行分析 。
(1) 表数范围 （ P39）
表数范围由这样一些参数构成,最小负数,最大负数,最小正数,最大正数,
最小绝对值 |N|min,最大绝对值 |N|max。 它们几何意义可以在数轴上表示,如下图 。
- ∞ 最小负数 最大负数 0 最小正数 最大正数 + ∞
图 2,3 数轴上的表数范围示意图图中阴影部分为浮点数的表数范围 。
根据浮点数的组成表达式可知,图 2.3中 4个边界值分别由尾数 m,阶码 e各自的边界值两两组合而成,如下所示 。
最大正数 ── 最大正尾数 /最大阶码；
最小正数 ── 最小正尾数 /最小阶码；
最大负数 ── 最大负尾数 /最小阶码；
最小负数 ── 最小负尾数 /最大阶码 。
2001.9.1 计算机系统结构 27
例 2.1
对规格化浮点数，尾数为原码，阶码为移 码，写出表数范围。（ P40）
11 )1( qeqe rmpmrmm rrNrr
qer?
解：由于原码在数轴的零点两边对称分布，即最大正数与最小负数的绝对值相等、最小正数与最大负数的绝对值相等，所以可以用最小、最大绝对值来描述它的分布。
首先根据图 2.2和式 2.1以及移码的基本定义，可以确定绝对值的极值表达式：
。，，又；，，
dr
m
p
m
q
e
p
m
d
mmm
q
errNdrerm
rrNderm
12
m a xm a xm a x
1
m i nm i n
1
m i n
)1(12)1(?
写在一起就是：
drmpmdmm qerrNrr 121 )1(
再用阶码的偏移量代换式中的 -d得：
2001.9.1 计算机系统结构 28
可以代入具体数字来帮助理解：
，如下图所示。，，
，于是有：按此题约定，
。，，，设
3101
m i n
3
m i n
1
m i n
3
1010 1010
10
310410
Ndem
d
qrpr em
，如下图所示。
，，
1104
m a x
3333
m a x
4
m a x
310)101(
1101011021102)101(
N
dem
1 位 1 位 阶码 3 位 尾数 4 位
x 0 0 0 0,,1 0 0 0
1 位 1 位 阶码 3 位 尾数 4 位
x 1 9 9 9,,9 9 9 9
2001.9.1 计算机系统结构 29
(2) 表数精度（ P42）
数轴
N
k
真实值 x N
k + 1
图 2,4 最大绝对误差示意图
e
m
p
m
e
mkkkk rrrmmNN
2
1)(
2
1)(
2
1
11m a x?
表数精度用最大表数误差表示 （ 指相对误差 ） ；
最大绝对误差 是真实值与可表示值之间的可能最大距离,也就是相邻两个可表示值间距的 1/2,如图 2.4所示
。 根据浮点数的组成式有其定义：
显然它随着阶码 e增大而增大,不是一个定数 。
2001.9.1 计算机系统结构 30
最大相对误差 与阶码 e无关，但与尾数 m的值有关。它的定义是
p
me
m
e
m
p
m
r
mrm
rr
N
1
2
12
1
m a x
m a x
上式中,当分母 |m|取最小值时分式值达到最大 。
。限为，所以最大相对误差上由于 21 )1(m a x01 pmmm rrmr?
2001.9.1 计算机系统结构 31
(3) 表数效率（ P45）
定义,
mm
m
q
e
p
m
q
e
p
mm
m rr
r
rr
rrrr 111
22
12)1(2)( 1
可以生成的浮点数个数其中规格化浮点数个数?
此式说明效率之所以低于 100%,是因为规格化的尾数最高位 m1只能有
rm-1种取值的缘故 。 可以看出,的极小值与极大值分别是
%100)(lim%501 12)2( mr r
m
,
[隐藏位技术 ]是一种提高表数效率的方法，但仅适用于 rm=2的情况：
尾数最高位 m1 在二进制条件下只有 0和 1两种可能，按照规格化要求，
m1 可由其它位推出，。,隐藏,了 m1之后，尾数只存储后面 p-1位，
它们中的任一位都有 rm种取值，所以表数效率 η =100%。
2001.9.1 计算机系统结构 32
2.3 指令格式的优化（ P90）
2.3.2 操作码优化目前常用的编码方法有 3种,定长编码,Huffman编码,扩展编码 。
2.3.2.1 定长编码 就是所有指令使用相同的代码位数，其最小码长等于
nL o glL i 2
式中 是平均码长,是第 i种指令的码长,n是指令总数。
例 2.2
已知 n = 15,求定长编码的最小平均码长。
解：
L il
4152 L o gL
2001.9.1 计算机系统结构 33
2.2.1.1 Huffman压缩编码（ P91）
(1)Huffman压缩概念 （ 最佳编码定理 ）,当用 n个长度不等的代码分别代表 n种发生概率不等的事件时,按照短代码给高概率事件,把长代码给低概率事件的原则分配,可使平均码长达到最低 。
(2) Huffman编码方法这种编码方法由两个过程组成 。
频度合并,将全部 n个事件 （ 在此即为 n条指令 ） 的频度值排序,选取其中最小的 2个频度合并,然后将剩下的 n-1个频度再次排序,再合并最小的 2个频度,如此重复,直至剩下 1个频度为止 。 记录所有的合并关系,形成一棵二叉树 ── Huffman树,所有原始频度值充当树叶,而最后剩下的总频度 1为树根；
码元分配,从树根开始,对每个中间结点的左右 2个分支边各赋予一位代码,0” 和,1” （,0” 在哪一侧不限 ） 。 读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件 （ 即指令 ） 的完整编码 。 由于频度高的事件较晚被合并,它的编码位数也就较少,符合 Huffman压缩原则 。
上面所说的 频度值 就是各事件实际出现次数的百分比,它是理论出现 概率的近似值 。
2001.9.1 计算机系统结构 34
(3) 编码方法性能指标（ P91-P93）
信息量,根据信息论的基本知识，在 n种可能发生的事件集合中，报告第 i
种事件发生的消息中包含的信息量为
ia
i
ai PPI lo g)
1(lo g
其中 Pi是第 i种事件发生的先验概率,a是编码基值 。 信息量的单位是表示位数 （ 最少所需位数 ） 。
这个定义式表明事件的发生概率越低，关于它的消息中的信息量越大
。
熵 （ entropy） ── 平均信息量,一个消息源对 n种事件发布的消息的信息量平均值,记为
n
i
iai
n
i
ii PPIPH
11
)(l o g)(
2001.9.1 计算机系统结构 35
平均码长,各事件编码长度的数学期望。
n
i
ii lPL
1
)(
信息冗余量,它表明消息编码中,无用成分,所占的百分比。
%100 L HLR
从减少存储与传输量的角度看,编码方法的平均码长越短越好 。 但是平均码长不可能无限制缩短,它的下限就是熵 （ 即 R=0时 ） 。 如果短于熵就一定会丢失有用信息 （ 即混淆不同指令 ）,这是不允许的 。
2001.9.1 计算机系统结构 36
2.2.1.2 扩展编码方法（ 等长扩展法,P93）
用码长表示：例如 4-8-12法 。这并不能说明具体编码方法，例如下面两种编码方法都是 4-8-12法。
用码点数表示：例如 15/15/15法,8/64/512法
– 15/15/15法,每一种码长都有 4位可编码位（前头可以有相同的扩展标识前缀），可产生 16个码点（即编码组合），但是至多只能使用其中 15个来表示事件，留下 1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。
这就是“非前缀原则”。
– 8/64/512法,每一种码长按 4位分段，每一段中至少要留下 1
位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。
2001.9.1 计算机系统结构 37
例 2.3
已知频度序列为 0.1,0.1,0.15,0.15,0.2,0.3，求 Huffman编码、等长扩展 3/3/3码、定长编码、三者的平均码长、信息冗余量以及熵。
解：
熵 H=
– (2× 0.1× log20.1+2× 0.15× log20.15+0.2× log20.2+0.3× log20.3)
≈2.47
根据 Huffman编码方法作 Huffman树如图 2.5所示，三种编码方法的结果列于表 2.1中。
1,0
0 1
0.4 0.6
0 1 0 1
0.2 0.3
0 1 0 1
0.1 0.1 0.15 0.15 0.2 0.3
图 2.5 H uffm a n 树
2001.9.1 计算机系统结构 38
表 2.1 Huffman编码、等长扩展 3/3/3码及定长编码指令 I
1
I
2
I
3
I
4
I
5
I
6
频度 0.1 0.1 0.15 0.15 0.2 0.3
000 001 100 101 01 11Huffman 码平均码长 L =2.5,信息冗余量 R ≈ 1.2%
1110 1101 1100 10 01 003/3/3 码平均码长 L =2.7,信息冗余量 R ≈ 7.5%
000 001 010 011 100 101定长编码平均码长 L =3.0,信息冗余量 R ≈ 17.7%
2001.9.1 计算机系统结构 39
2.2.2 操作数优化 ─── 寻址方式比较（ P95）
指令中操作数占用的位数由操作数的个数与寻址方式决定 。
按操作数的个数划分,有零操作数指令,一操作数指令,二操作数指令,三操作数指令共四种形式 。 应该按机器用途来选择 （ P99，
表 2.20） 。
缩短操作数长度的常用方法是 间址 和 变址 （ P99页末 ） 。
2001.9.1 计算机系统结构 40
本章主要内容有 数据表示 和 操作码优化 两个部分。具体细节如下：
(1) 浮点数的 表数范围 （在数轴上的 4个端点）,表数精度?,表数效率?；
(2) Huffman编码方法；
(3) 等长扩展编码方法（ 15/15/15法,8/64/512法 ）；
(4) 编码方法性能指标（ 熵 H,平均码长 L,信息冗余量 R）。
习题,P124,题 3（忽略 P124倒 1行 ~ P125第 8行文字），题 13。
本章小结
2001.9.1 计算机系统结构 41
第三章 存储系统（ P130）
长期存在的问题：在合理的总价格限制下，单纯性主存设备的速度跟不上 CPU的发展，容量不能满足软件尺寸扩大。
本章学习两种提高主存系统性能 /价格比的结构化方法,并行存储器 与 存储层次技术 。后者为主。
2001.9.1 计算机系统结构 42
3.1 并行存储器（ P136）
并行存储器技术可以提高主存系统的整体等效速度,实际应用中,
常将它与存储层次技术组合使用,可以互为补充,获得很高的性能 。
并行存储器技术的基本思想是 用多个独立的存储部件组成主存系统,让它们并行工作,在一个存储周期内可以访问到多个数据,从而实现较高的存取流量 。
并行存储器包括多种类型,我们仅介绍提高访问速度效果最显著的 低位交叉访问 这一种 。
2001.9.1 计算机系统结构 43
低位交叉访问并行存储器的结构：
它由 n个存储体组成（一般 n为 2的整次幂），每个体均有独立的地址译码器和数据缓冲器，以主存地址低位字段（ 最低的 log2n位 ）作为 体选译码信号,而剩下的高位字段则是 体内地址 。如图所示（设 n = 4）。
地址总线体 0 体 1 体 2 体 3
地址译码器 地址译码器 地址译码器 地址译码器
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
数据缓冲器 数据缓冲器 数据缓冲器 数据缓冲器数据总线
2001.9.1 计算机系统结构 44
主存地址与结构参数的换算（ P139）：
nAk
n
Aj
kjnA
m o d
，求结构参数：
求主存地址：
其中,n ── 存储体个数,A ── 主存地址,
j ── 体内地址,k ── 体序号 （ k = 0,1,2,…,n-1 ）
例 3.1
已知 n = 4,问主存地址 13是在几号体的几号单元？
解：
由于 n = 4,体选译码信号使用主存地址的最低 log2n = 2位,所以地址 13（ 其二进制为 1101B） 对应的体号 k = 1（ 即 01B）,体内地址 j = 3（
即 11B）,也就是说,地址 13位于 1号体的 3号单元 （ 参看前一页插图 ） 。
根据上式,所有 k值 （ 即体号 ） 相同的地址之间均相差 n的整倍数
,称之为,模 n同余,。
2001.9.1 计算机系统结构 45
低位交叉访问并行存储器的加速机理：
我们衡量存储器件速度的常用指标是存储周期 Tm,它是同一存储单元连续两次启动的最小时间间隔,数值越小表明存储器件速度越快 。
传统存储系统只有一套地址译码器和数据缓冲器,所以各单元必须串行工作
,也就是说每个 Tm周期内至多只能完成一次访问 。
由多个存储体构成的并行存储器中,各个存储体都有独立的地址译码器和数据缓冲器,它们可以并行工作,使得一个 Tm周期内可完成多次访问,相当于加速了多倍 。 最好情况下一个 Tm周期内可完成 n次访问 。
当前 Tm周期中只要发现有一个新的访问地址与前面地址属于同一个存储体,
该地址及其后面的地址就会被阻塞 （ 称为访存冲突 ）,留到下一个 Tm周期访问 。
机器地址序列常常具有顺序性,按照低位交叉的规律分配地址可使相继出现的地址落在相同存储体的概率降到最低 （ 参见上图 ） 。
考虑到地址总线与数据总线的拥挤问题,一个 Tm周期里发送的多个访问请求最好彼此错开 Tm/n时间,如 P140图 3.11所示,否则实现的复杂度会增加 。
2001.9.1 计算机系统结构 46
K
g=0
10.0
g=0.2
4.46
3.68
2.00 g=0.5
1.00 g=1
0 1 10 n
计算平均加速倍数（ P141）：
1.只考虑取指地址序列（假设地址顺序递增，直至出现一条转移指令）：
倒数第一行）（ 141 )1(1 Pg gK
n
其中 g是指令序列中出现转移指令的概率。此公式在右图中用 绿线 表示。
2.只考虑取数地址序列（假设地址完全随机）
28.02/nK
此公式在右图中用 红线 表示。
2001.9.1 计算机系统结构 47
例题,P203,题 5
。也对（文字理解差异）取。向下取整，得解出，得依题意有，其中，解：已知
161 15
28.15
9.0lg
2.0lg
2.09.0
2.0
)1(1
2.0
)1(1
1.0
)1(1
1
1
n
n
g
g
K
g
g
K
g
g
g
K
n
n
n
n
n
n
n
2001.9.1 计算机系统结构 48
3.2 存储层次原理及性能指标
3.2.1 基本原理
定义,（ 参见 P131第二段 ）
由 2种或多种存储部件构成的复合存储系统,通过内部管理机构的 自动更换机制,能够不断将大容量低速存储部件中的活跃内容复制到小容量高速存储部件中 （ 后者作为前者的 局部副本 ） 。
它既能满足 CPU的快速存取需要,又有很大的存储容量,平均单位价格也很低,等效于同时满足 3
方面要求的理想单一存储部件 。
依据：程序访问的局部化原理 （ 时间局部化,空间局部化 ） 。
模型：如右图所示,存储层次由 n层组成,
满足 3个不等式,Ti<Ti+1,Si<Si+1,ci>ci+1。
CPU
M1
M2
Mn
图 3.3 存储层次模型
2001.9.1 计算机系统结构 49
3.2.2 性能指标（ P132-P134）
(1) 容量,S=S2 （ 理论上 ）
(2) 单价,（ 美分 /bit）
2
0
2
1
21
2
1
21
2211
2
1
lim
1
cc
S
S
cc
S
S
SS
ScSc
c
S
S
它的最小值是
2001.9.1 计算机系统结构 50
(3) 速度：表现访问速度的参数很多
命中率：反映被访问数据事先已在 M1的发生概率
等效访问时间：命中时的访问时间为 T1,不命中时的访问时间为 T2,等效访问时间则是它们的概率均值
10
21
1
HNN
NH,
21 )1( THTHT
1%1 0 0lim TTH
2001.9.1 计算机系统结构 51
访问效率：这是一个相对值，便于不同系统之间的比较。
。, ereH
e
r = 1
1.0
r = 2
0.5
r = 10
0.1
0.0
0 1 H
H 和 r 对 e 的作用访问效率 e受 H和 r的影响（参见右图）：
是邻级速度比）。（，其中 rTTre 110
1
2
Hrr
rHH
THTH
T
T
T
e
)1(
1
)1(
1
)1(
21
1
1
2001.9.1 计算机系统结构 52
Cache预取技术对命中率的提高作用（ P134）：
这里所说的,预取,技术,并不是根据对程序执行的未来趋势进行猜测以提前调入数据,而仅仅是在发生不命中情况时把调入 1个数据字改为调入 1个数据块的策略 。 根据程序的局部化原理,在当前使用数据周围的其它数据未来被使用的几率大于远处数据,所以该数据块中被提前调入的邻近数据很可能成为未来的命中点,从而提高命中率
。
采用这种预取技术后新的命中率为
n
nHH 1'
其中,H ── 原命中率 （ 即按照不命中时取入 1字的策略 ） ；
H’ ── 新命中率 （ 即按照不命中时取入 1块的策略 ） ；
n ── 每块数据平均被访问次数 。
2001.9.1 计算机系统结构 53
按照定义，原不命中率,新不命中率
，并且有 。
由于预取使得每块数据中的不命中次数由 n次降低到 1次，所以有
。此式可改写为,
整理得 。
H’的推导：
21
21
NN
NH
''
''1
21
2
NN
NH
'' 2121 NNNN
22
1' N
nN? '1
1
'2
2
H
H
N
Nn
n
nHH 1'
2001.9.1 计算机系统结构 54
加速比（ P193）
Cache-主存层次的主要作用是提高访问速度，系统的等效速度应高于主存（即 M2） 的原有速度，两个速度之比称为加速比。
rHH
THTH
T
T
TM
M
S
p
/)1(
1
)1(
21
2
22
2
等效时间时间速度等效速度
2001.9.1 计算机系统结构 55
M1 103B T1=1us 103B
M2 106B TB2=10us
M3 109B TB3=100us 109B
(a) (b)
例 3.2
有一个 109字节的程序被装入右图所示的 M3准备运行。
假定指令字长 =1字节，程序中无转移指令和内存读 /写指令。
(1)按图 (a)求 T和 e；
增加中间层对 e的影响
(2)按图 (b)推导三层体系的 T公式；
(3)按图 (b)求 T和 e；
(4)比较 (1)(3)结果，有何结论？
2001.9.1 计算机系统结构 56
解：
32122111
3222111
32222
2111
1
1
3
23
33
3
3111
3
1
3
3
1
)1()1()1(
)1()1(
2
)1(
)1( )2(
%91
%)101(
10
11010
100
10
1
1
10
110
)1(
10
1
1
10
110
)1(
BB
BB
BB
B
THHTHHTH
THTHHTHT
THTHT
THTHT
T
T
e
Tsss
THTHT
HH
式有由上面
，
2001.9.1 计算机系统结构 57
效率提高。层间速度差减少，访问结论：插入中间层后,)4(
%99
%)11(
10
1010101010
100
10
1
10
10
110
10
1
1
10
110
10
1
1,
10
110
)3(
1
16
2346
33
3
33
3
323
3
2
T
T
e
Ts
sssT
HH
习题,P202,题 3。
2001.9.1 计算机系统结构 58
存储层次的管理方式 (P148)
根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在 3种存储层次管理方式。
(1)段式管理 (P148)。段是程序中的一个逻辑单位，可以是一个程序模块，
或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。
每段使用独立的逻辑地址空间,即都从 0开始计算地址 。
段式管理方法的主要缺点是各段长短不一,调进调出之后容易形成大量不规则的零碎空间 。
段式管理方法的虚实变换算法是查段表 (P150)。
2001.9.1 计算机系统结构 59
(2)页式管理 (P151)。页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。
我们把用户文件划分得到的一个长度单位称为,虚页,,因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为,实页,。
页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。
页式管理方法的虚实变换算法是查页表 (P152)。
(3)段页式管理 (P153)。 它把上述两种管理方式结合起来,首先将整个文件分段,然后在各段内分页,所以有一个段表和若干个页表 。 其虚实变换算法是先查段表,查出该段的页表起始地址再查相应的页表 (P154)。
段页式管理的主要缺点是多查一次表,虚实变换费时较多,占用空间也较大 。
由于段页式管理方法的最小调度单位仍是页,或者说它是分段之后的分页管理,为了叙述简单,下面的分析还是以页式管理为模型 。
2001.9.1 计算机系统结构 60
3.3 地址映象与变换 (P174)
基本术语：
逻辑地址 （ 又称为 相对地址,虚地址 ） 是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号,总是从 0开始 （ 可以按字节编址,按 CPU
字编址等 ） 。 逻辑地址的取值范围称为 逻辑地址空间,虚空间 或 虚存 。
物理地址 （ 又称为 绝对地址,实地址 ） 是任一级存储器为全部存储单元分配的序号 。 物理地址的取值范围称为 物理地址空间,实空间 或 实存 。
从 M1到 Mn各层都有自己的物理地址空间,而对当前执行的程序模块来说,逻辑地址空间只有一个 。
地址映象 方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。
地址变换 （又叫 虚实变换 ）指逻辑地址到物理地址的变换过程或者算法。
页失效 指当前被访问存储级中没有所需的信息，也就是不命中现象。
实页争用 又叫 实页冲突,指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。
2001.9.1 计算机系统结构 61
4种常见的地址映象方式
3.3.1 全相联 (P174)
全相联 就是无约束对应,或者说是一个完全关系,意思就是一个虚页可以调入任何一个实页 。 这种关系可用下页示意图 (a),(b)表示 。
全相联的虚实变换信息完全来自于变换表,查表过程如图 (c)所示 。
全相联映象方式使虚页调入有最大的选择范围,发生实页争用的可能性最小,调入 /调出的操作开销也最少,有利于命中率提高 。 但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高,在命中情况下花费在虚实变换上的时间也比较多 。
由于页表必须常驻在实存中,而主存 -辅存层次的实存 （ 即主存 ） 相对
Cache-主存层次的实存 （ 即 Cache存储器 ） 要低廉一些,所以全相联映象方式一般用于主存 -辅存层次 。
2001.9.1 计算机系统结构 62
全相联的地址映象方式与地址变换原理示意图 (a)(b)
虚存 实页 0 1 2 3
0 0 √ √ √ √
1 实存 1 √ √ √ √
2 · 0 2 √ √ √ √
3 · 1 虚 3 √ √ √ √
4 · 2 页 4 √ √ √ √
5 · 3 5 √ √ √ √
6 6 √ √ √ √
7 7 √ √ √ √
( a ) 虚页集合与实页集合的对应关系 ( b) 对应关系表 （ √ 为有关系）
2001.9.1 计算机系统结构 63
全相联的地址映象方式与地址变换原理示意图 (c)
虚地址 虚页号 P 页内偏移量 D
实地址 实页号 p 页内偏移量 d
实页号 装入位 修改位表项 0,,,
,,,,
表项 P p 1 0
,,,,
表项 7,,,
( c ) 通过 查表进行虚实变换
2001.9.1 计算机系统结构 64
3.3.2 直接相联 (P176)
直接相联 是一种最强的约束关系,它规定每个虚页只对应唯一的实页 。 为了便于虚实变换,用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号 。 实现起来非常简单,因为在二进制中,任何数 X对 2的整次幂 n求模等价于截取 X的最低 log2n位,如下页示意图 (c)所示 。
例 3.3 已知虚页号 = 7,实页总数 = 4,用直接相联求实页号 。
解：
可用十进制形式求,7 mod 4 = 3；
也可用二进制形式求：由于 n = 4,所以 log2n = 2,取 7的二进制形式 111B
的最低 2位,得 11B,即 3。
直接相联映象方式不需要借助页表来进行虚实变换,显然大大节省了相应的空间与时间 （ 当然页表中的装入位和修改位还得保留 ）,但是由于每个虚页的选择范围太小,实页争用的发生频率较高,常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况,这使系统的命中率和运行效率大大下降 。
这种映象方式主要用于一些对实存价格非常敏感的 Cache-主存层次 。
2001.9.1 计算机系统结构 65
直接相联的地址映象方式与地址变换原理虚存 实页 0 1 2 3
0 0 √
1 · 实存 1 √
2 · 0 2 √
3 · 1 虚 3 √
4 · 2 页 4 √
5 · 3 5 √
6 · 6 √
7 7 √
( a ) 虚页集合与实页集合的对应关系 ( b) 对应关系表 （ √ 为有关系）
虚地址 虚页号 1 1 1 页内偏移量 D
实地址 实页号 1 1 页内偏移量 d
( c ) 通过 求模运算进行虚实变换示例
2001.9.1 计算机系统结构 66
3.3.3 组相联 (P178)
组相联映象方式是全相联与直接相联的一个折中方案,性能也是二者的折中 。 具体做法是先将实存分组,每组内有若干实页,然后将虚存空间也以同样大小分组 。 所有虚组按照直接相联方式映射到实组集合,对应的虚实组之间各页则用全相联映射,如下页示意图 (a),(b)所 示 （ 设实组数为 2） 。
由于包含了两层不同的映射关系,页表须按虚组划分成许多子表 。 在虚实变换时,首先根据虚页号所在的虚组号,通过求模运算确定实组号,再按虚组号在相应的子表内读出组内页号,拼接在一起就是实页号 。 简记为,组号计算,组内查表,。 如图 (c)所示 。
采用组相联映象方式时,每个虚页在对应实组范围内有若干映象实页可供选择,实页争用的发生频率比直接相联要低；另一方面,由于页表内原来存放的实页号改成存组内页号,省略了实组号字段,所以页表占用空间也减少了 。 当然这两方面优点是互相抵触的：组内页数越多,实存空间划分的组数就越少,实组号字段所占位数也少,这时改善实页争用现象的效果较好,而节省页表空间的效果较差,反之亦然 。 实际使用中可根据性能要求选取合适参数 。
这种映象方式性价比较好,在 Cache-主存层次中被普遍使用 。
2001.9.1 计算机系统结构 67
组相联的地址映象方式与地址变换原理 (a)(b)
虚存 实页 0 1 2 3
虚组 0 0 0 √ √
1 实存 1 √ √
虚组 1 2 · 0 实组 0 2 √ √
3 · 1 虚 3 √ √
虚组 2 4 · 2 实组 1 页 4 √ √
5 · 3 5 √ √
虚组 3 6 6 √ √
7 7 √ √
( a ) 虚页集合与实页集合的对应关系 ( b) 对应关系表 （ √ 为有关系）
2001.9.1 计算机系统结构 68
组相联的地址映象方式与地址变换原理 (c)
虚地址 虚组号 1 0 组内页号 1 页内偏移量 D
实地址 实组号 0 组内页号 0 页内偏移量 d
0 组子表 项 0,,,
项 1,,,
1 组子表 项 0,,,
项 1,,,
2 组子表 项 0,,,
项 1 0 装入位 1,
3 组子表 项 0,,,
项 1,,,
( c ) 求模运算与分组查表结合进行虚实变换示例
2001.9.1 计算机系统结构 69
3.3.4 段相联 (P184)
段相联映象方式也是全相联与直接相联的一个折中方案 。 它的分段方法与组相联相同,不同的是所有虚段按照全相联方式映射到实段集合,对应的虚实段之间各页则用直接相联映射 （ 因为虚实段大小相同,所以实际上是一一对应 ）,如下页示意图 (a),(b)所示 （ 设实段数为 2） 。
段相联的虚实变换与组相联类似,不过可以通过计算来确定的部分不是在段外,而是在段内,即页表内只储存各虚页对应的实段号,段内页号则从虚页号中简单直接复制,拼接在一起就是实页号,简记为,段号查表,段内复制,。 如图 (c)所示 。
段相联映象方式的虚实段内页号对应关系是固定的,每个虚页在调入时可以选择的只是实段号 。 由于虚实段大小相同,所以虚段号比实段号位数多,
也就意味着,多 → 少,的映射 （ 组相联是等量映射 ）,其实页争用的发生频率比组相联要高 。 在节省页表存储空间方面,性能与组相联差不多 。
2001.9.1 计算机系统结构 70
段相联的地址映象方式与地址变换原理 (a)(b)
虚存 实页 0 1 2 3
虚 段 0 0 0 √ √
1 实存 1 √ √
虚 段 1 2 0 实 段 0 2 √ √
3 · 1 虚 3 √ √
虚 段 2 4 · 2 实 段 1 页 4 √ √
5 3 5 √ √
虚 段 3 6 6 √ √
7 7 √ √
( a ) 虚页集合与实页集合的对应关系 ( b) 对应关系表 （ √ 为有关系）
2001.9.1 计算机系统结构 71
段相联的地址映象方式与地址变换原理 (c)
虚地址 虚 段 号 1 0 段 内页号 1 页内偏移量 D
实地址 实 段 号 0 段 内页号 1 页内偏移量 d
0 段 子表 项 0,,,
项 1,,,
1 段 子表 项 0,,,
项 1,,,
2 段 子表 项 0,,,
项 1 0 装入位 1,
3 段 子表 项 0,,,
项 1,,,
( c ) 查表求实段号进行虚实变换示例
2001.9.1 计算机系统结构 72
多用户虚地址格式在多用户或多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从 CPU发出的虚地址还需要在前面拼接上一个,当前用户号,字段，形成,多用户虚地址,,
如下图所示 (参见 P154)。
在虚实变换时，上面所说的各种查表操作之前还得先去查一个,段表基址寄存器组,或,页表基址寄存器组,的小表格 (P150,P152),确定现在该查哪一张段表或页表。这个小表格建立在 CPU里，读写时间很短。
当前用户号 虚段号 虚页号 页内偏移量
2001.9.1 计算机系统结构 73
3.4 替换算法 (P164)
上面所讲的地址映象方式是在虚页调入时的,选址,规则，而地址变换方法则是命中时获得实地址的手段。
不命中时需要增加的操作就是首先调出一页，调出之后再调入称为
,替换,。
替换算法要解决的是选择调出对象的问题。
替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。
2001.9.1 计算机系统结构 74
3.4.1 几种常用的替换算法 (P164)
(1)随机算法 RAND ── 在比较范围内任取一页作为淘汰页；
(2)先进先出算法 FIFO ── 在比较范围内选取调入最早的一页作为淘汰页；
(3)最不经常使用算法 LFU ── 在比较范围内选取最近单位时间内使用次数最少的一页作为淘汰页；
(4)最不接近使用算法 LRU ── 在比较范围内选取最后一次使用离现在最久的一页作为淘汰页；
(5)最优替换算法 OPT ── 在比较范围内选取下一次使用时间离现在最久的一页作为淘汰页 。
2001.9.1 计算机系统结构 75
实例：实存状况图 (P166图 3.32)
例如 LRU 算法（其中 *号表示被选中的淘汰页）：
已访问次数 t 0 1 2 3 4 5 6 7 8 9 10
被访问虚页号 无 1 2 1 5 4 1 3 4 2 4
命中总次数
0 空 1 1 1 1 1 * 1 1 1 * 2 2
1 空 空 2 2 2 * 4 4 4 * 4 4 4
实存空间使用情况 （实页号为 0,1,2 ） 2 空 空 空 空 5 5 5 * 3 3 3 * 3 *
操作名称 初态 ( 空 ) 调入 调入 命中 调入 替换 命中 替换 命中 替换 命中
4 次被访问实页号 0 1 0 2 1 0 2 1 0 1
2001.9.1 计算机系统结构 76
这是对某些替换算法的统称 。 如果某些算法在同一地址流同一时刻的小容量分区情况下的保留页面集合必是大容量分区情况下的保留页面集合的子集
（ 当容量超过虚页总数时,保留页面集合相同 ）,则小容量下的命中点到大容量情况下仍然是命中点,并且随着容量加大,还可能会有新的命中点产生
。 具有这一特性的一类替换算法中成为,堆栈型算法,。
例如,P166图 3.32中,对 LRU算法,如果实页数增加到 4,则 t = 5时为了调入虚页 4就不必替换掉虚页 2,而是将虚页 1,2,4,5都留在实存,这时大容量分区情况下的保留页面集合 S2 = {1,2,4,5},同一时刻的小容量分区情况下的保留页面集合 S1 = {1,4,5}。 显然有 S1 S2。
P167第 4～ 8行是堆栈型算法的数学定义 。
堆栈型替换算法的主要性质就是 命中率 H随着实页分区容量 n的上升而单调上升 （ 不减性 ） 。
可以证明,LFU,LRU,OPT等算法都是堆栈型算法,而 RAND和 FIFO算法不是堆栈型算法 。 P168的图 3.34是一个实例,当实页数从 3增加到 4时,
FIFO的命中率反倒从 3降到 2。 具体观察,比如 t = 7时,S1 = {1,2,5},S2 =
{2,3,4,5},不满足子集关系 。 所以 FIFO不能保证当实页数增加时,原来的命中点不丢 。
3.4.2 堆栈型替换算法 (P166)
2001.9.1 计算机系统结构 77
实例：堆栈模拟图研究堆栈型替换算法的性质，一方面可以设计优化的操作系统算法（例如
P167倒数第 3行的 PFF法），另一方面也可推导出一些分析工具，例如“堆栈模拟法”。
堆栈模拟图可以通过一次作图,描述同一地址流在各种实存分区容量下的命中情况 。
例 3.4
t 1 2 3 4 5 6 7 8 9 10 11 12
P 2 3 2 1 5 2 4 5 3 2 5 2
s
t
( 1 ) 2 3 2 1 5 2 4 5 3 2 5 2
s
t
( 2 ) 2 3 2 1 5 2 4 5 3 2 5
s
t
( 3 ) 3 2 1 5 2 4 5 3 3
s
t
( 4 ) 3 3 1 1 2 4 4 4
s
t
( 5 ) 3 3 1 1 1 1
s
t
( 6 )
命中次数
n= 1 0
n= 2 * * 2
n= 3 * * * * * 5
n= 4 * * * * * * 6
n= 5 * * * * * * * 7
2001.9.1 计算机系统结构 78
3.5 虚拟存储器与 Cache的特点 (P146,P172)
虚拟存储器与 Cache的主要区别
(P173表 3.4)
Cache的主要组成与工作流程
(P173图 3.38)
2001.9.1 计算机系统结构 79
本章小结
(1) 并行存储系统原理；
(2) 存储层次的原理及 5项性能指标；
(3) 存储层次的 3种管理方式；
(4) 4种地址映象与地址变换方式；
(5) 5种替换算法；
(6) 堆栈型替换算法；
(7) 主存 -辅存层次与 Cache-主存层次的特点；
(8) 实存状况图、堆栈模拟图（ 2种分析工具）。
习题,P206,题 15，题 19。
2001.9.1 计算机系统结构 80
第四章 输入输出系统（ P208）
输入输出系统 是计算机系统中实现各种输入输出任务的资源总称 。 它包括各种输入输出设备,相关的管理软件等等 。 由于输入输出设备的特殊工作性质使其数据吞吐率通常远低于主机,设计输入输出系统就是要建立数据交换的最佳方案,使双方都能高效率地工作 。
本章重点是 中断优先级管理,通道流量设计 。
2001.9.1 计算机系统结构 81
4.1 基本输入输出方式 (P212)
4.1.1 程序控制 I/O方式
4.1.2 中断 I/O方式
4.1.3 DMA方式
4.1.4 通道方式
4.1.5 I/O处理机 方式
2001.9.1 计算机系统结构 82
4.2 中断优先级管理 (P219)
中断是为实时任务优先获得处理机资源而采用的一种调度技术,当系统中存在多个中断源时必须根据实时性强弱设定优先顺序,这也被称为 中断的分级 。 为了兼顾中断响应的时效与配置的灵活,通常采用两套机制结合组成中断优先序管理体系 。
(1)硬件响应优先序,未被屏蔽的几个中断源同时提出申请时,CPU选择服务对象的顺序 。 它由硬件电路实现,用户不能修改 。 如 P226图 4.11所示
。
(2)软件服务优先序,在各中断服务程序开头,用软件设置自己的中断屏蔽字 （ 在主程序中也设置 ） 。 以此改变实际服务顺序 (P230)。
例如某个硬件响应优先级高的中断源,其中断服务程序执行中屏蔽了自身,而开放了某个硬件响应优先级比它低的中断源,后者就可以在前者刚开放中断时就打断它,从而在实际上先得到服务 。
中断服务过程示意图如 P231图 4.14所示 。
由于常规用户主程序对处理机的需求紧迫性最低,所以它的中断屏蔽字是,全部开放,。
(3)实例分析,屏蔽字表,中断服务过程图 。
例 4.1（ P230倒数第 8行开始 ）
2001.9.1 计算机系统结构 83
4.3 通道处理机 (P233)
(1)定义：
通道处理机 （简称 "通道 "）是隶属于主处理机的输入输出专用协处理机。
(2)特点：
有一套输入输出功能很强的专用指令系统；
与主处理机共享主存，存放相应的程序和数据；
一个通道可以连接多台外部设备；
主处理机可用 "启动 I/O"指令 来启动一个通道；
当通道访存与主处理机冲突时，存控部件赋予通道较高的优先权；
通道程序执行完毕自动转入休眠状态，同时向主处理机发出一个特定的中断申请，通知该事件。
(3)地位：
从属于主处理机。
2001.9.1 计算机系统结构 84
字节多路通道,以字节为单位交叉为多台设备传输。子通道的概念。
选择通道,完成一台设备的全部传输再去为另一台设备服务。
数组多路通道,以数组为单位交叉为多台设备传输。
(5)通道传输过程的时间分配 (P241,其中 P是设备台数 )：
字节多路通道：,其中 n是单台设备的数据传输量；
选择通道：
数组多路通道：,其中 k是块尺寸,。
(4)分类 (P238)：
nPTTT DSB Y T E )(
nPTnTT DSS E L E C T )(
nPTkTT DSB L O C K )( nk?
2001.9.1 计算机系统结构 85
(6)通道流量分析 (P243)：
通道最大能力流量,
D
S
B L O C KM A X
D
S
S E L E C TM A X
DS
B Y T EM A X
T
k
T
f
T
n
T
f
TT
f
1
1
1
.
.
.
2001.9.1 计算机系统结构 86
通道实际最大负荷流量,
i
P
i
B L O C K
i
P
i
S E L E C T
P
i
iB Y T E
ff
ff
ff
1
1
1
m a x
m a x
通道正常工作条件,
jM A Xj ff,?
2001.9.1 计算机系统结构 87
实例分析：
通道时间关系图
例 4.2（ P243倒数第 2行开始）
）解：（见教材
，并作时间图。。求通道实际流量秒
，
秒
，
秒
，
秒
，
秒已知：
244243
1075
1
1050
1
1030
1
1030
1
1010
1
6564
636261
PP
fff
fff
B Y T E
2001.9.1 计算机系统结构 88
4.4 I/O处理机 (P245)
定义,有独立内存和操作系统的 I/O专用计算机。
2001.9.1 计算机系统结构 89
本章小结
(1) 5种 I/O方式；
(2) 中断优先级管理（屏蔽字表、中断服务过程图）；
(3) 3种通道处理机的特点；
(4) 3种 通道最大能力流量 ；
(5) 3种 通道实际最大负荷流量 ；
(6) 通道正常工作条件 ；
(7) 通道时间关系图（字节多路通道） ；
习题,P250,题 5,题 8。
2001.9.1 计算机系统结构 90
第五章 标量流水线技术 (P253)
本章学习标量计算机上使用的流水加速技术。主要内容有 流水技术的分类,流水线性能指标计算,非线性流水线的调度算法 。
5.1 基本名词术语 (P253)
标量处理机,超标量处理机,标量处理机指只能进行标量运算的处理机，
超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；
指令级并行技术,指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；
流水线处理机,超流水线处理机,流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；
超长指令字技术 VLIW,指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。
2001.9.1 计算机系统结构 91
5.2 流水处理与逻辑相关的概念流水线是一种通过改进ＣＰＵ结构来提高程序解释速度的方法。
5.2.1 流水线工作原理处理机解释程序的方式有 顺序方式,重叠方式,流水方式 等。
顺序方式 是解释完一条指令再开始解释下一条 (P254)；
流水方式 是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目 (P277)；
重叠方式 是一种简单的流水方式，它把指令分成 2个子过程，每条指令只与下一条指令相重叠 (P255)。
2001.9.1 计算机系统结构 92
流水线结构图 (P278)
Δ t
1
Δ t
2
Δ t
3
Δ t
4
入口 Ⅰ Ⅱ Ⅲ Ⅳ 出口图 5.1 流水线结构图
流水线工作时空图 (P278—P279)
2001.9.1 计算机系统结构 93
空间 （段号）
Ⅳ 1 2 3 4
Ⅲ 1 2 3 4
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
16 时间 （拍）
( a ) 顺序方式空间 （段号）
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
10 时间 （拍）
( b) 重叠方式空间 （段号）
Ⅳ 1 2 3 4
Ⅲ 1 2 3 4
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
7 时间 （拍）
Δ t ( c ) 流水方式图 3.2 C P U 工作时空图
2001.9.1 计算机系统结构 94
5.2.2 逻辑相关 (P263-276)
相关的定义,(P263倒数第 4段 )
一条指令必须等待前一条指令解释完成才能开始解释。
相关的分类及其对策
1,全局性相关 /局部性相关 (P312,P269/P263,P303)；
2,指令相关 /数相关 (P264/P263)；
3,主存数相关 /寄存器数相关 (P265/P266)；
4,数值相关 /变址值相关 (P266/P268)。
2001.9.1 计算机系统结构 95
5.3 流水技术的分类 (P280)
线性 /非线性 (P280)
部件级 /处理机级 /处理机间级（宏流水线） (P281)
单功能 /多功能 (P282
静态 /动态 (P283)
标量 /向量 (P285)
同步 /异步 (P285)
顺序 /乱序 (P285,P304)
2001.9.1 计算机系统结构 96
5.4.1 吞吐率 TP(P285)
吞吐率（ TP ─── ThroughPut） 指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。
，其中 k表示流水线划分的段数。
当满足 条件时，有 。
5.4 线性流水线性能分析 (P285)
kT
nTP?
tti tknT k )1(
2001.9.1 计算机系统结构 97
其中
5.4.2 加速比 (P288)
k
o
T
TS?
k
i
io tnT
1
2001.9.1 计算机系统结构 98
段效率：,各段平均效率：
其中 表示第 i段设备量占整条流水线全部设备量的百分比 。
当满足 条件时,有：
5.4.3 效率（设备利用率,P289）
k
i
i T
tnE
k
i
ii EE
1
)(?
ktt ii
1和
k
i
k
i k
o
i
k
i Tk
Tt
Tk
nE
kE 1 1)(
1
i?
2001.9.1 计算机系统结构 99
例 5.1(P292)
分析：已知下列表达式,有相关,单功能,k = 4,n = 7。 要求最少相关,
用,二叉树算法,以减少相关 。
Z = A + B + C + D + E + F + G + H
① ② ③ ④
⑤ ⑥
⑦
时空图和算式见 P293。
5.4.4 实例分析 (P292)
2001.9.1 计算机系统结构 100
例 5.2(P293)
分析：已知下列表达式，二功能，有切换，有相关,k = 8,n = 7。 要求用最少切换、最少相关算法。
Z = A? B + C? D + E? F + G? H
乘法,① ② ③ ④
加法,⑤ ⑥
加法,⑦
时空图和算式见 P293 - P294。
2001.9.1 计算机系统结构 101
(1)瓶颈,瓶颈就是 Δti最大的段，它使流水线“流速”减慢（ P287图 5.37）。
S1 S2 S3 S4
Δt 3Δt Δt Δt
(2)方法 1,再细分 ─── 将瓶颈设备再细分为下一级流水线（ P287图 5.38）。
S1 S2a S2b S2c S3 S4
Δt Δt Δt Δt Δt Δt
(3)方法 2,并行设置 ─── 将瓶颈设备重复设置多套，轮番接受任务（ P288图
5.39）。 S2a
3Δt
S1 S2b S3 S4
Δt 3Δt Δt Δt
S2c
注意两种方法的时空图不同。 3Δt
5.4.5,瓶颈”问题及其解决方法 (P286-P288)
2001.9.1 计算机系统结构 102
5.5 非线性流水线调度技术 (P294)
调度问题的提出,
一个任务在通过非线性流水线时对有些功能段要 通过多次 （非线性定义），所以容易与紧跟而来的后继任务发生 设备争用 。
调度机构的作用就是 合理安排 前后任务进入流水线的 相差时间,既要避免争用,又要使 相差时间尽可能少,以提高吞吐率。
2001.9.1 计算机系统结构 103
1.给出 预约表 R（ P295图 5.44）
(a)连接图；
(b)预约表 。
2.作 禁止表 F（ P297倒数第 2段）
F = { 3,4,6 }
3.作 原始 冲突向量 C（ P298倒数第 3段）
C = (101100),（ 电路见下页）
4.作 状态转移图 （ P299图 5.51）
从“根结点”开始画；每个结点中有几个,0”就要发出几条边，还有一条带“＊”号的边，它表示,≥”。
5.作 平均延迟拍数表 （ P300表 5.1）
取 平均延迟拍数最少的方案作为最优方案 （用计数器加译码电路实现） 。
5.5.1 不改变流水线结构的调度方法 (P295)
时间段
1 2 3 4 5 6 7
S1 1 1 1
S2 1 1
S3 1 1
S4 1
时间段
1 2 3 4 5 6 7
S1 2 2 2
S2 2 2
S3 2 2
S4 2
2001.9.1 计算机系统结构 104
动态冲突向量 （初值 000000）
0 010110 右移出 0
“或”运算器 0接通
1断开
101100
原始冲突向量共同时钟流水线 任务排队使用 冲突向量 C实现调度的原理图
2001.9.1 计算机系统结构 105
5.5.2 改变流水线结构的优化调度方法 ── 预留算法
(P296)
目的：等间隔的最小延迟调度方案
方法：插入延迟器件第 1步，确定 相邻任务间隔拍数,因为最小间隔拍数是一行内,×,的最大数目（第 11行）,取最小间隔拍数。
第 2步，确定插入延迟器件位置的原则（ P302第 2行 ）,从第一个,×,开始，凡是相距 最小间隔 拍数整倍数位置的,×,都要向后推迟。
实例（ P301倒数第 7行）：
1.确定间隔拍数（最多 3个,×,，所以是 3拍 ）；
2.插入延迟器件（使各行,×,的间距不为 3的倍数 ）；
3.修改预约表（ P302图 5.53(a)）；
4.写调度方案（ 3）。
（示意图见下页）
2001.9.1 计算机系统结构 106
a,未插入延迟段 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 1,2 1,2,3 2,3,4
S2 1 1,2 2,3 3,4
S3 1 2 1 3 2 4 3
S4 1 2 3 4
b,仅插入 1 个延迟段 D1 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 2 1 3 1,2 4 2,3
S2 1 2 1 3 2 4 3
S3 1 2 1 3 2 4
S4 1 2 3 4
D1 1 2 3
c,插入 2 个延迟段 D1,D2 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 2 1 3 2 1 4 3 2
S2 1 2 1 3 2 4 3
S3 1 2 1 3 2 4
S4 1 2 3 4
D1 1 2 3
D2 1 2
2001.9.1 计算机系统结构 107
5.6 超标量 /超流水技术 (P320)
超标量技术：一个时钟节拍内 同时 发射多条指令（ P324倒 2行）；
时空图见 P323图 5.71（ b）。
指令
9 9 9 9
8 8 8 8
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 6 节拍
2001.9.1 计算机系统结构 108
超流水技术：一个时钟节拍内 分时 发射多条指令（ P333第 1行）。
时空图见 P333图 5.79。
指令
9 9 9 9
8 8 8 8
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 6 节拍
2001.9.1 计算机系统结构 109
5.7 精简指令系统（ RISC） 技术 (P111)
什么是 RISC？（ P107）
CISC和 RISC是指令系统设计的两种思路,前者注重功能多，后者注重速度快。 双方各自发展了很多特色技术。
RISC主要用于工作站和其它高性能计算机，以 UNIX操作系统为主。 IBM-
PC个人计算机以 CISC为主，吸收了 RISC的若干适宜技术。
20%与 80%规律（ P112）
统计表明,CISC中 20%的常用指令使用率高达 80%，其它都是非常用指令。
RISC定义与特点（ P115）
①一个周期；②一种访存寻址方式；③硬联译码；④简化指令；⑤固定指令格式；⑥优化译码。
减少 CPI是 RISC思想的精华（ P116）
分析公式,T = IC · CPI · CYCLE,RISC使 IC增加，其它两项减少。
2001.9.1 计算机系统结构 110
RISC的关键技术 (P118)
1,延时转移技术将转移指令与它前面的不相关指令对调位置，以利用计算目的地址的时间。
2,指令取消技术在条件转移指令解释期间提前启动最有可能的一个分支的后继指令，如果
“猜”错则及时取消，“猜”对则赢得了时间。
3,重叠寄存器窗口技术用寄存器组代替堆栈传递参数，减少访问主存。
4,指令流调整技术用换名消除相关，消除不了的相关就调整顺序。
5,少数复杂指令用微程序实现不常用的复杂指令用微程序实现，避免专设电路，对平均速度影响也不大。
2001.9.1 计算机系统结构 111
本章小结
(1) 流水处理与相关的概念；
(2) 时空图画法及其应用；
(3) 7种流水线分类方法；
(4) 3个流水线性能指标；
(5) 2种,瓶颈”解决方法 ；
(6) 2种非线性流水线调度方法；
(7) 超标量与超流水技术的概念 ；
(8) 精简指令系统（ RISC） 技术。
习题,P343,题 9，题 15。
2001.9.1 计算机系统结构 112
6.1 特点多数为巨型机，有多条单功能流水线。
6.2 典型工作方式
CRAY-1是世界上第一台向量流水处理巨型机。
(1) CRAY-1的技术术语向量寄存器组 V0,V1,……,V7。
分量计数器链接方式 (P370)
启动、输出延迟（各 1拍）。
第六章 向量流水线技术 (P347)
2001.9.1 计算机系统结构 113
功能部件冲突 ── 指令运算符号相同；
Vi变量冲突 ── 指令中使用的 Vi变量相同，具体有 3种形式，
即左同名、右同名、上右下左同名。
冲突,① A=B+C ② A=B+C ③ A=B+C
A=D*E D=B*E B=D*E
相关,④ A=B+C
D=A*E
(3) CRAY-1分析指令的 3条策略无相关，无冲突 ── 同时启动；
有相关，无冲突 ── 链接启动；
有冲突 ── 顺序执行；
(4)计算向量程序执行时间的工具 ── 多流水线时空图 （结合 P391题 6.6实例学习 ）
(2) 冲突及其分类
2001.9.1 计算机系统结构 114
本章小结
(1) 向量流水处理机 特点 ；
(2) 冲突及其分类 ；
(3) CRAY-1分析指令的 3条策略 ；
(4) 链接方式；
(5) 启动、输出延迟（各 1拍）。
习题,P391，题 6（注意阅读 P372倒数第 9行－倒数第 6行）。
2001.9.1 计算机系统结构 115
本章内容：介绍用于多机并行计算的各种网络,它们统称为互连网络,
缩写符号是 ICN（ Interconnection Network） 。
7.1 目的与作用
(1) 当前提高计算速度的主要措施，一是改进器件，二是多机并行计算。 ICN
是多机之间传输数据的高速通路，对整体性能起关键作用。
(2) ICN的分类,通用网 （原用于计算机之间交换信息的普通网络）,专用网
（专用于并行计算系统各处理单元之间并行交换数据的特殊网络） 。
(3) ICN与处理单元的连接模式（ P453-P454,P505）,分布存储型，共享存储型。 0 ICN 0
从处理单元来 1 开关 1 到处理单元或存储单元
N-1 网络 N-1
(4) ICN的主要操作,置换 (N-N),广播 (1-N),选播 (1-N’)。
第七章 互连网络 (P394)
2001.9.1 计算机系统结构 116
特点：成本低，并行性差。
(1) 拓扑结构 (硬件,P402-P407),直线，单向环，双向环，带弦环，树，星型（真星型，假星型），完全网。
(2) 传输协议 (使用规则，软件,P427-P435),碰撞争用，令牌协议，剑桥环。
(3) 主要参数 (P399),直径，中剖宽度，结点的度，最长边。
示例：
(4) 典型代表：以太网，令牌网（环或直线）。
7.2 通用网
2001.9.1 计算机系统结构 117
特点：并行度高，造价昂贵。
(1) 互连函数
N个输入到 N个输出的一种对应状态可以用一个映射函数表示，称为互连函数。它是处理单元集合对于自身的双射映射，所以又称为,置换,，或者,循环,。
互连函数有多种表示方式，如下例所示：
f(0)=1 0 0
f(1)=2 1 1 f= 0 1 2 3 f=(0,1,2)(3)
f(2)=0 2 2 1 2 0 3
f(3)=3 3 3
a.枚举法 b.开关状态图 c.列表法 d.循环函数一个网络通过开关切换可以形成多个映射关系，所以要用,互连函数族,来定义一个网络。
7.3 专用网
2001.9.1 计算机系统结构 118
定义,单级 ICN只使用一级开关，如下图所示。
开关的每种接通组合方式可用一个互连函数表示。
f( j入 ) = j出,0≤ j≤N -1
在互连函数中，记：
N ── 结点数
n = log2N ── 维数
j= Xn-1…… X0 ─ ─ 结点编号的二进制形式，位数为 n。
互连函数族的组成必须使网络成为 连通图 。
(2) 单级 ICN
ICN
0 0
N-1 N-1
2001.9.1 计算机系统结构 119
该网络由立方体 函数定义,立方体 函数族有 n个成员,分别是 Cube0,Cube1
,……,Cuben-1。
立方体 函数 定义,Cubei的功能 是对 入端结点编号二进制形式的第 i位取反
Cubei(Xn-1… Xi+1XiXi-1… X0)=Xn-1… Xi+1XiXi-1… X0,其中 0≤ i≤n -1
例如,Cube0(0)=1,Cube3(7)=15。
n=3的单级立方体网络拓扑形状如 右 图所示 。
最坏情况下的传输需 对输入结点编号的全部
n位取反 。 所以 单级立方体网络的直径是 n。
立方体 函数 性质,结合律,交换律 以及 自反律 （ Cubei重复使用 2次的结果与原始自变量相同 ） 。
单级立方体网 （ Cube网,P396第 1行 / P404第 4行）
2 3
0 1
6 7
4 5
2001.9.1 计算机系统结构 120
该网络由 混洗函数 （ shuffle） 与 交换函数 （ exchange即 Cube0） 定义,或者说它的互连函数族只有这两个成员 。
混洗函数 定义：
2j mod（ N-1）,当 j < N-1
shuffle（ j） =
N-1,当 j = N-1
例如：当 N=8时,shuffle（ 0） = 0,shuffle（ 1） = 2,shuffle（ 7） = 7。
n=3的混洗函数开关状态如 P397图 7.6(a)所示,其连接规律就像洗牌 。
性质 1,shuffle（ Xn-1Xn-2…… X0） = Xn-2…… X0Xn-1（ 循环左移）
性质 2,shufflen（ j） = j
n=3的 混洗 网络拓扑形状如下图 绿线 所示,可以看出它不是一个 连通图,所以还需要增加一个 交换函数 （ 图中 红线 所示 ）,才能构成完整的单级混洗 —交换网络 。
单级混洗 —
交换网络的直径是 2n-1。
单级混洗 -交换网 （ P396倒数第 8行 ）
0 1 2 3 4 5 6 7
2001.9.1 计算机系统结构 121
该网络由 PM2I函数定义,PM2I函数共有 n对成员,分别是 PM2 ± 0,PM2 ± 1，
……,PM2 ± (n-1)。
PM2I函数定义,PM2± i的功能是对入端结点编号加或减 2i,然后再作模 N运算
PM2+i（ j） = j + 2i mod N
PM2-i（ j） = j - 2i mod N
其中 j = 0 ～ N - 1,i = 0 ～ n - 1。
例如：当 N = 8时,
PM2+0（ 0） = 0 + 20 = 1，
PM2+0（ 1） = 1 + 20 = 2，
PM2+0（ 7） = 7 + 20 = 0，
PM2+1（ 0） = 0 + 21 = 2。
N = 8的 PM2+1（ j） 函数开关状态如右图所示,其连接规律是把各入端结点编号加上相同的增量 21（ mod N）,获得出端结点编号 。
单级加减 2i网 （ PM2I网，移数网,P398倒数第 2行）
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
2001.9.1 计算机系统结构 122
N = 8的 PM2+i网络拓扑形状如下图所示，可以看出它包含多个强连通子图
（即除去若干边以后仍能保证任何一对结点互相可达），所以这 2n个函数并不是实现互连网的最小集合。实际应用中为了降低造价，人们往往取它们的一个子集来构造互连网。
性质 1：对相同的 i值,PM2+i
与 PM2-i函数的传送路径相同,
方向相反 （ 右图中所有箭头反向即为 PM2-1的拓扑形状 ） ；
性质 2,PM2+(n-1) = PM2-(n-1)。
根据性质 2,我们知道单级 PM2I网络实际上只能实现 2n-1种不同的置换 。
单级 PM2I网络的直径是 。?2/n
i=1 i=2
0
7 1
i=0
6 2
5 3
4
2001.9.1 计算机系统结构 123
(3) 多级 ICN（ P409）
定义：多级 ICN使用多级开关,使得数据在一次通过网络的过程中可以实现的置换种类更多 。
通常在 N个结点的网络中,多级 ICN由 n级构成 （ n = log2N） 。
经典的多级互连网有 多级立方体网,多级混洗 —交换网 和 多级 PM2I网 。 我们只学习多级混洗 —交换网 。
多级立方体网和多级混洗 —交换网不使用单级互连网中的那种多路选择开关
,而是用一种 2输入 /2输出的 二元交换开关,以减少开关总数 。 二元交换开关的基本接通状态有,直连,,,交换,,,上播,和,下播,,在进行数据置换时只能使用前 2种 。
各开关的控制信号可采用 3种分配方式之一,级控方式,部分级控方式 和 单元控制方式 。
级控方式 就是同一级 （ 即同一列 ） 开关共用一个控制信号,动作保持一致；
部分级控方式 在第 i级设置 i+1个独立的控制信号,每个信号管辖若干开关； 单元控制方式 为每个开关独自设置一个控制信号,各开关动作独立,性能比前两种方式都更灵活,结构也更复杂 。
( a ) 直连 ( b ) 交换 ( c ) 上播 ( d ) 下播
2001.9.1 计算机系统结构 124
多级混洗 —交换网络（ P410/P436）
多级混洗 —交换网络又称为 Omega网 。
多级混洗 —交换网络结构：它 由 n级构成,每一级包含 一个无条件 混洗拓扑 线路 和 一列可控的二元 交换开关,前后重复,便于制造 。 如 P436图 7.43所示 。
各级编号是 n-1,……,0,即按 降序排列 。
在多级混洗 —交换网络中,单独一级 混洗拓扑线路可完成一次 数据混洗 （
shuffle）,而单独一列二元交换开关在处于,交换,状态时可完成一次 交换操作 （ Cube0） 。 如果各级二元交换开关都处于,直连,状态,N个结点的数据通过网络仅经过 n次混洗操作,排列顺序最终 恢复输入状态 （ 混洗函数性质 2） ；如果各级二元交换开关都处于,交换,状态,则 N个结点的数据在每次混洗之后紧接着一次交换 （ Cube0）,也就是地址码的最低位取反,最后 n
位地址均被取反 。 程序员根据数据置换或复制的需要,可以灵活地设置各开关的状态 。
2001.9.1 计算机系统结构 125
多级混洗 —交换网络寻径算法（路由算法）
目的,根据给定的输入 /输出对应关系,确定各开关的状态 。
名称,源 -目的地址异或法操作,将任一个输入地址与它要到达的输出地址作异或运算,其结果的 biti
位控制数据到达的第 i级开关,,0” 表示,直连,,,1” 表示,交换,。
例如给定传输 101B→ 011B,二者异或结果为 110B,于是从 101B号输入端开始,把它遇到的第 2级开关置为,交换,,第 1级开关置为,交换,,第 0
级开关置为,直连,。 如下图 红线 所示 。
输入 第 2 级 第 1 级 第 0 级 输出
000 000
00 1 001
0 1 0 0 1 0
0 11 011
1 00 1 00
1 0 1 1 01
11 0 1 10
1 11 1 11
2001.9.1 计算机系统结构 126
本章小结
(1) 通用网的拓扑结构，传输协议，主要参数，典型代表；
(2) 互连函数（置换，循环）的 4种表示方式；
(3) 单级立方体网（ Cube网）的定义，拓扑形状，直径，性质，互连函数族的组成；
(4) 单级混洗 -交换网的定义，拓扑形状，直径，性质，互连函数族的组成；
(5) 单级加减 2i网（ PM2I网，移数网）的定义，拓扑形状，直径，性质，互连函数族的组成；
(6) 二元交换开关，控制信号的 3种分配方式；
(7) 多级混洗 —交换网络的结构，寻径算法（路由算法）。
习题,P446,必做 3,10,26(1)～ (3)； 选做 4,7,9。
2001.9.1 计算机系统结构 127
第八章 SIMD计算机 (P451)
SIMD计算机 指由 一个控制部件 和 多个运算部件 组成的处理机为核心的计算机系统。这样的处理机又被称为 并行处理机 或 阵列处理机 。
2001.9.1 计算机系统结构 128
8.1 SIMD的 5个组成部分 (P453)
运 ── PEi
控 ── CU
存 ── LMi
管 ── SC
网 ── ICN
2001.9.1 计算机系统结构 129
8.2 SIMD的两种结构类型 (P453～ P454)
(1)分布存储结构
(2)共享存储结构
2001.9.1 计算机系统结构 130
8.3 SIMD的代表实例 ─── ILLIAC IV(P457)
ILLIAC IV的 ICN（ P458）
它是单级 PM2I网络 的一个子集,F={PM2± 0,PM2± (n/2)},这里 n=6。
可以证明，任意两个结点之间的距离不超过 7步。
ILLIAC IV的 4条并行传输指令 （ P479）
循环左传 1（西），循环左传 8（北），循环右传 1（东），循环右传 8（南）。
每个 PEi的组成 （ P458～ P459）
A ── 累加器（ 64位）
B ── 通用寄存器（ 64位）
R ── 互连寄存器（ 64位）
M ── 模式寄存器（ 8位）
2001.9.1 计算机系统结构 131
8.4 SIMD的典型算法 (P483)
矩阵加,减 （ P484）
迭代平均 （ P483）
非数组问题的向量化算法 （ P486）
2001.9.1 计算机系统结构 132
本章小结
(1) SIMD的 5个组成部分
(2) SIMD的两种结构类型
(3) SIMD的代表实例 ─── ILLIAC IV
(4) SIMD的典型算法。
习题,P498，题 12。
2001.9.1 计算机系统结构 133
第九、十章 MIMD计算机 (P499)
目前实际使用的 MIMD计算机都是 多处理机系统,包括 多计算机系统 。
MIMD计算机与 SIMD计算机的主要区别,在于前者是 任务级并行处理,后者是 数据级并行处理 。
2001.9.1 计算机系统结构 134
9.1 MIMD的典型结构 (P500)
(1)共享存储器方案
(2)本地存储器方案
2001.9.1 计算机系统结构 135
(1)任务派生语句 ─── FORK <进程名 >
(2)任务汇合语句 ─── JOIN <汇合进程数 >,<计数器序号 >
实例,P608
x = ( a + b )× ( a - c )
程序：
k,Fork k+3
k+1,Add A,B,T1
k+2,Goto k+4
k+3,Sub A,C,T2
k+4,Join 2,1
k+5,Mul T1,T2,X
9.2 MIMD的并行程序控制 (P608)
k:A+B → T1 k+3:A-C → T2
k+5:T1*T2 → X
2001.9.1 计算机系统结构 136
9.3 MIMD的加速性能模型 (P502～ P512)
(1)两个处理机的并行模型 （ P504） ；
总处理时间 = R× max{ M-K,K } + C× ( M-K )× K
其中,M ── 任务总数；
K ── 分配给处理机 1的任务数；
R ── 执行 1个任务所需时间；
C ── 进行 1次通信所需时间 。
最优解,P505第 1～ 3行 。
(2)N个处理机的并行模型 （ P505） 。
总处理时间 = R× max{ Ki } + (C/2)× Σ [Ki× ( M-Ki )]
= R× max{ Ki } + (C/2)× ( M2-Σ Ki2 )
处理机 1 处理机 2
任务 1 任务 K + 1
任务 2 任务 K + 2
┇ ┇
任务 K 任务 M
2001.9.1 计算机系统结构 137
本章小结
(1) MIMD的 2种典型结构
(2) MIMD的并行程序控制
(3) MIMD的加速性能模型习题,P562，题 18。
2001.9.1 计算机系统结构 138
附录 1
部分习题参考答案
2001.9.1 计算机系统结构 139
第一章 (P33)
题 15
题 19
2001.9.1 计算机系统结构 140
第二章 (P124)
题 3（忽略 P124倒 1行 ~ P125第 8行文字）
题 13
2001.9.1 计算机系统结构 141
第三章 (P202)
题 3
题 15
题 19
2001.9.1 计算机系统结构 142
第四章 (P250)
题 5
题 8
2001.9.1 计算机系统结构 143
第五章 (P343)
题 9
题 15
2001.9.1 计算机系统结构 144
第六章 (P391)
题 6.6（注意阅读 P372倒数第 9行－倒数第 6行）
解：
已知 n=32,k加 =6,k乘 =7,k访存 =6,k倒数 =14，启动、输出延迟各 1。求各小题总拍数。
2001.9.1 计算机系统结构 145
( 1) V 0 ← 存储器
V 1 ← V 2 + V 3 并行
V 4 ← V 5 * V 6
访存加乘
9 31
总拍数 =40 （并行执行，以最长指令为准）
( 2) V 2 ← V 0 * V 1 并行
V 3 ← 存储器
V 4 ← V 2 + V 3 串行 （ P 372 ）
乘访存加
9 31 8 31
总拍数 =79 （第 3 条错过时机，不能链接）
2001.9.1 计算机系统结构 146
( 3) V 0 ← 存储器 并行
V 3 ← V 1 + V 2 链接
V 4 ← V 0 * V 3
V 6 ← V 4 + V 5 串行访存加乘
8 9 31 8 31
总拍数 =87 （第 4 条功能部件冲突）
( 4) V 0 ← 存储器 链接
V 1 ← 1 / V 0 链接
V 3 ← V 1 + V 2 链接
V 5 ← V 3 * V 4
访存倒数加乘
8 16 8 9 31
总拍数 =72 （各条依次链接）
2001.9.1 计算机系统结构 147
( 5) V 0 ← 存储器
V 1 ← V 2 + V 3 并行
V 4 ← V 5 * V 6
s 0 ← s 1 + s 2 串行访存加乘
9 31 8
总拍数 =48 （标量看成 1 个分量的向量）
( 6) V 3 ← 存储器 并行
V 2 ← V 0 + V 1 串行
s 0 ← s 2 + s 3 并行
V 3 ← V 1 * V 4
访存加乘
8 31 9 31
总拍数 =79 （标量看成 1 个分量的向量）
2001.9.1 计算机系统结构 148
( 7) V 3 ← 存储器 并行
V 2 ← V 0 + V 1 链接
V 4 ← V 2 * V 3
存储器 ← V 4 串行访存加乘
8 9 31 8 31
总拍数 =87 （第 4 条功能部件冲突）
( 8) V 0 ← 存储器 链接
V 2 ← V 0 + V 1
V 3 ← V 2 * V 1 串行
V 5 ← V 3 * V 4 串行访存加乘
8 8 31 9 31 9 31
总拍数 =127 （ Vi 冲突，功能部件冲突）
2001.9.1 计算机系统结构 149
第七章 (P446)
必做 3,10,26(1)～ (3)；
选做 4,7,9。
2001.9.1 计算机系统结构 150
第八章 (P498)
题 12
2001.9.1 计算机系统结构 151
第九、十章 (P562)
题 18
2001.9.1 计算机系统结构 152
再见
计算机系统结构主讲：华中科技大学计算机学院林安
2001.9.1 计算机系统结构 2
教学计划
教材：
《计算机系统结构》（第二版）
郑纬民等清华大学出版社
参考书：
《计算机系统结构复习与考试指导》
郑纬民等高等教育出版社
总学时,40
– 第 1章,4
– 第 2章,4
– 第 3章,10
– 第 4章,4
– 第 5章,6
– 第 6章,2
– 第 7章,6
– 第 8章,2
– 第 9,10章,2
2001.9.1 计算机系统结构 3
第一章 基本概念（ P1）
本章介绍计算机系统结构的一些基本知识。包括定性知识和定量知识两大组内容。为了便于学习，本章各节重新编号，与教材编号不同。
定性知识,本课程经常使用的一些名词概念，以及对计算机的定性认识、分析方法。
定量知识,对计算机性能进行定量评价的几个重要公式。
2001.9.1 计算机系统结构 4
1.1 定性知识 ─── 几个基本概念
1.1.1 什么是 计算机系统结构？ （ P4）
英文名称,Computer Architectrue
计算机系统结构（也叫,计算机体系结构,） 课程,传授计算机整机（硬软件统一条件下）设计的重大技术知识 。
Architectrue的英文原义是“建筑学”。
“计算机系统结构”作为 事物名称,使用者必须了解的机器外部特性知识 （广义定义）。在本课程中“使用者”目前特指最低级语言的程序员，“外部特性”特指整个硬件的外部特性（狭义定义）。
透明性概念,使用者可以不了解的知识。
2001.9.1 计算机系统结构 5
“计算机系统结构”狭义定义包含的内容（ P4）
1.数据表示 （ 硬件能够直接识别和处理的数据类型和格式等 ） ；
2.寻址方式 （ 包括最小寻址单位,寻址方式的种类,表示和地址计算等 ） ；
3.寄存器组织 （ 包括各种寄存器的配置数目和功能定义 ） ；
4.指令系统 （ 包括机器指令的操作类型和格式,指令间的排序方式和控制机构等 ） ；
5.存储系统 （ 包括编址方式,存储容量,最大编址空间等 ） ；
6.中断机构 （ 中断源的分类管理和中断服务功能设计 ） ；
7.机器工作状态 （ 如管态,目态等 ） 的定义和切换；
8.输入 /输出 子系统结构与管理；
9.信息保护 手段及其实现 。
2001.9.1 计算机系统结构 6
第 5级 专用应用语言机器 特定应用用户 （ 使用特定应用语言 ）
（ 经应用程序翻译成高级语言 ）
第 4级 通用高级语言机器 高级语言程序员 （ 使用通用高级语言 ）
（ 经编译程序翻译成汇编语言 ）
第 3级 汇编语言机器 汇编语言程序员 （ 使用汇编语言 ）
（ 经汇编程序翻译成机器语言,操作系统原语 ）
第 2级 操作系统语言机器 操作系统用户 （ 使用操作系统原语 ）
（ 经原语解释子程序翻译成机器语言 ）
第 1级 传统机器语言机器 传统机器程序员 （ 使用二进制机器语言 ）
（ 由微程序解释成微指令序列 ）
第 0级 微指令语言机器 微指令程序员 （ 使用微指令语言 ）
（ 由硬件译码器解释成控制信号序列 ）
图 1.1 计算机系统的多级层次模型
1.1.2 计算机系统的多级层次模型（ P3）
2001.9.1 计算机系统结构 7
1.1.3 其他重要名词概念（自学）
[计算机组成 ]计算机系统结构的逻辑实现 。 （ P5）
[计算机实现 ]计算机组成的物理实现 。 （ P5）
[计算机系统设计的 3种主要方法 ]：,由下往上,,,由上往下,,
,由中间开始,。 （ P14）
[系列机 ] （ P23）
[兼容性 ] （ P24）
[模拟 ] （ P24）
[仿真 ] （ P24）
[虚拟机 ] （ P24）
[宿主机 ] （ P24）
[并行性 ] 求解一个问题的若干操作在时间安排上的可重叠性 。
2001.9.1 计算机系统结构 8
1.1.4 冯,诺依曼（ Von Neumann） 型机器的特点（ P22）
传统计算机又称为 冯,诺依曼型机器,它由运算器,控制器,存储器,输入设备和输出设备 5部分组成,并具有如下特点：
1.以运算器为数据流动中枢,以控制器为控制命令中枢；
2.存储程序并且执行,程序象数据一样可以修改；
3.存储器按地址访问,线性顺序编址；
4.程序顺序执行；
5.指令由操作码与操作数两部分组成；
6.数据用二进制编码；
7.机器由硬件与软件组成,硬件功能不能改变 。
2001.9.1 计算机系统结构 9
1.1.5 现代计算机系统的分类（ Flynn分类法,P6）
按照指令流和数据流的多倍性状况把计算机分为：
1.单指令流单数据流 （ SISD---Single Instruction Stream Single
Data Stream）
2,单 指 令 流 多 数 据 流 （ SIMD---Single Instruction Stream
Multiple Data Stream）
3.多 指 令 流 单 数 据 流 （ MISD---Multiple Instruction Stream
Single Data Stream）
4.多 指 令 流 多 数 据 流 （ MIMD---Multiple Instruction Stream
Multiple Data Stream）
例题,P32,题 7，题 8,题 9 。
2001.9.1 计算机系统结构 10
1.2 定量知识 ───3 个性能公式
1.2.1 Amdahl定律 （ 加快经常性事件原理,P9）
e
e
e
n
o
n
S
FFT
TS
)1(
1
其中,Sn ── 全局加速比；
To ── 原执行时间 （ old） ；
Tn ── 新执行时间 （ new） ；
Se ── 被改进部分的局部加速比；
Fe ── 被改进部分原执行时间占原来总时间的百分比 。
2001.9.1 计算机系统结构 11
Amdahl定律的推导
e
e
e
n
o
n
e
e
eon
eeoo
S
F
F
T
T
S
S
F
FTT
FFTT
)1(
1
)1(
)1(
根据加速比定义，有：
：操作加快，总时间降为改进之后由于其中部分
，间可写为：改进之前程序运行总时
2001.9.1 计算机系统结构 12
Amdahl定律的图形
S
n
极限 2 =
2
1
1
e
F?
极限 1 =
1
1
1
e
F?
F e = F
e2
F e = F
e1
1,0
（设 F
e2
> F
e1
）
0,0 1,0 S
e
图 1.2 Amdahl 定律的图形从图 1.2可以看出,增大 Se和 Fe对 Sn都有提升作用；但当 Fe固定时
,一味增大 Se对 Sn的作用会越来越不显著 。
2001.9.1 计算机系统结构 13
1.2.2 CPI与程序执行时间 Te（ P11）
CPI是衡量 CPU执行指令效率的重要指标。让我们先考虑一个标准测速程序的 全部执行时间 Te和其中 所有第 i种指令的累计时间 Ti,易知的加权平均值。为所有，它表明）（或者写为
）（
的关系与一式，可以得到比较上面第一式与最后写另一方面，我们又可以
，
i
n
i
i
i
n
i
ii
n
i
ii
n
i
ii
n
i
ie
n
i
i
iii
e
C P IC P IC P I
IC
IC
C P I
C P IICC P IIC
C Y C L EC P IICC Y C L EC P IICTT
ICIC
f
C Y C L E
C Y C L EC P IICT
C Y C L EC P IICT
C P IC P I
)()(
1
其中：
1
1
i
111
1
2001.9.1 计算机系统结构 14
1.2.3 每秒百万指令数 MIPS与每秒百万浮点数 MFLOPS
（ P11）
。，主要用于向量计算机条数每次浮点运算所需指令；，主要用于标量计算机
M I P S
M F LO P S
C P I
f
C Y C LEC P IIC
IC
T
IC
M I P S
e
666 101010
例题,P10,例 1.1~例 1.5。
P33,题 12,题 13,题 14 。
2001.9.1 计算机系统结构 15
例题选讲（ 1）
例 1.1（ P10）
Amdahl定律公式,已知,Fe=0.4,Se=10,求 Sn。
它说明局部（ 40%）的大幅度改进（ 10倍）对全局的作用要小得多（ 1.56倍）。
例 1.2（ P10）
Amdahl定律公式,已知方案 1,Fe1=0.2,Se1=10,求 Sn1；
已知方案 2,Fe2=0.5,Se2=2,求 Sn2 。
它说明大范围的小幅度改进（方案 2）效果可能更好。
2001.9.1 计算机系统结构 16
例题选讲（ 2）
例 1.3（ P11）
CPI公式,注意该公式中的指令数百分比不同于 Amdahl定律中的时间百分比 Fe,避免用错。
已知,ICFP / IC = 25%,IC非 FP / IC = 75%；
IC FPSQR / IC = 2%,IC非 FPSQR / IC = 98%。
改进前,CPI FP = 4.0,CPI非 FP = 1.33；
CPI FPSQR = 20,CPI非 FPSQR =？
改进后,CPI FP = 2.0,CPI非 FP = 老 值；
CPI FPSQR = 2.0,CPI非 FPSQR = 老值 。
求,两种方案改进后的 CPI。
分析,方案 2缺一个条件 CPI非 FPSQR,但改进前用两种方法算出的 CPI应该是相同的，所以由
CPI 老 = CPI FP× ICFP / IC+ CPI非 FP × IC非 FP / IC
= CPI FPSQR× ICFPSQR / IC+ CPI非 FPSQR × IC非 FPSQR / IC
2001.9.1 计算机系统结构 17
例题选讲（ 3）
解出 CPI非 FPSQR = 80 / 49
现在分别用两种方案改进后的参数代入公式，算出新的 CPI为
1.64和 1.5，显然 CPI值较小的方案 2较好。
教材的解法中有两个小公式值得注意，一个是：
iii
ii
i
ICC P IC P IICC P IC P I
C P IC P I
IC
IC
C P IC P I
)()(
)(
__
__
老新老新新老老新时钟周期数总改变量它的实质就是
另一个公式较容易理解：
新老新老
C PI
C PI
T
TS
e
e
n
_
_
2001.9.1 计算机系统结构 18
例题选讲（ 4）
例 1.4（ P12）
Te公式,其中 CPI用相应的公式代换
C Y C LEICICICC P IT
n
i
i
ie
1
)(
对 A机器，已知 CPI转 =2,IC转 /ICA=20%,CPI非转 =1,IC非转 /ICA=80%，
Te_A=1.2× ICA × CYCLEA；
对 B机器，从题义可知,IC比转 = IC转,ICB = ICA × 80%,CYCLEB
=1.25 × CYCLEA,CPI比转 =2，所以 IC比转 /ICB= IC转 /（ ICA × 80% ）
=25%,CPI非比转 =1,IC非 比转 /ICB=75%，
Te_B = 1.25× ICB × CYCLEB
= 1.25× 80%× ICA× 1.25× CYCLEA
= 1.25× ICA× CYCLEA > Te_A
显然 A机器快一些。
2001.9.1 计算机系统结构 19
例题选讲（ 5）
例 1.5（ P12）
Te公式,改动上题中 CYCLEB =1.1 × CYCLEA,则最后
Te_B = 1.25× ICB × CYCLEB
= 1.25× 80%× ICA× 1.1× CYCLEA
= 1.1× ICA× CYCLEA < Te_A
这时 B机器快一些。
题 12 （ P33）
Amdahl定律公式,代入已知量
Se=20变成一元函数
Sn=20/(20-19Fe)
用三点作图法作出关系曲线。
Sn
20
10.5
1.8
1
0 0.5 1 Fe
2001.9.1 计算机系统结构 20
例题选讲（ 6）
题 13 （ P33）
Amdahl定律公式,代入已知量 Se=20,Sn=2,解出 Fe=10/19
题 14 （ P33）
Amdahl定律公式,代入已知量 Se=20,Sn=10,解出 Fe=18/19
2001.9.1 计算机系统结构 21
本章小结本章从定性知识和定量知识两个方面介绍计算机系统结构的基本概念。有关重点如下：
(1) 计算机系统结构的广义定义与狭义定义（ 9项内容），计算机系统结构与计算机组成的主要分工；
(2) 计算机系统的多级层次模型（ 6级），以及基于该模型的透明性判断方法；
(3) 计算机实现、计算机系统设计的主要思路、模拟、仿真、虚拟机、
宿主机、系列机、兼容性、并行性等重要名词的含义；
(4) 冯,诺依曼型机器的 7个特点；
(5) 现代计算机系统分类的 Flynn法（ 4类）；
(6) Amdahl定律；
(7) 平均周期数 CPI公式，程序执行时间 Te公式；
(8) 每秒百万指令数 MIPS公式，每秒百万浮点数 MFLOPS公式。
习题,P33,题 15，题 19 ； P392,题 10，题 11,题 12 。
2001.9.1 计算机系统结构 22
第二章 指令系统（ P36）
本章介绍指令系统设计中 2个最基本的内容：数据表示、操作码优化。
2.1 数据表示
[数据表示 ]就是 计算机硬件能够直接辨认与处理的数据类型 。
人们通常使用的数据类型有整数、实数、逻辑数（布尔数）、字符串、
队列、堆栈、链表、文件等，它们的运算方法各不相同。
所谓,硬件能够直接辨认与处理,,指的是对该数据类型的各种运算操作都有相应的实现硬件电路。
硬件不能直接辨认与处理的数据类型就要根据 数据结构 的知识编制软件 转化 为硬件能处理的数据类型。
下面介绍通用型计算机数据表示集合中的一个基本成员 ── 浮点数据的分析与设计。
2001.9.1 计算机系统结构 23
2.1.1 浮点数据表示（ P38,P39）
浮点数据就是高级语言课程中所说的,实型数,。
2.1.1.1 浮点数的组成浮点数的组成与人们通常所说的,科学记数法,非常相似，唯一不同的是各部分均为有限位数，如下所示
emrmN
它的主要参数有 8个：
m ── 尾数,一般为纯小数，符合 规格化 原则（即最高位的绝对值不为 0），
用 原码 或 补码 表示；
e ── 阶码,整数，常用 移码 表示（见下文解释）；
rm ── 尾数的基值，简称 尾基,常见的有 2进制,8进制,16进制,10进制等，
选定以后不变；
re ── 阶码的基值，简称 阶基,目前都采用 2，也是选定以后不变；
p ── 尾数的位数，未将符号位计入；
q ── 阶码的位数，未将符号位计入。
mf ── 尾数的符号，表示数的正负，简称 数符 ；
ef ── 阶码的符号，表示阶码的正负，简称 阶符 。但对移码表示来说，这仅仅是额外的 1位 2进制数，不决定正负。
2001.9.1 计算机系统结构 24
移码（ P41）
移码是一种 2进制记数方法,它的 真值等于相同编码的无符号数加上一个指定的偏移量 d。 例如,同样是 2进制编码 000000 ～ 111111,看作 6位无符号数时的取值范围是 0
～ 63,而看作 6位移 -10码的取值范围就是 –10 ～ 53。 如下图所示 。
移码是一种有符号数,但它的最高位通常不决定数的正负,不应称为符号位 。 它的独特之处在于其最小取值的 2进制编码是全 0,这给机器零的判断和处理电路设计带来很大方便 。
十进制真值
63
无符号数
53
移 -10 码
0 111111
-10 二进制编码图 2,1 移码与无符号数的比较实例
2001.9.1 计算机系统结构 25
2.1.1.2 浮点数的机内格式（ P39）
一种浮点数中每个数据的尾基 rm,阶基 re都是相同的,在设计运算电路已经作为默认值来使用,各个具体数据在存储时只需要存入如下参数即可：
各字段位数,1 位 1 位 阶码 q 位 尾数 p 位浮点数字段,m
f
e
f
e
q - 1
… … e
0
,,m
1
… … m
p
对应位的权,r
e
q-1
… … r
e
0
r
m
-1
… … r
m
-p
隐含小数点图 2,2 浮点数的机内格式
2001.9.1 计算机系统结构 26
2.1.1.3 浮点数的性能（ P38）
浮点数的性能主要用 表数范围,表数精度 和 表数效率 来刻画,下面分别进行分析 。
(1) 表数范围 （ P39）
表数范围由这样一些参数构成,最小负数,最大负数,最小正数,最大正数,
最小绝对值 |N|min,最大绝对值 |N|max。 它们几何意义可以在数轴上表示,如下图 。
- ∞ 最小负数 最大负数 0 最小正数 最大正数 + ∞
图 2,3 数轴上的表数范围示意图图中阴影部分为浮点数的表数范围 。
根据浮点数的组成表达式可知,图 2.3中 4个边界值分别由尾数 m,阶码 e各自的边界值两两组合而成,如下所示 。
最大正数 ── 最大正尾数 /最大阶码；
最小正数 ── 最小正尾数 /最小阶码；
最大负数 ── 最大负尾数 /最小阶码；
最小负数 ── 最小负尾数 /最大阶码 。
2001.9.1 计算机系统结构 27
例 2.1
对规格化浮点数，尾数为原码，阶码为移 码，写出表数范围。（ P40）
11 )1( qeqe rmpmrmm rrNrr
qer?
解：由于原码在数轴的零点两边对称分布，即最大正数与最小负数的绝对值相等、最小正数与最大负数的绝对值相等，所以可以用最小、最大绝对值来描述它的分布。
首先根据图 2.2和式 2.1以及移码的基本定义，可以确定绝对值的极值表达式：
。，，又；，，
dr
m
p
m
q
e
p
m
d
mmm
q
errNdrerm
rrNderm
12
m a xm a xm a x
1
m i nm i n
1
m i n
)1(12)1(?
写在一起就是：
drmpmdmm qerrNrr 121 )1(
再用阶码的偏移量代换式中的 -d得：
2001.9.1 计算机系统结构 28
可以代入具体数字来帮助理解：
，如下图所示。，，
，于是有：按此题约定，
。，，，设
3101
m i n
3
m i n
1
m i n
3
1010 1010
10
310410
Ndem
d
qrpr em
，如下图所示。
，，
1104
m a x
3333
m a x
4
m a x
310)101(
1101011021102)101(
N
dem
1 位 1 位 阶码 3 位 尾数 4 位
x 0 0 0 0,,1 0 0 0
1 位 1 位 阶码 3 位 尾数 4 位
x 1 9 9 9,,9 9 9 9
2001.9.1 计算机系统结构 29
(2) 表数精度（ P42）
数轴
N
k
真实值 x N
k + 1
图 2,4 最大绝对误差示意图
e
m
p
m
e
mkkkk rrrmmNN
2
1)(
2
1)(
2
1
11m a x?
表数精度用最大表数误差表示 （ 指相对误差 ） ；
最大绝对误差 是真实值与可表示值之间的可能最大距离,也就是相邻两个可表示值间距的 1/2,如图 2.4所示
。 根据浮点数的组成式有其定义：
显然它随着阶码 e增大而增大,不是一个定数 。
2001.9.1 计算机系统结构 30
最大相对误差 与阶码 e无关，但与尾数 m的值有关。它的定义是
p
me
m
e
m
p
m
r
mrm
rr
N
1
2
12
1
m a x
m a x
上式中,当分母 |m|取最小值时分式值达到最大 。
。限为，所以最大相对误差上由于 21 )1(m a x01 pmmm rrmr?
2001.9.1 计算机系统结构 31
(3) 表数效率（ P45）
定义,
mm
m
q
e
p
m
q
e
p
mm
m rr
r
rr
rrrr 111
22
12)1(2)( 1
可以生成的浮点数个数其中规格化浮点数个数?
此式说明效率之所以低于 100%,是因为规格化的尾数最高位 m1只能有
rm-1种取值的缘故 。 可以看出,的极小值与极大值分别是
%100)(lim%501 12)2( mr r
m
,
[隐藏位技术 ]是一种提高表数效率的方法，但仅适用于 rm=2的情况：
尾数最高位 m1 在二进制条件下只有 0和 1两种可能，按照规格化要求，
m1 可由其它位推出，。,隐藏,了 m1之后，尾数只存储后面 p-1位，
它们中的任一位都有 rm种取值，所以表数效率 η =100%。
2001.9.1 计算机系统结构 32
2.3 指令格式的优化（ P90）
2.3.2 操作码优化目前常用的编码方法有 3种,定长编码,Huffman编码,扩展编码 。
2.3.2.1 定长编码 就是所有指令使用相同的代码位数，其最小码长等于
nL o glL i 2
式中 是平均码长,是第 i种指令的码长,n是指令总数。
例 2.2
已知 n = 15,求定长编码的最小平均码长。
解：
L il
4152 L o gL
2001.9.1 计算机系统结构 33
2.2.1.1 Huffman压缩编码（ P91）
(1)Huffman压缩概念 （ 最佳编码定理 ）,当用 n个长度不等的代码分别代表 n种发生概率不等的事件时,按照短代码给高概率事件,把长代码给低概率事件的原则分配,可使平均码长达到最低 。
(2) Huffman编码方法这种编码方法由两个过程组成 。
频度合并,将全部 n个事件 （ 在此即为 n条指令 ） 的频度值排序,选取其中最小的 2个频度合并,然后将剩下的 n-1个频度再次排序,再合并最小的 2个频度,如此重复,直至剩下 1个频度为止 。 记录所有的合并关系,形成一棵二叉树 ── Huffman树,所有原始频度值充当树叶,而最后剩下的总频度 1为树根；
码元分配,从树根开始,对每个中间结点的左右 2个分支边各赋予一位代码,0” 和,1” （,0” 在哪一侧不限 ） 。 读出从根结点到任一片树叶的路径上依次出现的代码位就排成了这个事件 （ 即指令 ） 的完整编码 。 由于频度高的事件较晚被合并,它的编码位数也就较少,符合 Huffman压缩原则 。
上面所说的 频度值 就是各事件实际出现次数的百分比,它是理论出现 概率的近似值 。
2001.9.1 计算机系统结构 34
(3) 编码方法性能指标（ P91-P93）
信息量,根据信息论的基本知识，在 n种可能发生的事件集合中，报告第 i
种事件发生的消息中包含的信息量为
ia
i
ai PPI lo g)
1(lo g
其中 Pi是第 i种事件发生的先验概率,a是编码基值 。 信息量的单位是表示位数 （ 最少所需位数 ） 。
这个定义式表明事件的发生概率越低，关于它的消息中的信息量越大
。
熵 （ entropy） ── 平均信息量,一个消息源对 n种事件发布的消息的信息量平均值,记为
n
i
iai
n
i
ii PPIPH
11
)(l o g)(
2001.9.1 计算机系统结构 35
平均码长,各事件编码长度的数学期望。
n
i
ii lPL
1
)(
信息冗余量,它表明消息编码中,无用成分,所占的百分比。
%100 L HLR
从减少存储与传输量的角度看,编码方法的平均码长越短越好 。 但是平均码长不可能无限制缩短,它的下限就是熵 （ 即 R=0时 ） 。 如果短于熵就一定会丢失有用信息 （ 即混淆不同指令 ）,这是不允许的 。
2001.9.1 计算机系统结构 36
2.2.1.2 扩展编码方法（ 等长扩展法,P93）
用码长表示：例如 4-8-12法 。这并不能说明具体编码方法，例如下面两种编码方法都是 4-8-12法。
用码点数表示：例如 15/15/15法,8/64/512法
– 15/15/15法,每一种码长都有 4位可编码位（前头可以有相同的扩展标识前缀），可产生 16个码点（即编码组合），但是至多只能使用其中 15个来表示事件，留下 1个或多个码点组合作为更长代码的扩展标识前缀。已经用来表示事件的码点组合不能再作为其它更长代码的前导部分，否则接收者会混淆。
这就是“非前缀原则”。
– 8/64/512法,每一种码长按 4位分段，每一段中至少要留下 1
位或多位作为扩展标识。各段剩下的可编码位一起编码，所产生的码点用来对应被编码事件。每一段中的标识位指出后面还有没有后续段。
2001.9.1 计算机系统结构 37
例 2.3
已知频度序列为 0.1,0.1,0.15,0.15,0.2,0.3，求 Huffman编码、等长扩展 3/3/3码、定长编码、三者的平均码长、信息冗余量以及熵。
解：
熵 H=
– (2× 0.1× log20.1+2× 0.15× log20.15+0.2× log20.2+0.3× log20.3)
≈2.47
根据 Huffman编码方法作 Huffman树如图 2.5所示，三种编码方法的结果列于表 2.1中。
1,0
0 1
0.4 0.6
0 1 0 1
0.2 0.3
0 1 0 1
0.1 0.1 0.15 0.15 0.2 0.3
图 2.5 H uffm a n 树
2001.9.1 计算机系统结构 38
表 2.1 Huffman编码、等长扩展 3/3/3码及定长编码指令 I
1
I
2
I
3
I
4
I
5
I
6
频度 0.1 0.1 0.15 0.15 0.2 0.3
000 001 100 101 01 11Huffman 码平均码长 L =2.5,信息冗余量 R ≈ 1.2%
1110 1101 1100 10 01 003/3/3 码平均码长 L =2.7,信息冗余量 R ≈ 7.5%
000 001 010 011 100 101定长编码平均码长 L =3.0,信息冗余量 R ≈ 17.7%
2001.9.1 计算机系统结构 39
2.2.2 操作数优化 ─── 寻址方式比较（ P95）
指令中操作数占用的位数由操作数的个数与寻址方式决定 。
按操作数的个数划分,有零操作数指令,一操作数指令,二操作数指令,三操作数指令共四种形式 。 应该按机器用途来选择 （ P99，
表 2.20） 。
缩短操作数长度的常用方法是 间址 和 变址 （ P99页末 ） 。
2001.9.1 计算机系统结构 40
本章主要内容有 数据表示 和 操作码优化 两个部分。具体细节如下：
(1) 浮点数的 表数范围 （在数轴上的 4个端点）,表数精度?,表数效率?；
(2) Huffman编码方法；
(3) 等长扩展编码方法（ 15/15/15法,8/64/512法 ）；
(4) 编码方法性能指标（ 熵 H,平均码长 L,信息冗余量 R）。
习题,P124,题 3（忽略 P124倒 1行 ~ P125第 8行文字），题 13。
本章小结
2001.9.1 计算机系统结构 41
第三章 存储系统（ P130）
长期存在的问题：在合理的总价格限制下，单纯性主存设备的速度跟不上 CPU的发展，容量不能满足软件尺寸扩大。
本章学习两种提高主存系统性能 /价格比的结构化方法,并行存储器 与 存储层次技术 。后者为主。
2001.9.1 计算机系统结构 42
3.1 并行存储器（ P136）
并行存储器技术可以提高主存系统的整体等效速度,实际应用中,
常将它与存储层次技术组合使用,可以互为补充,获得很高的性能 。
并行存储器技术的基本思想是 用多个独立的存储部件组成主存系统,让它们并行工作,在一个存储周期内可以访问到多个数据,从而实现较高的存取流量 。
并行存储器包括多种类型,我们仅介绍提高访问速度效果最显著的 低位交叉访问 这一种 。
2001.9.1 计算机系统结构 43
低位交叉访问并行存储器的结构：
它由 n个存储体组成（一般 n为 2的整次幂），每个体均有独立的地址译码器和数据缓冲器，以主存地址低位字段（ 最低的 log2n位 ）作为 体选译码信号,而剩下的高位字段则是 体内地址 。如图所示（设 n = 4）。
地址总线体 0 体 1 体 2 体 3
地址译码器 地址译码器 地址译码器 地址译码器
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
数据缓冲器 数据缓冲器 数据缓冲器 数据缓冲器数据总线
2001.9.1 计算机系统结构 44
主存地址与结构参数的换算（ P139）：
nAk
n
Aj
kjnA
m o d
，求结构参数：
求主存地址：
其中,n ── 存储体个数,A ── 主存地址,
j ── 体内地址,k ── 体序号 （ k = 0,1,2,…,n-1 ）
例 3.1
已知 n = 4,问主存地址 13是在几号体的几号单元？
解：
由于 n = 4,体选译码信号使用主存地址的最低 log2n = 2位,所以地址 13（ 其二进制为 1101B） 对应的体号 k = 1（ 即 01B）,体内地址 j = 3（
即 11B）,也就是说,地址 13位于 1号体的 3号单元 （ 参看前一页插图 ） 。
根据上式,所有 k值 （ 即体号 ） 相同的地址之间均相差 n的整倍数
,称之为,模 n同余,。
2001.9.1 计算机系统结构 45
低位交叉访问并行存储器的加速机理：
我们衡量存储器件速度的常用指标是存储周期 Tm,它是同一存储单元连续两次启动的最小时间间隔,数值越小表明存储器件速度越快 。
传统存储系统只有一套地址译码器和数据缓冲器,所以各单元必须串行工作
,也就是说每个 Tm周期内至多只能完成一次访问 。
由多个存储体构成的并行存储器中,各个存储体都有独立的地址译码器和数据缓冲器,它们可以并行工作,使得一个 Tm周期内可完成多次访问,相当于加速了多倍 。 最好情况下一个 Tm周期内可完成 n次访问 。
当前 Tm周期中只要发现有一个新的访问地址与前面地址属于同一个存储体,
该地址及其后面的地址就会被阻塞 （ 称为访存冲突 ）,留到下一个 Tm周期访问 。
机器地址序列常常具有顺序性,按照低位交叉的规律分配地址可使相继出现的地址落在相同存储体的概率降到最低 （ 参见上图 ） 。
考虑到地址总线与数据总线的拥挤问题,一个 Tm周期里发送的多个访问请求最好彼此错开 Tm/n时间,如 P140图 3.11所示,否则实现的复杂度会增加 。
2001.9.1 计算机系统结构 46
K
g=0
10.0
g=0.2
4.46
3.68
2.00 g=0.5
1.00 g=1
0 1 10 n
计算平均加速倍数（ P141）：
1.只考虑取指地址序列（假设地址顺序递增，直至出现一条转移指令）：
倒数第一行）（ 141 )1(1 Pg gK
n
其中 g是指令序列中出现转移指令的概率。此公式在右图中用 绿线 表示。
2.只考虑取数地址序列（假设地址完全随机）
28.02/nK
此公式在右图中用 红线 表示。
2001.9.1 计算机系统结构 47
例题,P203,题 5
。也对（文字理解差异）取。向下取整，得解出，得依题意有，其中，解：已知
161 15
28.15
9.0lg
2.0lg
2.09.0
2.0
)1(1
2.0
)1(1
1.0
)1(1
1
1
n
n
g
g
K
g
g
K
g
g
g
K
n
n
n
n
n
n
n
2001.9.1 计算机系统结构 48
3.2 存储层次原理及性能指标
3.2.1 基本原理
定义,（ 参见 P131第二段 ）
由 2种或多种存储部件构成的复合存储系统,通过内部管理机构的 自动更换机制,能够不断将大容量低速存储部件中的活跃内容复制到小容量高速存储部件中 （ 后者作为前者的 局部副本 ） 。
它既能满足 CPU的快速存取需要,又有很大的存储容量,平均单位价格也很低,等效于同时满足 3
方面要求的理想单一存储部件 。
依据：程序访问的局部化原理 （ 时间局部化,空间局部化 ） 。
模型：如右图所示,存储层次由 n层组成,
满足 3个不等式,Ti<Ti+1,Si<Si+1,ci>ci+1。
CPU
M1
M2
Mn
图 3.3 存储层次模型
2001.9.1 计算机系统结构 49
3.2.2 性能指标（ P132-P134）
(1) 容量,S=S2 （ 理论上 ）
(2) 单价,（ 美分 /bit）
2
0
2
1
21
2
1
21
2211
2
1
lim
1
cc
S
S
cc
S
S
SS
ScSc
c
S
S
它的最小值是
2001.9.1 计算机系统结构 50
(3) 速度：表现访问速度的参数很多
命中率：反映被访问数据事先已在 M1的发生概率
等效访问时间：命中时的访问时间为 T1,不命中时的访问时间为 T2,等效访问时间则是它们的概率均值
10
21
1
HNN
NH,
21 )1( THTHT
1%1 0 0lim TTH
2001.9.1 计算机系统结构 51
访问效率：这是一个相对值，便于不同系统之间的比较。
。, ereH
e
r = 1
1.0
r = 2
0.5
r = 10
0.1
0.0
0 1 H
H 和 r 对 e 的作用访问效率 e受 H和 r的影响（参见右图）：
是邻级速度比）。（，其中 rTTre 110
1
2
Hrr
rHH
THTH
T
T
T
e
)1(
1
)1(
1
)1(
21
1
1
2001.9.1 计算机系统结构 52
Cache预取技术对命中率的提高作用（ P134）：
这里所说的,预取,技术,并不是根据对程序执行的未来趋势进行猜测以提前调入数据,而仅仅是在发生不命中情况时把调入 1个数据字改为调入 1个数据块的策略 。 根据程序的局部化原理,在当前使用数据周围的其它数据未来被使用的几率大于远处数据,所以该数据块中被提前调入的邻近数据很可能成为未来的命中点,从而提高命中率
。
采用这种预取技术后新的命中率为
n
nHH 1'
其中,H ── 原命中率 （ 即按照不命中时取入 1字的策略 ） ；
H’ ── 新命中率 （ 即按照不命中时取入 1块的策略 ） ；
n ── 每块数据平均被访问次数 。
2001.9.1 计算机系统结构 53
按照定义，原不命中率,新不命中率
，并且有 。
由于预取使得每块数据中的不命中次数由 n次降低到 1次，所以有
。此式可改写为,
整理得 。
H’的推导：
21
21
NN
NH
''
''1
21
2
NN
NH
'' 2121 NNNN
22
1' N
nN? '1
1
'2
2
H
H
N
Nn
n
nHH 1'
2001.9.1 计算机系统结构 54
加速比（ P193）
Cache-主存层次的主要作用是提高访问速度，系统的等效速度应高于主存（即 M2） 的原有速度，两个速度之比称为加速比。
rHH
THTH
T
T
TM
M
S
p
/)1(
1
)1(
21
2
22
2
等效时间时间速度等效速度
2001.9.1 计算机系统结构 55
M1 103B T1=1us 103B
M2 106B TB2=10us
M3 109B TB3=100us 109B
(a) (b)
例 3.2
有一个 109字节的程序被装入右图所示的 M3准备运行。
假定指令字长 =1字节，程序中无转移指令和内存读 /写指令。
(1)按图 (a)求 T和 e；
增加中间层对 e的影响
(2)按图 (b)推导三层体系的 T公式；
(3)按图 (b)求 T和 e；
(4)比较 (1)(3)结果，有何结论？
2001.9.1 计算机系统结构 56
解：
32122111
3222111
32222
2111
1
1
3
23
33
3
3111
3
1
3
3
1
)1()1()1(
)1()1(
2
)1(
)1( )2(
%91
%)101(
10
11010
100
10
1
1
10
110
)1(
10
1
1
10
110
)1(
BB
BB
BB
B
THHTHHTH
THTHHTHT
THTHT
THTHT
T
T
e
Tsss
THTHT
HH
式有由上面
，
2001.9.1 计算机系统结构 57
效率提高。层间速度差减少，访问结论：插入中间层后,)4(
%99
%)11(
10
1010101010
100
10
1
10
10
110
10
1
1
10
110
10
1
1,
10
110
)3(
1
16
2346
33
3
33
3
323
3
2
T
T
e
Ts
sssT
HH
习题,P202,题 3。
2001.9.1 计算机系统结构 58
存储层次的管理方式 (P148)
根据程序的局部化性质，存储层次机构对用户文件的管理应该划分成较小的基本调度单位来进行。依划分标准不同，存在 3种存储层次管理方式。
(1)段式管理 (P148)。段是程序中的一个逻辑单位，可以是一个程序模块，
或者是一个数据结构。段的长度不一，但段内所有数据的信息属性一般是相同的，便于统一进行信息保护。
每段使用独立的逻辑地址空间,即都从 0开始计算地址 。
段式管理方法的主要缺点是各段长短不一,调进调出之后容易形成大量不规则的零碎空间 。
段式管理方法的虚实变换算法是查段表 (P150)。
2001.9.1 计算机系统结构 59
(2)页式管理 (P151)。页是系统规定的固定长度单位。按页划分用户文件可以避免上述零碎空间浪费。
我们把用户文件划分得到的一个长度单位称为,虚页,,因为它的页号是在虚地址空间中编排的；实地址空间按页的大小划分得到的一个长度单位称为,实页,。
页式管理方法的主要缺点是按固定长度分出来的同一页内常有不同属性的信息，不便于信息保护的实现。
页式管理方法的虚实变换算法是查页表 (P152)。
(3)段页式管理 (P153)。 它把上述两种管理方式结合起来,首先将整个文件分段,然后在各段内分页,所以有一个段表和若干个页表 。 其虚实变换算法是先查段表,查出该段的页表起始地址再查相应的页表 (P154)。
段页式管理的主要缺点是多查一次表,虚实变换费时较多,占用空间也较大 。
由于段页式管理方法的最小调度单位仍是页,或者说它是分段之后的分页管理,为了叙述简单,下面的分析还是以页式管理为模型 。
2001.9.1 计算机系统结构 60
3.3 地址映象与变换 (P174)
基本术语：
逻辑地址 （ 又称为 相对地址,虚地址 ） 是程序员在编写和编译一个程序模块时分配指令和数据的空间单位序号,总是从 0开始 （ 可以按字节编址,按 CPU
字编址等 ） 。 逻辑地址的取值范围称为 逻辑地址空间,虚空间 或 虚存 。
物理地址 （ 又称为 绝对地址,实地址 ） 是任一级存储器为全部存储单元分配的序号 。 物理地址的取值范围称为 物理地址空间,实空间 或 实存 。
从 M1到 Mn各层都有自己的物理地址空间,而对当前执行的程序模块来说,逻辑地址空间只有一个 。
地址映象 方式指的是虚页集合与实页集合的对应规则，或者说是约束关系。
地址变换 （又叫 虚实变换 ）指逻辑地址到物理地址的变换过程或者算法。
页失效 指当前被访问存储级中没有所需的信息，也就是不命中现象。
实页争用 又叫 实页冲突,指虚页调入时，根据地址映象方式划定的实空间范围内已没有空闲实页的状况。
2001.9.1 计算机系统结构 61
4种常见的地址映象方式
3.3.1 全相联 (P174)
全相联 就是无约束对应,或者说是一个完全关系,意思就是一个虚页可以调入任何一个实页 。 这种关系可用下页示意图 (a),(b)表示 。
全相联的虚实变换信息完全来自于变换表,查表过程如图 (c)所示 。
全相联映象方式使虚页调入有最大的选择范围,发生实页争用的可能性最小,调入 /调出的操作开销也最少,有利于命中率提高 。 但这种方式的页表占用空间和查表时间开销都比较大,也就是说实现成本比较高,在命中情况下花费在虚实变换上的时间也比较多 。
由于页表必须常驻在实存中,而主存 -辅存层次的实存 （ 即主存 ） 相对
Cache-主存层次的实存 （ 即 Cache存储器 ） 要低廉一些,所以全相联映象方式一般用于主存 -辅存层次 。
2001.9.1 计算机系统结构 62
全相联的地址映象方式与地址变换原理示意图 (a)(b)
虚存 实页 0 1 2 3
0 0 √ √ √ √
1 实存 1 √ √ √ √
2 · 0 2 √ √ √ √
3 · 1 虚 3 √ √ √ √
4 · 2 页 4 √ √ √ √
5 · 3 5 √ √ √ √
6 6 √ √ √ √
7 7 √ √ √ √
( a ) 虚页集合与实页集合的对应关系 ( b) 对应关系表 （ √ 为有关系）
2001.9.1 计算机系统结构 63
全相联的地址映象方式与地址变换原理示意图 (c)
虚地址 虚页号 P 页内偏移量 D
实地址 实页号 p 页内偏移量 d
实页号 装入位 修改位表项 0,,,
,,,,
表项 P p 1 0
,,,,
表项 7,,,
( c ) 通过 查表进行虚实变换
2001.9.1 计算机系统结构 64
3.3.2 直接相联 (P176)
直接相联 是一种最强的约束关系,它规定每个虚页只对应唯一的实页 。 为了便于虚实变换,用求模运算作为变换关系式：将虚页号对实页总数求模得到实页号 。 实现起来非常简单,因为在二进制中,任何数 X对 2的整次幂 n求模等价于截取 X的最低 log2n位,如下页示意图 (c)所示 。
例 3.3 已知虚页号 = 7,实页总数 = 4,用直接相联求实页号 。
解：
可用十进制形式求,7 mod 4 = 3；
也可用二进制形式求：由于 n = 4,所以 log2n = 2,取 7的二进制形式 111B
的最低 2位,得 11B,即 3。
直接相联映象方式不需要借助页表来进行虚实变换,显然大大节省了相应的空间与时间 （ 当然页表中的装入位和修改位还得保留 ）,但是由于每个虚页的选择范围太小,实页争用的发生频率较高,常出现明明实存有空闲空间却不得不调出一个现有虚页以腾出所在实页的情况,这使系统的命中率和运行效率大大下降 。
这种映象方式主要用于一些对实存价格非常敏感的 Cache-主存层次 。
2001.9.1 计算机系统结构 65
直接相联的地址映象方式与地址变换原理虚存 实页 0 1 2 3
0 0 √
1 · 实存 1 √
2 · 0 2 √
3 · 1 虚 3 √
4 · 2 页 4 √
5 · 3 5 √
6 · 6 √
7 7 √
( a ) 虚页集合与实页集合的对应关系 ( b) 对应关系表 （ √ 为有关系）
虚地址 虚页号 1 1 1 页内偏移量 D
实地址 实页号 1 1 页内偏移量 d
( c ) 通过 求模运算进行虚实变换示例
2001.9.1 计算机系统结构 66
3.3.3 组相联 (P178)
组相联映象方式是全相联与直接相联的一个折中方案,性能也是二者的折中 。 具体做法是先将实存分组,每组内有若干实页,然后将虚存空间也以同样大小分组 。 所有虚组按照直接相联方式映射到实组集合,对应的虚实组之间各页则用全相联映射,如下页示意图 (a),(b)所 示 （ 设实组数为 2） 。
由于包含了两层不同的映射关系,页表须按虚组划分成许多子表 。 在虚实变换时,首先根据虚页号所在的虚组号,通过求模运算确定实组号,再按虚组号在相应的子表内读出组内页号,拼接在一起就是实页号 。 简记为,组号计算,组内查表,。 如图 (c)所示 。
采用组相联映象方式时,每个虚页在对应实组范围内有若干映象实页可供选择,实页争用的发生频率比直接相联要低；另一方面,由于页表内原来存放的实页号改成存组内页号,省略了实组号字段,所以页表占用空间也减少了 。 当然这两方面优点是互相抵触的：组内页数越多,实存空间划分的组数就越少,实组号字段所占位数也少,这时改善实页争用现象的效果较好,而节省页表空间的效果较差,反之亦然 。 实际使用中可根据性能要求选取合适参数 。
这种映象方式性价比较好,在 Cache-主存层次中被普遍使用 。
2001.9.1 计算机系统结构 67
组相联的地址映象方式与地址变换原理 (a)(b)
虚存 实页 0 1 2 3
虚组 0 0 0 √ √
1 实存 1 √ √
虚组 1 2 · 0 实组 0 2 √ √
3 · 1 虚 3 √ √
虚组 2 4 · 2 实组 1 页 4 √ √
5 · 3 5 √ √
虚组 3 6 6 √ √
7 7 √ √
( a ) 虚页集合与实页集合的对应关系 ( b) 对应关系表 （ √ 为有关系）
2001.9.1 计算机系统结构 68
组相联的地址映象方式与地址变换原理 (c)
虚地址 虚组号 1 0 组内页号 1 页内偏移量 D
实地址 实组号 0 组内页号 0 页内偏移量 d
0 组子表 项 0,,,
项 1,,,
1 组子表 项 0,,,
项 1,,,
2 组子表 项 0,,,
项 1 0 装入位 1,
3 组子表 项 0,,,
项 1,,,
( c ) 求模运算与分组查表结合进行虚实变换示例
2001.9.1 计算机系统结构 69
3.3.4 段相联 (P184)
段相联映象方式也是全相联与直接相联的一个折中方案 。 它的分段方法与组相联相同,不同的是所有虚段按照全相联方式映射到实段集合,对应的虚实段之间各页则用直接相联映射 （ 因为虚实段大小相同,所以实际上是一一对应 ）,如下页示意图 (a),(b)所示 （ 设实段数为 2） 。
段相联的虚实变换与组相联类似,不过可以通过计算来确定的部分不是在段外,而是在段内,即页表内只储存各虚页对应的实段号,段内页号则从虚页号中简单直接复制,拼接在一起就是实页号,简记为,段号查表,段内复制,。 如图 (c)所示 。
段相联映象方式的虚实段内页号对应关系是固定的,每个虚页在调入时可以选择的只是实段号 。 由于虚实段大小相同,所以虚段号比实段号位数多,
也就意味着,多 → 少,的映射 （ 组相联是等量映射 ）,其实页争用的发生频率比组相联要高 。 在节省页表存储空间方面,性能与组相联差不多 。
2001.9.1 计算机系统结构 70
段相联的地址映象方式与地址变换原理 (a)(b)
虚存 实页 0 1 2 3
虚 段 0 0 0 √ √
1 实存 1 √ √
虚 段 1 2 0 实 段 0 2 √ √
3 · 1 虚 3 √ √
虚 段 2 4 · 2 实 段 1 页 4 √ √
5 3 5 √ √
虚 段 3 6 6 √ √
7 7 √ √
( a ) 虚页集合与实页集合的对应关系 ( b) 对应关系表 （ √ 为有关系）
2001.9.1 计算机系统结构 71
段相联的地址映象方式与地址变换原理 (c)
虚地址 虚 段 号 1 0 段 内页号 1 页内偏移量 D
实地址 实 段 号 0 段 内页号 1 页内偏移量 d
0 段 子表 项 0,,,
项 1,,,
1 段 子表 项 0,,,
项 1,,,
2 段 子表 项 0,,,
项 1 0 装入位 1,
3 段 子表 项 0,,,
项 1,,,
( c ) 查表求实段号进行虚实变换示例
2001.9.1 计算机系统结构 72
多用户虚地址格式在多用户或多进程并发环境下，由于机器中同时保存并交替运行多个程序模块，各模块中的相同虚页号会发生混淆。这时从 CPU发出的虚地址还需要在前面拼接上一个,当前用户号,字段，形成,多用户虚地址,,
如下图所示 (参见 P154)。
在虚实变换时，上面所说的各种查表操作之前还得先去查一个,段表基址寄存器组,或,页表基址寄存器组,的小表格 (P150,P152),确定现在该查哪一张段表或页表。这个小表格建立在 CPU里，读写时间很短。
当前用户号 虚段号 虚页号 页内偏移量
2001.9.1 计算机系统结构 73
3.4 替换算法 (P164)
上面所讲的地址映象方式是在虚页调入时的,选址,规则，而地址变换方法则是命中时获得实地址的手段。
不命中时需要增加的操作就是首先调出一页，调出之后再调入称为
,替换,。
替换算法要解决的是选择调出对象的问题。
替换算法的目的是在发生实页争用（即根据地址映象方式，将要调入的虚页被允许进入的所有实页均被其它虚页占用）时，选择将来不太可能使用或者使用最晚的虚页作为调出对象，以腾出一个实页来。
2001.9.1 计算机系统结构 74
3.4.1 几种常用的替换算法 (P164)
(1)随机算法 RAND ── 在比较范围内任取一页作为淘汰页；
(2)先进先出算法 FIFO ── 在比较范围内选取调入最早的一页作为淘汰页；
(3)最不经常使用算法 LFU ── 在比较范围内选取最近单位时间内使用次数最少的一页作为淘汰页；
(4)最不接近使用算法 LRU ── 在比较范围内选取最后一次使用离现在最久的一页作为淘汰页；
(5)最优替换算法 OPT ── 在比较范围内选取下一次使用时间离现在最久的一页作为淘汰页 。
2001.9.1 计算机系统结构 75
实例：实存状况图 (P166图 3.32)
例如 LRU 算法（其中 *号表示被选中的淘汰页）：
已访问次数 t 0 1 2 3 4 5 6 7 8 9 10
被访问虚页号 无 1 2 1 5 4 1 3 4 2 4
命中总次数
0 空 1 1 1 1 1 * 1 1 1 * 2 2
1 空 空 2 2 2 * 4 4 4 * 4 4 4
实存空间使用情况 （实页号为 0,1,2 ） 2 空 空 空 空 5 5 5 * 3 3 3 * 3 *
操作名称 初态 ( 空 ) 调入 调入 命中 调入 替换 命中 替换 命中 替换 命中
4 次被访问实页号 0 1 0 2 1 0 2 1 0 1
2001.9.1 计算机系统结构 76
这是对某些替换算法的统称 。 如果某些算法在同一地址流同一时刻的小容量分区情况下的保留页面集合必是大容量分区情况下的保留页面集合的子集
（ 当容量超过虚页总数时,保留页面集合相同 ）,则小容量下的命中点到大容量情况下仍然是命中点,并且随着容量加大,还可能会有新的命中点产生
。 具有这一特性的一类替换算法中成为,堆栈型算法,。
例如,P166图 3.32中,对 LRU算法,如果实页数增加到 4,则 t = 5时为了调入虚页 4就不必替换掉虚页 2,而是将虚页 1,2,4,5都留在实存,这时大容量分区情况下的保留页面集合 S2 = {1,2,4,5},同一时刻的小容量分区情况下的保留页面集合 S1 = {1,4,5}。 显然有 S1 S2。
P167第 4～ 8行是堆栈型算法的数学定义 。
堆栈型替换算法的主要性质就是 命中率 H随着实页分区容量 n的上升而单调上升 （ 不减性 ） 。
可以证明,LFU,LRU,OPT等算法都是堆栈型算法,而 RAND和 FIFO算法不是堆栈型算法 。 P168的图 3.34是一个实例,当实页数从 3增加到 4时,
FIFO的命中率反倒从 3降到 2。 具体观察,比如 t = 7时,S1 = {1,2,5},S2 =
{2,3,4,5},不满足子集关系 。 所以 FIFO不能保证当实页数增加时,原来的命中点不丢 。
3.4.2 堆栈型替换算法 (P166)
2001.9.1 计算机系统结构 77
实例：堆栈模拟图研究堆栈型替换算法的性质，一方面可以设计优化的操作系统算法（例如
P167倒数第 3行的 PFF法），另一方面也可推导出一些分析工具，例如“堆栈模拟法”。
堆栈模拟图可以通过一次作图,描述同一地址流在各种实存分区容量下的命中情况 。
例 3.4
t 1 2 3 4 5 6 7 8 9 10 11 12
P 2 3 2 1 5 2 4 5 3 2 5 2
s
t
( 1 ) 2 3 2 1 5 2 4 5 3 2 5 2
s
t
( 2 ) 2 3 2 1 5 2 4 5 3 2 5
s
t
( 3 ) 3 2 1 5 2 4 5 3 3
s
t
( 4 ) 3 3 1 1 2 4 4 4
s
t
( 5 ) 3 3 1 1 1 1
s
t
( 6 )
命中次数
n= 1 0
n= 2 * * 2
n= 3 * * * * * 5
n= 4 * * * * * * 6
n= 5 * * * * * * * 7
2001.9.1 计算机系统结构 78
3.5 虚拟存储器与 Cache的特点 (P146,P172)
虚拟存储器与 Cache的主要区别
(P173表 3.4)
Cache的主要组成与工作流程
(P173图 3.38)
2001.9.1 计算机系统结构 79
本章小结
(1) 并行存储系统原理；
(2) 存储层次的原理及 5项性能指标；
(3) 存储层次的 3种管理方式；
(4) 4种地址映象与地址变换方式；
(5) 5种替换算法；
(6) 堆栈型替换算法；
(7) 主存 -辅存层次与 Cache-主存层次的特点；
(8) 实存状况图、堆栈模拟图（ 2种分析工具）。
习题,P206,题 15，题 19。
2001.9.1 计算机系统结构 80
第四章 输入输出系统（ P208）
输入输出系统 是计算机系统中实现各种输入输出任务的资源总称 。 它包括各种输入输出设备,相关的管理软件等等 。 由于输入输出设备的特殊工作性质使其数据吞吐率通常远低于主机,设计输入输出系统就是要建立数据交换的最佳方案,使双方都能高效率地工作 。
本章重点是 中断优先级管理,通道流量设计 。
2001.9.1 计算机系统结构 81
4.1 基本输入输出方式 (P212)
4.1.1 程序控制 I/O方式
4.1.2 中断 I/O方式
4.1.3 DMA方式
4.1.4 通道方式
4.1.5 I/O处理机 方式
2001.9.1 计算机系统结构 82
4.2 中断优先级管理 (P219)
中断是为实时任务优先获得处理机资源而采用的一种调度技术,当系统中存在多个中断源时必须根据实时性强弱设定优先顺序,这也被称为 中断的分级 。 为了兼顾中断响应的时效与配置的灵活,通常采用两套机制结合组成中断优先序管理体系 。
(1)硬件响应优先序,未被屏蔽的几个中断源同时提出申请时,CPU选择服务对象的顺序 。 它由硬件电路实现,用户不能修改 。 如 P226图 4.11所示
。
(2)软件服务优先序,在各中断服务程序开头,用软件设置自己的中断屏蔽字 （ 在主程序中也设置 ） 。 以此改变实际服务顺序 (P230)。
例如某个硬件响应优先级高的中断源,其中断服务程序执行中屏蔽了自身,而开放了某个硬件响应优先级比它低的中断源,后者就可以在前者刚开放中断时就打断它,从而在实际上先得到服务 。
中断服务过程示意图如 P231图 4.14所示 。
由于常规用户主程序对处理机的需求紧迫性最低,所以它的中断屏蔽字是,全部开放,。
(3)实例分析,屏蔽字表,中断服务过程图 。
例 4.1（ P230倒数第 8行开始 ）
2001.9.1 计算机系统结构 83
4.3 通道处理机 (P233)
(1)定义：
通道处理机 （简称 "通道 "）是隶属于主处理机的输入输出专用协处理机。
(2)特点：
有一套输入输出功能很强的专用指令系统；
与主处理机共享主存，存放相应的程序和数据；
一个通道可以连接多台外部设备；
主处理机可用 "启动 I/O"指令 来启动一个通道；
当通道访存与主处理机冲突时，存控部件赋予通道较高的优先权；
通道程序执行完毕自动转入休眠状态，同时向主处理机发出一个特定的中断申请，通知该事件。
(3)地位：
从属于主处理机。
2001.9.1 计算机系统结构 84
字节多路通道,以字节为单位交叉为多台设备传输。子通道的概念。
选择通道,完成一台设备的全部传输再去为另一台设备服务。
数组多路通道,以数组为单位交叉为多台设备传输。
(5)通道传输过程的时间分配 (P241,其中 P是设备台数 )：
字节多路通道：,其中 n是单台设备的数据传输量；
选择通道：
数组多路通道：,其中 k是块尺寸,。
(4)分类 (P238)：
nPTTT DSB Y T E )(
nPTnTT DSS E L E C T )(
nPTkTT DSB L O C K )( nk?
2001.9.1 计算机系统结构 85
(6)通道流量分析 (P243)：
通道最大能力流量,
D
S
B L O C KM A X
D
S
S E L E C TM A X
DS
B Y T EM A X
T
k
T
f
T
n
T
f
TT
f
1
1
1
.
.
.
2001.9.1 计算机系统结构 86
通道实际最大负荷流量,
i
P
i
B L O C K
i
P
i
S E L E C T
P
i
iB Y T E
ff
ff
ff
1
1
1
m a x
m a x
通道正常工作条件,
jM A Xj ff,?
2001.9.1 计算机系统结构 87
实例分析：
通道时间关系图
例 4.2（ P243倒数第 2行开始）
）解：（见教材
，并作时间图。。求通道实际流量秒
，
秒
，
秒
，
秒
，
秒已知：
244243
1075
1
1050
1
1030
1
1030
1
1010
1
6564
636261
PP
fff
fff
B Y T E
2001.9.1 计算机系统结构 88
4.4 I/O处理机 (P245)
定义,有独立内存和操作系统的 I/O专用计算机。
2001.9.1 计算机系统结构 89
本章小结
(1) 5种 I/O方式；
(2) 中断优先级管理（屏蔽字表、中断服务过程图）；
(3) 3种通道处理机的特点；
(4) 3种 通道最大能力流量 ；
(5) 3种 通道实际最大负荷流量 ；
(6) 通道正常工作条件 ；
(7) 通道时间关系图（字节多路通道） ；
习题,P250,题 5,题 8。
2001.9.1 计算机系统结构 90
第五章 标量流水线技术 (P253)
本章学习标量计算机上使用的流水加速技术。主要内容有 流水技术的分类,流水线性能指标计算,非线性流水线的调度算法 。
5.1 基本名词术语 (P253)
标量处理机,超标量处理机,标量处理机指只能进行标量运算的处理机，
超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；
指令级并行技术,指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；
流水线处理机,超流水线处理机,流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理机；
超长指令字技术 VLIW,指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技术。
2001.9.1 计算机系统结构 91
5.2 流水处理与逻辑相关的概念流水线是一种通过改进ＣＰＵ结构来提高程序解释速度的方法。
5.2.1 流水线工作原理处理机解释程序的方式有 顺序方式,重叠方式,流水方式 等。
顺序方式 是解释完一条指令再开始解释下一条 (P254)；
流水方式 是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目 (P277)；
重叠方式 是一种简单的流水方式，它把指令分成 2个子过程，每条指令只与下一条指令相重叠 (P255)。
2001.9.1 计算机系统结构 92
流水线结构图 (P278)
Δ t
1
Δ t
2
Δ t
3
Δ t
4
入口 Ⅰ Ⅱ Ⅲ Ⅳ 出口图 5.1 流水线结构图
流水线工作时空图 (P278—P279)
2001.9.1 计算机系统结构 93
空间 （段号）
Ⅳ 1 2 3 4
Ⅲ 1 2 3 4
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
16 时间 （拍）
( a ) 顺序方式空间 （段号）
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
10 时间 （拍）
( b) 重叠方式空间 （段号）
Ⅳ 1 2 3 4
Ⅲ 1 2 3 4
Ⅱ 1 2 3 4
Ⅰ 1 2 3 4
7 时间 （拍）
Δ t ( c ) 流水方式图 3.2 C P U 工作时空图
2001.9.1 计算机系统结构 94
5.2.2 逻辑相关 (P263-276)
相关的定义,(P263倒数第 4段 )
一条指令必须等待前一条指令解释完成才能开始解释。
相关的分类及其对策
1,全局性相关 /局部性相关 (P312,P269/P263,P303)；
2,指令相关 /数相关 (P264/P263)；
3,主存数相关 /寄存器数相关 (P265/P266)；
4,数值相关 /变址值相关 (P266/P268)。
2001.9.1 计算机系统结构 95
5.3 流水技术的分类 (P280)
线性 /非线性 (P280)
部件级 /处理机级 /处理机间级（宏流水线） (P281)
单功能 /多功能 (P282
静态 /动态 (P283)
标量 /向量 (P285)
同步 /异步 (P285)
顺序 /乱序 (P285,P304)
2001.9.1 计算机系统结构 96
5.4.1 吞吐率 TP(P285)
吞吐率（ TP ─── ThroughPut） 指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。
，其中 k表示流水线划分的段数。
当满足 条件时，有 。
5.4 线性流水线性能分析 (P285)
kT
nTP?
tti tknT k )1(
2001.9.1 计算机系统结构 97
其中
5.4.2 加速比 (P288)
k
o
T
TS?
k
i
io tnT
1
2001.9.1 计算机系统结构 98
段效率：,各段平均效率：
其中 表示第 i段设备量占整条流水线全部设备量的百分比 。
当满足 条件时,有：
5.4.3 效率（设备利用率,P289）
k
i
i T
tnE
k
i
ii EE
1
)(?
ktt ii
1和
k
i
k
i k
o
i
k
i Tk
Tt
Tk
nE
kE 1 1)(
1
i?
2001.9.1 计算机系统结构 99
例 5.1(P292)
分析：已知下列表达式,有相关,单功能,k = 4,n = 7。 要求最少相关,
用,二叉树算法,以减少相关 。
Z = A + B + C + D + E + F + G + H
① ② ③ ④
⑤ ⑥
⑦
时空图和算式见 P293。
5.4.4 实例分析 (P292)
2001.9.1 计算机系统结构 100
例 5.2(P293)
分析：已知下列表达式，二功能，有切换，有相关,k = 8,n = 7。 要求用最少切换、最少相关算法。
Z = A? B + C? D + E? F + G? H
乘法,① ② ③ ④
加法,⑤ ⑥
加法,⑦
时空图和算式见 P293 - P294。
2001.9.1 计算机系统结构 101
(1)瓶颈,瓶颈就是 Δti最大的段，它使流水线“流速”减慢（ P287图 5.37）。
S1 S2 S3 S4
Δt 3Δt Δt Δt
(2)方法 1,再细分 ─── 将瓶颈设备再细分为下一级流水线（ P287图 5.38）。
S1 S2a S2b S2c S3 S4
Δt Δt Δt Δt Δt Δt
(3)方法 2,并行设置 ─── 将瓶颈设备重复设置多套，轮番接受任务（ P288图
5.39）。 S2a
3Δt
S1 S2b S3 S4
Δt 3Δt Δt Δt
S2c
注意两种方法的时空图不同。 3Δt
5.4.5,瓶颈”问题及其解决方法 (P286-P288)
2001.9.1 计算机系统结构 102
5.5 非线性流水线调度技术 (P294)
调度问题的提出,
一个任务在通过非线性流水线时对有些功能段要 通过多次 （非线性定义），所以容易与紧跟而来的后继任务发生 设备争用 。
调度机构的作用就是 合理安排 前后任务进入流水线的 相差时间,既要避免争用,又要使 相差时间尽可能少,以提高吞吐率。
2001.9.1 计算机系统结构 103
1.给出 预约表 R（ P295图 5.44）
(a)连接图；
(b)预约表 。
2.作 禁止表 F（ P297倒数第 2段）
F = { 3,4,6 }
3.作 原始 冲突向量 C（ P298倒数第 3段）
C = (101100),（ 电路见下页）
4.作 状态转移图 （ P299图 5.51）
从“根结点”开始画；每个结点中有几个,0”就要发出几条边，还有一条带“＊”号的边，它表示,≥”。
5.作 平均延迟拍数表 （ P300表 5.1）
取 平均延迟拍数最少的方案作为最优方案 （用计数器加译码电路实现） 。
5.5.1 不改变流水线结构的调度方法 (P295)
时间段
1 2 3 4 5 6 7
S1 1 1 1
S2 1 1
S3 1 1
S4 1
时间段
1 2 3 4 5 6 7
S1 2 2 2
S2 2 2
S3 2 2
S4 2
2001.9.1 计算机系统结构 104
动态冲突向量 （初值 000000）
0 010110 右移出 0
“或”运算器 0接通
1断开
101100
原始冲突向量共同时钟流水线 任务排队使用 冲突向量 C实现调度的原理图
2001.9.1 计算机系统结构 105
5.5.2 改变流水线结构的优化调度方法 ── 预留算法
(P296)
目的：等间隔的最小延迟调度方案
方法：插入延迟器件第 1步，确定 相邻任务间隔拍数,因为最小间隔拍数是一行内,×,的最大数目（第 11行）,取最小间隔拍数。
第 2步，确定插入延迟器件位置的原则（ P302第 2行 ）,从第一个,×,开始，凡是相距 最小间隔 拍数整倍数位置的,×,都要向后推迟。
实例（ P301倒数第 7行）：
1.确定间隔拍数（最多 3个,×,，所以是 3拍 ）；
2.插入延迟器件（使各行,×,的间距不为 3的倍数 ）；
3.修改预约表（ P302图 5.53(a)）；
4.写调度方案（ 3）。
（示意图见下页）
2001.9.1 计算机系统结构 106
a,未插入延迟段 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 1,2 1,2,3 2,3,4
S2 1 1,2 2,3 3,4
S3 1 2 1 3 2 4 3
S4 1 2 3 4
b,仅插入 1 个延迟段 D1 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 2 1 3 1,2 4 2,3
S2 1 2 1 3 2 4 3
S3 1 2 1 3 2 4
S4 1 2 3 4
D1 1 2 3
c,插入 2 个延迟段 D1,D2 （每隔 3 拍启动一个任务）
时间功能段
1 2 3 4
1
5
2
6
3
7
4
1
8
5
2
9
6
3
10
7
4
11
8
5
12
9
6
S1 1 2 1 3 2 1 4 3 2
S2 1 2 1 3 2 4 3
S3 1 2 1 3 2 4
S4 1 2 3 4
D1 1 2 3
D2 1 2
2001.9.1 计算机系统结构 107
5.6 超标量 /超流水技术 (P320)
超标量技术：一个时钟节拍内 同时 发射多条指令（ P324倒 2行）；
时空图见 P323图 5.71（ b）。
指令
9 9 9 9
8 8 8 8
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 6 节拍
2001.9.1 计算机系统结构 108
超流水技术：一个时钟节拍内 分时 发射多条指令（ P333第 1行）。
时空图见 P333图 5.79。
指令
9 9 9 9
8 8 8 8
7 7 7 7
6 6 6 6
5 5 5 5
4 4 4 4
3 3 3 3
2 2 2 2
1 1 1 1
1 2 3 4 5 6 节拍
2001.9.1 计算机系统结构 109
5.7 精简指令系统（ RISC） 技术 (P111)
什么是 RISC？（ P107）
CISC和 RISC是指令系统设计的两种思路,前者注重功能多，后者注重速度快。 双方各自发展了很多特色技术。
RISC主要用于工作站和其它高性能计算机，以 UNIX操作系统为主。 IBM-
PC个人计算机以 CISC为主，吸收了 RISC的若干适宜技术。
20%与 80%规律（ P112）
统计表明,CISC中 20%的常用指令使用率高达 80%，其它都是非常用指令。
RISC定义与特点（ P115）
①一个周期；②一种访存寻址方式；③硬联译码；④简化指令；⑤固定指令格式；⑥优化译码。
减少 CPI是 RISC思想的精华（ P116）
分析公式,T = IC · CPI · CYCLE,RISC使 IC增加，其它两项减少。
2001.9.1 计算机系统结构 110
RISC的关键技术 (P118)
1,延时转移技术将转移指令与它前面的不相关指令对调位置，以利用计算目的地址的时间。
2,指令取消技术在条件转移指令解释期间提前启动最有可能的一个分支的后继指令，如果
“猜”错则及时取消，“猜”对则赢得了时间。
3,重叠寄存器窗口技术用寄存器组代替堆栈传递参数，减少访问主存。
4,指令流调整技术用换名消除相关，消除不了的相关就调整顺序。
5,少数复杂指令用微程序实现不常用的复杂指令用微程序实现，避免专设电路，对平均速度影响也不大。
2001.9.1 计算机系统结构 111
本章小结
(1) 流水处理与相关的概念；
(2) 时空图画法及其应用；
(3) 7种流水线分类方法；
(4) 3个流水线性能指标；
(5) 2种,瓶颈”解决方法 ；
(6) 2种非线性流水线调度方法；
(7) 超标量与超流水技术的概念 ；
(8) 精简指令系统（ RISC） 技术。
习题,P343,题 9，题 15。
2001.9.1 计算机系统结构 112
6.1 特点多数为巨型机，有多条单功能流水线。
6.2 典型工作方式
CRAY-1是世界上第一台向量流水处理巨型机。
(1) CRAY-1的技术术语向量寄存器组 V0,V1,……,V7。
分量计数器链接方式 (P370)
启动、输出延迟（各 1拍）。
第六章 向量流水线技术 (P347)
2001.9.1 计算机系统结构 113
功能部件冲突 ── 指令运算符号相同；
Vi变量冲突 ── 指令中使用的 Vi变量相同，具体有 3种形式，
即左同名、右同名、上右下左同名。
冲突,① A=B+C ② A=B+C ③ A=B+C
A=D*E D=B*E B=D*E
相关,④ A=B+C
D=A*E
(3) CRAY-1分析指令的 3条策略无相关，无冲突 ── 同时启动；
有相关，无冲突 ── 链接启动；
有冲突 ── 顺序执行；
(4)计算向量程序执行时间的工具 ── 多流水线时空图 （结合 P391题 6.6实例学习 ）
(2) 冲突及其分类
2001.9.1 计算机系统结构 114
本章小结
(1) 向量流水处理机 特点 ；
(2) 冲突及其分类 ；
(3) CRAY-1分析指令的 3条策略 ；
(4) 链接方式；
(5) 启动、输出延迟（各 1拍）。
习题,P391，题 6（注意阅读 P372倒数第 9行－倒数第 6行）。
2001.9.1 计算机系统结构 115
本章内容：介绍用于多机并行计算的各种网络,它们统称为互连网络,
缩写符号是 ICN（ Interconnection Network） 。
7.1 目的与作用
(1) 当前提高计算速度的主要措施，一是改进器件，二是多机并行计算。 ICN
是多机之间传输数据的高速通路，对整体性能起关键作用。
(2) ICN的分类,通用网 （原用于计算机之间交换信息的普通网络）,专用网
（专用于并行计算系统各处理单元之间并行交换数据的特殊网络） 。
(3) ICN与处理单元的连接模式（ P453-P454,P505）,分布存储型，共享存储型。 0 ICN 0
从处理单元来 1 开关 1 到处理单元或存储单元
N-1 网络 N-1
(4) ICN的主要操作,置换 (N-N),广播 (1-N),选播 (1-N’)。
第七章 互连网络 (P394)
2001.9.1 计算机系统结构 116
特点：成本低，并行性差。
(1) 拓扑结构 (硬件,P402-P407),直线，单向环，双向环，带弦环，树，星型（真星型，假星型），完全网。
(2) 传输协议 (使用规则，软件,P427-P435),碰撞争用，令牌协议，剑桥环。
(3) 主要参数 (P399),直径，中剖宽度，结点的度，最长边。
示例：
(4) 典型代表：以太网，令牌网（环或直线）。
7.2 通用网
2001.9.1 计算机系统结构 117
特点：并行度高，造价昂贵。
(1) 互连函数
N个输入到 N个输出的一种对应状态可以用一个映射函数表示，称为互连函数。它是处理单元集合对于自身的双射映射，所以又称为,置换,，或者,循环,。
互连函数有多种表示方式，如下例所示：
f(0)=1 0 0
f(1)=2 1 1 f= 0 1 2 3 f=(0,1,2)(3)
f(2)=0 2 2 1 2 0 3
f(3)=3 3 3
a.枚举法 b.开关状态图 c.列表法 d.循环函数一个网络通过开关切换可以形成多个映射关系，所以要用,互连函数族,来定义一个网络。
7.3 专用网
2001.9.1 计算机系统结构 118
定义,单级 ICN只使用一级开关，如下图所示。
开关的每种接通组合方式可用一个互连函数表示。
f( j入 ) = j出,0≤ j≤N -1
在互连函数中，记：
N ── 结点数
n = log2N ── 维数
j= Xn-1…… X0 ─ ─ 结点编号的二进制形式，位数为 n。
互连函数族的组成必须使网络成为 连通图 。
(2) 单级 ICN
ICN
0 0
N-1 N-1
2001.9.1 计算机系统结构 119
该网络由立方体 函数定义,立方体 函数族有 n个成员,分别是 Cube0,Cube1
,……,Cuben-1。
立方体 函数 定义,Cubei的功能 是对 入端结点编号二进制形式的第 i位取反
Cubei(Xn-1… Xi+1XiXi-1… X0)=Xn-1… Xi+1XiXi-1… X0,其中 0≤ i≤n -1
例如,Cube0(0)=1,Cube3(7)=15。
n=3的单级立方体网络拓扑形状如 右 图所示 。
最坏情况下的传输需 对输入结点编号的全部
n位取反 。 所以 单级立方体网络的直径是 n。
立方体 函数 性质,结合律,交换律 以及 自反律 （ Cubei重复使用 2次的结果与原始自变量相同 ） 。
单级立方体网 （ Cube网,P396第 1行 / P404第 4行）
2 3
0 1
6 7
4 5
2001.9.1 计算机系统结构 120
该网络由 混洗函数 （ shuffle） 与 交换函数 （ exchange即 Cube0） 定义,或者说它的互连函数族只有这两个成员 。
混洗函数 定义：
2j mod（ N-1）,当 j < N-1
shuffle（ j） =
N-1,当 j = N-1
例如：当 N=8时,shuffle（ 0） = 0,shuffle（ 1） = 2,shuffle（ 7） = 7。
n=3的混洗函数开关状态如 P397图 7.6(a)所示,其连接规律就像洗牌 。
性质 1,shuffle（ Xn-1Xn-2…… X0） = Xn-2…… X0Xn-1（ 循环左移）
性质 2,shufflen（ j） = j
n=3的 混洗 网络拓扑形状如下图 绿线 所示,可以看出它不是一个 连通图,所以还需要增加一个 交换函数 （ 图中 红线 所示 ）,才能构成完整的单级混洗 —交换网络 。
单级混洗 —
交换网络的直径是 2n-1。
单级混洗 -交换网 （ P396倒数第 8行 ）
0 1 2 3 4 5 6 7
2001.9.1 计算机系统结构 121
该网络由 PM2I函数定义,PM2I函数共有 n对成员,分别是 PM2 ± 0,PM2 ± 1，
……,PM2 ± (n-1)。
PM2I函数定义,PM2± i的功能是对入端结点编号加或减 2i,然后再作模 N运算
PM2+i（ j） = j + 2i mod N
PM2-i（ j） = j - 2i mod N
其中 j = 0 ～ N - 1,i = 0 ～ n - 1。
例如：当 N = 8时,
PM2+0（ 0） = 0 + 20 = 1，
PM2+0（ 1） = 1 + 20 = 2，
PM2+0（ 7） = 7 + 20 = 0，
PM2+1（ 0） = 0 + 21 = 2。
N = 8的 PM2+1（ j） 函数开关状态如右图所示,其连接规律是把各入端结点编号加上相同的增量 21（ mod N）,获得出端结点编号 。
单级加减 2i网 （ PM2I网，移数网,P398倒数第 2行）
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
2001.9.1 计算机系统结构 122
N = 8的 PM2+i网络拓扑形状如下图所示，可以看出它包含多个强连通子图
（即除去若干边以后仍能保证任何一对结点互相可达），所以这 2n个函数并不是实现互连网的最小集合。实际应用中为了降低造价，人们往往取它们的一个子集来构造互连网。
性质 1：对相同的 i值,PM2+i
与 PM2-i函数的传送路径相同,
方向相反 （ 右图中所有箭头反向即为 PM2-1的拓扑形状 ） ；
性质 2,PM2+(n-1) = PM2-(n-1)。
根据性质 2,我们知道单级 PM2I网络实际上只能实现 2n-1种不同的置换 。
单级 PM2I网络的直径是 。?2/n
i=1 i=2
0
7 1
i=0
6 2
5 3
4
2001.9.1 计算机系统结构 123
(3) 多级 ICN（ P409）
定义：多级 ICN使用多级开关,使得数据在一次通过网络的过程中可以实现的置换种类更多 。
通常在 N个结点的网络中,多级 ICN由 n级构成 （ n = log2N） 。
经典的多级互连网有 多级立方体网,多级混洗 —交换网 和 多级 PM2I网 。 我们只学习多级混洗 —交换网 。
多级立方体网和多级混洗 —交换网不使用单级互连网中的那种多路选择开关
,而是用一种 2输入 /2输出的 二元交换开关,以减少开关总数 。 二元交换开关的基本接通状态有,直连,,,交换,,,上播,和,下播,,在进行数据置换时只能使用前 2种 。
各开关的控制信号可采用 3种分配方式之一,级控方式,部分级控方式 和 单元控制方式 。
级控方式 就是同一级 （ 即同一列 ） 开关共用一个控制信号,动作保持一致；
部分级控方式 在第 i级设置 i+1个独立的控制信号,每个信号管辖若干开关； 单元控制方式 为每个开关独自设置一个控制信号,各开关动作独立,性能比前两种方式都更灵活,结构也更复杂 。
( a ) 直连 ( b ) 交换 ( c ) 上播 ( d ) 下播
2001.9.1 计算机系统结构 124
多级混洗 —交换网络（ P410/P436）
多级混洗 —交换网络又称为 Omega网 。
多级混洗 —交换网络结构：它 由 n级构成,每一级包含 一个无条件 混洗拓扑 线路 和 一列可控的二元 交换开关,前后重复,便于制造 。 如 P436图 7.43所示 。
各级编号是 n-1,……,0,即按 降序排列 。
在多级混洗 —交换网络中,单独一级 混洗拓扑线路可完成一次 数据混洗 （
shuffle）,而单独一列二元交换开关在处于,交换,状态时可完成一次 交换操作 （ Cube0） 。 如果各级二元交换开关都处于,直连,状态,N个结点的数据通过网络仅经过 n次混洗操作,排列顺序最终 恢复输入状态 （ 混洗函数性质 2） ；如果各级二元交换开关都处于,交换,状态,则 N个结点的数据在每次混洗之后紧接着一次交换 （ Cube0）,也就是地址码的最低位取反,最后 n
位地址均被取反 。 程序员根据数据置换或复制的需要,可以灵活地设置各开关的状态 。
2001.9.1 计算机系统结构 125
多级混洗 —交换网络寻径算法（路由算法）
目的,根据给定的输入 /输出对应关系,确定各开关的状态 。
名称,源 -目的地址异或法操作,将任一个输入地址与它要到达的输出地址作异或运算,其结果的 biti
位控制数据到达的第 i级开关,,0” 表示,直连,,,1” 表示,交换,。
例如给定传输 101B→ 011B,二者异或结果为 110B,于是从 101B号输入端开始,把它遇到的第 2级开关置为,交换,,第 1级开关置为,交换,,第 0
级开关置为,直连,。 如下图 红线 所示 。
输入 第 2 级 第 1 级 第 0 级 输出
000 000
00 1 001
0 1 0 0 1 0
0 11 011
1 00 1 00
1 0 1 1 01
11 0 1 10
1 11 1 11
2001.9.1 计算机系统结构 126
本章小结
(1) 通用网的拓扑结构，传输协议，主要参数，典型代表；
(2) 互连函数（置换，循环）的 4种表示方式；
(3) 单级立方体网（ Cube网）的定义，拓扑形状，直径，性质，互连函数族的组成；
(4) 单级混洗 -交换网的定义，拓扑形状，直径，性质，互连函数族的组成；
(5) 单级加减 2i网（ PM2I网，移数网）的定义，拓扑形状，直径，性质，互连函数族的组成；
(6) 二元交换开关，控制信号的 3种分配方式；
(7) 多级混洗 —交换网络的结构，寻径算法（路由算法）。
习题,P446,必做 3,10,26(1)～ (3)； 选做 4,7,9。
2001.9.1 计算机系统结构 127
第八章 SIMD计算机 (P451)
SIMD计算机 指由 一个控制部件 和 多个运算部件 组成的处理机为核心的计算机系统。这样的处理机又被称为 并行处理机 或 阵列处理机 。
2001.9.1 计算机系统结构 128
8.1 SIMD的 5个组成部分 (P453)
运 ── PEi
控 ── CU
存 ── LMi
管 ── SC
网 ── ICN
2001.9.1 计算机系统结构 129
8.2 SIMD的两种结构类型 (P453～ P454)
(1)分布存储结构
(2)共享存储结构
2001.9.1 计算机系统结构 130
8.3 SIMD的代表实例 ─── ILLIAC IV(P457)
ILLIAC IV的 ICN（ P458）
它是单级 PM2I网络 的一个子集,F={PM2± 0,PM2± (n/2)},这里 n=6。
可以证明，任意两个结点之间的距离不超过 7步。
ILLIAC IV的 4条并行传输指令 （ P479）
循环左传 1（西），循环左传 8（北），循环右传 1（东），循环右传 8（南）。
每个 PEi的组成 （ P458～ P459）
A ── 累加器（ 64位）
B ── 通用寄存器（ 64位）
R ── 互连寄存器（ 64位）
M ── 模式寄存器（ 8位）
2001.9.1 计算机系统结构 131
8.4 SIMD的典型算法 (P483)
矩阵加,减 （ P484）
迭代平均 （ P483）
非数组问题的向量化算法 （ P486）
2001.9.1 计算机系统结构 132
本章小结
(1) SIMD的 5个组成部分
(2) SIMD的两种结构类型
(3) SIMD的代表实例 ─── ILLIAC IV
(4) SIMD的典型算法。
习题,P498，题 12。
2001.9.1 计算机系统结构 133
第九、十章 MIMD计算机 (P499)
目前实际使用的 MIMD计算机都是 多处理机系统,包括 多计算机系统 。
MIMD计算机与 SIMD计算机的主要区别,在于前者是 任务级并行处理,后者是 数据级并行处理 。
2001.9.1 计算机系统结构 134
9.1 MIMD的典型结构 (P500)
(1)共享存储器方案
(2)本地存储器方案
2001.9.1 计算机系统结构 135
(1)任务派生语句 ─── FORK <进程名 >
(2)任务汇合语句 ─── JOIN <汇合进程数 >,<计数器序号 >
实例,P608
x = ( a + b )× ( a - c )
程序：
k,Fork k+3
k+1,Add A,B,T1
k+2,Goto k+4
k+3,Sub A,C,T2
k+4,Join 2,1
k+5,Mul T1,T2,X
9.2 MIMD的并行程序控制 (P608)
k:A+B → T1 k+3:A-C → T2
k+5:T1*T2 → X
2001.9.1 计算机系统结构 136
9.3 MIMD的加速性能模型 (P502～ P512)
(1)两个处理机的并行模型 （ P504） ；
总处理时间 = R× max{ M-K,K } + C× ( M-K )× K
其中,M ── 任务总数；
K ── 分配给处理机 1的任务数；
R ── 执行 1个任务所需时间；
C ── 进行 1次通信所需时间 。
最优解,P505第 1～ 3行 。
(2)N个处理机的并行模型 （ P505） 。
总处理时间 = R× max{ Ki } + (C/2)× Σ [Ki× ( M-Ki )]
= R× max{ Ki } + (C/2)× ( M2-Σ Ki2 )
处理机 1 处理机 2
任务 1 任务 K + 1
任务 2 任务 K + 2
┇ ┇
任务 K 任务 M
2001.9.1 计算机系统结构 137
本章小结
(1) MIMD的 2种典型结构
(2) MIMD的并行程序控制
(3) MIMD的加速性能模型习题,P562，题 18。
2001.9.1 计算机系统结构 138
附录 1
部分习题参考答案
2001.9.1 计算机系统结构 139
第一章 (P33)
题 15
题 19
2001.9.1 计算机系统结构 140
第二章 (P124)
题 3（忽略 P124倒 1行 ~ P125第 8行文字）
题 13
2001.9.1 计算机系统结构 141
第三章 (P202)
题 3
题 15
题 19
2001.9.1 计算机系统结构 142
第四章 (P250)
题 5
题 8
2001.9.1 计算机系统结构 143
第五章 (P343)
题 9
题 15
2001.9.1 计算机系统结构 144
第六章 (P391)
题 6.6（注意阅读 P372倒数第 9行－倒数第 6行）
解：
已知 n=32,k加 =6,k乘 =7,k访存 =6,k倒数 =14，启动、输出延迟各 1。求各小题总拍数。
2001.9.1 计算机系统结构 145
( 1) V 0 ← 存储器
V 1 ← V 2 + V 3 并行
V 4 ← V 5 * V 6
访存加乘
9 31
总拍数 =40 （并行执行，以最长指令为准）
( 2) V 2 ← V 0 * V 1 并行
V 3 ← 存储器
V 4 ← V 2 + V 3 串行 （ P 372 ）
乘访存加
9 31 8 31
总拍数 =79 （第 3 条错过时机，不能链接）
2001.9.1 计算机系统结构 146
( 3) V 0 ← 存储器 并行
V 3 ← V 1 + V 2 链接
V 4 ← V 0 * V 3
V 6 ← V 4 + V 5 串行访存加乘
8 9 31 8 31
总拍数 =87 （第 4 条功能部件冲突）
( 4) V 0 ← 存储器 链接
V 1 ← 1 / V 0 链接
V 3 ← V 1 + V 2 链接
V 5 ← V 3 * V 4
访存倒数加乘
8 16 8 9 31
总拍数 =72 （各条依次链接）
2001.9.1 计算机系统结构 147
( 5) V 0 ← 存储器
V 1 ← V 2 + V 3 并行
V 4 ← V 5 * V 6
s 0 ← s 1 + s 2 串行访存加乘
9 31 8
总拍数 =48 （标量看成 1 个分量的向量）
( 6) V 3 ← 存储器 并行
V 2 ← V 0 + V 1 串行
s 0 ← s 2 + s 3 并行
V 3 ← V 1 * V 4
访存加乘
8 31 9 31
总拍数 =79 （标量看成 1 个分量的向量）
2001.9.1 计算机系统结构 148
( 7) V 3 ← 存储器 并行
V 2 ← V 0 + V 1 链接
V 4 ← V 2 * V 3
存储器 ← V 4 串行访存加乘
8 9 31 8 31
总拍数 =87 （第 4 条功能部件冲突）
( 8) V 0 ← 存储器 链接
V 2 ← V 0 + V 1
V 3 ← V 2 * V 1 串行
V 5 ← V 3 * V 4 串行访存加乘
8 8 31 9 31 9 31
总拍数 =127 （ Vi 冲突，功能部件冲突）
2001.9.1 计算机系统结构 149
第七章 (P446)
必做 3,10,26(1)～ (3)；
选做 4,7,9。
2001.9.1 计算机系统结构 150
第八章 (P498)
题 12
2001.9.1 计算机系统结构 151
第九、十章 (P562)
题 18
2001.9.1 计算机系统结构 152
再见
