深入理解并行编程 PDF 文档

Question

本书的目的是帮助您理解：如何编写基于共享内存的并行程序，而不用经历一次危险的旅程。通过描述以往行之有效的算法及设计，我们希望帮助您避免一些将困扰并行编程的意外错误。但是，您应当把本书作为工作的基础，而不是把它作为解决问题的全部指南。如果您认可的话，您的使命是帮助促进并行编程的发展，最终使得本书显得过时；并行编程将不再被认为是困难的，希望本书对您来说显得更简单。

目录

深入理解并行编程
1. 简介.........................................................................................................14
1.1. 导致并行编程困难的历史原因......................................................14
1.2. 并行编程的目标..............................................................................15
1.2.1. 性能...........................................................................................16
1.2.2. 生产率.......................................................................................17
1.2.3. 通用性.......................................................................................18
1.3. 并行编程的替代方案......................................................................20
1.3.1. 顺序应用多实例化...................................................................20
1.3.2. 使用现有的并行软件...............................................................21
1.3.3. 性能优化...................................................................................21
1.4. 是什么使并行编程变得复杂？......................................................22
1.4.1. 工作分割...................................................................................22
1.4.2. 并行访问控制...........................................................................23
1.4.3. 资源分割和复制.......................................................................24
1.4.4. 与硬件交互...............................................................................24
1.4.5. 组合使用...................................................................................24
1.4.6. 语言和环境如何对这样的任务进行支持？...........................25
1.5. 本书导读..........................................................................................25
1.5.1. 小问题.......................................................................................25
1.5.2. 随书源码...................................................................................26
2. 硬件的习性.............................................................................................28
2.1. 概述..................................................................................................28
2.1.1. CPU 流水线..............................................................................29
2.1.2. 内存引用...................................................................................30
2.1.3. 原子操作...................................................................................31
2.1.4. 内存屏障...................................................................................32
2.1.5. Cache Miss................................................................................33
2.1.6. I/O 操作 ....................................................................................34
2.2. 开销..................................................................................................35
2.2.1. 硬件体系结构...........................................................................36
2.2.2. 操作的开销...............................................................................37
2.3. 硬件的免费午餐?............................................................................38
2.3.1. 3D 集成.....................................................................................39
2.3.2. 新材料和新工艺.......................................................................39
2.3.3. 专用加速器...............................................................................39
2.3.4. 现有的并行软件.......................................................................40
2.4. 软件设计 Implication ......................................................................40
3. 工具.........................................................................................................43
3.1. 脚本语言..........................................................................................43
3.2. POSIX 多进程.................................................................................44
3.2.1. POSIX 进程创建和撤销..........................................................44
3.2.2. POSIX 线程的创建和撤销......................................................46
3.2.3. POSIX 锁..................................................................................48
3.2.4. POSIX 读写锁..........................................................................52
3.3. 原子操作..........................................................................................55
3.4. Linux 内核中类似 POSIX 的操作 .................................................56
3.5. 趁手的工具——该如何选择？......................................................58
4. 计数.........................................................................................................59
4.1. 为什么并发计数不可小看？..........................................................60
4.2. 统计计数器......................................................................................62
4.2.1. 设计...........................................................................................62
4.2.2. 基于数组的实现.......................................................................62
4.2.3. 结果一致的实现.......................................................................64
4.2.4. 基于每线程变量的实现...........................................................66
4.2.5. 讨论...........................................................................................69
4.3. 近似上限计数器..............................................................................69
4.3.1. 设计...........................................................................................69
4.3.2. 简单的上限计数器实现...........................................................70
4.3.3. 关于简单上限计数器的讨论...................................................76
4.3.4. 近似上限计数器的实现...........................................................76
4.3.5. 关于近似上限计数器的讨论...................................................77
4.4. 精确上限计数器..............................................................................77
4.4.1. 原子上限计数器的实现...........................................................77
4.4.2. 关于原子上限计数器的讨论...................................................86
4.4.3. Signal-Theft 上限计数器的设计 .............................................86
4.4.4. Signal-Theft 上限计数器的实现 .............................................87
4.4.5. Signal-Theft 上限计数器讨论 .................................................94
4.5. 特殊的并行计数器..........................................................................95
4.6. 并行计数的讨论..............................................................................96
5. 分割和同步设计...................................................................................100
5.1. 分割练习........................................................................................100
5.1.1. 哲学家就餐问题.....................................................................100
5.1.2. 双端队列.................................................................................102
5.1.3. 关于分割问题示例的讨论..................................................... 111
5.2. 设计准则........................................................................................ 111
5.3. 同步粒度........................................................................................113
5.3.1. 串行程序.................................................................................114
5.3.2. 代码锁.....................................................................................116
5.3.3. 数据锁.....................................................................................117
5.3.4. 数据所有权.............................................................................120
5.3.5. 锁粒度与性能.........................................................................121
5.4. 并行快速路径................................................................................121
5.4.1. 读写锁.....................................................................................122
5.4.2. 层级锁.....................................................................................123
5.4.3. 资源分配器缓存.....................................................................125
5.5. 性能总结........................................................................................131
6. 锁...........................................................................................................132
6.1. 生存（staying alive） ...................................................................133
6.1.1. 死锁.........................................................................................133
6.1.2. 活锁.........................................................................................136
6.1.3. 不公平.....................................................................................137
6.1.4. 低效率.....................................................................................137
6.2. 锁的类型........................................................................................137
6.2.1. 互斥锁.....................................................................................138
6.2.2. 读写锁.....................................................................................138
6.2.3. Beyond Reader-Writer Locks .................................................138
6.3. 基于锁的存在担保（existence guarantee）................................138
7. 数据所有者...........................................................................................140
8. 延迟处理...............................................................................................142
8.1. 屏障................................................................................................142
8.2. 引用计数........................................................................................142
8.2.1. 引用计数类型的实现.............................................................143
8.2.2. 支持引用计数的 Linux 原语.................................................150
8.2.3. 计数器优化.............................................................................151
8.3. Read-Copy Update（RCU）.........................................................151
8.3.1. RCU 基础 ...............................................................................151
8.3.2. RCU 用法 ...............................................................................163
8.3.3. Linux 内核中的 RCU API......................................................176
8.3.4. “玩具式”的 RCU 实现 ......................................................183
8.3.5. RCU 练习 ...............................................................................206
9. 使用 RCU .............................................................................................207
9.1. RCU 和基于每线程变量的统计计数器 ......................................207
9.1.1. 设计.........................................................................................207
9.1.2. 实现.........................................................................................207
9.1.3. 讨论.........................................................................................211
9.2. RCU 和可移除 I/O 设备的计数器...............................................211
10. 验证：调试及分析...............................................................................214
11. 数据结构...............................................................................................216
12. 高级同步...............................................................................................218
12.1. 避免锁............................................................................................218
12.2. 内存屏障........................................................................................218
12.2.1. 内存序及内存屏障..........................................................218
12.2.2. 如果 B 在 A 后面, 并且 C 在 B 后面, 为什么 C 不在 A 后面? 220
12.2.3. 变量可以拥有多个值......................................................221
12.2.4. 能信任什么东西?............................................................222
12.2.5. 锁实现回顾......................................................................229
12.2.6. 一些简单的规则..............................................................230
12.2.7. 抽象内存访问模型..........................................................230
12.2.8. 设备操作..........................................................................233
12.2.9. 保证..................................................................................233
12.2.10. 什么是内存屏障?............................................................234
12.2.11. 锁约束..............................................................................247
12.2.12. 内存屏障示例..................................................................248
12.2.13. CPU..................................................................................251
12.2.14. 哪里需要内存屏障?........................................................253
12.3. 非阻塞同步....................................................................................253
12.3.1. 简单 NBS........................................................................253
12.3.2. 冒险指针..........................................................................253
12.3.3. 原子数据结构..................................................................253
12.3.4. ``Macho'' NBS..................................................................253
13. 易于使用...............................................................................................254
13.1. Rusty Scale for API Design ...........................................................254
13.2. Shaving the Mandelbrot Set...........................................................255
14. 时间管理...............................................................................................258
15. 未来的冲突...........................................................................................259
15.1. 可交易内存....................................................................................259
15.1.1. I/O 操作 ..........................................................................260
15.1.2. RPC 操作........................................................................260
15.1.3. 内存映射操作..................................................................261
15.1.4. 多线程事务......................................................................262
15.1.5. 外部的事务访问..............................................................263
15.1.6. 延时..................................................................................264
15.1.7. 锁......................................................................................264
15.1.8. 读者-写者锁 ....................................................................265
15.1.9. 持续性..............................................................................266
TM 如何提供类似的持续性功能？.................................................................266
15.1.10. 动态链接装载..................................................................266
15.1.11. 调试..................................................................................267
15.1.12. exec() 系统调用..............................................................268
15.1.13. RCU .................................................................................268
15.1.14. 讨论..................................................................................270
15.2. 共享内存并行编程........................................................................270
15.3. 基于任务的并行编程....................................................................270
A. 重要问题...............................................................................................271
A.1 “after“的含义是什么?...................................................................271
B. 同步原语...............................................................................................277
B.1 初始化............................................................................................277
B.1.1 smp_init()................................................................................277
B.2 线程创建、销毁及控制................................................................278
B.2.1 create_thread() ........................................................................278
B.2.2 smp_thread_id()......................................................................278
B.2.3 for_each_thread()....................................................................278
B.2.4 for_each_running_thread() .....................................................279
B.2.5 wait_thread()...........................................................................279
B.2.6 wait_all_threads() ...................................................................279
B.2.7 用法示例..........................................................................279
B.3 锁....................................................................................................280
B.3.1 spin_lock_init().......................................................................280
B.3.2 spin_lock() ..............................................................................280
B.3.3 spin_trylock()..........................................................................281
B.3.4 spin_unlock() ..........................................................................281
B.3.5 用法示例..........................................................................281
B.4 每线程变量....................................................................................281
B.4.1 DEFINE_PER_THREAD()....................................................282
B.4.2 DECLARE_PER_THREAD()................................................282
B.4.3 per_thread().............................................................................282
B.4.4 __get_thread_var()..................................................................282
B.4.5 init_per_thread() .....................................................................282
B.4.6 用法示例..........................................................................282
B.5 性能................................................................................................283
C. 为什么使用内存屏障...........................................................................284
C.1 Cache 结构....................................................................................284
C.2 缓存一致性协议............................................................................286
C.2.1 MESI 状态.............................................................................286
C.2.2 MESI 协议消息.....................................................................287
C.2.3 MESI 状态图..........................................................................288
C.2.4 MESI 协议示例.....................................................................289
C.3 不必要的存储延迟........................................................................291
C.3.1 Store Buffers...........................................................................291
C.3.2 Store Forwarding ....................................................................292
C.3.3 存储缓冲区及内存屏障..................................................293
C.4 不必要的存储延迟........................................................................296
C.4.1 无效队列..........................................................................296
C.4.2 使无效队列及使无效应答..............................................296
C.4.3 无效队列及内存屏障......................................................297
C.5 读和写内存屏障............................................................................300
C.6 内存屏障示例................................................................................300
C.6.1 乱序体系结构..................................................................300
C.6.2 示例 1..............................................................................301
C.6.3 示例 2..............................................................................302
C.6.4 示例 3..............................................................................303
C.7 特定 CPUs 的内存屏障指令 ........................................................304
C.7.1 Alpha.......................................................................................306
C.7.2 AMD64 ...................................................................................308
C.7.3 ARMv7-A/R ...........................................................................309
6 ISB();...............................................................................................................309
C.7.4 IA64 ........................................................................................309
C.7.5 PA-RISC..................................................................................310
C.7.6 POWER / Power PC ...............................................................310
C.7.7 SPARC RMO, PSO, and TSO ................................................311
C.7.8 x86...........................................................................................312
C.7.9 zSeries.....................................................................................313
C.8 内存屏障是永恒的?......................................................................313
C.9 对硬件设计者的建议....................................................................314
D. RCU 实现 .............................................................................................315
D.1 可睡眠 RCU 实现........................................................................315
D.1.1 SRCU 实现原理....................................................................316
D.1.2 SRCU API 及用法.................................................................317
D.1.3 实现..................................................................................320
D.1.4 SRCU 概述............................................................................326
D.2 分级 RCU 概述 ...........................................................................326
D.2.1 RCU 基础回顾 ......................................................................326
D.2.2 经典 RCU 实现概要......................................................327
D.2.3 RCU 迫切要解决的问题.......................................................328
D.2.4 可扩展 RCU 实现...........................................................329
D.2.5 迈向不成熟的 RCU 实现...............................................332
D.2.6 状态机..............................................................................334
D.2.7 用例..................................................................................335
D.2.8 测试..................................................................................340
D.2.9 结论..................................................................................345
D.3 分级 RCU 代码走查.....................................................................346
D.3.1 数据结构及内核参数......................................................346
D.3.2 外部接口..........................................................................354
D.3.3 初始化..............................................................................362
D.3.4 CPU 热插拨...........................................................................367
D.3.5 杂项函数..........................................................................372
D.3.6 Grace-Period 检测函数 ..........................................................373
D.3.7 Dyntick-Idle 函数..................................................................385
D.3.8 强制静止状态..................................................................390
D.3.9 CPU-延迟检测 .......................................................................397
D.3.10 可能的缺陷及变更..........................................................400
D.4 可抢占 RCU .................................................................................400
D.4.1 RCU 概念 ...............................................................................401
D.4.2 可抢占 RCU 算法概述 ...................................................402
D.4.3 验证可抢占 RCU............................................................419
E. 形式验证...............................................................................................422
E.1 什么是 Promela 和 Spin? ...........................................................422
E.2 Promela 示例: 非原子性递增.....................................................423
E.3 Promela 示例: 原子递增.............................................................426
E.3.1 组合.........................................................................................427
E.4 如何使用 Promela ........................................................................428
E.4.1 Promela 特性 .........................................................................428
E.4.2 Promela 编程技巧 ..................................................................429
E.5 Promela 示例: 锁.........................................................................430
E.6 Promela 示例: QRCU...................................................................433
E.6.1 运行 QRCU 示例 .................................................................438
E.6.2 到底需要多少读者和写者?...................................................439
E.6.3 可选方法: 正确性校验..........................................................439
E.6.4 可选方法: 更多工具..............................................................440
E.6.5 可选方法: 分而治之..............................................................440
E.7 Promela Parable: dynticks 和可抢占 RCU .................................440
E.7.1 可抢占 RCU 和 dynticks 介绍............................................441
E.7.2 验证可抢占 RCU 和 dynticks................................................445
E.7.3 回顾.........................................................................................466
E.8 简单的避免形式校验....................................................................467
E.8.1 简单 Dynticks 接口的状态变量 ...........................................467
E.8.2 进入和退出 Dynticks-Idle 模式............................................468
E.8.3 从 Dynticks-Idle 模式进入 NMIs.........................................469
E.8.4 Interrupts From Dynticks-Idle Mode ......................................470
E.8.5 检查 Dynticks 静止状态.......................................................471
E.8.6 讨论.........................................................................................473
E.9 概要................................................................................................473
F. 问题答案...............................................................................................474
G. 术语表...................................................................................................475
H. 感谢.......................................................................................................476

下载地址：https://www.wenjiangs.com/wp-content/uploads/2021/09/understanding-parallel-programming.zip