深入理解并行编程(第2版)电子书

前折页

内容简介

推荐序

译者序

第1章　如何使用本书

1.1　路线图

1.2　小问题

1.3　本书之外的选择

1.4　示例源代码

1.5　这本书属于谁

第2章　简介

2.1　导致并行编程困难的历史原因

2.2　并行编程的目标

2.2.1　性能

2.2.2　生产率

2.2.3　通用性

2.3　并行编程的替代方案

2.3.1　运行多个串行应用实例

2.3.2　利用现有的并行软件

2.3.3　性能优化

2.4　是什么使并行编程变得复杂

2.4.1　任务分片

2.4.2　并行访问控制

2.4.3　资源分片和复制

2.4.4　与硬件交互

2.4.5　组合使用

2.4.6　语言和环境如何支持这些任务

2.5　本章讨论

第3章　硬件和它的特性

3.1　概述

3.1.1　流水线式的CPU

3.1.2　内存引用

3.1.3　原子操作

3.1.4　内存屏障

3.1.5　缓存未命中

3.1.6　I/O操作

3.2　开销

3.2.1　硬件体系结构

3.2.2　操作的开销

3.2.3　硬件上的优化

3.3　硬件免费午餐

3.3.1　3D集成

3.3.2　新材料和新工艺

3.3.3　用光来替换电子

3.3.4　专用加速器

3.3.5　已有的并行软件

3.4　对软件设计的启示

第4章　编程的工具

4.1　脚本语言

4.2　POSIX多进程

4.2.1　POSIX进程的创建和销毁

4.2.2　POSIX线程的创建和销毁

4.2.3　POSIX锁

4.2.4　POSIX读写锁

4.2.5　原子操作（经典GCC）

4.2.6　原子操作（C11）

4.2.7　原子操作（现代GCC）

4.2.8　每线程变量

4.3　POSIX接口的替代者

4.3.1　代码组织和初始化

4.3.2　线程创建、销毁和控制

4.3.3　锁操作

4.3.4　访问共享变量

4.3.5　原子操作

4.3.6　每CPU变量

4.4　正确的工具：如何选择

第5章　计数

5.1　为什么不可小看并发计数

5.2　统计计数器

5.2.1　设计

5.2.2　基于数组的实现

5.2.3　基于每线程变量的实现

5.2.4　最终一致性的实现

5.2.5　本节讨论

5.3　近似上限计数器

5.3.1　设计

5.3.2　简单上限计数器的实现

5.3.3　关于简单上限计数器的讨论

5.3.4　近似上限计数器的实现

5.3.5　关于近似上限计数器的讨论

5.4　精确上限计数器

5.4.1　原子上限计数器的实现

5.4.2　关于原子上限计数器的讨论

5.4.3　信号-窃取（Signal-Theft）上限计数器的设计

5.4.4　信号-窃取上限计数器的实现

5.4.5　关于信号-窃取上限计数器的讨论

5.4.6　精确上限计数器的应用

5.5　关于并行计数的讨论

5.5.1　并行计数的性能

5.5.2　并行计数的专门化

5.5.3　从并行计数中学到了什么

第6章　对分片和同步的设计

6.1　分片练习

6.1.1　哲学家就餐问题

6.1.2　双端队列

6.1.3　关于分片问题示例的讨论

6.2　设计准则

6.3　同步粒度

6.3.1　串行程序

6.3.2　代码锁

6.3.3　数据锁

6.3.4　数据所有权

6.3.5　锁粒度和性能

6.4　并行快速路径

6.4.1　读写锁

6.4.2　层次锁

6.4.3　资源分配器缓存

6.5　分片以外

6.5.1　使用工作队列的迷宫问题的并行解法

6.5.2　迷宫问题的另一种并行解法

6.5.3　性能比较I

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

6.5.5　性能比较II

6.5.6　未来展望与本节总结

6.6　分片、并行化与优化

第7章　锁

7.1　努力活着

7.1.1　死锁

7.1.2　活锁与饥饿

7.1.3　不公平的锁

7.1.4　低效率的锁

7.2　锁的类型

7.2.1　互斥锁

7.2.2　读写锁

7.2.3　读写锁之外的锁

7.2.4　作用域锁

7.3　锁在实现中的问题

7.3.1　基于原子交换的互斥锁实现示例

7.3.2　互斥锁的其他实现

7.4　基于锁的存在性保证

7.5　锁：是英雄还是坏蛋

7.5.1　应用程序中的锁：英雄

7.5.2　并行库中的锁：只是一个工具

7.5.3　并行化串行库时的锁：坏蛋

7.6　本章总结

第8章　数据所有权

8.1　多进程

8.2　部分数据所有权和pthreads

8.3　函数输送

8.4　指派线程

8.5　私有化

8.6　数据所有权的其他用途

第9章　延迟处理

9.1　运行示例

9.2　引用计数

9.3　危险指针

9.4　顺序锁

9.5　读-复制-更新

9.5.1　RCU介绍

9.5.2　RCU基础机制

9.5.3　Linux内核RCU API

9.5.4　RCU的使用

9.5.5　RCU相关工作

9.5.6　RCU练习

9.6　如何选择

9.6.1　概述

9.6.2　细节

9.6.3　产品应用

9.7　如何处理写操作

第10章　数据结构

10.1　示例应用

10.2　可分片数据结构

10.2.1　哈希表的设计

10.2.2　哈希表的实现

10.2.3　哈希表的性能

10.3　主读数据结构

