第1章 绪论 1
1.1 并行计算机的发展概况 1
1.2 并行性与并行处理技术 2
1.2.1 并行性概念 2
1.2.2 并行处理的技术途径 3
1.2.3 并行处理系统的分类 5
1.3 计算机系统结构的分类 7
1.3.1 Flynn分类法 7
1.3.2 Feng分类法 7
1.3.3 H？ndler分类法 8
1.3.4 按基本结构特征分类法 8
1.4 并行计算模型 9
1.4.1 算法与并行算法的概念 9
1.4.2 算法复杂性的概念 10
1.4.3 并行计算模型 14
第2章 互连网络的拓扑与互连函数 17
2.1 预备知识 17
2.1.1 图论术语与记号 17
2.1.2 二进制串及其运算 20
2.2 互连网络及其性能指标 21
2.2.1 互连网络概念 21
2.2.2 互连网络的性能指标 22
2.3 网络的互连函数 23
2.3.1 互连函数的概念 23
2.3.2 常见的互连函数 24
2.4 静态互连网络 29
2.4.1 线性阵列 29
2.4.2 环形网 30
2.4.3 全连接网 31
2.4.4 星形网 31
2.4.5 网格形网 32
2.4.6 树形网 33
2.4.7 总线形网 35
2.4.8 立方体形网 37
2.5 动态互连网络 38
2.5.1 单级互连网络 38
2.5.2 多级互连网络 41
第3章 立方形递归网络 44
3.1 基本概念 44
3.1.1 立方形递归邻接函数 44
3.1.2 立方形递归网络 46
3.2 常见立方形递归网络 46
3.2.1 超立方体 46
3.2.2 扭n－立方体 48
3.2.3 M？bius立方体 49
3.2.4 交叉立方体 51
3.2.5 扭立方体连接网络 52
3.3 常见立方形递归网络的等价定义 53
3.3.1 关于超立方体 53
3.3.2 关于扭n－立方体 54
3.3.3 关于M？bius立方体 56
3.3.4 关于交叉立方体 57
3.3.5 关于扭立方体连接网络 60
3.4 立方形递归网络的等价定义 60
3.4.1 低维立方形递归网络的拓扑类型 60
3.4.2 立方形递归邻接函数的一般形式 61
3.4.3 立方形递归网络的等价定义 62
第4章 立方形递归网络的参数与拓扑特性 64
4.1 正则性与连通度 64
4.1.1 正则性 64
4.1.2 连通度 65
4.2 子网与超网 67
4.2.1 子网 67
4.2.2 子网的邻接关系与超网 68
4.3 结构的递归性 69
4.3.1 超立方体的结构递归性 69
4.3.2 扭n－立方体的结构递归性 72
4.3.3 M？bius立方体的结构递归性 74
4.3.4 交叉立方体的结构递归性 75
4.3.5 扭立方体连接网络的结构递归性 82
4.4 直径 90
4.4.1 超立方体的直径 91
4.4.2 扭n－立方体的直径 91
4.4.3 M？bius立方体的直径 92
4.4.4 扭立方体连接网络的直径 97
4.4.5 交叉立方体的直径 100
4.5 （扭）立方体子图的存在性 101
4.5.1 扭3－立方体子图的存在性 102
4.5.2 3－立方体子图的存在性 103
4.5.3 扭立方体连接网络的无立方体子图性 103
第5章 立方形递归网络上的算法 109
5.1 路由算法 109
5.2 几种特定网络上的路由算法 113
5.2.1 超立方体上的路由算法 113
5.2.2 扭n－立方体上的路由算法 113
5.2.3 M？bius立方体上的路由算法 115
5.2.4 交叉立方体上的路由算法 119
5.2.5 扭立方体连接网络上的路由算法 122
5.3 广播算法 126
5.3.1 单端口I/O广播算法 126
5.3.2 多端口I/O广播算法 128
5.4 半群运算 131
第6章 立方形递归网络中图的嵌入与容错指标 134
6.1 图的嵌入及其相关概念 134
6.2 线性阵列与环的嵌入 136
6.2.1 基本概念与基本结论 137
6.2.2 超立方体中的圈 139
6.2.3 扭n－立方体的几乎泛圈性 140
6.2.4 交叉立方体的几乎泛圈性 141
6.2.5 扭立方体连接网络的几乎泛圈性 145
6.2.6 M？bius立方体中的圈 150
6.3 网格的嵌入 151
6.3.1 超立方体中网格的嵌入 151
6.3.2 扭n－立方体中网格的嵌入 154
6.3.3 扭立方体连接网络中网格的嵌入 155
6.4 树的嵌入 157
6.4.1 二项树的嵌入 157
6.4.2 完全二叉树的嵌入 159
6.5 超立方体的嵌入 169
6.5.1 扭n－立方体中的超立方体子图 169
6.5.2 扭立方体连接网络中超立方体的嵌入问题 169
6.5.3 其他网络中超立方体子图的存在性问题 177
6.6 顶点容错度和边容错度 177
6.7 故障直径 179
6.7.1 基本概念 179
6.7.2 超立方体的故障直径 180
6.7.3 交叉立方体的故障直径 182
6.7.4 扭立方体连接网络的故障直径 184
参考文献 188