计算机系统结构

“数字逻辑与数字系统”、“计算机组成原理”、“计算机系统结构”和“微机原理及其接口技术”是计算机科学与技术专业本科生硬件一条线的必修课程，其中“计算机系统结构”属于专业课。通过本课程的学习，学生应认识到计算机科学与技术的发展是计算机性能不断提高的过程，是计算机系统结构不断改善的过程，是并行处理技术不断进步的过程；应系统理解计算机系统结构的基本概念、组织结构、分析设计方法，以及目前计算机系统结构发展的新理论、新技术。以此培养学生的组织结构思维能力和概念理论创新能力。

“计算机系统结构”作为计算机科学与技术发展的前导性学科，其主要特点有以下几个方面。一是有许多内容既不完善，也不具体，教材及相应的参考书不多，教材间无论是思想内容，还是侧重点，差异都较大；二是内容本身是以概念、理论和方法为主，与其他硬件课程相比，理论性强、抽象度大；三是内容广泛，涉及面广，它不仅与大量软硬件课程有密切的关系，还与系统学、结构学等有密切的关系，但其关系主要不是知识结构间的关系，而是认识思维间的关系；四是计算机系统结构的发展迅速，应及时补充新的内容。

本书作者长期从事“计算机系统结构”等相关课程的教学和科研工作，在查阅和综合分析相关资料的基础上，编写了本书。本书在系统介绍计算机系统结构基本概念、基本性能和基本理论的基础上，突出并行处理技术是改善计算机系统结构的关键技术。从并行性实现的技术途径——时间重叠、资源重复和资源共享出发，全面分析流水线技术、指令优化与调度技术、精简指令技术、向量处理技术、存储组织技术和互连网络技术等的基本概念、理论方法、实现的逻辑结构要求、提高计算机性能的效果及其技术应用的典型的计算机结构。阐述流水线处理机、向量处理机、阵列处理机、多处理机系统和机群系统等实现的技术基础、基本结构和性能分析。指出了目前计算机系统结构存在的问题和未来计算机系统结构发展的基本框架，对数据流计算机的系统结构作了较全面的介绍。

本书的主要特点是：①在章节和内容安排上思路新，将计算机系统结构的设计技术与典型结构尽量分开，突出前者来满足不同学时的需要；②强调基本概念、基本理论和基本设计技术的系统性，与许多教材强调结构体系的多样性不同；③注重基本概念与基本理论的一般解释，而不是典型解释或狭意解释；④突出硬件结构性，对于软件实现的内容少讲或不讲；⑤在保持知识体系完整的前提下，尽量避免与“计算机组成原理”、“操作系统”等课程内容的重复。

本书结构新颖、内容实用、逻辑性强、重点突出、语言精炼，可作为高等院校计算机各专业及有关专业本科生的教材，同时也可作为相关方向的研究生或研究人员的参考书。建议本书教学用时为70～80学时。

本书由刘超主编，参与本书部分章节编写及大纲讨论的还有万承兴、衷尔英等。本书在编写与出版过程中，得到了江西师范大学薛锦云、甘登文、谢旭升等教授的关心与帮助，在此表示衷心感谢。

由于作者水平有限，加之时间仓促，书中错误在所难免，敬请各位专家、读者批评指正。

编者

2005年7月

