并行程序设计：概念与实践

译者序
前言
致谢
第1章　绪论 1
11　一个有趣的例子及其分析 2
12　并行计算基础 10
121　分布式内存系统 10
122　共享内存系统 11
123　并行程序设计需考虑的因素 13
13　HPC动态和排名 15
14　附加练习 17
第2章　理论背景 19
21　PRAM 20
211　PRAM变体 21
212　PRAM上的并行前缀计算 22
213　PRAM上稀疏数组的压缩算法 24
22　网络拓扑 25
23　Amdahl定律和Gustafson定律 29
24　Foster的并行算法设计方法学 34
25　附加练习 37
参考文献 40
第3章　现代体系结构 41
31　存储层次 42
311　冯·诺依曼瓶颈 42
312　高速缓冲存储器 43
313　缓存算法 44
314　优化缓存访问 45
315　高速缓存一致性 48
316　虚假共享 50
317　并发多线程技术和预取技术 50
318　展望 51
32　并行性的层次 51
321　Flynn分类法 51
322　SIMD概念 53
323　通用微处理器上的向量化 54
324　结构体数组和数组结构体 57
325　展望 63
33　附加练习 63
参考文献 67
第4章　C++多线程编程 68
41　多线程编程简介 69
411　多线程编程和多进程编程的区别 69
412　派生和并入线程 69
413　我们的第一个多线程程序 71
42　处理返回值 73
421　传统方法 74
422　使用promise和future的现代方法 75
423　异步方式 80
43　基于静态分发的调度机制 82
431　串行程序 83
432　线程的区块分发 87
433　线程的循环分发 90
434　虚假共享 91
435　线程的块循环分发 93
44　处理负载不平衡 95
441　静态调度 99
442　动态块循环分发 101
45　用条件变量通知线程 104
451　为一个睡觉的学生建模 105
452　使用条件变量 107
453　使用future和promise单发同步 108
46　隐式可数集合上的并行化 110
461　隐式可数集合 111
462　线程池用例 112
463　一个简单线程池的实现 114
47　附加练习 119
参考文献 121
第5章　高级C++11多线程编程 122
51　无锁编程 122
511　原子计数 123
512　非基本原子数据类型 124
513　利用比较交换以原子方式并行化最大值归约 126
514　任意原子操作 129
515　ABA问题 132
52　工作共享线程池 133
521　工作共享线程池的用例 133
522　工作共享的实现 135
53　并行图搜索 137
531　二元背包问题 138
532　串行实现 139
533　并行实现 144
54　展望 146
55　附加练习 148
参考文献 149
第6章　OpenMP 150
61　OpenMP简介 151
611　OpenMP简史 151
612　基础 151
62　parallel for制导语句 153
621　向量加法 154
622　变量共享和私有化 157
623　矩阵向量乘法 160
63　基本的并行归约 162
631　最近邻分类 162
632　手写数字数据集MNIST 163
633　完全配对距离计算的理论视角 164
634　完全配对计算的实现 165
635　并行标签预测 168
636　性能评测 169
64　不平衡循环调度 171
641　对称性引起的负载失衡 172
642　内积计算实现 173
643　性能评测 174
65　高级归约 175
651　MNIST数据集上的SOFTMAX回归分类器 175
652　定制归约操作符 183
653　OpenMP高级归约 187
66　任务并行 189
661　树遍历 190
662　循环中生成任务 193
67　SIMD向量化 193
671　数据依赖 195
672　向量化感知函数 196
68　展望 196
69　附加练习 197
参考文献 202
第7章　统一计算设备架构 203
71　CUDA简介 204
72　支持CUDA的GPU硬件架构 206
721　主机与设备之间的互连 206
722　显存和峰值宽度 207
723　计算资源的组织 207
73　内存访问模式 211
731　均值名人脸的计算 212
732　计算中心化的数据矩阵 218
733　计算协方差矩阵 221
734　计算特征脸 229
74　内存层次结构 232
741　问题简介 233
742　串行DTW的线性内存算法 237
743　线性内存DTW的一个初始CUDA移植 243
744　共享内存中的波前松弛 248
745　并发调度和bank冲突 253
746　纹理内存和常量内存 254
75　优化准则 257
76　附加练习 258
参考文献 259
第8章　高级CUDA编程 261
81　warp内联函数和原子操作 261
811　分段并行归约 262
812　全局并行归约 265
813　任意原子操作 267
814　展望 269
82　利用多块GPU和流 269
821　牛顿迭代 269
822　利用多块GPU 272
823　通信和计算交叉 274
824　多块GPU上的流式计算 278
83　展望 280
831　统一内存 280
832　动态并行性 281
833　协作组 281
834　张量核心 281
835　GPU集群上的分布式计算 282
84　附加练习 282
参考文献 284
第9章　MPI 286
91　MPI简介 286
92　基本概念 288
93　点到点通信 289
94　非阻塞通信 292
9

并行无处不在！如今，任意一款现代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编程。
希望本书陪伴你度过快乐时光。充满活力，探索代码！最后，我们将非常高兴能收到你的任何反馈，以便帮助我们尽可能完善本书相关内容。