并行程序设计[按需印刷]

.1.5 提高计算速度的潜力21
1.6 小结26
推荐读物26
参考文献27
习题29
第2章 消息传递计算31
2.1 消息传递编程基础31
2.1.1 编程的选择31
2.1.2 进程的创建31
2.1.3 消息传递例程33
2.2 使用工作站集群38
2.2.1 软件工具38
2.2.2 pvm38
2.2.3 mpi43
2.2.4 伪代码构造49
2.3 并行程序的评估50
2.3.1 并行执行时间50
2.3.2 时间复杂性52
2.3.3 对渐近分析的评注55
2.3.4 广播/汇集的时间复杂性55
2.4 并行程序的调试和评估58
2.4.1 低层次调试58
2.4.2 可视化工具59
2.4.3 调试策略60
2.4.4 用经验方法评估程序60
2.4.5 对优化并行代码的评注62
2.5 小结63
推荐读物63
参考文献63
习题65
第3章 易并行计算67
3.1 理想的并行计算67
3.2 易并行计算举例68
3.2.1 图像的几何变换68
3.2.2 曼德勃罗特集72
3.2.3 蒙特卡罗法78
3.3 小结82
推荐读物82
参考文献82
习题83
第4章 划分和分治策略88
4.1 划分88
4.1.1 划分策略88
4.1.2 分治91
4.1.3 m路分治95
4.2 分治技术举例97
4.2.1 使用桶排序法排序97
4.2.2 数值积分100
4.2.3 n体问题103
4.3 小结107
推荐读物107
参考文献108
习题109
第5章 流水线计算114
5.1 流水线技术114
5.2 流水线应用的计算平台117
5.3 流水线程序举例118
5.3.1 数字相加118
5.3.2 数的排序120
5.3.3 生成质数123
5.3.4 线性方程组求解—特殊案例125
5.4 小结127
推荐读物128
参考文献128
习题128
第6章 同步计算132
6.1 同步132
6.1.1 路障132
6.1.2 计数器实现133
6.1.3 树实现135
6.1.4 蝶形路障136
6.1.5 局部同步136
6.1.6 死锁137
6.2 同步计算137
6.2.1 数据并行计算137
6.2.2 同步迭代140
6.3 同步迭代程序举例140
6.3.1 用迭代法解线性方程组140
6.3.2 热分布问题145
6.3.3 细胞自动机152
6.4 小结153
推荐读物153
参考文献154
习题154
第7章 负载平衡与终止检测160
7.1 负载平衡160
7.2 动态负载平衡161
7.2.1 集中式动态负载平衡162
7.2.2 分散式动态负载平衡163
7.2.3 使用线形结构的负载平衡165
7.3 分布式终止检测算法167
7.3.1 终止条件167
7.3.2 使用应答消息实现终止167
7.3.3 环形终止算法168
7.3.4 固定能量分布式终止算法170
7.4 程序举例170
7.4.1 最短路径问题170
7.4.2 图表示171
7.4.3 图的搜索172
7.5 小结177
推荐读物177
参考文献178
习题179
第8章 共享存储器编程184
8.1 共享存储器多处理机184
8.2 说明并行性的结构186
8.2.1 创建并发进程186
8.2.2 线程187
8.3 共享数据191
8.3.1 创建共享数据191
8.3.2 访问共享数据192
8.3.3 并行性的语言结构198
8.3.4 相关性分析199
8.3.5 具有高速缓存的系统中
的共享数据201
8.4 程序举例203
8.4.1 unix进程204
8.4.2 pthreads的例子206
8.4.3 java的例子208
8.5 小结209
推荐读物210
参考文献210
习题211
第二部分 算法和应用
第9章 排序算法216
9.1 概述216
9.1.1 排序216
9.1.2 可能的加速216
9.1.3 秩排序217
9.2 比较和交换排序算法219
9.2.1 比较和交换219
9.2.2 冒泡排序与奇偶互换排序221
9.2.3 二维排序224
9.2.4 归并排序226
9.2.5 快速排序228
9.2.6 超立方体上的快速排序230
9.2.7 奇偶归并排序234
9.2.8 双调谐归并排序235
9.3 小结238
推荐读物239
参考文献239
习题240
第10章 数值算法243
10.1 矩阵—回顾243
10.1.1 矩阵相加243
10.1.2 矩阵相乘243
10.1.3 矩阵－向量相乘244
10.1.4 矩阵与线性方程组的关系244
10.2 矩阵乘法的实现244
10.2.1 算法244
10.2.2 直接实现246
10.2.3 递归实现248
10.2.4 网格实现249
10.2.5 其他矩阵相乘方法252
10.3 求解线性方程组253
10.3.1 线性方程组253
10.3.2 高斯消去法253
10.3.3 并行实现254
10.4 迭代方法256
10.4.1 雅可比迭代256
10.4.2 快速收敛方法260
10.5 小结263
推荐读物263
参考文献264
习题265
第11章 图像处理268
11.1 低层图像处理268
11.2 点处理269
11.3 直方图270
11.4 平滑、锐化和噪声消减270
11.4.1 平均值271
11.4.2 中值272
11.4.3 加权掩码274
11.5 边缘检测275
11.5.1 梯度和幅度275
11.5.2 边缘检测掩码276
11.6 霍夫变换279
11.7 向频域的变换282
11.7.1 傅里叶级数282
11.7.2 傅里叶变换282
11.7.3 图像处理中的傅里叶变换283
11.7.4 离散傅里叶变换算法的并行化285
11.7.5 快速傅里叶变换287
11.8 小结293
推荐读物293
参考文献293
习题295
第12章 搜索和优化298
12.1 应用和技术298
12.2 分枝限界搜索299
12.2.1 顺序分枝限界299
12.2.2 并行分枝限界300
12.3 遗传算法301
12.3.1 进化算法和遗传算法301
12.3.2 顺序遗传算法303
12.3.3 初始种群303
12.3.4 选择过程305
12.3.5 后代的生成306
12.3.6 变异307
12.3.7 终止条件307
12.3.8 并行遗传算法308
12.4 连续求精311
12.5 爬山法311
12.5.1 银行业务应用问题312
12.5.2 爬山法在银行业务中的应用314
12.5.3 并行化315
12.6 小结315
推荐读物315
参考文献315
习题317
附 录
附录a 基本的pvm例程323
附录b 基本的mpi例程328
附录c 基本的pthread例程333
附录d 并行计算模型337
索引346