第一章 并行计算模型与并行算法设计 1
1.1 引言 1
1.2 PRAM并行计算模型 5
1.2.1 SIMD共享存储器PRAM并行计算模型(SIMD-PRAM) 6
1.2.2 MIMD共享存储器PRAM并行计算模型(MIMD-PRAM) 8
1.2.3 SIMD-PRAM和MIMD-PRAM算法设计举例 10
1.3 一种符合实际的并行计算模型——LogP 15
1.3.1 技术推动 16
1.3.2 LogP模型 18
1.3.3 算法设计 23
1.3.4 模型与并行机的匹配 28
1.3.5 LogP与PRAM模型的比较 31
1.4 其它并行计算模型 33
1.4.1 分布存储器多处理机体系结构的特点 35
1.4.2 分布存储器多处理机算法设计的特点 38
1.4.3 分布存储器多处理机中算法设计、分析的一般方法和原则 38
1.4.4 算法设计与分析举例 39
第二章 阵列和树 45
2.1 基本概念 45
2.1.1 阵列与树模型基本概念 46
2.1.2 固定连接网络的基本性质 49
2.1.3 算法性能评价准则 50
2.1.4 有关固定连接网络上并行算法的时间下界 53
2.1.5 一个示例——计数分类 54
2.2 整数运算 60
2.2.1 超前进位加法 60
2.2.2 并行前缀计算 63
2.2.3 进位保留加法 67
2.2.4 乘法与卷积 70
2.2.5 除法 76
2.3 矩阵运算 78
2.3.1 矩阵乘法 78
2.3.2 三角矩阵算法 83
2.3.3 三对角矩阵算法 87
2.3.4 高斯消去法 93
2.3.5 迭代法 98
2.4 分类算法 104
2.4.1 线性阵列上分类算法 105
2.4.2 奇偶比较交换分类 113
2.4.3 两种快速网格分类算法 115
2.4.4 网格分类算法的一个时间下界 120
2.5 数据包路由选择算法 121
2.5.1 贪心法 122
2.5.2 贪心法平均效能分析 128
2.5.3 随机路由选择算法 137
2.5.4 小队列确定型路由选择算法 141
2.5.5 其它路由选择算法 144
2.6 高维阵列 147
2.6.1 定义与性质 147
2.6.2 矩阵乘法 149
2.6.3 分类算法 151
2.6.4 数据包路由选择算法 153
2.6.5 低维阵列模拟高维阵列 154
第三章 树网 160
3.1 二维树网 160
3.1.1 定义和性质 160
3.1.3 N×N树网可看作完全二分图KN×N的近似 162
3.1.2 N×N树网的递归分解 162
3.1.4 N×N树网的变形 163
3.2 三维树网和高维树网 165
3.2.1 三维树网的定义和性质 165
3.2.2 高维树网的定义和性质 166
3.3 二维树网上一些基本算法的实现 167
3.3.1 路由选择 167
3.3.2 分类 168
3.3.3 矩阵向量乘 169
3.3.4 Jacobi迭代 169
3.3.5 高斯主元消去法 170
3.3.6 卷积 171
3.3.7 整数运算 173
3.3.8 图论算法 178
3.4 三维树网上一些基本算法的实现 183
3.4.1 矩阵乘法 183
3.4.2 求下三角矩阵的逆 183
3.4.3 求任意矩阵的逆 186
3.4.4 相关问题 189
第四章 超立方体网络 193
4.1 定义与性质 193
4.2 阵列在超立方体网络中的嵌入 195
4.2.1 高维阵列在超立方体中的嵌入 197
4.2.2 完全二叉树在超立方体中的嵌入 202
4.3 树网在超立方体中的嵌入 205
4.3.1 稍微修改树网结构使之成为超立方体子图 205
4.3.2 算法的直接映射 206
4.4 任意树在超立方体中的嵌入 208
5.1 蝶网、CCC网与Beněs网 215
第五章 超立方体类型网络 215
5.1.1 定义与性质 216
5.1.2 蝶网对任意网络的模拟 226
5.1.3 蝶网对正规超立方体算法的模拟 228
5.1.4 其它模拟结果 230
5.2 混洗交换网和de Bruijn网 235
5.2.1 定义与性质 235
5.2.2 混洗交换网和de Bruijn网与超立方体的相似性 244
5.2.3 混洗交换网和de Bruijn网与蝶网的相似性 247
5.3 其它超立方体类型网络 257
5.3.1 蝶网类型网络 258
5.3.2 De Bruijn类型网络 265
第六章 超立方体类型网络上基本算法的实现 269
6.1 Diaconis扑克牌游戏 269
6.2 数据包路由选择算法 275
6.2.1 路由选择模型定义 276
6.2.2 贪心路由选择算法 277
6.2.3 包装、分散和单调路由选择问题 282
6.2.4 贪心路由选择算法在一般情形下的性能分析 289
6.2.5 将最坏情形的路由选择问题转变为一般情形的路由选择问题 303
6.2.6 限制申请队列的长度 308
6.2.7 合并路由选择 318
6.2.8 路由选择中的消息分散方法 320
6.3 分类算法 329
6.3.1 奇偶归并分类算法 330
6.3.2 小集合分类算法 335
6.4 快速傅里叶变换(FFT) 340
6.4.1 快速傅里叶变换(FFT)算法 340
6.4.2 FFT算法在蝶网上的实现 342
6.4.3 FFT算法在卷积与多项式运算中的应用 346