并行算法设计与性能优化PDF电子书下载

第1章 绪论 1

1.1 并行和向量化的作用 2

1.2 为什么要并行或向量化 3

1.3 为什么向量化或并行难 4

1.4 并行的替代方法 9

1.5 进程、线程与处理器 10

1.6 并行硬件平台 13

1.7 向量化和多核技术不是万能的 17

1.8 本章小结 18

第2章 现代处理器特性 19

2.1 指令级并行 20

2.1.1 指令流水线 20

2.1.2 乱序执行 22

2.1.3 指令多发射 22

2.1.4 分支预测 23

2.1.5 VLIW 23

2.2 向量化并行 24

2.2.1 SIMD 24

2.2.2 SIMT 25

2.3 线程级并行 25

2.3.1 内核线程和用户线程 26

2.3.2 多线程编程库 26

2.3.3 多核上多线程并行要注意的问题 27

2.3.4 多线程程序在多核和单核上运行的不同 28

2.4 缓存 28

2.4.1 缓存层次结构 29

2.4.2 缓存一致性 30

2.4.3 缓冲不命中 31

2.4.4 写缓存 32

2.4.5 越过缓存 33

2.4.6 硬件预取 34

2.4.7 缓存结构 34

2.4.8 映射策略 35

2.5 虚拟存储器和TLB 36

2.6 NUMA技术 37

2.7 本章小结 39

第3章 算法性能和程序性能的度量与分析 40

3.1 算法分析的性能度量标准 40

3.1.1 时间复杂度与空间复杂度 41

3.1.2 实现复杂度 43

3.2 程序和指令的性能度量标准 47

3.3 程序性能优化的度量标准 52

3.3.1 加速比与并行效率 52

3.3.2 Amdahl定律和Gustafson定律 53

3.4 程序性能分析实用工具 54

3.5 本章小结 60

第4章 串行代码性能优化 61

4.1 系统级别 62

4.2 应用级别 65

4.3 算法级别 68

4.4 函数级别 71

4.4.1 函数调用参数 71

4.4.2 内联小函数 72

4.5 循环级别 72

4.5.1 循环展开 72

4.5.2 循环累积 73

4.5.3 循环合并 74

4.5.4 循环拆分 74

4.6 语句级别 75

4.6.1 减少内存读写 75

4.6.2 选用尽量小的数据类型 76

4.6.3 结构体对齐 77

4.6.4 表达式移除 78

4.6.5 分支优化 78

4.6.6 优化交换性能 82

4.7 指令级别 83

4.8 本章小结 84

第5章 依赖分析 86

5.1 指令级依赖 87

5.1.1 结构化依赖 87

5.1.2 数据依赖 88

5.1.3 控制依赖 89

5.2 循环级依赖 90

5.2.1 循环数据依赖 90

5.2.2 循环控制依赖 92

5.3 寄存器重命名 93

5.4 本章小结 94

第6章 并行编程模型及环境 95

6.1 并行编程模型 95

6.1.1 指令级并行 96

6.1.2 向量化并行 97

6.1.3 易并行 98

6.1.4 任务并行 99

6.1.5 数据并行 100

6.1.6 循环并行化 101

6.1.7 流水线并行 102

6.1.8 区域分解并行 103

6.1.9 隐式和显式并行化 104

6.1.10 SPMD 104

6.1.11 共享存储器并行 105

6.1.12 分布式存储器并行 105

6.2 常见并行编程环境 105

6.2.1 MPI 106

6.2.2 OpenMP 108

6.2.3 fork/pthread 108

6.2.4 CUDA 109

6.2.5 OpenCL 109

6.2.6 OpenACC 110

6.2.7 NEON内置函数 111

6.2.8 SSE/AVX内置函数 111

6.3 本章小结 111

第7章 并行算法设计方法 114

7.1 划分 114

7.1.1 分而治之 115

7.1.2 划分原则 116

7.1.3 常见划分方法 116

7.1.4 并行性和局部性 117

7.2 通信 118

7.2.1 操作的原子性 119

7.2.2 结果的可见性 120

7.2.3 顺序一致性 121

7.2.4 函数的可重入与线程安全 122

7.2.5 volatile关键字 122

7.2.6 锁 123

7.2.7 临界区 126

7.2.8 原子操作 127

7.2.9 栅栏 128

7.3 结果归并 129

7.4 负载均衡 129

7.4.1 静态负载均衡 130

7.4.2 动态负载均衡 130

7.4.3 动态负载均衡算法的一般步骤 131

7.5 本章小结 133

第8章 并行算法缺陷 134

8.1 启动结束时间 134

8.2 负载均衡 135

8.3 竞写 136

8.4 锁 136

8.4.1 死锁 137

8.4.2 活锁 139

8.5 饿死 140

8.6 伪共享 140

8.7 原子操作 141

8.8 存储器栅栏 142

8.9 缓存一致性 142

8.10 顺序一致性 143

8.11 volatile同步错误 143

8.12 本章小结 144

第9章 并行编程模式实践 146

9.1 map模式 147

9.2 reduce模式 149

9.3 结合map和reduce模式 152

9.4 scan模式 155

9.5 zip/unzip模式 156

9.6 流水线模式 159

9.7 本章小结 161

第10章 如何并行遗留代码 162

10.1 找出软件的计算热点 163

10.2 判断是否并行化热点 164

10.3 设计算法并实现 166

10.3.1 选择何种工具进行向量化或并行化 166

10.3.2 重构热点代码 167

10.3.3 依据硬件实现算法 168

10.4 将实现后的代码嵌入原软件 169

10.4.1 混合编译 169

10.4.2 动态链接库 170

10.5 示例：如何并行化word2vec 171

10.6 本章小结 174

第11章 超级并行 176

11.1 超级并行方式编程 176

11.1.1 进程＋线程 177

11.1.2 进程＋GPU线程 178

11.1.3 线程＋GPU线程 181

11.1.4 线程＋向量指令 181

11.1.5 进程＋线程＋向量指令 182

11.1.6 进程＋线程＋GPU线程 183

11.2 矩阵乘法 184

11.2.1 多机CPU矩阵乘法 184

11.2.2 单机多GPU矩阵乘法 187

11.2.3 多机多GPU矩阵乘法 188

11.3 本章小结 189

第12章 并行算法设计的一般准则 190

12.1 并行算法设计14准则 190

12.2 本章小结 194

附录A 整型数据与浮点数据 195