高性能并行运行时系统 设计与实现

本书首先简要回顾了现代计算机架构的主要概念，特别关注并行代码的性能以及并行编程模型中的相关概念。然后，转向用于实现并行编程模型的基本算法，讨论它们如何与现代处理器交互。为了证明架构问题的普遍性，本书展示了当代多核处理器的性能。本书中的关键算法和概念都以易于理解的方式进行讨论，并且用许多具体示例、图表和源代码片段进行说明。 本书的目标读者是研究编译器构造、并行编程或编程系统的计算机科学专业的学生。对用于实现并行运行时系统的核心算法感兴趣的软件开发人员，或者需要为需要本书中讨论的算法和概念的项目自学的软件开发人员，也将从阅读本书中受益。 读者可以在https://github.com/parallel-runtimes/lomp找到本书的源代码。

并行无处不在。从小的设备（例如支持物联网的处理器）到大的超级计算机，几乎所有设备都提供具有多个处理元件的执行环境。因此，这要求程序员编写能够充分利用硬件中多个处理单元的并行代码。并行程序需要一个提供有效执行机制的软件基础设施（“并行运行时”），这些运行时必须考虑底层计算机架构的特定结构以及执行环境所提供的特性。
在《高性能并行运行时系统：设计与实现》中，我们将展示由现代处理器设计方式所带来的有趣效果。程序员在实现高性能并行运行时系统的时候，需要考虑底层机器细节。我们将展示其中存在的（性能）陷阱，你将看到一些违反直觉的结论，它们很可能会误导你对机器性能的思考及实现决策。通过阅读本书，你将了解：
现代计算机架构的主要概念；
每种构造的合理性能指标是什么；
根据底层硬件特性，理论性能极限是什么；
如何测量硬件与程序代码两者的性能；
如何使用硬件特性的度量设计性能良好的软件；
用于实现并行编程模型的基本算法，以及它们如何与现代处理器交互。
《高性能并行运行时系统：设计与实现》的目标读者主要是正在学习编译器构建、并行编程或系统编程的学生。对于那些想要编写并行代码，理解并行代码的性能，深入理解代码，以及想要实现并行运行时系统的人员，阅读本书也大有裨益。

译者序
序
前言
术语表
第1章 绪论
1.1 本书结构
1.2 探索设计空间
1.2.1 作为库的并行
1.2.2 作为语言的并行
1.3 代码示例
1.4 机器配置
第2章 并行编程模型与概念
2.1 多进程与多线程
2.1.1 线程基础
2.1.2 线程亲和性
2.1.3 基于线程编程的Open MP API
2.1.4 工作分享
2.1.5 0penMP线程亲和性
2.2 基于任务的并行编程
2.3 同步构造
2.3.1 锁与互斥
2.3.2 同步障、归约和闭锁
2.3.3 任务同步障
2.3.4 任务依赖
2.4 阿姆达尔定律
2.4.1 呈现性能结果
2.4.2 对性能的影响
2.4.3 将开销映射到阿姆达尔定律中
2.4.4 阿姆达尔定律变体
2.5 总结
第3章 众核与多核计算机架构
3.1 执行机制
3.1.1 冯·诺依曼架构与按序执行
3.1.2 按序流水线执行
3.1.3 乱序执行
3.1.4 分支预测
3.1.5 超标量执行
3.1.6 同步多线程
3.1.7 单指令多数据
3.2 现代内存子系统
3.2.1 内存层次结构
3.2.2 内存模型与内存一致性
3.2.3 缓存
3.2.4 缓存一致性：概述
3.2.5 缓存一致性：MESl协议
3.2.6 性能影响
3.2.7 非统一内存架构
3.3 总结
第4章 编译器和运行时的交互
4.1 编译器基础
4.2 基于任务的并行模型的实现
4.2.1 lambda函数和闭包
4.2.2 TBB中的排队任务
4.3 并行编程语言的编译器
4.4 并行代码生成模式
4.4.1 并行域的代码生成
4.4.2 线程并行循环的代码生成
4.4.3 SIMD并行循环的代码生成
4.4.4 串行构造的代码生成
4.4.5 静态任务的代码生成
4.4.6 动态任务的代码生成
4.5 0penMP实现示例
4.5.1 GNU编译器套件
4.5.2 Intel编译器和LLVM编译器
4.6 总结
第5章 并行运行时基本机制
5.1 管理并行性
5.1.1 生成并行性
5.1.2 等待
5.2 并行性管理与硬件结构
5.2.1 检测硬件结构
5.2.2 线程固定
5.3 并行运行时系统中的内存管理
5.3.1 内存效率及缓存使用
5.3.2 单线程内存分配器
5.3.3 多线程内存分配器
5.3.4 并行运行时系统的专用内存分配器
5.3.5 线程本地存储
5.3.6 线程对象的数据布局
5.4 总结
寮6章 互斥和原子性
6.1 互斥问题
6.1.1 锁的硬件支持：原子指令
6.1.2 ABA问题
6.2 我们应该写锁代码吗
6.3 锁的类别
6.4 锁算法的特性
6.5 锁算法
6.5.1 测试并设置锁
6.5.2 测试及测试并设置锁
6.5.3 票锁
6.5.4 排队锁
6.6 实际代码性能
6.6.1 无争用锁开销
6.6.2 争用锁的吞吐量
6.6.3 性能总结
6.7 如何等待
6.8 事务同步
6.8.1 事务语义
6.8.2 MESI协议中的实现
6.8.3 事务指令
6.8.4 事务锁
6.8.5 互斥和预测的比较
6.9 其他串行操作
6.9.1 master和masked构造
6.9.2 single构造
6.10 原子操作
6.10.1 原子指令映射
6.10.2 最小值和优选值的原子实现
6.11总结
6.11.1 锁总结
6.11.2 原子操作总结
第7章 同步障和归约
7.1 同步障基本原理
7.2 同步障性能测量
7.2.1 同步障微基准程序
7.2.2 同步障性能模型
7.3 同步障组件
7.3.1 计数器和标志
7.3.2 广播
7.4 同步障算法分类
7.5 同步障算法
7.5.1 计数同步障
7.5.2 多对多同步障
7.5.3 蝶形／超立方体同步障
7.5.4 传播型同步障
7.5.5 树形签入同步障
7.6 归约
7.7 其他优化
7.8 总结
第8章 调度并行循环
8.1 调度目标
8.2 调度效率的理论极限
8.3 基本调度万法
8.3.1 静态循环调度
8.3.2 动态循环调度
8.4 映射为规范形式
8.5 编译器循环转换
8.6 循环调度单调性
8.7 静态循环调度实现
8.7.1 分块式循环调度
8.7.2 块循环式循环调度
8.8 动态循环调度实现
8.8.1 指导式调度
8.8.2 monotonic： dynamic
8.8.3 nonmonotonic： dynamic
8.9 循环调度评估
8.10 其他循环调度方案
8.10.1 使用历史信息
8.10.2 用户控制调度
8.11 总结
第9章 任务并行模型的运行时支持
9.1 任务描述符
9.2 任务池实现
9.2.1 单任务池
9.2.2 多任务池
9.3 任务同步
9.3.1 等待任务子集完成
9.3.2 等待直接子任务完成
9.3.3 任务依赖
9.4 任务调度
9.4.1 任务调度点
9.4.2 广度优先调度和深度优先调度
9.4.3 任务窃取
9.5 任务调度约束
9.5.1 栈调度
9.5.2 循环调度
9.6 其他任务主题
9.6.1 任务优先级
9.6.2 任务亲和性
9.7 总结
第10章 总结和感想
附录 技术缩略语
参考文献