10.3.1　受RCU保护的哈希表的实现

10.3.2　受RCU保护的哈希表的性能分析

10.3.3　受RCU保护的哈希表的相关讨论

10.4　不可分片的数据结构

10.4.1　可变长哈希表的设计

10.4.2　可变长哈希表的实现

10.4.3　对可变长哈希表的探讨

10.4.4　其他类型的可变长哈希表

10.5　其他数据结构

10.6　微优化

10.6.1　专用化

10.6.2　位与字节

10.6.3　硬件适配

10.7　本章总结

第11章　验证

11.1　简介

11.1.1　Bug来自何处

11.1.2　验证时所需的心态

11.1.3　应该从何时开始验证

11.1.4　开源之路

11.2　跟踪

11.3　断言

11.4　静态分析

11.5　代码评审

11.5.1　审查

11.5.2　走查

11.5.3　自查

11.6　概率及海森堡Bug

11.6.1　离散测试统计

11.6.2　简单离散测试统计

11.6.3　持续测试统计

11.6.4　定位海森堡Bug

11.7　性能评估

11.7.1　性能基准测试

11.7.2　剖析

11.7.3　差异分析

11.7.4　微基准测试

11.7.5　隔离

11.7.6　检测干扰

11.8　本章总结

第12章　形式化验证

12.1　通用目的的状态空间搜索

12.1.1　Promela和Spin

12.1.2　如何使用Promela

12.1.3　Promela示例：锁

12.1.4　Promela示例：QRCU

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

12.1.6　验证dynticks和可抢占RCU

12.2　特定目的的状态空间搜索

12.2.1　对litmus测试的剖析

12.2.2　litmus测试代表什么

12.2.3　运行litmus测试

12.2.4　PPCMEM讨论

12.3　公理方法

12.3.1　公理方法和加锁

12.3.2　公理方法和RCU

12.4　SAT求解器

12.5　无状态模型检查器

12.6　本章总结

12.7　选择验证方案

第13章　合而为一

13.1　计数器难题

13.1.1　计数更新

13.1.2　计数查找

13.2　引用计数再改造

13.2.1　引用计数分类的实现

13.2.2　计数器优化

13.3　使用危险指针做辅助

13.3.1　可扩展的引用计数

13.4　顺序锁的特殊用法

13.4.1　关联数据元素

13.4.2　升级为写端

13.5　使用RCU补救程序

13.5.1　RCU和基于每线程变量的统计计数器

13.5.2　针对可移除I/O的RCU和计数器

13.5.3　数组和长度

13.5.4　关联字段

13.5.5　对更新友好的遍历

13.5.6　再谈可扩展引用计数

第14章　高级同步

14.1　避免使用锁

14.2　非阻塞同步

14.2.1　简单NBS

14.2.2　对NBS优点的应用

14.2.3　NBS相关讨论

14.3　并行实时计算

14.3.1　什么是实时计算

14.3.2　谁需要实时计算

14.3.3　谁需要并行实时计算

14.3.4　并行实时系统的实现

14.3.5　并行实时操作系统的实现

14.3.6　实现并行实时应用

14.3.7　实时计算和高速计算：如何选择

第15章　高级同步：内存序

15.1　有序：为什么和怎么做

15.1.1　硬件为什么会打乱内存访问顺序

15.1.2　如何强制有序

15.1.3　基本经验法则

15.2　技巧和陷阱

15.2.1　具有多个值的变量

15.2.2　内存引用重排

15.2.3　地址依赖

15.2.4　数据依赖

15.2.5　控制依赖

15.2.6　缓存一致性

15.2.7　多拷贝原子性

15.3　编译时的困惑

15.3.1　内存引用的限制

15.3.2　地址依赖和数据依赖的困难

15.3.3　控制依赖造成的灾难

15.4　高级原语

15.4.1　内存分配

15.4.2　RCU

15.5　硬件相关的内存序

15.5.1　Alpha

15.5.2　ARMv7-A/R

15.5.3　ARMv8

15.5.4　Itanium

15.5.5　MIPS

15.5.6　POWER/PowerPC

15.5.7　SPARC TSO

15.5.8　x86

15.5.9　z Systems

15.6　哪里需要对内存排序

第16章　易于使用

16.1　简单是什么

16.2　Rusty Scale API设计

16.3　修整Mandelbrot集合

第17章　未来的冲突

17.1　曾经的CPU技术不代表未来

17.1.1　单处理器统治一切

17.1.2　多线程狂热

17.1.3　更多的是一成不变

17.1.4　撞上内存墙

17.1.5　惊人的加速器

17.2　事务内存

17.2.1　外部世界

17.2.2　进程修改

17.2.3　同步

17.2.4　讨论

17.3　硬件事务内存

17.3.1　HTM与锁相比的优势

17.3.2　HTM与锁相比的劣势

17.3.3　HTM与增强后的锁机制相比的劣势

17.3.4　HTM最适合的场合

17.3.5　潜在的搅局者

17.3.6　结论

17.4　形式化回归测试

17.4.1　自动转换

17.4.2　环境

17.4.3　性能开销

17.4.4　定位Bug

17.4.5　最简单的脚手架

17.4.6　相关的Bug

17.4.7　形式化回归工具评分表

17.5　并行函数式编程

17.6　本章总结

第18章　回顾过去，展望未来

附录A　重要问题

附录B　“玩具式”的RCU实现

附录C　为什么需要内存屏障

附录D　小问题答案

后折页