深入理解并行编程
出版时间：2017
内容简介
《深入理解并行编程》首先以霍金提出的两个理论物理限制为引子，解释了多核并行计算兴起的原因，并从硬件的角度阐述并行编程的难题。接着，《深入理解并行编程》以常见的计数器为例，探讨其不同的实现方法及适用场景。在这些实现方法中，除了介绍常见的锁以外，《深入理解并行编程》还重点介绍了RCU的使用及其原理，以及实现RCU的基础：内存屏障。最后，《深入理解并行编程》还介绍了并行软件的验证，以及并行实时计算等内容。 《深入理解并行编程》适合于对并行编程有兴趣的大学生、研究生，以及需要对项目进行深度性能优化的软硬件工程师，特别值得一提的是，《深入理解并行编程》对操作系统内核工程师也很有价值。
目录
第1章 如何使用本书1
1.1 路线图1
1.2 小问题2
1.3除本书之外的选择3
1.4 示例源代码4
1.5 这本书属于谁4
第2章 简介6
2.1 导致并行编程困难的历史原因6
2.2 并行编程的目标7
2.2.1 性能8
2.2.2 生产率9
2.2.3 通用性9
2.3 并行编程的替代方案11
2.3.1 串行应用的多个实例11
2.3.2 使用现有的并行软件11
2.3.3 性能优化12
2.4 是什么使并行编程变得复杂12
2.4.1 分割任务13
2.4.2 并行访问控制13
2.4.3 资源分割和复制14
2.4.4 与硬件的交互14
2.4.5 组合使用14
2.4.6 语言和环境如何支持这些任务14
2.5 本章的讨论15
第3章 硬件和它的习惯16
3.1 概述16
3.1.1 流水线CPU16
3.1.2 内存引用17
3.1.3 原子操作18
3.1.4 内存屏障19
3.1.5 高速缓存未命中19
3.1.6 I/O操作19
3.2 开销20
3.2.1 硬件体系结构20
3.2.2 操作的开销21
3.3 硬件的免费午餐23
3.3.1 3D集成23
3.3.2 新材料和新工艺24
3.3.3 是光，不是电子24
3.3.4 专用加速器24
3.3.5 现有的并行软件25
3.4 对软件设计的启示25
第4章 办事的家伙27
4.1 脚本语言27
4.2 POSIX多进程28
4.2.1 POSIX进程创建和销毁28
4.2.2 POSIX线程创建和销毁30
4.2.3 POSIX锁31
4.2.4 POSIX读/写锁34
4.3 原子操作37
4.4 Linux内核中类似POSIX的操作38
4.5 如何选择趁手的工具39
第5章 计数40
5.1 为什么并发计数不可小看41
5.2 统计计数器42
5.2.1 设计43
5.2.2 基于数组的实现43
5.2.3 最终结果一致的实现44
5.2.4 基于每线程变量的实现46
5.2.5 本节讨论48
5.3 近似上限计数器48
5.3.1 设计48
5.3.2 简单的上限计数实现50
5.3.3 关于简单上限计数的讨论55
5.3.4 近似上限计数器的实现55
5.3.5 关于近似上限计数器的讨论55
5.4 精确上限计数56
5.4.1 原子上限计数的实现56
5.4.2 关于原子上限计数的讨论62
5.4.3 Signal-Theft上限计数的设计62
5.4.4 Signal-Theft上限计数的实现63
5.4.5 关于Signal-Theft上限计数的讨论68
5.5 特殊场合的并行计数68
5.6 关于并行计数的讨论69
5.6.1 并行计数的性能70
5.6.2 并行计数的专门化71
5.6.3 从并行计数中学到什么71
第6章 对分割和同步的设计73
6.1 分割练习73
6.1.1 哲学家就餐问题73
6.1.2 双端队列75
6.1.3 关于分割问题示例的讨论81
6.2 设计准则82
6.3 同步粒度83
6.3.1 串行程序84
6.3.2 代码锁85
6.3.3 数据锁86
6.3.4 数据所有权88
6.3.5 锁粒度与性能88
6.4 并行快速路径90
6.4.1 读/写锁91
6.4.2 层次锁91
6.4.3 资源分配器缓存92
6.5 分割之外97
6.5.1 使用工作队列的迷宫问题并行解法97
6.5.2 另一种迷宫问题的并行解法100
6.5.3 性能比较I102
6.5.4 另一种迷宫问题的串行解法104
6.5.5 性能比较II104
6.5.6 未来展望与本节总结105
6.6 分割、并行化与优化106
第7章 锁107
7.1 努力活着108
7.1.1 死锁108
7.1.2 活锁与饥饿114
7.1.3 不公平的锁116
7.1.4 低效率的锁117
7.2 锁的类型117
7.2.1 互斥锁117
7.2.2 读/写锁118
7.2.3 读/写锁之外118
7.2.4 范围锁119
7.3 锁在实现中的问题121
7.3.1 基于原子交换的互斥锁实现示例121
7.3.2 互斥锁的其他实现122
7.4 基于锁的存在保证124
7.5 锁：是英雄还是恶棍125
7.5.1 应用程序中的锁：英雄125
7.5.2 并行库中的锁：只是一个工具126
7.5.3 并行化串行库时的锁：恶棍128
7.6 总结130
第8章 数据所有权131
8.1 多进程131
8.2 部分数据所有权和pthread线程库132
8.3 函数输送132
8.4 指派线程132
8.5 私有化133
8.6 数据所有权的其他用途133
第9章 延后处理134
9.1 引用计数134
9.1.1 各种引用计数的实现135
9.1.2 危险指针140
9.1.3 支持引用计数的Linux原语141
9.1.4 计数优化142
9.2 顺序锁142
9.3 读-复制-修改（RCU）145
9.3.1 RCU介绍145
9.3.2 RCU基础147
9.3.3 RCU用法155
9.3.4 Linux内核中的RCU API166
9.3.5 “玩具式”的RCU实现171
9.3.6 RCU练习188
9.4 如何选择？188
9.5 更新端怎么办190
第10章 数据结构191
10.1 从例子入手191
10.2 可分割的数据结构192
10.2.1 哈希表的设计192
10.2.2 哈希表的实现192
10.2.3 哈希表的性能195
10.3 读侧重的数据结构197
10.3.1 受RCU保护的哈希表的实现197
10.3.2 受RCU保护的哈希表的性能199
10.3.3 对受RCU保护的哈希表的讨论201
10.4 不可分割的数据结构201
10.4.1 可扩展哈希表的设计202
10.4.2 可扩展哈希表的实现203
10.4.3 可扩展哈希表的讨论210
10.4.4 其他可扩展的哈希表211
10.5 其他数据结构214
10.6 微优化214
10.6.1 实例化215
10.6.2 比特与字节215
10.6.3 硬件层面的考虑216
10.7 总结217
第11章 验证218
11.1 简介218
11.1.1 BUG来自于何处218
11.1.2 所需的心态220
11.1.3 应该何时开始验证221
11.1.4 开源之路221
11.2 跟踪222
11.3 断言223
11.4 静态分析224
11.5 代码走查224
11.5.1 审查224
11.5.2 走查225
11.5.3 自查225
11.6 几率及海森堡BUG227
11.6.1 离散测试统计228
11.6.2 滥用离散测试统计229
11.6.3 持续测试统计229
11.6.4 定位海森堡BUG232
11.7 性能评估235
11.7.1 性能基准236
11.7.2 剖析236
11.7.3 差分分析237
11.7.4 微基准237
11.7.5 隔离237
11.7.6 检测干扰238
11.8 总结242
第12章 形式验证244
12.1 通用目的的状态空间搜索244
12.1.1 Promela和Spin244
12.1.2 如何使用 Promela249
12.1.3 Promela 示例: 锁251
12.1.4 Promela 示例: QRCU254
12.1.5 Promela初试牛刀：dynticks和可抢占RCU260
12.1.6 验证可抢占RCU和dynticks264
12.2 特定目的的状态空间搜索288
12.2.1 解析Litmus测试289
12.2.2 Litmus测试意味着什么290
12.2.3 运行Litmus测试291
12.2.4 PPCMEM讨论292
12.3 公理方法293
12.4 SAT求解器294
12.5 总结295
第13章 综合应用296
13.1 计数难题296
13.1.1 对更新进行计数296
13.1.2 对查找进行计数296
13.2 使用RCU拯救并行软件性能297
13.2.1 RCU和基于每CPU变量的统计计数297
13.2.2 RCU及可插拔I/O设备的计数器300
13.2.3 数组及长度300
13.2.4 相关联的字段301
13.3 散列难题302
13.3.1 相关联的数据元素302
13.3.2 更新友好的哈希表遍历303
第14章 高级同步304
14.1 避免锁304
14.2 内存屏障304
14.2.1 内存序及内存屏障305
14.2.2 如果B在A后面，并且C在B后面，为什么C不在A后面306
14.2.3 变量可以拥有多个值307
14.2.4 能信任什么东西308
14.2.5 锁实现回顾312
14.2.6 一些简单的规则313
14.2.7 抽象内存访问模型314
14.2.8 设备操作315
14.2.9 保证315
14.2.10 什么是内存屏障316
14.2.11 锁约束325
14.2.12 内存屏障示例326
14.2.13 CPU缓存的影响328
14.2.14 哪里需要内存屏障329
14.3 非阻塞同步329
14.3.1 简单NBS330
14.3.2 NBS讨论331
第15章 并行实时计算332
15.1 什么是实时计算332
15.1.1 软实时332
15.1.2 硬实时333
15.1.3 现实世界的实时334
15.2 谁需要实时计算336
15.3 谁需要并行实时计算337
15.4 实现并行实时系统337
15.4.1 实现并行实时操作系统339
15.4.2 实现并行实时应用349
15.5 实时VS.快速：如何选择351
第16章 易于使用353
16.1 简单是什么353
16.2 API设计的Rusty准则353
16.3 修整Mandelbrot集合354
第17章 未来的冲突357
17.1 曾经的CPU技术不代表未来357
17.1.1 单处理器Uber Alles358
17.1.2 多线程Mania359
17.1.3 更多类似的场景359
17.1.4 撞上内存墙359
17.2 事务内存360
17.2.1 外部世界361
17.2.2 进程修改364
17.2.3 同步367
17.2.4 讨论370
17.3 硬件事务内存371
17.3.1 HTM与锁相比的优势372
17.3.2 HTM与锁相比的劣势373
17.3.3 HTM与增强后的锁机制相比的劣势379
17.3.4 HTM最适合的场合380
17.3.5 潜在的搅局者380
17.3.6 结论382
17.4 并行函数式编程383
附录A 重要问题385
A.1 “After”的含义是什么385
A.2 “并发”和“并行”之间的差异是什么388
A.3 现在是什么时间389
附录B 同步原语391
B.1 组织和初始化391
B.1.1 smp_init()391
B.2 线程创建、销毁及控制392
B.2.1 create_thread()392
B.2.2 smp_thread_id()392
B.2.3 for_each_thread()392
B.2.4 for_each_running_thread()392
B.2.5 wait_thread()393
B.2.6 wait_all_threads()393
B.2.7 用法示例393
B.3 锁394
B.3.1 spin_lock_init()394
B.3.2 spin_lock()394
B.3.3 spin_trylock()394
B.3.4 spin_unlock()394
B.3.5 用法示例395
B.4 每线程变量395
B.4.1 DEFINE_PER_THREAD()395
B.4.2 DECLARE_PER_THREAD()395
B.4.3 per_thread()395
B.4.4 __get_thread_var()396
B.4.5 init_per_thread()396
B.4.6 用法示例396
B.5 性能396
附录C 为什么需要内存屏障397
C.1 缓存结构397
C.2 缓存一致性协议399
C.2.1 MESI状态399
C.2.2 MESI协议消息400
C.2.3 MESI状态图400
C.2.4 MESI协议示例401
C.3 存储导致不必要的停顿402
C.3.1 存储缓冲403
C.3.2 存储转发403
C.3.3 存储缓冲区及内存屏障404
C.4 存储序列导致不必要的停顿406
C.4.1 使无效队列406
C.4.2 使无效队列及使无效应答407
C.4.3 使无效队列及内存屏障407
C.5 读和写内存屏障409
C.6 内存屏障示例410
C.6.1 乱序体系结构410
C.6.2 示例1411
C.6.3 示例2412
C.6.4 示例3412
C.7 特定的内存屏障指令413
C.7.1 Alpha414
C.7.2 AMD64417
C.7.3 ARMv7-A/R417
C.7.4 IA64418
C.7.5 PA-RISC418
C.7.6 POWER / Power PC418
C.7.7 SPARC RMO、PSO及TSO419
C.7.8 x86420
C.7.9 zSeries421
C.8 内存屏障是永恒的吗421
C.9 对硬件设计者的建议422
附录D 问题答案423
D.1 如何使用本书423
D.2 简介424
D.3 硬件和它的习惯427
D.4 办事的家伙429
D.5 计数433
D.6 对分割和同步的设计445
D.7 锁449
D.8 数据所有权455
D.9 延迟处理456
D.10 数据结构471
D.11 验证473
D.12 形式验证478
D.13 综合应用481
D.14 高级同步483
D.15 并行实时计算486
D.16 易于使用487
D.17 未来的冲突487
D.18 重要问题490
D.19 同步原语491
D.20 为什么需要内存屏障491
附录E 术语495
附录F 感谢502
F.1 评审者502
F.2 硬件提供者502
F.3 原始出处503
F.4 图表作者503
F.5 其他帮助505
