结构化并行程序设计：高效计算模式 PDF下载

编辑推荐

暂无

内容简介

本书由Intel的三位并行计算专家联合撰写，注重实践方法而非理论阐释，从问题分析伊始便引入并行思维，而非基于串行的思维定式。全书囊括了并行程序设计中通用且实用的编程模式，围绕IntelTBB和CilkPlus两个主要模型给出了大量示例，帮助读者学会编写高效的、结构化的、可维护的程序。本书可作为高年级本科生和研究生并行计算课程的理论教材或实验参考资料，也可供从事并行编程的程序员参考。

作者简介

---作者简介---

迈克尔·麦库尔（Michael McCool） Intel公司软件架构师，滑铁卢大学兼职副教授。

阿奇·D. 罗宾逊（Arch D. Robison） Intel公司线程构建块架构师，KAI C++首席程序员。

仁达敬（James Reinders） Intel公司高级工程师，并行编程布道师，并行工具首席发言人。

---译者简介---

于策，天津大学计算机科学与技术学院副教授，NAOC-TJU天文信息技术联合研究中心主任，曾参与中国第32次南极科考。

结构化并行程序设计：高效计算模式 PDF下载

目　　录
Structured Parallel Programming: Patterns for Efficient Computation
译者序
前言
写在前面
第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

前沿

前　　言Structured Parallel Programming: Patterns for Efficient Computation当今计算机全部采用了并行架构，所以程序员必须熟悉（或者应该熟悉）并行编程。随着并行编程越来越普遍，理应将它视为“编程”概念的一部分，并且是所有软件开发人员都应掌握的基本技能。但是众多并行编程相关书籍都过于专业化，过于强调特定编程模型与特定计算机体系结构。另外，部分书籍将并行计算定位为理论研究领域，提供的信息不足以让读者自行编写出并行应用程序。因此需要一部以主流且务实的方式介绍并行编程的书籍，让读者可以快速上手编写实用的并行应用程序，同时涉及多种计算机体系结构和编程模型。
讲授并行编程的传统方式是基于串行代码与算法，将并行编程视为串行编程的进阶。在我们看来这种方式并不好，讲授并行编程应该从零开始，避免陷入串行编程的前提假设和思考方式。目前，由于受到传统教学方式的影响，串行思想已经贯穿我们的教学和编程实践，甚至扎根于我们的行业工具——编程语言。这造成的后果就是很多程序员觉得并行编程很难，而实际上并不是。之所以我们接触的很多程序都是串行的，并不是因为问题本身需要按一定流程解决，而是编程工具的限制或程序员的思维定式。
尽管计算机硬件本来就是并行的，但是人们在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则是在现有语言中添加注释，需要静态编译。这五种编程模型使用了不同的句法来表现并行化，但我们将会看到编程模式适用于所有这些编程模型。这也进一步说明了编程模式是通用的，编程模式的研究绝不仅仅对如今的编程模型有意义，将来也会有用。
本书既不是理论类书籍，也不是标准手册，而是实用的方法指南。借助于范例分析，本书能帮助读者更好地理解怎样实现高效的并行应用程序。虽然使用超级计算机的程序员可能会关注本书，但本书并非针对这些人员，而是针对那些没有并行编程知识但是想要提升程序性能的主流