第一章 并行处理系统与互连网络 1
1.1 并行处理——提高计算机系统性能的重要途径 1
1.1.1 推动并行处理技术发展的因素 1
1.1.2 并行性的概念及其实现途径 3
1.2 并行处理系统的系统结构 6
1.2.1 流水线处理机的工作原理与特点 6
1.2.2 阵列处理机的功能结构与性能 7
1.2.3 多处理机的系统结构与控制 10
1.2.4 计算机系统的分类 12
1.3 互连网络在并行处理系统中的地位和作用 14
1.3.1 互连网络的作用与功能模型 14
1.3.2 互连网络的连接通路 15
1.4 互连网络与互连函数 16
1.4.1 互连函数的表示形式 17
1.4.2 几种基本互连函数 17
1.4.3 FUB互连函数 24
1.4.4 BPC互连函数 26
1.5 映射和置换的初步知识 27
1.5.1 映射 27
1.5.2 置换 31
1.6 互连网络的结构分类 36
1.6.1 静态互连网络 36
1.6.2 动态互连网络 41
参考文献 47
2.1.1 单总线 48
第二章 静态互连网络结构分析 48
2.1 总线型网络 48
2.1.2 多总线 49
2.1.3 多级总线 50
2.1.4 多维总线 52
2.1.5 分割总线 53
2.2 环形网络 54
2.2.1 单环网络的结构特征与寻径算法 55
2.2.2 带弦环形网络的特性和分布控制算法 59
23 立方体网络 64
2.3.1 立方体网络的结构与特性 64
2.3.2 带环立方体网络的组成与特点 65
2.3.3 一般化的超立方体网络 67
2.4 树形网络 72
2.4.1 二叉树和半环、全环二叉树网络 72
2.4.2 超树形网络的构成与特性 75
2.4.3 多树网络的结构分析 78
2.5 网孔形、星形和全连接网络 80
2.5.1 网孔形网络 80
2.5.2 星形网络 81
2.5.3 全连接网络 82
2.6 静态互连网络的生成方法 82
参考文献 85
3.1.1 SIMD机器的两种基本组态 87
第三章 单级互连网络 87
3.1 SIMD机器的结构模型 87
3.1.2 STMD机器的结构模型 88
3.2 单级互连网络 93
3.2.1 单级互连网络的概念模型 94
3.2.2 网孔连接的Illiac网络 95
3.2.3 加减2？网络 99
3.2.4 洗牌交换网络 103
3.2.5 立方体网络 106
3.3 单级互连网络的划分 110
3.3.1 网络划分的原理 112
3.3.2 立方体网络的划分 114
3.3.3 Illiac网络的划分 116
3.3.4 PM2I网络的划分 116
3.3.5 洗牌交换网络的划分 119
3.4 单级互连网络的相互模拟 119
3.4.1 单级互连网络相互模拟原理 119
3.4.2 PM2I网络模拟其它网络 121
3.4.3 立方体网络模拟其它网络 127
3.4.4 Illiac网络模拟其它网络 134
3.4.5 SE网络模拟其它网络 146
参考文献 150
4.1 STARAN网络 152
4.1.1 STARAN网络的作用 152
第四章 动态多级阻塞互连网络 152
4.1.2 拓扑结构 154
4.1.3 控制方式与连接特性 155
4.2 间接二进制n方体网络 160
4.2.1 拓扑结构及其控制 160
4.2.2 容许通过的置换 163
4.3 Ω网络 172
4.3.1 并行存储器的无冲突访问 172
4.3.2 Ω网络的结构与控制 176
4.3.3 连接特性与应用 179
4.4 数据变换网络 188
4.4.1 DM网络的构成与变换功能 188
4.4.2 ADM网络及其控制 191
4.5 榕树网络 195
4.5.1 榕树网络 195
4.5.2 SW榕树网络 197
4.6 Delta网络 203
4.6.1 工作原理与网络组成 203
4.6.2 性能分析与交叉开关的比较 208
4.7 基准网络 213
4.7.1 基准网络 213
4.7.2 基准网络与位序颠倒交换网络 215
4.7.3 一次通过网络的容许置换 216
4.7.4 二次通过网络实现任意置换 218
4.8.1 拓扑等价 219
4.8 多级互连网络的拓扑与功能等价 219
4.8.2 功能等价 226
4.9 多级互连的网络划分 233
4.9.1 多级互连网络的划分 233
4.9.2 STARAN网络的划分 234
4.9.3 间接二进翻n方体网络的划分 235
4.9.4 Ω网络的划分 238
4.9.5 数据变换网络的划分 239
参考文献 240
第五章 动态多级非阻塞互连网络 243
5.1 开关连接系统与互连网络 243
5.1.1 连接系统的一般特性 243
5.1.2 互连网络的连接能力 244
5.1.3 多级非阻塞网络的研究概况 247
5.2 交叉开关网络 250
5.3 多级非阻塞网络 252
5.3.1 非阻塞Clos网络 252
5.3.2 非对称Clos网络的某些术语及符号 258
5.3.3 非对称严格非阻塞Clos网络 260
5.3.4 严格非阻塞Cantor网络 263
5.4 可重排非阻塞网络 266
5.4.1 可重排三级Clos非阻塞网络 266
5.4.2 非对称的可重排非阻塞网络 268
5.4.3 二进制置换网络 274
5.4.4 二项网络 279
5.4.5 细胞结构的可重排网络 286
5.5 一般化的连接网络 294
5.5.1 一般化的连接网络及其图的表示 294
5.5.2 GCN的构造方法 296
5.5.3 信息播送与开关设置算法 300
5.6 非阻塞网络复杂度的边界值 303
5.6.1 严格非阻塞网络的边界值 303
5.6.2 可重排非阻塞网络的边界值 305
5.6.3 单边互连网络的边界值 307
附录 定理5.2α的证明 308
参考文献 311
6.1 多级互连网络的控制 314
第六章 多级互连网络的控制 314
6.2 可重排网络的路径控制算法 316
6.2.1 方阵分解算法 316
6.2.2 循环控制算法 321
6.2.3 并行设置算法 327
6.2.4 递归分治算法 335
6.2.5 改进的终端标记算法 341
6.2.6 一般控制算法 345
6.3 多级阻塞网络的路径控制算法 349
6.3.1 Ω网络的简化控制法 349
6.3.2 π网络的改进终端标记法 354
6.3.3 洗牌-交换网络多次通过实现任意置换的控制算法 357
参考文献 365
7.1 排序网络和互连网络 367
7.1.1 排序和互连网络的关系 367
第七章 排序和选择网络 367
7.1.2 排序网络的非自适应和非阻塞特性 368
7.1.3 用排序网络实现任意的互连函数 369
7.1.4 用洗牌交换函数构造排序网络 371
7.2 Batcher归并和排序网络 371
7.2.1 比较器网络和［0-1原理］ 371
7.2.2 Batcher奇-偶归并网络 376
7.2.3 Batcher双调归并网络 381
7.2.4 Batcher排序网络 386
7.3.1 布尔对称函数及其性质 392
7.3 布尔排序网络和Preparata枚举排序网络 392
7.3.2 布尔对称函数在分析和综合排序网络时的应用 396
7.3.8 Muller和Preparata的枚举排序网络 401
7.4 Ajtai O(nlogn)排序网络 404
7.4.1 Aitai排序网络的基本原理 404
7.4.2 扩展图 405
7.4.3 ε-对分和ε-准排序 407
7.4.4 寄存器的分配和划分 409
7.4.5 Ajtai算祛的形式描述 411
7.5 分组选择网络 412
7.5.1 次第选择和区分选择 412
7.5.2 分组原理在选择算法中的应用 414
7.5.3 分组选择网络 417
7.5.4 平衡分组选择网络 420
7.6 递归选择网络 425
7.6.1 分离原理在递归算法中的应用 425
7.6.2 关于选择网络边界值的研究 427
7.6.3 Yao的递归选择网络 430
7.6.4 平衡递归选择网络的工程设计 435
参考文献 441
第八章 互连网络的设计和应用 444
8.1 多级互连网络的图分析与设计法 444
8.1.1 多级互连网络的图模型 444
8.1.2 多级互连网络的图分析法 447
3.1.3 多级互连网络的图设计法 453
8.2 开关元件的设计与实现 455
8.2.1 2×2交换开关的设计与实现 455
8.2.2 4×4交叉开关的设计与实现 461
8.3 互连网络在数值运算中的应用 470
8.3.1 多项式计算 471
8.3.2 矩阵运算 472
8.3.3 快速傅里叶变换 477
8.4 互连网络在非数值运算中的应用 482
8.4.1 并行排序 482
8.4.2 图象数据的不规则展开与压缩 490
参考文献 492