多面体编译理论与深度学习实践 (赵捷 李宝亮)

本书分十大章节和三章附录章节，以现代体系结构特征为目标，从理论、方法及应用等不同角度，详细描述了各种提升程序并行性、数据局部性及适配目标架构特征的高级编译优化技术。本书还结合深度学习应用场景展开讨论，介绍了如何在深度学习框架中使用高级编译优化技术。

第  1章体系结构发展对编译技术的影响  ..............................................................  1

1.1面向经典体系结构的性能优化  ...................................................................1

1.1.1并行性发掘  ...................................................................................1

1.1.2存储层次结构................................................................................3

1.1.3领域专用架构................................................................................4

1.2编译器面临的挑战....................................................................................7

1.2.1并行性发掘  ...................................................................................8

1.2.2局部性发掘  .................................................................................10

1.2.3编程模型和抽象层次....................................................................11

1.3循环优化的数学抽象  ..............................................................................12

1.3.1多面体模型的基本概念  ................................................................12

1.3.2多面体模型在编译器中的应用  ......................................................15

1.3.3基于多面体模型的编译流程..........................................................16

第  2章程序抽象表示基础  .................................................................................25

2.1抽象表示在编译器中发挥的作用..............................................................25

2.2整数集合与仿射函数  ..............................................................................28

2.2.1静态仿射约束..............................................................................28

2.2.2整数集合....................................................................................29

2.2.3仿射函数....................................................................................32

2.2.4集合与映射的运算  .......................................................................34

2.3Fourier-Motzkin消去法..........................................................................38

2.4调度树.................................................................................................41

2.4.1调度的表示方式  ..........................................................................41

2.4.2调度树的结点..............................................................................44

2.4.3调度树的操作..............................................................................47

2.4.4调度表示的比较  ..........................................................................49

2.5抽象语法树............................................................................................50

2.5.1被执行关系  .................................................................................50

2.5.2上下文信息  .................................................................................51

2.5.3结点和表达式..............................................................................52

2.6各种抽象的工程实现  ..............................................................................53

2.6.1整数集合和仿射函数的实现..........................................................54

2.6.2调度树的实现..............................................................................58

2.6.3抽象语法树的实现  .......................................................................59

第  3章依赖关系分析  ........................................................................................61

3.1依赖关系分析在编译优化中的作用  ..........................................................61

3.2依赖及其性质  ........................................................................................62

3.2.1依赖的分类  .................................................................................65

3.2.2距离向量与方向向量....................................................................66

3.2.3循环无关依赖和循环携带依赖  ......................................................67

3.2.4依赖与变换  .................................................................................68

3.2.5依赖的复杂性..............................................................................69

3.3依赖测试  ...............................................................................................72

3.3.1精确测试与保守测试....................................................................73

3.3.2  ZIV测试  ....................................................................................74

3.3.3  SIV测试  ....................................................................................74

3.3.4  GCD测试  ..................................................................................78

3.3.5  Banerjee测试  .............................................................................79

3.3.6  I测试.........................................................................................80

3.4耦合下标依赖测试..................................................................................82

3.4.1扩展的  GCD测试  .......................................................................83

3.4.2  ζ测试  ........................................................................................84

3.4.3  Delta测试  ..................................................................................85

3.4.4  Omega测试................................................................................86

3.5特殊的依赖测试  .....................................................................................89

3.5.1  D测试  .......................................................................................89

3.5.2  Range依赖测试  ..........................................................................90

3.6数据流分析............................................................................................91

3.6.1精确数据流分析  ..........................................................................93

3.6.2近似数据流分析  ..........................................................................96

3.6.3带标记的数据流分析....................................................................98

3.7依赖与并行化  ........................................................................................99

第  4章循环变换.............................................................................................103

4.1适配体系结构特征的关键技术  ...............................................................  103

4.2预处理  ................................................................................................  104

4.2.1循环正规化  ...............................................................................  104

4.2.2死代码删除  ...............................................................................  105

4.2.3别名分析  ..................................................................................  106

4.2.4迭代空间分裂............................................................................  106

4.3多面体模型中的循环变换......................................................................  107

4.3.1循环变换分类............................................................................  108

4.3.2循环变换的复杂性  .....................................................................  109

4.3.3  Pluto调度算法  .........................................................................  113

4.4仿射循环变换  ......................................................................................  124

