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

　　本书聚焦于当今高性能多核处理器的并行编程系统的理论和实践方面，探讨实现并行编程模型所需的关键算法的有效实现。此类实现需要考虑底层计算机体系结构的特定体系结构方面以及执行环境提供的功能。本书简要回顾了现代计算机体系结构的关键概念，特别关注并行代码的性能以及并行编程模型中的相关概念。然后，本书转向用于实现并行编程模型的基本算法，并讨论它们如何与现代处理器交互。虽然本书将重点介绍一般机制，但我们将主要使用英特尔处理器体系结构来举例说明所讨论的实现概念，但也将在适当的情况下介绍其他处理器体系结构。所有的算法和概念都以一种易于理解的方式进行了讨论，并附有许多示例、图表和源代码片段。

　　Michael Klemm是一位高性能计算专家，他主要研究高性能计算应用程序、并行编程、编译器和运行时实现的性能调整以及编程语言的设计。Jim Cownie是ACM杰出工程师，曾任Intel高级首席工程师。他曾是LLVM中OpenMP运行时的组件所有者。他喜欢滑雪。

Contents　目　录
译者序
序
前言
术语表
第1章　绪论1
1.1　本书结构1
1.2　探索设计空间2
1.2.1　作为库的并行3
1.2.2　作为语言的并行5
1.3　代码示例6
1.4　机器配置6
第2章　并行编程模型与概念9
2.1　多进程与多线程9
2.1.1　线程基础11
2.1.2　线程亲和性14
2.1.3　基于线程编程的OpenMP API14
2.1.4　工作分享15
2.1.5　OpenMP线程亲和性18
2.2　基于任务的并行编程19
2.3　同步构造22
2.3.1　锁与互斥22
2.3.2　同步障、归约和闭锁24
2.3.3　任务同步障26
2.3.4　任务依赖28
2.4　阿姆达尔定律31
2.4.1　呈现性能结果32
2.4.2　对性能的影响34
2.4.3　将开销映射到阿姆达尔定律中35
2.4.4　阿姆达尔定律变体35
2.5　总结37
第3章　众核与多核计算机架构39
3.1　执行机制39
3.1.1　冯·诺依曼架构与按序执行40
3.1.2　按序流水线执行42
3.1.3　乱序执行44
3.1.4　分支预测47
3.1.5　超标量执行48
3.1.6　同步多线程49
3.1.7　单指令多数据52
3.2　现代内存子系统54
3.2.1　内存层次结构54
3.2.2　内存模型与内存一致性58
3.2.3　缓存62
3.2.4　缓存一致性：概述62
3.2.5　缓存一致性：MESI协议62
3.2.6　性能影响66
3.2.7　非统一内存架构70
3.3　总结72
第4章　编译器和运行时的交互73
4.1　编译器基础73
4.2　基于任务的并行模型的实现76
4.2.1　lambda函数和闭包77
4.2.2　TBB中的排队任务79
4.3　并行编程语言的编译器80
4.4　并行代码生成模式83
4.4.1　并行域的代码生成83
4.4.2　线程并行循环的代码生成85
4.4.3　SIMD并行循环的代码生成88
4.4.4　串行构造的代码生成91
4.4.5　静态任务的代码生成93
4.4.6　动态任务的代码生成94
4.5　OpenMP实现示例97
4.5.1　GNU编译器套件97
4.5.2　Intel编译器和LLVM编译器99
4.6　总结102
第5章　并行运行时基本机制103
5.1　管理并行性103
5.1.1　生成并行性103
5.1.2　等待104
5.2　并行性管理与硬件结构105
5.2.1　检测硬件结构105
5.2.2　线程固定107
5.3　并行运行时系统中的内存管理108
5.3.1　内存效率及缓存使用109
5.3.2　单线程内存分配器109
5.3.3　多线程内存分配器112
5.3.4　并行运行时系统的专用内存
　　　分配器113
5.3.5　线程本地存储114
5.3.6　线程对象的数据布局116
5.4　总结117
第6章　互斥和原子性118
6.1　互斥问题118
6.1.1　锁的硬件支持：原子指令120
6.1.2　ABA问题122
6.2　我们应该写锁代码吗123
6.3　锁的类别124
6.4　锁算法的特性124
6.5　锁算法127
6.5.1　测试并设置锁128
6.5.2　测试及测试并设置锁129
6.5.3　票锁130
6.5.4　排队锁131
6.6　实际代码性能133
6.6.1　无争用锁开销133
6.6.2　争用锁的吞吐量134
6.6.3　性能总结136
6.7　如何等待138
6.8　事务同步143
6.8.1　事务语义144
6.8.2　MESI协议中的实现145
6.8.3　事务指令146
6.8.4　事务锁146
6.8.5　互斥和预测的比较149
6.9　其他串行操作149
6.9.1　master和masked构造149
6.9.2　single构造150
6.10　原子操作151
6.10.1　原子指令映射151
6.10.2　最小值和最大值的原子实现153
6.11　总结155
6.11.1　锁总结155
6.11.2　原子操作总结155
第7章　同步障和归约156
7.1　同步障基本原理157
7.2　同步障性能测量158
7.2.1　同步障微基准程序159
7.2.2　同步障性能模型161
7.3　同步障组件161
7.3.1　计数器和标志161
7.3.2　广播163
7.4　同步障算法分类166
7.5　同步障算法166
7.5.1　计数同步障166
7.5.2　多对多同步障169
7.5.3　蝶形/超立方体同步障170
7.5.4　传播型同步障172
7.5.5　树形签入同步障174
7.6　归约178
7.7　其他优化182
7.8　总结183
第8章　调度并行循环185
8.1　调度目标185
8.2　调度效率的理论极限186
8.3　基本调度方法188
8.3.1　静态循环调度188
8.3.2　动态循环调度189
8.4　映射为规范形式189
8.5　编译器循环转换191
8.6　循环调度单调性193
8.7　静态循环调度实现194
8.7.1　分块式循环调度195
8.7.2　块循环式循环调度195
8.8　动态循环调度实现196
8.8.1　指导式调度197
8.8.2　monotonic:dynamic199
8.8.3　nonmonotonic:dynamic201
8.9　循环调度评估203
8.10　其他循环调度方案207
8.10.1　使用历史信息208
8.10.2　用户控制调度208
8.11　总结208
第9章　任务并行模型的运行时
　　　　支持210
9.1　任务描述符210
9.2　任务池实现211
9.2.1　单任务池212
9.2.2　多任务池217
9.3　任务同步223
9.3.1　等待任务子集完成224
9.3.2　等待直接子任务完成227
9.3.3　任务依赖231
9.4　任务调度234
9.4.1　任务调度点234
9.4.2　广度优先调度和深度优先
　　　调度235
9.4.3　任务窃取236
9.5　任务调度约束239
9.5.1　栈调度239
9.5.2　循环调度240
9.6　其他任务主题241
9.6.1　任务优先级241
9.6.2　任务亲和性243
9.7　总结245
第10章　总结和感想246
附录　技术缩略语248
参考文献251