结构化并行程序设计 高效计算模式PDF|Epub|txt|kindle电子书版本网盘下载

结构化并行程序设计 高效计算模式PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第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

第一部分 模式62

第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-Join68

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 Plus86

3.8.2 线程构建块87

3.8.3 OpenMP88

3.8.4 阵列构建块89

3.8.5 OpenCL90

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 CilkPlus中的显式融合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 CilkPlus实现119

5.3.6 OpenMP实现120

5.3.7 ArBB实现121

5.4 扫描122

5.4.1 Cilk Plus123

5.4.2 TBB124

5.4.3 ArBB124

5.4.4 OpenMP124

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-Join156

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-Join185

8.12.1 分析188

8.12.2 平面Fork-Join188

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 CilkPlus中的流水线193

9.5 更多通用的拓扑结构195

9.6 强制并行性与可选并行性196

9.7 小结196

第二部分 示例198

第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 三段流水线的CilkPlus实现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

附录242

附录A 拓展阅读242

附录B Cilk Plus244

附录C TBB259

附录D C+++11269

附录E 术语表273

参考文献291

索引296