本书由德国约翰内斯·古腾堡大学并行和分布式架构团队撰写，对并行编程的高级主题进行了深入讨论，除了涵盖基础概念外，还讲授了共享内存和分布式内存体系结构的实用编程技巧。作者提供了一套进行自动代码评估的开源系统，可方便地访问并行计算资源，这也使得本书特别适合于课堂教学。

针对共享内存和分布式内存体系结构，全面提升并行编程能力
涵盖C++11线程API、OpenMP、CUDA、MPI、UPC++等主题，关注算法及其性能
提供免费的Web实验工具，提升教学效率
Parallel Programming: Concepts and Practice
并行程序设计
概念与实践
[ 德 ] 贝蒂尔·施密特（Bertil Schmidt）
[ 西 ] 豪尔赫·冈萨雷斯-多明格斯（Jorge Gonzá lez-Domínguez）
[ 德 ] 克里斯蒂安·洪特（Christian Hundt）著
[ 德 ] 莫里茨·施拉布（Moritz Schlarb）

　　　 张常有 吴长茂 解庆春　　译

并行无处不在！如今，任意一款现代CPU都至少包含2个核心，一些CPU甚至配置了超过50个处理单元。对于有多个CPU的更大的系统，比如多个服务器节点、计算机集群、超级计算机等，它们甚至能够获得更高的并行度。因此，对于科学家、工程师、程序员来说，必须具备在这类系统上直接高效编写程序的能力。本书的主题是全面介绍并行编程领域的知识，以满足上述需求。本书针对共享内存和分布式内存体系结构讲解了实用的并行编程方法，包括C++11线程API、OpenMP、CUDA、MPI、UPC++，以及必不可少的理论背景。本书还提供大量的编程实例，它们基于C++编程语言针对多线程特性的扩展版本C++11和C++14。
本书以“并行编程”或者“高性能计算”两门课程的学生为目标读者。在计算机科学专业或计算机工程专业，很多大学都为高年级本科生或者研究生开设了这两门课程。此外，本书还适合用作其他学科学生在辅修计算机科学时的教材，或者用作相关领域专业人员的参考资料，譬如研究科学家、数据分析师或研发工程师等。理解本书内容需要有编写C/C++串行代码的经验，并具备基本的数学知识。
高性能计算和自然科学之间历来有良好的共生关系，我们将基于真实应用讲述并行概念。这些应用包括：基本线性代数例程、机器学习算法，以及物理模拟和计算机科学领域中的传统算法。编写正确而高效的代码是每一位程序员的关键技能，因此我们关注算法的真正实现和性能评估。尽管如此，我们还是深入讨论了算法的理论特性。每章都有一组附加的编程练习，可在本书配套的Web框架中完成这些练习。自动代码评估系统（System for Automated Code Evaluation，SAUCE）为提交解答方案和后续的课堂讲解提供了一个基于Web的测试环境。仅需的前提条件是一个与HTML5兼容的Web浏览器，以支持嵌入课堂教学的交互编程练习。SAUCE已经以docker镜像发布，可在下列网站下载：
https://parallelprogrammingbook.org
该网站汇集了本书相关的在线资源，比如安装指南、勘误表、附加材料（如课件、针对教师精选的部分练习答案）等。
如果你是一名学生或者专业人士，目标是学习编程技术，那么我们建议你首先阅读前3章，从并行编程基础、理论模型、硬件体系结构开始。然后，你就可以深入学习C++11多线程、OpenMP、CUDA或MPI中的任意一章。这些都是介绍性章节，内容几乎自成体系。关于高级C++11多线程、高级CUDA和UPC++的内容依赖前导章节中的技术，所以不能独立阅读。
如果你是一名教师，我们推荐一套包含14讲的授课体系，大体上覆盖了介绍性章节中提到的全部应用程序。你可以从第1章开始，第1讲讨论基础知识，包括利用超立方体并行求和的算法及其分析、基本度量标准（如加速比、并行效率、开销等）以及对排名指标的讨论等。第2讲应该包括PRAM、网络拓扑、强弱可扩展性等。如果将来想详细讨论CUDA，或者重点强调CPU的硬件体系结构，可以在PRAM上分配更多时间。可以用2～3讲的时间讲解C++11线程API、CUDA、MPI方面的基础知识。OpenMP相关内容可以分配1～2讲的时间。剩余时间可以选择讨论多线程、CUDA或者基于PGAS的UPC++语言等高级章节的相关内容。
另外一种可选的方法是，把本书内容分成两门课程，重点放在课堂上的“结对编程”。第一门课可以从基于CPU的并行编程技术开始，涵盖从前3章中选定的主题。这样，C++11多线程、OpenMP、MPI就能够讲解得足够细致。第二门课将侧重于高级并行方法，包括CUDA感知的MPI或基于PGAS的UPC++等技术相结合的扩展CUDA编程。
希望本书陪伴你度过快乐时光。充满活力，探索代码！最后，我们将非常高兴能收到你的任何反馈，以便帮助我们尽可能完善本书相关内容。

