多面体编译理论与深度学习实践

　　多面体编译理论与深度学习实践

　　赵捷，2009年于清华大学获得工学学士学位，2018年于法国巴黎高等师范学校获得工学博士学位，现就职于数学工程与先进计算国家重点实验室。赵捷博士长期从事编译器高级优化和代码生成方面的研究，目前主要从事深度学习编译器的研究。李宝亮，2009年于清华大学获工学学士学位，2014年赴加拿大麦吉尔大学交流访问，2015年于国防科学技术大学获工学博士学位。李宝亮博士长期从事体系结构性能分析优化方面的研究，目前主要从事深度学习专用加速芯片的研制和相关系统软件和编程语言的开发。

目录

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

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

1.1.1并行性发掘 .1

1.1.2存储层次结构3

1.1.3领域专用架构4

1.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.3 Fourier-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