并行程序设计导论(原书第2版)

目　　录
An Introduction to Parallel Programming, Second Edition
译者序
前言
第1章　为什么需要并行计算 1
1.1　为什么需要不断提高性能 1
1.2　为什么需要建立并行系统 2
1.3　为什么需要编写并行程序 2
1.4　如何编写并行程序 5
1.5　我们将做什么 6
1.6　并发、并行和分布式 7
1.7　本书其余部分 8
1.8　一点警告 8
1.9　排版惯例 9
1.10　小结 9
1.11　练习 10
第2章　并行硬件与并行软件 12
2.1　背景知识 12
2.1.1　冯·诺依曼体系结构 12
2.1.2　进程、多任务和线程 13
2.2　冯·诺依曼模型的改进 14
2.2.1　缓存基础 14
2.2.2　缓存映射 16
2.2.3　缓存和程序：示例 17
2.2.4　虚拟内存 18
2.2.5　指令级并行 19
2.2.6　硬件多线程 21
2.3　并行硬件 22
2.3.1　并行计算机的分类 22
2.3.2　SIMD系统 22
2.3.3　MIMD系统 24
2.3.4　互连网络 26
2.3.5　高速缓存一致性 30
2.3.6　共享内存与分布式内存 32
2.4　并行软件 33
2.4.1　注意事项 33
2.4.2　协调进程/线程 33
2.4.3　共享内存 34
2.4.4　分布式内存 37
2.4.5　GPU编程 40
2.4.6　混合系统编程 40
2.5　输入和输出 41
2.5.1　MIMD系统 41
2.5.2　GPU 41
2.6　性能 42
2.6.1　在MIMD系统中的加速比和
效率 42
2.6.2　阿姆达定律 44
2.6.3　MIMD系统的可扩展性 45
2.6.4　MIMD程序的计时 46
2.6.5　GPU性能 48
2.7　并行程序设计 49
2.7.1　示例 49
2.8　编写和运行并行程序 53
2.9　假设 53
2.10　小结 54
2.10.1　串行系统 54
2.10.2　并行硬件 55
2.10.3　并行软件 56
2.10.4　输入和输出 57
2.10.5　性能 57
2.10.6　并行程序设计 58
2.10.7　假设 58
2.11　练习 58
第3章　基于MPI的分布式
内存编程 62
3.1　入门 62
3.1.1　编译和执行 63
3.1.2　MPI程序 64
3.1.3　MPI_Init和
MPI_Finalize 64
3.1.4　通信域、MPI_Comm_size和MPI_Comm_rank 65
3.1.5　SPMD程序 66
3.1.6　通信 66
3.1.7　MPI_Send 66
3.1.8　MPI_Recv 67
3.1.9　消息匹配 68
3.1.10　status_p参数 69
3.1.11　MPI_Send和MPI_Recv的
语义 69
3.1.12　一些潜在的陷阱 70
3.2　MPI中的梯形法则 70
3.2.1　梯形法则 70
3.2.2　梯形法则的并行化 71
3.3　处理I/O 74
3.3.1　输出 74
3.3.2　输入 75
3.4　集合通信 76
3.4.1　树形结构的通信 76
3.4.2　MPI_Reduce 77
3.4.3　集合通信与点对点通信 78
3.4.4　MPI_Allreduce 79
3.4.5　广播 80
3.4.6　数据分布 82
3.4.7　分散 83
3.4.8　收集 84
3.4.9　综合实例 85
3.5　MPI派生的数据类型 88
3.6　MPI程序的性能评估 91
3.6.1　计时 91
3.6.2　结果 93
3.6.3　加速比和效率 95
3.6.4　可扩展性 95
3.7　一种并行排序算法 96
3.7.1　一些简单的串行排序算法 96
3.7.2　并行奇偶移项排序 98
3.7.3　MPI程序中的安全性 100
3.7.4　关于并行奇偶排序的一些
补充细节 102
3.8　小结 103
3.9　练习 106
3.10　编程作业 112
第4章　Pthreads共享内存编程 114
4.1　进程、线程和Pthreads 114
4.2　Hello, world 115
4.2.1　执行 116
4.2.2　预备 117
4.2.3　启动线程 117
4.2.4　运行线程 119
4.2.5　停止线程 120
4.2.6　错误检查 120
4.2.7　启动线程的其他方法 120
4.3　矩阵-向量乘法 121
4.4　临界区 123
4.5　忙等待 126
4.6　互斥锁 128
4.7　生产者-消费者同步和信号量 131
4.8　栅栏和条件变量 135
4.8.1　忙等待和互斥锁 135
4.8.2　信号量 136
4.8.3　条件变量 137
4.8.4　Pthreads栅栏 139
4.9　读写锁 139
4.9.1　排序的链表函数 140
4.9.2　多线程链表 142
4.9.3　Pthreads的读写锁 144
4.9.4　各种实现方案的性能 145
4.9.5　实现读写锁 146
4.10　缓存、缓存一致性和伪共享 147
4.11　线程安全 150
4.11.1　不正确的程序可以产生
正确的输出 153
4.12　小结 153
4.13　练习 154
4.14　编程作业 159
第5章　OpenMP共享内存编程 161
5.1　入门 162
5.1.1　编译和运行OpenMP程序 163
5.1.2　程序 163
5.1.3　错误检查 165
5.2　梯形法则 166
5.2.1　**个OpenMP版本 166
5.3　变量的作用域 170
5.4　归约子句 170
5.5　parallel指令 173
5.5.1　注意事项 174
5.5.2　数据依赖性 175
5.5.3　寻找循环迭代相关 176
5.5.4　估算π 176
5.5.5　关于作用域的更多内容 178
5.6　关于OpenMP中的循环的更多
内容：排序 179
5.6.1　冒泡排序 179
5.6.2　奇偶移项排序 180
5.7　循环的调度 182
5.7.1　schedule子句 183
5.7.2　static调度类型 185
5.7.3　dynamic和guided调度
类型 185
5.7.4　runtime调度类型 186
5.7.5　哪种调度 187
5.8　生产者和消费者 188
5.8.1　队列 188
5.8.2　消息传递 188
5.8.3　发送消息 189
5.8.4　接收消息 189
5.8.5　终止检测 190
5.8.6　开始 190
5.8.7　atomic指令 191
5.8.8　临界区和锁 191
5.8.9　在消息传递程序中使用锁 193
5.8.10　critical指令、atomic
指令或锁 194
5.8.11　注意事项 194
5.9　缓存、缓存一致性和伪共享 195
5.10　任务化 199
5.11　线程安全 202
5.11.1　不正确的程序可以产生
正确的输出 204
5.12　小结 204
5.13　练习 208
5.14　编程作业 211
第6章　用CUDA进行GPU编程 215
6.1　GPU和GPGPU 215
6.2　GPU架构 215
6.3　异构计算 217
6.4　CUDA hello 217
6.4.1　源代码 218
6.4.2　编译与运行程序 219
6.5　深入了解 219
6.6　线程、线程块和线程网格 220
6.7　NVIDIA计算能力和设备架构 223
6.8　向量加法 223
6.8.1　核函数 224
6.8.2　Get_args函数 225
6.8.3　Allocate_vectors函数和
托管内存 226
6.8.4　main函数调用的其他函数 227
6.8.5　显式内存传输 229
6.9　从CUDA核函数返回结果 231
6.10　CUDA梯形法则I 233
6.10.1　梯形法则 233
6.10.2　一种CUDA实现 234
6.10.3　初始化、返回值和*后
更新 235
6.10.4　使用正确的线程 236
6.10.5　更新返回值和atomicAdd
函数 236
6.10.6　CUDA梯形法则的性能 237
6.11　CUDA梯形法则II：提升性能 238
6.11.1　树形通信 238
6.11.2　局部变量、寄存器、共享和
全局内存 239
6.11.3　线程束和线程束洗牌 240
6.11.4　使用线程束洗牌实现树形
全局求和 241
6.11.5　共享内存和线程束洗牌的
替代方案 242
6.12　用warpSize个线程块实现
梯形法则 243
6.12.1　主机代码 244
6.12.2　使用线程束洗牌的核函数 244
6.12.3　使用共享内存的核函数 244
6.12.4　性能 245
6.13　CUDA梯形法则III：使用具有
多个线程束的线程块 245
6.13.1　__syncthreads函数 246
6.13.2　关于共享内存的更多内容 247
6.13.3　使用共享内存的线程束
求和 247
6.13.4　共享内存库 248
6.13.5　收尾工作 249
6.13.6　性能 251
6.14　双调排序 251
6.14.1　串行双调排序 251
6.14.2　蝶式交换和二进制表示 254
6.14.3　并行双调排序I 256
6.14.4　并行双调排序II 258
6.14.5　CUDA双调排序的性能 259
6.15　小结 260
6.16　练习 264
6.17　编程作业 267
第7章　并行程序开发 269
7.1　两种n-body问题的解决方案 269
7.1.1　问题描述 269
7.1.2　两种串行方案 270
7.1.3　并行化n-body求解方案 274
7.1.4　关于I/O的说明 276
7.1.5　使用OpenMP并行化基本
求解方案 277
7.1.6　使用OpenMP并行化简化
求解方案 279
7.1.7　评估OpenMP代码 283
7.1.8　使用Pthreads并行化求解
方案 284
7.1.9　使用MPI并行化求解方案 284
7.1.10　使用MPI并行化简化求解
方案 286
7.1.11　MPI简化求解的性能 291
7.1.12　使用CUDA并行化基本
求解方案 292
7.1.13　关于CUDA协同组的说明 294
7.1.14　基本CUDA n-body求解
方案的性能 295
7.1.15　提高CUDA n-body求解
方案性能的方法 295
7.1.16　在n-body求解方案中使用
共享内存技术 296
7.2　样本排序 299
7.2.1　样本排序和桶排序 299
7.2.2　选择样本数据 300
7.2.3　Map函数的简单实现 301
7.2.4　Map的另一种实现方案 302
7.2.5　并行化样本排序 305
7.2.6　使用OpenMP实现样本
排序 308
7.2.7　使用Pthreads实现样本
排序 312
7.2.8　使用MPI实现样本排序 314
7.2.9　使用CUDA实现样本排序 323
7.3　注意事项 331
7.4　使用哪种API 331
7.5　小结 332
7.5.1　MPI 333
7.6　练习 334
7.7　编程作业 340
第8章　下一步该怎么走 343
参考文献 345