结构化并行程序设计

现今的编程是并行编程的时代。尽管在10年前结构化编程就已经彻底变革了传统的串行编程技术，但现在一种新型的基于模式的结构化编程技术正在成为并行编程的主流。并行计算专家和业界资深人士Michael McCool、Arch Robison和James Reinders联合编写了本书，描述了如何使用一种基于模式的结构化编程方法来设计和实现可维护和高效的并行算法。书中给出了多个编程模型的具体实例，主要采用两个最流行和前沿的并行编程模型：线程构造模块和Cilk Plus。这些独立于架构的模型使得我们能够轻易集成现有的应用，加速并行应用程序的开发。

本书由Intel的三位并行计算专家联合撰写，囊括了并行程序设计中通用且实用的编程模式，如Fork-Join、模板、扫描、流水线、散发和分类归约等，并围绕Intel TBB、Cilk Plus和OpenCL等模型给出了大...

(展开全部)

现今的编程是并行编程的时代。尽管在10年前结构化编程就已经彻底变革了传统的串行编程技术，但现在一种新型的基于模式的结构化编程技术正在成为并行编程的主流。并行计算专家和业界资深人士Michael McCool、Arch Robison和James Reinders联合编写了本书，描述了如何使用一种基于模式的结构化编程方法来设计和实现可维护和高效的并行算法。书中给出了多个编程模型的具体实例，主要采用两个最流行和前沿的并行编程模型：线程构造模块和Cilk Plus。这些独立于架构的模型使得我们能够轻易集成现有的应用，加速并行应用程序的开发。

本书由Intel的三位并行计算专家联合撰写，囊括了并行程序设计中通用且实用的编程模式，如Fork-Join、模板、扫描、流水线、散发和分类归约等，并围绕Intel TBB、Cilk Plus和OpenCL等模型给出了大量示例，如K均值聚类、Bzip2数据压缩和样本排序等。

本书特色

并行思维。从开篇即引入并行思维，避免陷入串行计算的前提假设和思考方式，使得初学者能够快速入门，直接以并行计算的方式解决问题。

编程模式。并行编程正在趋于结构化，因此掌握编程模式成为学习的关键，是程序员迈向高效的、结构化的、可维护的程序设计的必由之路。

实践指南。关注实用方法，详细介绍了性能模型，特别是度量并行复杂度的工作量-跨度模型，网站parallelbook.com免费提供源代码、PPT等参考资料。

译者序
前言
写在前面
第1章　导论 1
1.1　并行思维 2
1.2　性能 3
· · · · · · (更多)

译者序
前言
写在前面
第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
· · · · · · (收起)