深入理解并行编程

第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 流水线CPU 16

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 性能比较I 102

6.5.4 另一种迷宫问题的串行解法 104

6.5.5 性能比较II 104

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 API 166

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 几率及海森堡BUG 227

11.6.1 离散测试统计 228

11.6.2 滥用离散测试统计 229

11.6.3 持续测试统计 229

11.6.4 定位海森堡BUG 232

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和Spin 244

12.1.2 如何使用 Promela 249

12.1.3 Promela 示例: 锁 251

12.1.4 Promela 示例: QRCU 254

12.1.5 Promela初试牛刀：dynticks和可抢占RCU 260

12.1.6 验证可抢占RCU和dynticks 264

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 简单NBS 330

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 Alles 358

17.1.2 多线程Mania 359

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 示例1 411

C.6.3 示例2 412

C.6.4 示例3 412

C.7 特定的内存屏障指令 413

C.7.1 Alpha 414

C.7.2 AMD64 417

C.7.3 ARMv7-A/R 417

C.7.4 IA64 418

C.7.5 PA-RISC 418

C.7.6 POWER / Power PC 418

C.7.7 SPARC RMO、PSO及TSO 419

C.7.8 x86 420

C.7.9 zSeries 421

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

......(更多)