4.4.1循环交换  ..................................................................................  124

4.4.2循环反转  ..................................................................................  126

4.4.3循环延展  ..................................................................................  127

4.4.4循环倾斜  ..................................................................................  128

4.4.5循环合并  ..................................................................................  130

4.4.6循环分布  ..................................................................................  131

4.5近似仿射循环变换................................................................................  133

4.5.1循环分块  ..................................................................................  133

4.5.2循环分段  ..................................................................................  135

4.5.3循环展开压紧............................................................................  137

4.6代码生成过程中的循环变换  ..................................................................  139

4.6.1分块分离  ..................................................................................  139

4.6.2循环展开  ..................................................................................  140

4.6.3其他循环变换............................................................................  141

4.7循环压紧  .............................................................................................  141

第  5章开发并行性  .........................................................................................143

5.1利用多面体模型发掘数据并行  ...............................................................  143

5.2复杂的分块形状  ...................................................................................  144

5.2.1交叉分块  ..................................................................................  144

5.2.2分裂分块  ..................................................................................  146

5.2.3钻石分块  ..................................................................................  149

5.2.4六角形分块  ...............................................................................  151

5.3  Feautrier调度算法...............................................................................  153

5.3.1一维时间表示的调度计算  ...........................................................  153

5.3.2多维时间表示的调度计算  ...........................................................  159

5.4开发向量化..........................................................................................  164

5.4.1可向量化  Codelet......................................................................  165

5.4.2利于向量化的调度算法  ..............................................................  166

5.5面向分布式存储结构的并行  ..................................................................  172

5.5.1构造通信数据集  ........................................................................  173

5.5.2通信优化  ..................................................................................  176

第  6章挖掘局部性  .........................................................................................179

6.1金字塔形存储层次结构之外的挑战  ........................................................  179

6.2面向不同优化目标的循环合并策略  ........................................................  180

6.2.1基于依赖图的循环合并算法........................................................  181

6.2.2拆分弱连通图............................................................................  183

6.2.3合并强连通分量  ........................................................................  184

6.3循环合并与循环分块的组合  ..................................................................  185

6.3.1先合并后分块............................................................................  186

6.3.2分块后再合并............................................................................  189

6.3.3提升高速缓存的使用率  ..............................................................  192

6.4数据空间变换  ......................................................................................  195

6.4.1间接数据空间变换  .....................................................................  195

6.4.2显式数据空间变换  .....................................................................  198

6.5提升局部性的调度优化  .........................................................................  202

6.5.1循环分块后的重新调度  ..............................................................  202

6.5.2面向数据访存连续性的调度优化  .................................................  203

6.6数组压缩  .............................................................................................  213

6.6.1内存竞争关系............................................................................  213

6.6.2划分数据空间............................................................................  215

6.6.3代价模型  ..................................................................................  218

第  7章代码生成.............................................................................................221

7.1一个比输出指令序列更复杂的任务  ........................................................  221

7.2代码生成方法  ......................................................................................  222

7.2.1凸包算法  ..................................................................................  222

7.2.2分割算法  ..................................................................................  224

7.3分割代码生成  ......................................................................................  227

7.3.1  for循环生成  .............................................................................  228

7.3.2  if语句的生成位置  .....................................................................  234

7.3.3循环展开  ..................................................................................  234

7.3.4分块分离  .................................................................................  236

7.3.5循环退化  ..................................................................................  237

7.3.6带偏移的跨步循环  .....................................................................  238

7.4  if控制流优化.......................................................................................  239

7.5内存管理  .............................................................................................  240

7.5.1  CPU与  GPU间的传输  .............................................................  241

7.5.2内存提升  ..................................................................................  243

7.6同步指令  .............................................................................................  245

第  8章多面体编译理论的最新进展  ..................................................................247

8.1  MLIR  .................................................................................................  247

8.1.1  MLIR基本概念  ........................................................................  249

8.1.2与多面体模型的集成..................................................................  253

8.2  Halide.................................................................................................  258

8.2.1  Halide设计理念........................................................................  259

8.2.2  Halide调度树  ...........................................................................  260

8.3  Tiramisu  .............................................................................................  265

8.4  Tensor  Comprehensions........................................................................  270

8.5  AKG...................................................................................................  275

8.6面向  Tensor  Core的自动代码生成  ........................................................  280

参考文献  ...........................................................................................................285