现今的编程是并行编程的时代。尽管在10年前结构化编程就已经彻底变革了传统的串行编程技术，但现在一种新型的基于模式的结构化编程技术正在成为并行编程的主流。并行计算专家和业界资深人士Michael McCool、Arch Robison和James Reinders联合编写了本书，描述了如何使用一种基于模式的结构化编程方法来设计和实现可维护和高效的并行算法。书中给出了多个编程模型的具体实例，主要采用两个最流行和前沿的并行编程模型：线程构造模块和Cilk Plus。这些独立于架构的模型使得我们能够轻易集成现有的应用，加速并行应用程序的开发。
无
当今计算机全部采用了并行架构，所以程序员必须熟悉（或者应该熟悉）并行编程。随着并行编程越来越普遍，理应将它视为“编程”概念的一部分，并且是所有软件开发人员都应掌握的基本技能。但是众多并行编程相关书籍都过于专业化，过于强调特定编程模型与特定计算机体系结构。另外，部分书籍将并行计算定位为理论研究领域，提供的信息不足以让读者自行编写出并行应用程序。因此需要一部以主流且务实的方式介绍并行编程的书籍，让读者可以快速上手编写实用的并行应用程序，同时涉及多种计算机体系结构和编程模型。
讲授并行编程的传统方式是基于串行代码与算法，将并行编程视为串行编程的进阶。在我们看来这种方式并不好，讲授并行编程应该从零开始，避免陷入串行编程的前提假设和思考方式。目前，由于受到传统教学方式的影响，串行思想已经贯穿我们的教学和编程实践，甚至扎根于我们的行业工具——编程语言。这造成的后果就是很多程序员觉得并行编程很难，而实际上并不是。之所以我们接触的很多程序都是串行的，并不是因为问题本身需要按一定流程解决，而是编程工具的限制或程序员的思维定式。
尽管计算机硬件本来就是并行的，但是人们在40年前选择的计算机架构却只给程序员提供串行编程概念。这些年来计算机体系结构方面的工作都是基于“串行执行”这一表象。在现代处理器的设计上，大量工作致力于将串行程序以并行方式处理，使其可以利用处理器内部的细粒度并行硬件高效执行。摩尔定律指出晶体管数量呈指数增长，由此带来的并行化需求越来越大，基于串行表象继续提高性能已不再现实。如今想要继续提高性能，就要求程序员直接使用并行算法。其实并行机制无处不在，它也是现代计算机体系结构提高性能的途径。甚至在个人计算机（或笔记本电脑）的很多地方也用到了并行机制，包括向量指令（SIMD）、多核处理器、图形处理器（GPU）、协处理器和众核处理器。如今进行并行编程需要对这些硬件的并行机制有一定的了解，以结合硬件自身的特点编写并行应用程序。
我们认为将来的并行编程将趋于结构化。本书总结了一些编写高效的、扩展性强的程序的编程模式。编程模式不仅可以提高学习并行编程的效率，而且在设计高效的、结构化的、可维护的程序时同样高效。使用编程模式的标准名称也能帮助程序员更好地进行交流。鉴于标准名称的重要性，我们广泛收集了相关术语，这会对阅读本书起到帮助作用。读者在阅读时不必按照章节顺序，可以通过术语表查找相关章节的术语解释或论述。
为了增强本书的实用性，在介绍编程模式时，我们给出了一些示例来说明其使用方法。我们知道并行编程模型有很多种，那么在示例中应使用哪种或哪些编程模型呢？我们希望给出足够多的示例来帮助读者在不过于依赖其他参考资料的情况下写出完善的应用程序。这要求本书的示例坚持用一种或很少的几种编程模型。另一方面，我们介绍的编程模式有很强的通用性，可以适用于很多编程模型。
综合考虑，我们决定对于两个主要模型给出大量示例，而对于“二线”模型给出较少的示例。我们选择的主要模型是Intel线程构建块（Intel TBB）和Intel Cilk Plus，两者都很高效且有很好的技术支持，而且很容易获取，同时遵循开放源码协议并提供商业支持。它们提供了完全不同的句法来实现并行：TBB是一套适用于多数ISO标准C++编译器的模板库，Cilk Plus是C/C++语言的扩展。本书中讨论的所有模式都可以通过这两个模型展现。http://parallelbook.com网站上提供了所有使用主要模型的示例的完整可执行代码和一系列其他资源。我们认为本书提供的示例结合官方文档足够用来学习TBB和Cilk Plus编程。
我们讨论的模式几乎适用于所有并行编程模型，为了说明其通用性，我们选择了三个“二线”编程模型：Intel阵列构建块（ArBB）、OpenCL和OpenMP。ArBB以库的形式提供了并行虚拟机，ArBB虚拟机提供透明的面向程序员的运行时代码生成环境，可以在多种编程语言下使用。本书中使用前端为C++的ArBB虚拟机，它将并行编程语法集成到了C++中，可以使用C++的各种特性，如宏定义和操作符重载等。我们也给出了一些OpenCL和OpenMP的例子。OpenCL和OpenMP使用的都是标准版本，其中OpenCL主要针对GPU体系结构，而OpenMP则针对共享内存的多核CPU体系结构。OpenCL基于独立的编译好的kernel语言，这种语言以字符串的形式提供给库接口。与ArBB一样，OpenCL也支持动态编译。OpenMP则是在现有语言中添加注释，需要静态编译。这五种编程模型使用了不同的句法来表现并行化，但我们将会看到编程模式适用于所有这些编程模型。这也进一步说明了编程模式是通用的，编程模式的研究绝不仅仅对如今的编程模型有意义，将来也会有用。
本书既不是理论类书籍，也不是标准手册，而是实用的方法指南。借助于范例分析，本书能帮助读者更好地理解怎样实现高效的并行应用程序。虽然使用超级计算机的程序员可能会关注本书，但本书并非针对这些人员，而是针对那些没有并行编程知识但是想要提升程序性能的主流C和C++程序员。为此，我们详细介绍了性能模型，尤其是度量并行复杂度的工作量–跨度（Work-Span）模型。相比于Amdahl定律中过于简化的假设，工作量–跨度模型要完善得多，因为它能给出算法加速的上下限，且给出的是一个严格的上限，通过这些参数可以很好地预测算法的加速能力。
我们希望读者能从本书学到如何在现代计算机上设计和实现高效、可靠、易维护的并行程序。本书从程序员的视角出发，没有冗余的应试知识和并行计算机体系结构先验知识。我们尽量避免介绍太多的计算机体系结构知识，但仍然对重要体系结构的局限性和应对策略进行了详述，目的是帮助程序员更精准地了解其所使用的计算机体系结构，从而更好地判断怎么组织应用程序以便获得最好的性能和扩展性。
我们的宗旨是通过适当的模式和示例学到高超的并行编程技能。我们介绍了模式，给它们起了名字，并用大量示例进行了说明。这种方式可以帮助读者很快写出有用且高效的并行程序，并且方便向其他程序员进行展示。另外，它有可能激发你对并行计算机体系结构、并行语言设计或其他相关话题的兴趣。任何一本书都不可能包含与并行编程相关的所有信息，所以我们不得不做取舍。对于感兴趣的读者，我们在附录部分给出了拓展阅读的建议。我们的网站http://parallelbook.com也提供了相关资料，包括本书没有提到的一些资源。
我们希望本书能帮助读者将“并行编程”纳入对“编程”的理解中。
计算机\并行计算
【内封署名】于策 孙超 肖健 汤善江 毕重科 译
本书是一项开拓性工作，不仅展示了真实的算法，而且介绍了在多核和众核时代如何真正让这些算法落地。
—— Michele Delsol，并行程序设计顾问及讲师
很多人都向我咨询并行计算的问题，想要了解多线程加速的概念以及实现方法。现在，我终于找到了回答他们的好办法：快去读一读这本书吧！
—— Martin Watt，梦工厂动画资深工程师
本书由Intel的三位并行计算专家联合撰写，囊括了并行程序设计中通用且实用的编程模式，如Fork-Join、模板、扫描、流水线、散发和分类归约等，并围绕Intel TBB、Cilk Plus和OpenCL等模型给出了大量示例，如K均值聚类、Bzip2数据压缩和样本排序等。
本书特色
并行思维。从开篇即引入并行思维，避免陷入串行计算的前提假设和思考方式，使得初学者能够快速入门，直接以并行计算的方式解决问题。
编程模式。并行编程正在趋于结构化，因此掌握编程模式成为学习的关键，是程序员迈向高效的、结构化的、可维护的程序设计的必由之路。
实践指南。关注实用方法，详细介绍了性能模型，特别是度量并行复杂度的工作量-跨度模型，网站parallelbook.com免费提供源代码、PPT等参考资料。
作者简介
迈克尔·麦库尔（Michael McCool） Intel公司软件架构师，滑铁卢大学兼职副教授。
阿奇·D. 罗宾逊（Arch D. Robison） Intel公司线程构建块架构师，KAI C++首席程序员。
仁达敬（James Reinders） Intel公司高级工程师，并行编程布道师，并行工具首席发言人。
译者简介
于策 天津大学计算机科学与技术学院副教授，NAOC-TJU天文信息技术联合研究中心主任。
[日]迈克尔·麦库尔（Michael McCool） [美]阿奇·D. 罗宾逊（Arch D. Robison） [美]仁达敬（James Reinders）著：---作者简介---
迈克尔·麦库尔（Michael McCool） Intel公司软件架构师，滑铁卢大学兼职副教授。
阿奇·D. 罗宾逊（Arch D. Robison） Intel公司线程构建块架构师，KAI C++首席程序员。
仁达敬（James Reinders） Intel公司高级工程师，并行编程布道师，并行工具首席发言人。
---译者简介---
于策，天津大学计算机科学与技术学院副教授，NAOC-TJU天文信息技术联合研究中心主任，曾参与中国第32次南极科考。
现代处理器本质上都是并行计算体系结构，并行程序设计已是程序员不可或缺的技能。本书从并行计算思想以及并行编程模型的角度，介绍了共享内存环境中的并行算法策略，为程序员提供了学习并行编程的一种有效途径。
并行程序设计的难度和复杂度远高于传统的串行编程，原因在于：一方面，并行计算硬件本身的多样化，如多核处理器、众核加速卡、分布式并行计算环境、云计算环境等，不同并行计算环境下的程序设计与性能优化方法不同；另一方面，程序员最初学习的一般都是串行编程方法，分析与求解问题时难免会先入为主地采用串行计算的思路，再考虑其并行化，这实际上是走了弯路。
本书从设计模式的角度出发，对并行程序设计与实现方式进行了分类与抽象，并给出了六个问题求解的实例，在开始问题分析之际便引入并行计算的思想，直接以并行计算的方式解决问题，其内容的组织更适合初学并行程序设计的程序员。
本书适用于高年级本科生以及研究生并行计算相关课程的理论教学，也可用作实验教学的参考资料。
本书的翻译是多位并行计算科研人员通力合作的结果，其中于策与孙超组织了全书的统稿与审校工作，肖健、汤善江、毕重科、傅浩、王建美、罗琦、邹慧慧参与了部分章节的翻译与审校。
感谢机械工业出版社华章分社曲熠编辑对本书翻译工作的组织，感谢佘洁编辑对全书内容的耐心审校。
受语言背景以及技术水平所限，再加之时间紧张，书中难免出现翻译错误，诚挚欢迎广大读者批评指正。
译者
2018年5月于天津大学
译者序
前言
写在前面
第1章 导论 1
1.1 并行思维 2
1.2 性能 3
1.3 动机：无处不在的并行 6
1.3.1 硬件发展推进并行化 6
1.3.2 并行化的历史趋势 8
1.3.3 显式并行编程的需求 12
1.4 基于模式的结构化编程 15
1.5 并行编程模型 16
1.5.1 理想特征 16
1.5.2 用抽象代替具体 17
1.5.3 规则数据并行 18
1.5.4 可组合性 21
1.5.5 功能可移植性 21
1.5.6 性能可移植性 22
1.5.7 安全性、确定性和可维护性 22
1.5.8 编程模型概述 23
1.5.9 何时使用模型 28
1.6 本书的结构 29
1.7 小结 29
第2章 背景知识 31
2.1 名词和符号 31
2.2 策略 31
2.3 机制 33
2.4 计算机模型 35
2.4.1 计算机模型概述 35
2.4.2 影响性能的关键因素 39
2.4.3 Flynn分类法 41
2.4.4 革新 42
2.5 性能理论 43
2.5.1 延迟和吞吐量 44
2.5.2 加速比、效率和可扩展性 44
2.5.3 功耗 45
2.5.4 Amdahl定律 46
2.5.5 Gustafson-Barsis定律 48
2.5.6 工作量–跨度模型 49
2.5.7 渐近复杂度 51
2.5.8 渐近加速比和渐近效率 52
2.5.9 Little公式 53
2.6 并行陷阱 54
2.6.1 竞态条件 54
2.6.2 互斥和锁 55
2.6.3 死锁 56
2.6.4 扩展性抑制 57
2.6.5 局部性不足 57
2.6.6 负载不均衡 58
2.6.7 额外开销 58
2.7 小结 59
第一部分 模式
第3章 模式概述 62
3.1 嵌套模式 63
3.2 结构化串行控制流模式 64
3.2.1 序列 64
3.2.2 选择 65
3.2.3 迭代 66
3.2.4 递归 68
3.3 并行控制模式 68
3.3.1 Fork-Join 68
3.3.2 映射 68
3.3.3 模板 69
3.3.4 归约 70
3.3.5 扫描 71
3.3.6 递推 73
3.4 串行数据管理模式 74
3.4.1 随机读写 74
3.4.2 栈分配 74
3.4.3 堆分配 75
3.4.4 闭包 75
3.4.5 对象 75
3.5 并行数据管理模式 76
3.5.1 打包 76
3.5.2 流水线 76
3.5.3 几何分解 77
3.5.4 聚合 78
3.5.5 散发 78
3.6 其他并行模式 79
3.6.1 超标量序列 79
3.6.2 期货 80
3.6.3 投机选择 80
3.6.4 工作堆 81
3.6.5 搜索 81
3.6.6 切片 81
3.6.7 展开 81
3.6.8 分类归约 82
3.6.9 项图重写 83
3.7 非确定性模式 83
3.7.1 分支限界 83
3.7.2 事务 84
3.8 编程模型对模式的支持 84
3.8.1 Cilk Plus 86
3.8.2 线程构建块 87
3.8.3 OpenMP 88
3.8.4 阵列构建块 89
3.8.5 OpenCL 90
3.9 小结 91
第4章 映射 92
4.1 概述 93
4.2 带缩放系数的向量加法 94
4.2.1 问题描述 94
4.2.2 串行实现 95
4.2.3 TBB实现 96
4.2.4 Cilk Plus实现 96
4.2.5 使用数组符号的Cilk Plus实现 97
4.2.6 OpenMP实现 97
4.2.7 使用向量操作的ArBB实现 97
4.2.8 使用元素函数的ArBB实现 98
4.2.9 OpenCL实现 99
4.3 芒德布罗分形图 100
4.3.1 问题描述 100
4.3.2 串行实现 100
4.3.3 TBB实现 101
4.3.4 Cilk Plus实现 101
4.3.5 使用数组符号的Cilk Plus实现 101
4.3.6 OpenMP实现 103
4.3.7 ArBB实现 103
4.3.8 OpenCL实现 104
4.4 映射的序列和序列的映射 105
4.5 并行模型的对比 107
4.6 相关模式 107
4.6.1 模板 107
4.6.2 工作堆 108
4.6.3 分治 108
4.7 小结 108
第5章 集合 109
5.1 归约 109
5.1.1 计算重排序 110
5.1.2 向量化 111
5.1.3 分块 112
5.1.4 精度 113
5.1.5 实现 113
5.2 映射和归约的融合 114
5.2.1 TBB中的显式融合 115
5.2.2 Cilk Plus中的显式融合 115
5.2.3 ArBB中的自动融合 115
5.3 点积 115
5.3.1 问题描述 115
5.3.2 串行实现 116
5.3.3 SEE内联函数实现 116
5.3.4 TBB实现 117
5.3.5 Cilk Plus实现 119
5.3.6 OpenMP实现 120
5.3.7 ArBB实现 121
5.4 扫描 122
5.4.1 Cilk Plus 123
5.4.2 TBB 124
5.4.3 ArBB 124
5.4.4 OpenMP 124
5.5 映射和扫描的融合 127
5.6 积分 127
5.6.1 问题描述 128
5.6.2 串行实现 128
5.6.3 Cilk Plus实现 130
5.6.4 OpenMP实现 130
5.6.5 TBB实现 131
5.6.6 ArBB实现 132
5.7 小结 134
第6章 数据重组 135
6.1 聚合 135
6.1.1 常规聚合 135
6.1.2 移位 137
6.1.3 拉合 137
6.2 散发 138
6.2.1 原子散发 139
6.2.2 排列散发 139
6.2.3 归并散发 139
6.2.4 优先散发 140
6.3 将散发转换为聚合 140
6.4 打包 141
6.5 映射和打包的融合 142
6.6 几何分解和分区 143
6.7 结构的数组和数组的结构 145
6.8 小结 148
第7章 模板和递推 149
7.1 模板 149
7.2 用移位实现模板 151
7.3 针对缓存的分块式模板 151
7.4 模板通信优化 152
7.5 递推 153
7.6 小结 155
第8章 Fork-Join 156
8.1 定义 156
8.2 编程模型对Fork-Join的支持 157
8.2.1 Cilk Plus对Fork-Join的支持 158
8.2.2 TBB对Fork-Join的支持 159
8.2.3 OpenMP对Fork-Join的支持 159
8.3 映射的递归实现 160
8.4 基本情形的选择 162
8.5 负载均衡 163
8.6 并行分治的复杂度 165
8.7 Karatsuba多项式乘法 167
8.8 缓存局部性和缓存参数无关算法 170
8.9 快速排序 172
8.9.1 Cilk Plus快速排序 174
8.9.2 TBB快速排序 175
8.9.3 快速排序的工作量和跨度 178
8.10 归约和超对象 178
8.11 用Fork-Join实现扫描 181
8.12 在递推中使用Fork-Join 185
8.12.1 分析 188
8.12.2 平面Fork-Join 188
8.13 小结 188
第9章 流水线 189
9.1 基本流水线 189
9.2 有并行阶段的流水线 190
9.3 流水线的实现 191
9.4 编程模型对流水线的支持 192
9.4.1 TBB中的流水线 192
9.4.2 Cilk Plus中的流水线 193
9.5 更多通用的拓扑结构 195
9.6 强制并行性与可选并行性 196
9.7 小结 196
第二部分 示例
第10章 地震正演模拟 198
10.1 背景 198
10.2 模板的计算 199
10.3 缓存对运算强度的影响 200
10.4 使用时空分块提高运算强度 202
10.5 Cilk Plus代码 203
10.6 ArBB实现 206
10.7 小结 207
第11章 K均值聚类 208
11.1 算法 208
11.2 K均值的Cilk Plus实现 209
11.3 K均值的TBB实现 212
11.4 小结 216
第12章 Bzip2数据压缩 217
12.1 Bzip2算法 217
12.2 三段流水线的TBB实现 218
12.3 四段流水线的TBB实现 221
12.4 三段流水线的Cilk Plus实现 221
12.5 小结 222
第13章 归并排序 223
13.1 并行归并 223
13.1.1 并行归并的TBB实现 225
13.1.2 并行归并的工作量和跨度 225
13.2 并行归并排序 226
13.3 小结 227
第14章 样本排序 228
14.1 总体结构 228
14.2 选取分箱数量 229
14.3 分箱 229
14.4 再打包和子排序 231
14.5 样本排序的性能分析 232
14.6 写给C++高手 232
14.7 小结 233
第15章 Cholesky因式分解 234
15.1 Fortran规范 234
15.2 递归Cholesky分解 235
15.3 三角矩阵求解 236
15.4 对称秩校正 238
15.5 时间用在哪里 239
15.6 小结 239
附录
附录A 拓展阅读 242
附录B Cilk Plus 244
附录C TBB 259
附录D C++11 269
附录E 术语表 273
参考文献 291
索引 296
