深入理解并行编程 _生活百科

文章插图
深入理解并行编程【深入理解并行编程】《深入理解并行编程》一书原作者Paul E.Mckenney （保罗·E·麦肯尼），中文版由谢宝友、鲁阳译，电子工业出版社2017年7月出版
基本介绍书名：深入理解并行编程
作者：【美】Paul E.Mckenney （保罗·E·麦肯尼）
译者：谢宝友鲁阳
ISBN：978-7-121-31508-4
页数：524
定价：129.00
出版社：电子工业出版社
出版时间：2017年7月
开本：16
内容提要《深入理解并行编程》首先以霍金提出的两个理论物理限制为引子，解释了多核并行计算兴起的原因，并从硬体的角度阐述并行编程的难题。接着，《深入理解并行编程》以常见的计数器为例，探讨其不同的实现方法及适用场景。在这些实现方法中，除了介绍常见的锁以外，《深入理解并行编程》还重点介绍了RCU的使用及其原理，以及实现RCU的基础：记忆体屏障。最后，《深入理解并行编程》还介绍了并行软体的验证，以及并行实时计算等内容。《深入理解并行编程》适合于对并行编程有兴趣的大学生、研究生，以及需要对项目进行深度性能最佳化的软硬体工程师，特别值得一提的是，《深入理解并行编程》对作业系统核心工程师也很有价值。目录第1章如何使用本书 11.1 路线图 11.2 小问题 21.3　除本书之外的选择 31.4 示例原始码 41.5 这本书属于谁 4第2章简介 62.1 导致并行编程困难的历史原因 62.2 并行编程的目标 72.2.1 性能 82.2.2 生产率 92.2.3 通用性 92.3 并行编程的替代方案 112.3.1 串列套用的多个实例 112.3.2 使用现有的并行软体 112.3.3 性能最佳化 122.4 是什幺使并行编程变得複杂 122.4.1 分割任务 132.4.2 并行访问控制 132.4.3 资源分割和複製 142.4.4 与硬体的互动 142.4.5 组合使用 142.4.6 语言和环境如何支持这些任务 142.5 本章的讨论 15第3章硬体和它的习惯 163.1 概述 163.1.1 流水线CPU 163.1.2 记忆体引用 173.1.3 原子操作 183.1.4 记忆体屏障 193.1.5 高速快取未命中 193.1.6 I/O操作 193.2 开销 203.2.1 硬体体系结构 203.2.2 操作的开销 213.3 硬体的免费午餐 233.3.1 3D集成 233.3.2 新材料和新工艺 243.3.3 是光，不是电子 243.3.4 专用加速器 243.3.5 现有的并行软体 253.4 对软体设计的启示 25第4章办事的家伙 274.1 脚本语言 274.2 POSIX多进程 284.2.1 POSIX进程创建和销毁 284.2.2 POSIX执行绪创建和销毁 304.2.3 POSIX锁 314.2.4 POSIX读/写锁 344.3 原子操作 374.4 Linux核心中类似POSIX的操作 384.5 如何选择趁手的工具 39第5章计数 405.1 为什幺并发计数不可小看 415.2 统计计数器 425.2.1 设计 435.2.2 基于数组的实现 435.2.3 最终结果一致的实现 445.2.4 基于每执行绪变数的实现 465.2.5 本节讨论 485.3 近似上限计数器 485.3.1 设计 485.3.2 简单的上限计数实现 505.3.3 关于简单上限计数的讨论 555.3.4 近似上限计数器的实现 555.3.5 关于近似上限计数器的讨论 555.4 精确上限计数 565.4.1 原子上限计数的实现 565.4.2 关于原子上限计数的讨论 625.4.3 Signal-Theft上限计数的设计 625.4.4 Signal-Theft上限计数的实现 635.4.5 关于Signal-Theft上限计数的讨论 685.5 特殊场合的并行计数 685.6 关于并行计数的讨论 695.6.1 并行计数的性能 705.6.2 并行计数的专门化 715.6.3 从并行计数中学到什幺 71第6章对分割和同步的设计 736.1 分割练习 736.1.1 哲学家就餐问题 736.1.2 双端伫列 756.1.3 关于分割问题示例的讨论 816.2 设计準则 826.3 同步粒度 836.3.1 串列程式 846.3.2 代码锁 856.3.3 数据锁 866.3.4 数据所有权 886.3.5 锁粒度与性能 886.4 并行快速路径 906.4.1 读/写锁 916.4.2 层次锁 916.4.3 资源分配器快取 926.5 分割之外 976.5.1 使用工作伫列的迷宫问题并行解法 976.5.2 另一种迷宫问题的并行解法 1006.5.3 性能比较I 1026.5.4 另一种迷宫问题的串列解法 1046.5.5 性能比较II 1046.5.6 未来展望与本节总结 1056.6 分割、并行化与最佳化 106第7章锁 1077.1 努力活着 1087.1.1 死锁 1087.1.2 活锁与饥饿 1147.1.3 不公平的锁 1167.1.4 低效率的锁 1177.2 锁的类型 1177.2.1 互斥锁 1177.2.2 读/写锁 1187.2.3 读/写锁之外 1187.2.4 範围锁 1197.3 锁在实现中的问题 1217.3.1 基于原子交换的互斥锁实现示例 1217.3.2 互斥锁的其他实现 1227.4 基于锁的存在保证 124 7.5 锁：是英雄还是恶棍 1257.5.1 应用程式中的锁：英雄 1257.5.2 并行库中的锁：只是一个工具 1267.5.3 并行化串列库时的锁：恶棍 1287.6 总结 130第8章数据所有权 1318.1 多进程 1318.2 部分数据所有权和pthread执行绪库 1328.3 函式输送 1328.4 指派执行绪 1328.5 私有化 1338.6 数据所有权的其他用途 133第9章延后处理 1349.1 引用计数 1349.1.1 各种引用计数的实现 1359.1.2 危险指针 1409.1.3 支持引用计数的Linux原语 1419.1.4 计数最佳化 1429.2 顺序锁 1429.3 读-複製-修改（RCU） 1459.3.1 RCU介绍 1459.3.2 RCU基础 1479.3.3 RCU用法 1559.3.4 Linux核心中的RCU API 1669.3.5 “玩具式”的RCU实现 1719.3.6 RCU练习 1889.4 如何选择？ 1889.5 更新端怎幺办 190第10章数据结构 19110.1 从例子入手 19110.2 可分割的数据结构 19210.2.1 哈希表的设计 19210.2.2 哈希表的实现 19210.2.3 哈希表的性能 19510.3 读侧重的数据结构 19710.3.1 受RCU保护的哈希表的实现 19710.3.2 受RCU保护的哈希表的性能 19910.3.3 对受RCU保护的哈希表的讨论 20110.4 不可分割的数据结构 20110.4.1 可扩展哈希表的设计 20210.4.2 可扩展哈希表的实现 20310.4.3 可扩展哈希表的讨论 21010.4.4 其他可扩展的哈希表 21110.5 其他数据结构 21410.6 微最佳化 21410.6.1 实例化 21510.6.2 比特与位元组 21510.6.3 硬体层面的考虑 21610.7 总结 217第11章验证 21811.1 简介 21811.1.1 BUG来自于何处 21811.1.2 所需的心态 22011.1.3 应该何时开始验证 22111.1.4 开源之路 22111.2 跟蹤 22211.3 断言 22311.4 静态分析 22411.5 代码走查 22411.5.1 审查 22411.5.2 走查 22511.5.3 自查 225 11.6 几率及海森堡BUG 22711.6.1 离散测试统计 22811.6.2 滥用离散测试统计 22911.6.3 持续测试统计 22911.6.4 定位海森堡BUG 23211.7 性能评估 23511.7.1 性能基準 23611.7.2 剖析 23611.7.3 差分分析 23711.7.4 微基準 23711.7.5 隔离 23711.7.6 检测干扰 23811.8 总结 242第12章形式验证 24412.1 通用目的的状态空间搜寻 24412.1.1 Promela和Spin 24412.1.2 如何使用 Promela 24912.1.3 Promela 示例: 锁 25112.1.4 Promela 示例: QRCU 25412.1.5 Promela初试牛刀：dynticks和可抢占RCU 26012.1.6 验证可抢占RCU和dynticks 26412.2 特定目的的状态空间搜寻 28812.2.1 解析Litmus测试 28912.2.2 Litmus测试意味着什幺 29012.2.3 运行Litmus测试 29112.2.4 PPCMEM讨论 29212.3 公理方法 29312.4 SAT求解器 29412.5 总结 295第13章综合套用 29613.1 计数难题 29613.1.1 对更新进行计数 29613.1.2 对查找进行计数 29613.2 使用RCU拯救并行软体性能 29713.2.1 RCU和基于每CPU变数的统计计数 29713.2.2 RCU及可插拔I/O设备的计数器 30013.2.3 数组及长度 30013.2.4 相关联的栏位 30113.3 散列难题 30213.3.1 相关联的数据元素 30213.3.2 更新友好的哈希表遍历 303第14章高级同步 30414.1 避免锁 30414.2 记忆体屏障 30414.2.1 记忆体序及记忆体屏障 30514.2.2 如果B在A后面，并且C在B后面，为什幺C不在A后面 30614.2.3 变数可以拥有多个值 30714.2.4 能信任什幺东西 30814.2.5 锁实现回顾 31214.2.6 一些简单的规则 31314.2.7 抽象记忆体访问模型 31414.2.8 设备操作 31514.2.9 保证 31514.2.10什幺是记忆体屏障 31614.2.11锁约束 32514.2.12记忆体屏障示例 326 14.2.13CPU快取的影响 32814.2.14哪里需要记忆体屏障 32914.3 非阻塞同步 32914.3.1 简单NBS 33014.3.2 NBS讨论 331第15章并行实时计算 33215.1 什幺是实时计算 33215.1.1 软实时 33215.1.2 硬实时 33315.1.3 现实世界的实时 33415.2 谁需要实时计算 33615.3 谁需要并行实时计算 33715.4 实现并行实时系统 33715.4.1 实现并行实时作业系统 33915.4.2 实现并行实时套用 34915.5 实时VS.快速：如何选择 351第16章易于使用 35316.1 简单是什幺 35316.2 API设计的Rusty準则 35316.3 修整Mandelbrot集合 354第17章未来的冲突 35717.1 曾经的CPU技术不代表未来 35717.1.1 单处理器Uber Alles 35817.1.2 多执行绪Mania 35917.1.3 更多类似的场景 35917.1.4 撞上记忆体墙 35917.2 事务记忆体 36017.2.1 外部世界 36117.2.2 进程修改 36417.2.3 同步 36717.2.4 讨论 37017.3 硬体事务记忆体 37117.3.1 HTM与锁相比的优势 37217.3.2 HTM与锁相比的劣势 37317.3.3 HTM与增强后的锁机制相比的劣势 37917.3.4 HTM最适合的场合 38017.3.5 潜在的搅局者 38017.3.6 结论 38217.4 并行函式式编程 383附录A 重要问题 385A.1 “After”的含义是什幺 385A.2 “并发”和“并行”之间的差异是什幺 388A.3 现在是什幺时间 389附录B 同步原语 391B.1 组织和初始化 391B.1.1 smp_init() 391B.2 执行绪创建、销毁及控制 392B.2.1 create_thread() 392B.2.2 smp_thread_id() 392B.2.3 for_each_thread() 392B.2.4 for_each_running_thread() 392B.2.5 wait_thread() 393B.2.6 wait_all_threads() 393B.2.7 用法示例 393B.3 锁 394B.3.1 spin_lock_init() 394 B.3.2 spin_lock() 394B.3.3 spin_trylock() 394B.3.4 spin_unlock() 394B.3.5 用法示例 395B.4 每执行绪变数 395B.4.1 DEFINE_PER_THREAD() 395B.4.2 DECLARE_PER_THREAD() 395B.4.3 per_thread() 395B.4.4 __get_thread_var() 396B.4.5 init_per_thread() 396B.4.6 用法示例 396B.5 性能 396附录C 为什幺需要记忆体屏障 397C.1 快取结构 397C.2 快取一致性协定 399C.2.1 MESI状态 399C.2.2 MESI协定讯息 400C.2.3 MESI状态图 400C.2.4 MESI协定示例 401C.3 存储导致不必要的停顿 402C.3.1 存储缓冲 403C.3.2 存储转发 403C.3.3 存储缓冲区及记忆体屏障 404C.4 存储序列导致不必要的停顿 406C.4.1 使无效伫列 406C.4.2 使无效伫列及使无效应答 407C.4.3 使无效伫列及记忆体屏障 407C.5 读和写记忆体屏障 409C.6 记忆体屏障示例 410C.6.1 乱序体系结构 410C.6.2 示例1 411C.6.3 示例2 412C.6.4 示例3 412C.7 特定的记忆体屏障指令 413C.7.1 Alpha 414C.7.2 AMD64 417C.7.3 ARMv7-A/R 417C.7.4 IA64 418C.7.5 PA-RISC 418C.7.6 POWER / Power PC 418C.7.7 SPARC RMO、PSO及TSO 419C.7.8 x86 420C.7.9 zSeries 421C.8 记忆体屏障是永恆的吗 421C.9 对硬体设计者的建议 422附录D 问题答案 423D.1 如何使用本书 423D.2 简介 424D.3 硬体和它的习惯 427D.4 办事的家伙 429D.5 计数 433D.6 对分割和同步的设计 445D.7 锁 449D.8 数据所有权 455D.9 延迟处理 456D.10数据结构 471D.11验证 473D.12形式验证 478D.13综合套用 481D.14高级同步 483D.15并行实时计算 486D.16易于使用 487D.17未来的冲突 487D.18重要问题 490D.19同步原语 491 D.20为什幺需要记忆体屏障 491附录E 术语 495附录F 感谢 502F.1 评审者 502F.2 硬体提供者 502F.3 原始出处 503F.4 图表作者 503F.5 其他帮助 505