计算机\并行计算

并行无处不在！任意一款现代CPU都至少包含两个核心，几乎人手一部的智能手机都配备了多核CPU与异构加速器。因此，对于工程师和程序员而言，学会在这类系统上直接高效编写程序，成为必须具备的重要技能。

本书针对共享内存和分布式内存两种体系结构，介绍了实用的并行编程方法，涵盖C++11线程API、OpenMP、CUDA、MPI、UPC++等内容，既包含基础概念，也提供大量的编程实例和编程工具。

本书特色：
·搭建从概念到实践的桥梁。基于实际应用讲授理论知识，包括基本线性代数例程、机器学习算法、物理模拟等，关注算法的实现和性能评估。
·配备便于教学的实验工具。SAUCE（自动代码评估系统）是专为本书而开发的基于Web的测试环境，便于读者完成章末练习或实现交互编程。
·提供不同侧重的学习路线。无论是高校学生还是企业技术人员，均可从相对独立的介绍性章节开始阅读，然后根据各自需求进阶高级内容。

本书的作者Bertil Schmidt是德国美因茨约翰内斯·古腾堡大学并行与分布式架构领域的终身全职教授和首席教授。此前，他曾是南洋理工大学（新加坡）和新南威尔士大学（UNSW）的教师。在本书中，作者结合大量编程实例，讲述了他对并行计算概念和编程方法的独到理解，分享了基于Web的并行代码自动评估工具。
如今，并行计算无处不在。任意一款现代CPU都至少包含2个核心，几乎人手一部的智能手机都配备了多核CPU与异构加速器。高性能计算机已经广泛用于工业、农业、服务业、科研教育等行业。因此，学会在这类系统上直接高效编写程序，成为工程师、科学家等必须具备的重要能力。本书针对共享内存和分布式内存两种体系结构，介绍了实用的并行编程方法，包括C++11线程API、开放式多重处理（Open Multiprocessing，OpenMP）、统一计算设备架构（Compute Unified Device Architecture，CUDA）、消息传递接口（Message Passing Interface，MPI）、统一并行C++（Unified Parallel C++，UPC++），以及必不可少的理论背景。另外，还提供了大量的编程实例和实用编程工具。
本书非常适合用作并行计算/编程方面的教材，也适合用作相关课程的参考资料。本书的内容分为并行编程基础和高级并行编程两部分，教师可根据学生的专业基础和学习目标，适当筛选部分内容讲授。本书也很适合用作相关领域专业人员的参考资料，譬如研究科学家、数据分析师或研发工程师等，因为书中自带的并行实例和源代码都可以用作并行程序的范例，成为并行算法开发的初始版本。阅读本书内容需要的预备知识主要有编写C/C++串行代码的经验，以及基本的数学知识。
张常有、吴长茂、解庆春是本书翻译工作的主要组织者。张常有博士现任中国科学院软件研究所并行软件与计算科学实验室研究员，主要负责第1章到第5章以及前言的翻译；吴长茂博士现任中国科学院软件研究所并行软件与计算科学实验室副研究员，负责第6章、第9章、第10章的翻译；解庆春博士现任新思科技（中国）公司高级工程师，曾任AMD异构计算高级工程师，负责第7章和第8章的翻译；张常有负责全书的统稿审校。
我们的一致想法是，通过理解作者的思想，融入译者的经验，结合汉语表达特点和习惯，尽力保持本书的可读性。希望它的出版能够帮助读者结合并行编程实践，深入理解并行计算概念，建立并行计算思想，并顺利应用于各自从事的工作领域。
感谢许多同行学者的协助。肖娇娇、李良燕、石琳、薄文、孟繁堃、蔡晓峰、段磊等参与了本书不同章节的代码测试与文字校对工作，感谢他们在翻译过程中的贡献。
由于时间仓促，加之译者水平有限，书中错误和不准确之处在所难免。敬请广大读者指正。译者邮箱：changyou@iscas.ac.cn。

