《面向结构的并行算法 设计与分析》求取 ⇩

第一章 并行计算模型与并行算法设计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 一种符合实际的并行计算模型——LogP15

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