具体描述
本书系统介绍并行程序设计原理及应用。除介绍常用的一些算法范例,包括分治、流水、同步计算、主从及工作池,还介绍了一些常用的经典数值和非数值算法,如排序、矩阵相乘、线性方程组求解、图像处理中的预处理和相应的变换、搜索和优化等。第2版新增了机群计算等使用机群的内容,对如何打造专用和通用的机群以及设置相应的程序设计环境做了较为详尽的介绍。章后包含大量习题,其中现实生活习题非常实用,既可增强学习兴趣,又可提高并行程序设计技巧。
本书可作为高等院校计算机专业高年级本科生或研究生的教材,对从事高性能计算的科技工作者也是一本很有价值的参考书。
作者简介
目录信息
第1章 并行计算机 2
1.1 对计算速度的需求 2
1.2 提高计算速度的潜力 4
1.2.1 加速系数 4
1.2.2 什么是最大的加速比 5
1.2.3 消息传递计算 9
1.3 并行计算机的类型 9
1.3.1 共享存储器多处理机系统 10
1.3.2 消息传递多计算机 11
1.3.3 分布式共享存储器 17
1.3.4 MIMD和SIMD的分类 17
1.4 机群计算 18
1.4.1 以互联计算机作为计算平台 18
1.4.2 机群的配置 23
1.4.3 打造“Beowulf风格”的专用机群 26
1.5 小结 27
推荐读物 27
参考文献 28
习题 30
第2章 消息传递计算 31
2.1 消息传递程序设计基础 31
2.1.1 编程的选择 31
2.1.2 进程的创建 31
2.1.3 消息传递例程 33
2.2 使用计算机机群 37
2.2.1 软件工具 37
2.2.2 MPI 37
2.2.3 伪代码构造 44
2.3 并行程序的评估 45
2.3.1 并行执行时间方程式 45
2.3.2 时间复杂性 48
2.3.3 对渐近分析的评注 50
2.3.4 广播/集中的通信时间 50
2.4 用经验方法进行并行程序的调试和评估 51
2.4.1 低层调试 52
2.4.2 可视化工具 52
2.4.3 调试策略 53
2.4.4 评估程序 53
2.4.5 对优化并行代码的评注 55
2.5 小结 55
推荐读物 55
参考文献 56
习题 57
第3章 易并行计算 59
3.1 理想的并行计算 59
3.2 易并行计算举例 60
3.2.1 图像的几何转换 60
3.2.2 曼德勃罗特集 64
3.2.3 蒙特卡罗法 69
3.3 小结 73
推荐读物 73
参考文献 73
习题 74
第4章 划分和分治策略 79
4.1 划分 79
4.1.1 划分策略 79
4.1.2 分治 82
4.1.3 M路分治 86
4.2 分治技术举例 87
4.2.1 使用桶排序法排序 87
4.2.2 数值积分 91
4.2.3 N体问题 93
4.3 小结 96
推荐读物 97
参考文献 97
习题 98
第5章 流水线计算 104
5.1 流水线技术 104
5.2 流水线应用的计算平台 107
5.3 流水线程序举例 107
5.3.1 数字相加 108
5.3.2 数的排序 110
5.3.3 生成质数 112
5.3.4 线性方程组求解—特殊个例 114
5.4 小结 117
推荐读物 117
参考文献 117
习题 117
第6章 同步计算 122
6.1 同步 122
6.1.1 障栅 122
6.1.2 计数器实现 123
6.1.3 树实现 124
6.1.4 蝶形障栅 125
6.1.5 局部同步 126
6.1.6 死锁 126
6.2 同步计算 127
6.2.1 数据并行计算 127
6.2.2 同步迭代 129
6.3 同步迭代程序举例 130
6.3.1 用迭代法解线性方程组 130
6.3.2 热分布问题 135
6.3.3 细胞自动机 142
6.4 部分同步方法 143
6.5 小结 144
推荐读物 144
参考文献 144
习题 145
第7章 负载平衡与终止检测 151
7.1 负载平衡 151
7.2 动态负载平衡 152
7.2.1 集中式动态负载平衡 152
7.2.2 分散式动态负载平衡 153
7.2.3 使用线形结构的负载平衡 155
7.3 分布式终止检测算法 157
7.3.1 终止条件 157
7.3.2 使用确认消息实现终止 158
7.3.3 环形终止算法 158
7.3.4 固定能量分布式终止算法 160
7.4 程序举例 160
7.4.1 最短路径问题 160
7.4.2 图的表示 161
7.4.3 图的搜索 162
7.5 小结 166
推荐读物 166
参考文献 167
习题 168
第8章 共享存储器程序设计 172
8.1 共享存储器多处理机 172
8.2 说明并行性的构造 173
8.2.1 创建并发进程 173
8.2.2 线程 175
8.3 共享数据 178
8.3.1 创建共享数据 179
8.3.2 访问共享数据 179
8.4 并行程序设计语言和构造 185
8.4.1 并行语言 185
8.4.2 并行语言构造 186
8.4.3 相关性分析 187
8.5 OpenMP 189
8.6 性能问题 193
8.6.1 共享数据的访问 193
8.6.2 共享存储器的同步 195
8.6.3 顺序一致性 196
8.7 程序举例 199
8.7.1 使用UNIX进程的举例 199
8.7.2 使用Pthread的举例 201
8.7.3 使用Java的举例 203
8.8 小结 204
推荐读物 205
参考文献 205
习题 206
第9章 分布式共享存储器系统及其程序设计 211
9.1 分布式共享存储器 211
9.2 分布式共享存储器的实现 212
9.2.1 软件DSM系统 212
9.2.2 DSM系统的硬件实现 213
9.2.3 对共享数据的管理 214
9.2.4 基于页面系统的多阅读器/单写入器策略 214
9.3 在DSM系统中实现一致性存储器 214
9.4 分布式共享存储器的程序设计原语 216
9.4.1 进程的创建 216
9.4.2 共享数据的创建 216
9.4.3 共享数据的访问 217
9.4.4 同步访问 217
9.4.5 改进性能的要点 217
9.5 分布式共享存储器的程序设计 219
9.6 实现一个简易的DSM系统 219
9.6.1 使用类和方法作为用户接口 220
9.6.2 基本的共享变量实现 220
9.6.3 数据组的重叠 222
9.7 小结 224
推荐读物 224
参考文献 224
习题 225
第二部分 算法和应用
第10章 排序算法 230
10.1 概述 230
10.1.1 排序 230
10.1.2 可能的加速比 230
10.2 比较和交换排序算法 231
10.2.1 比较和交换 231
10.2.2 冒泡排序与奇偶互换排序 233
10.2.3 归并排序 236
10.2.4 快速排序 237
10.2.5 奇偶归并排序 239
10.2.6 双调谐归并排序 240
10.3 在专用网络上排序 243
10.3.1 二维排序 243
10.3.2 在超立方体上进行快速排序 244
10.4 其他排序算法 247
10.4.1 秩排序 248
10.4.2 计数排序 249
10.4.3 基数排序 250
10.4.4 采样排序 252
10.4.5 在机群上实现排序算法 253
10.5 小结 253
推荐读物 254
参考文献 254
习题 255
第11章 数值算法 258
11.1 矩阵回顾 258
11.1.1 矩阵相加 258
11.1.2 矩阵相乘 258
11.1.3 矩阵-向量相乘 259
11.1.4 矩阵与线性方程组的关系 259
11.2 矩阵乘法的实现 259
11.2.1 算法 259
11.2.2 直接实现 260
11.2.3 递归实现 262
11.2.4 网格实现 263
11.2.5 其他矩阵相乘方法 266
11.3 求解线性方程组 266
11.3.1 线性方程组 266
11.3.2 高斯消去法 266
11.3.3 并行实现 267
11.4 迭代方法 269
11.4.1 雅可比迭代 269
11.4.2 快速收敛方法 272
11.5 小结 274
推荐读物 275
参考文献 275
习题 276
第12章 图像处理 279
12.1 低层图像处理 279
12.2 点处理 280
12.3 直方图 281
12.4 平滑、锐化和噪声消减 281
12.4.1 平均值 281
12.4.2 中值 283
12.4.3 加权掩码 284
12.5 边缘检测 285
12.5.1 梯度和幅度 285
12.5.2 边缘检测掩码 286
12.6 霍夫变换 288
12.7 向频域的变换 290
12.7.1 傅里叶级数 291
12.7.2 傅里叶变换 291
12.7.3 图像处理中的傅里叶变换 292
12.7.4 离散傅里叶变换算法的并行化 294
12.7.5 快速傅里叶变换 296
12.8 小结 300
推荐读物 300
参考文献 300
习题 302
第13章 搜索和优化 305
13.1 应用和技术 305
13.2 分支限界搜索 306
13.2.1 顺序分支限界 306
13.2.2 并行分支限界 307
13.3 遗传算法 308
13.3.1 进化算法和遗传算法 308
13.3.2 顺序遗传算法 310
13.3.3 初始种群 310
13.3.4 选择过程 312
13.3.5 后代的生成 312
13.3.6 变异 314
13.3.7 终止条件 314
13.3.8 并行遗传算法 314
13.4 连续求精 317
13.5 爬山法(hill climbing) 318
13.5.1 银行业务应用问题 319
13.5.2 爬山法在金融业务中的应用 320
13.5.3 并行化 321
13.6 小结 321
推荐读物 321
参考文献 322
习题 323
附录A 基本的MPI例程 329
附录B 基本的Pthread例程 335
附录C OpenMP命令、库函数以及
环境变量 339
索引 347
· · · · · · (收起)
读后感
用户评价
这本书给我的感觉是非常“硬核”和“实用”的。从目录上看,它应该涵盖了从单机多线程到分布式系统的各种并行计算模式。我最感兴趣的是关于“并行设计模式”的那部分,这就像是一种解决常见并行编程问题的“套路”,能够大大提高开发效率,避免重复造轮子。比如,像MapReduce、Actor模型这样的经典模式,书中肯定会进行详细的介绍和分析,并提供相应的代码实现。此外,关于“并行化策略”的讨论,也应该非常有价值,比如如何判断一个问题是否适合并行化,以及应该选择哪种并行化方法。书中对各种并行编程接口和框架的介绍,比如OpenMP、MPI、CUDA等,可能也会非常详尽,并且会对比它们的特点和适用范围。这对于我们选择合适的工具来解决实际问题非常有帮助。我预感书中会对“错误处理与容错机制”在并行系统中的重要性进行强调,因为在分布式环境下,任何一个节点的故障都可能影响整个系统的运行,如何设计健壮的容错机制是关键。这本书应该是那种你遇到具体问题时,翻开来就能找到答案,并且能够学到更深层次的解决方案的工具书。
不得不说,这本书的语言风格非常沉稳,读起来有一种踏实感。从章节的标题和内容简介来看,它应该着重于“并行算法分析”和“性能调优”的深度挖掘。我个人非常期待书中关于“并行算法的复杂度分析”的部分,这有助于我们更科学地评估不同算法的效率,并在实际应用中做出最优选择。同时,对于“线程安全与数据竞争”的深入剖析,也绝对是这本书的亮点,这关系到程序的正确性和稳定性。我猜书中会列举很多常见的“并发陷阱”,并提供详细的讲解和避免方法。而且,关于“利用GPU进行并行计算”的章节,应该会非常具有吸引力,这代表了当前并行计算的前沿方向,掌握这方面的知识能够极大地提升计算能力。这本书应该会引导读者从宏观的设计思维,到微观的底层优化,全方位地掌握并行程序设计。它不仅仅是一本技术手册,更像是一次对并行计算世界深邃探索的指引,让我对未来的编程方向有了更清晰的认识,并且充满了学习的动力。
这本书的封面设计倒是挺吸引人的,那种抽象的、流动的线条,让人一下子就联想到了信息的快速传递和多维度的展开。封面上“并行程序设计”几个字,虽然朴实无华,但却有一种莫名的力量感,好像真的能把那些原本杂乱无章的代码,瞬间变得井然有序,而且效率倍增。我翻了一下目录,里面的章节标题都很专业,像“多线程同步机制”、“分布式内存模型”、“并发数据结构”等等,听起来就很高深。我猜这本书应该会很深入地讲解各种并行编程的技术和算法,而且很有可能会包含大量的代码示例,帮助我们理解那些抽象的概念。比如,讲到线程同步的时候,可能会详细介绍各种锁的类型、信号量的使用,以及它们在实际场景中的应用。还有分布式内存模型,这部分听起来就很有挑战性,肯定会涉及如何有效地在多台机器之间协调和通信,解决数据一致性和同步的问题。我个人对这方面一直很好奇,总觉得未来的计算都离不开并行和分布式,而这本书好像就是打开这扇大门的钥匙。虽然我目前还没有机会深入阅读,但仅仅从目录和封面给我的初步印象来看,这绝对是一本值得认真研究的技术书籍,而且可能会对我的编程思路产生一些颠覆性的影响。
读完之后,这本书给我留下的最深刻印象就是其系统性和前瞻性。作者似乎非常注重从基础概念出发,循序渐进地构建起整个并行程序设计的知识体系。比如,在讲解多核处理器的基本原理时,就详细阐述了缓存一致性、内存模型等底层机制,这为后续理解更复杂的并发问题打下了坚实的基础。我个人很欣赏书中对“并发通信与同步”的细致分析,这里面涉及到各种协调机制,像消息传递、共享内存等,以及它们各自的优缺点和适用场景。而且,作者还花了相当大的篇幅来探讨“并行程序的可伸缩性”问题,这是一个非常实际且关键的考量因素,即随着处理器数量的增加,程序的性能能否相应地提升。这需要考虑很多因素,比如通信开销、负载均衡等等。我感觉这本书不仅仅是教你如何写出能运行的并行程序,更重要的是让你理解“为什么”要这样做,以及如何写出“高效”的并行程序。里面应该有很多关于如何避免死锁、活锁等常见并发问题的解决方案,以及如何进行并行程序的调试和测试,这些都是实践中非常重要的技能。这本书就像一位经验丰富的导师,能够引领读者深入理解并行程序设计的精髓。
拿到这本书的时候,我首先注意到它的装帧质量,纸张厚实,印刷清晰,那种沉甸甸的手感就让人觉得内容一定分量十足。书的整体风格非常严谨,从章节的逻辑编排到内容的深度,都透露出作者在并行程序设计领域的深厚功底。我尝试性地翻阅了几页,发现里面对一些经典并行算法的讲解非常到位,比如并行排序、并行搜索等,而且还分析了它们在不同硬件架构下的性能表现。我尤其关注书中关于“任务分解与调度”的部分,这应该是并行程序设计的核心之一,如何将一个大的问题拆分成若干个可以同时执行的小任务,并且有效地分配到不同的处理器上,这需要精妙的设计和策略。这本书的叙述方式应该偏向于理论与实践相结合,既有严谨的理论推导,又不乏实际的应用案例,这对于我们这些希望将理论知识转化为实际项目能力的读者来说,是非常宝贵的。我特别期待书中关于“性能优化与瓶颈分析”的内容,在并行编程中,性能的提升往往是最终目的,如何识别并解决程序中的性能瓶颈,让并行计算发挥出最大的效能,这绝对是重中之重。这本书的出现,无疑为想要深入理解并行计算的读者提供了一本权威的参考书。
相对偏理论
相对偏理论
相对偏理论
相对偏理论
相对偏理论