译者
于北京（中国科学院软件园区）

译者序
前言
致谢
第1章　绪论 1
1.1　一个有趣的例子及其分析 2
1.2　并行计算基础 10
1.2.1　分布式内存系统 10
1.2.2　共享内存系统 11
1.2.3　并行程序设计需考虑的因素 13
1.3　HPC动态和排名 15
1.4　附加练习 17
第2章　理论背景 19
2.1　PRAM 20
2.1.1　PRAM变体 21
2.1.2　PRAM上的并行前缀计算 22
2.1.3　PRAM上稀疏数组的压缩算法 24
2.2　网络拓扑 25
2.3　Amdahl定律和Gustafson定律 29
2.4　Foster的并行算法设计方法学 34
2.5　附加练习 37
参考文献 40
第3章　现代体系结构 41
3.1　存储层次 42
3.1.1　冯·诺依曼瓶颈 42
3.1.2　高速缓冲存储器 43
3.1.3　缓存算法 44
3.1.4　优化缓存访问 45
3.1.5　高速缓存一致性 48
3.1.6　虚假共享 50
3.1.7　并发多线程技术和预取技术 50
3.1.8　展望 51
3.2　并行性的层次 51
3.2.1　Flynn分类法 51
3.2.2　SIMD概念 53
3.2.3　通用微处理器上的向量化 54
3.2.4　结构体数组和数组结构体 57
3.2.5　展望 63
3.3　附加练习 63
参考文献 67
第4章　C++多线程编程 68
4.1　多线程编程简介 69
4.1.1　多线程编程和多进程编程的区别 69
4.1.2　派生和并入线程 69
4.1.3　我们的第一个多线程程序 71
4.2　处理返回值 73
4.2.1　传统方法 74
4.2.2　使用promise和future的现代方法 75
4.2.3　异步方式 80
4.3　基于静态分发的调度机制 82
4.3.1　串行程序 83
4.3.2　线程的区块分发 87
4.3.3　线程的循环分发 90
4.3.4　虚假共享 91
4.3.5　线程的块循环分发 93
4.4　处理负载不平衡 95
4.4.1　静态调度 99
4.4.2　动态块循环分发 101
4.5　用条件变量通知线程 104
4.5.1　为一个睡觉的学生建模 105
4.5.2　使用条件变量 107
4.5.3　使用future和promise单发同步 108
4.6　隐式可数集合上的并行化 110
4.6.1　隐式可数集合 111
4.6.2　线程池用例 112
4.6.3　一个简单线程池的实现 114
4.7　附加练习 119
参考文献 121
第5章　高级C++11多线程编程 122
5.1　无锁编程 122
5.1.1　原子计数 123
5.1.2　非基本原子数据类型 124
5.1.3　利用比较交换以原子方式并行化最大值归约 126
5.1.4　任意原子操作 129
5.1.5　ABA问题 132
5.2　工作共享线程池 133
5.2.1　工作共享线程池的用例 133
5.2.2　工作共享的实现 135
5.3　并行图搜索 137
5.3.1　二元背包问题 138
5.3.2　串行实现 139
5.3.3　并行实现 144
5.4　展望 146
5.5　附加练习 148
参考文献 149
第6章　OpenMP 150
6.1　OpenMP简介 151
6.1.1　OpenMP简史 151
6.1.2　基础 151
6.2　parallel for制导语句 153
6.2.1　向量加法 154
6.2.2　变量共享和私有化 157
6.2.3　矩阵向量乘法 160
6.3　基本的并行归约 162
6.3.1　最近邻分类 162
6.3.2　手写数字数据集MNIST 163
6.3.3　完全配对距离计算的理论视角 164
6.3.4　完全配对计算的实现 165
6.3.5　并行标签预测 168
6.3.6　性能评测 169
6.4　不平衡循环调度 171
6.4.1　对称性引起的负载失衡 172
6.4.2　内积计算实现 173
6.4.3　性能评测 174
6.5　高级归约 175
6.5.1　MNIST数据集上的SOFTMAX回归分类器 175
6.5.2　定制归约操作符 183
6.5.3　OpenMP高级归约 187
6.6　任务并行 189
6.6.1　树遍历 190
6.6.2　循环中生成任务 193
6.7　SIMD向量化 193
6.7.1　数据依赖 195
6.7.2　向量化感知函数 196
6.8　展望 196
6.9　附加练习 197
参考文献 202
第7章　统一计算设备架构 203
7.1　CUDA简介 204
7.2　支持CUDA的GPU硬件架构 206
7.2.1　主机与设备之间的互连 206
7.2.2　显存和峰值宽度 207
7.2.3　计算资源的组织 207
7.3　内存访问模式 211
7.3.1　均值名人脸的计算 212
7.3.2　计算中心化的数据矩阵 218
7.3.3　计算协方差矩阵 221
7.3.4　计算特征脸 229
7.4　内存层次结构 232
7.4.1　问题简介 233
7.4.2　串行DTW的线性内存算法 237
7.4.3　线性内存DTW的一个初始CUDA移植 243
7.4.4　共享内存中的波前松弛 248
7.4.5　并发调度和bank冲突 253
7.4.6　纹理内存和常量内存 254
7.5　优化准则 257
7.6　附加练习 258
参考文献 259
第8章　高级CUDA编程 261
8.1　warp内联函数和原子操作 261
8.1.1　分段并行归约 262
8.1.2　全局并行归约 265
8.1.3　任意原子操作 267
8.1.4　展望 269
8.2　利用多块GPU和流 269
8.2.1　牛顿迭代 269
8.2.2　利用多块GPU 272
8.2.3　通信和计算交叉 274
8.2.4　多块GPU上的流式计算 278
8.3　展望 280
8.3.1　统一内存 280
8.3.2　动态并行性 281
8.3.3　协作组 281
8.3.4　张量核心 281
8.3.5　GPU集群上的分布式计算 282
8.4　附加练习 282
参考文献 284
第9章　MPI 286
9.1　MPI简介 286
9.2　基本概念 288
9.3　点到点通信 289
9.4　非阻塞通信 292
9.5　集合通信 295
9.6　计算通信重叠 300
9.7　派生数据类型 309
9.8　复杂通信域 315
9.9　展望 322
9.10　附加练习 322
参考文献 327
第10章　统一并行C++ 329
10.1　PGAS和UPC++简介 329
10.2　基本概念 331
10.3　内存亲和性和私有化 332
10.4　全局指针和集合函数 337
10.5　锁 343
10.6　远程函数调用 348
10.7　附加练习 355
参考文献 357