前言
第1章 计算机系统结构导论 1
1.1 计算机系统结构的基本概念 1
1.1.1 提高计算机系统性能的硬件因素 1
1.1.2 计算机系统中的有关术语 2
1.1.3 计算机系统结构与组成及其实现 3
1.1.4 计算机系统结构的特性 5
1.2 计算机系统结构的发展及其影响因素 10
1.2.1 计算模型及其驱动方式 10
1.2.2 冯•诺依曼型计算机系统结构及其发展 11
1.2.3 归约型计算机 13
1.2.4 智能型计算机 13
1.2.5 计算机系统结构发展的影响因素 14
1.2.6 计算机系统结构的生命周期 16
1.3 计算机系统结构中的并行性及其发展 16
1.3.1 并行性及其等级的划分 16
1.3.2 提高计算机系统并行性的技术途径 18
1.3.3 多机系统及其耦合度 18
1.3.4 计算机系统结构向并行处理系统的发展 21
1.3.5 计算机系统结构的分类 23
1.4 计算机系统结构的设计 27
1.4.1 计算机系统结构设计的主要方法 27
1.4.2 计算机系统结构设计中软硬件取舍的基本原则 28
1.4.3 软件可移植性及其实现的基本方法 28
1.4.4 并行处理及其实现的技术问题 30
1.4.5 并行计算机及其性能 33
1.5 计算机系统结构的定量分析 33
1.5.1 系统结构设计的定量原理 33
1.5.2 计算机系统结构的评价标准 36
1.5.3 程序执行时间的测定 38
1.6 数据流计算机 39
1.6.1 数据驱动原理 39
1.6.2 数据流计算机的指令结构及其执行过程 40
1.6.3 数据流计算机的结构模型 41
1.6.4 数据流计算机的优点与存在的问题 43
1.6.5 数据流计算机的发展趋势 45
习题一 46
第2章 数据表示、指令系统与I/O系统的优选技术 49
2.1 数据表示的选择 49
2.1.1 数据表示的基本概念 49
2.1.2 引入数据表示的基本原则 50
2.1.3 自定义数据表示 51
2.1.4 浮点数据表示 54
2.2 指令集结构格式的优化设计 56
2.2.1 指令集结构的分类 56
2.2.2 指令集结构格式的选择 58
2.2.3 操作码的优化表示 60
2.2.4 缩短地址码长度的方法 64
2.3 指令集结构的功能设计 65
2.3.1 指令集结构功能的发展方向 65
2.3.2 CISC指令集结构的功能设计 65
2.3.3 RISC计算机指令集结构的功能设计 66
2.3.4 精简指令系统计算机 67
2.4 编译技术与指令集结构的设计 70
2.4.1 现代编译器的组成结构 70
2.4.2 现代编译技术与指令集结构之间的影响 72
2.5 总线的设计 74
2.5.1 总线的类型 74
2.5.2 通用总线的控制方式 74
2.5.3 数据宽度与总线线数 76
2.6 输入输出系统的设计 77
2.6.1 输入输出系统的基本概念 77
2.6.2 输入输出设备与主机信息传送的控制方式 78
2.6.3 中断系统中的软硬件功能分配 79
习题二 80
第3章 流水线技术 83
3.1 流水线的基本概念 83
3.1.1 什么是流水线 83
3.1.2 流水线的表示方法 84
3.1.3 流水线的分类 86
3.1.4 流水线的特点 89
3.2 流水线实现的基本结构 90
3.2.1 重叠执行方式的基本结构 90
3.2.2 先行控制方式的基本结构 91
3.2.3 运算操作流水线和宏流水线的基本结构 93
3.3 线性流水线的性能分析 93
3.3.1 吞吐率（TP，Though put rate） 93
3.3.2 加速比（S，Speedup ratio） 96
3.3.3 效率（E，Efficiency） 97
3.3.4 吞吐率、加速比和效率之间的关系 98
3.3.5 流水线最佳段数的选择 98
3.4 流水线的相关及其处理 101
3.4.1 流水线中相关的基本概念 101
3.4.2 数据相关的形成 102
3.4.3 数据相关的处理 103
3.4.4 控制相关的形成 104
3.4.5 条件转移的处理 104
3.4.6 中断转移的处理 108
3.5 非线性流水线的调度技术 108
3.5.1 问题的提出 108
3.5.2 非线性流水线调度的相关术语及其计算方法 110
3.5.3 最小启动循环调度策略的求解及其实现 112
3.5.4 非线性流水线的优化调度方法 112
习题三 114
第4章 存储组织技术 118
4.1 存储系统的层次结构 118
4.1.1 存储系统的基本概念 118
4.1.2 存储系统的层次结构 119
4.1.3 存储系统的基本结构与典型结构 120
4.1.4 存储系统的性能指标 121
4.2 并行存储器与相联存储器 123
4.2.1 什么是并行存储器 123
4.2.2 单体多字并行存储器 123
4.2.3 交叉访问存储器 124
4.2.4 无访问冲突存储器 126
4.2.5 相联存储器 128
4.3 高速缓冲存储器（Cache） 129
4.3.1 Cache存储器的工作原理 129
4.3.2 几种地址映像和地址变换的方法 130
4.3.3 Cache系统的性能指标 136
4.3.4 影响命中率的基本因素 137
4.3.5 Cache的预取算法 138
4.3.6 Cache的一致性问题 138
4.4 虚拟存储器 140
4.4.1 虚拟存储器的工作原理 140
4.4.2 虚拟存储器的管理方式 140
4.4.3 加快地址变换的方法 145
4.5 存储系统的替换算法及其实现 147
4.5.1 问题的提出 147
4.5.2 替换算法及其实现 148
4.5.3 堆栈型替换算法 149
4.6 存储系统的组织与虚拟地址Cache 153
4.6.1 三级存储系统的组织方式 153
4.6.2 虚拟地址Cache 155
习题四 156
第5章 互连网络技术 160
5.1 互连网络的基本概念 160
5.1.1 互连网络的功能和特征 160
5.1.2 互连网络的描述工具 161
5.1.3 常用的基本互连函数 161
5.1.4 互连网络结构特性和传输性能参数 165
5.1.5 互连网络的分类 166
5.2 静态互连网络 167
5.2.1 静态互连网络的概念 167
5.2.2 静态互连网络的种类与结构 167
5.2.3 静态互连网络特性 168
5.3 动态互连网络 169
5.3.1 动态互连网络的概念 169
5.3.2 动态互连网络的互连形式 169
5.3.3 几种常用的多级互连网络 173
5.4 互连网络的消息传递机制 181
5.4.1 路由选择的基本概念 181
5.4.2 消息传递的格式与方式 182
5.4.3 死锁和虚拟通道 184
5.4.4 流量控制策略 186
5.4.5 互连网络的通信模式 187
习题五 187
第6章 指令级高度并行处理机 190
6.1 指令级高度并行处理机的基本概念 190
6.1.1 标量指令与标量处理机 190
6.1.2 标量指令级并行的实现方法及其衡量指标 190
6.1.3 指令调度及其方法 192
6.1.4 动态调度技术 192
6.1.5 向量处理的基本概念 195
6.2 超标量和超流水线处理机 196
6.2.1 超标量处理机（Superscalar Processor） 196
6.2.2 超流水线处理机（Superpipelining Processor） 199
6.2.3 超标量超流水线处理机 202
6.2.4 四种不同类型处理机的性能比较 203
6.3 超长指令字处理机 204
6.3.1 超长指令字处理机（VLIW：Very Long Instruction Word）的时空图 204
6.3.2 超长指令字处理机工作的基本原理 204
6.3.3 VLIW方式的特征 206
6.4 向量处理机 207
6.4.1 向量指令 207
6.4.2 向量处理机的结构 209
6.4.3 向量协处理器 212
6.4.4 向量处理机的性能 213
习题六 213
第7章 阵列处理机 215
7.1 阵列处理机的基本概念 215
7.1.1 阵列处理机的操作模型 215
7.1.2 阵列处理机的特点 215
7.1.3 阵列处理机的基本结构 216
7.2 阵列处理机的并行算法 218
7.2.1 阵列处理机的系统结构与并行算法的关系 218
7.2.2 阵列处理机的算法 219
7.3 几种典型的阵列处理机 222
7.3.1 Illiac IV阵列处理机 222
7.3.2 MasPar MP-1阵列处理机 224
7.3.3 CM-2阵列处理机 227
7.4 大规模并行处理机 230
7.4.1 大规模并行处理机的基本概念 230
7.4.2 大规模并行处理机系统软件设计的新概念 230
习题七 231
第8章 多处理机系统 233
8.1 多处理机系统的基本概念 233
8.1.1 多处理机系统及其分类 233
8.1.2 一般性多处理机系统的模型 233
8.1.3 多处理机系统的基本结构 235
8.1.4 多处理机系统的特点 236
8.1.5 多处理机系统的操作系统 237
8.2 多处理机的Cache一致性 238
8.2.1 多处理机Cache不一致性的由来 238
8.2.2 解决多处理机Cache不一致的方法 239
8.2.3 总线监听协议法 240
8.2.4 基于目录协议法 242
8.3 多处理机并行性的实现技术 245
8.3.1 并行算法 246
8.3.2 程序结构中的数据相关及其处理 247
8.3.3 并行程序设计语言 249
8.3.4 并行优化编译器 250
8.4 多处理机系统性能 252
8.4.1 性能指标及其计算模型 252
8.4.2 任务粒度对性能的影响 255
8.5 机群系统 259
8.5.1 机群系统的基本概念 259
8.5.2 机群系统的关键技术 259
8.5.3 机群系统的通信技术 261
8.5.4 并行程序设计语言 262
8.5.5 并行程序调试技术 262
8.5.6 负载平衡技术 263
8.6 典型的多处理机系统 264
8.6.1 CM-5系统 264
8.6.2 SGI Origin 2000系列服务器 267
习题八 270
参考文献 272

1. 计算机组织与系统结构 [季福坤 主编]