深入理解并行编程 PDF 文档 - PDF 电子书

深入理解并行编程 PDF 文档

发布于 2021-09-26 字数 28509 浏览 922 评论 0

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

深入理解并行编程 PDF 文档

目录

深入理解并行编程
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

如果你对这篇文章有疑问,欢迎到本站 社区 发帖提问或使用手Q扫描下方二维码加群参与讨论,获取更多帮助。

扫码加入群聊

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

目前还没有任何评论,快来抢沙发吧!

关于作者

JSmiles

生命进入颠沛而奔忙的本质状态,并将以不断告别和相遇的陈旧方式继续下去。

2512 文章
30 评论
82839 人气
更多

推荐作者

qianbiandeboy

文章 0 评论 0

少女净妖师

文章 2 评论 0

zangqw

文章 0 评论 0

qq_7HKsl

文章 0 评论 0

伪装你

文章 1 评论 0