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

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

赵捷，2009年于清华大学获得工学学士学位，2018年于法国巴黎高等师范学校获得工学博士学位，现就职于数学工程与先进计算国家重点实验室。赵捷博士长期从事编译器高级优化和代码生成方面的研究，目前主要从事深度学习编译器的研究。

李宝亮，2009年于清华大学获工学学士学位，2014年赴加拿大麦吉尔大学交流访问，2015年于国防科学技术大学获工学博士学位。李宝亮博士长期从事体系结构性能分析优化方面的研究，目前主要从事深度学习专用加速芯片的研制和相关系统软件和编程语言的开发。

前言

编译技术是计算机科学领域的一个重要分支，其发展历史可追溯至 20世纪中叶。

作为编译技术的载体，编译器的功能是将一种语言转换成另外一种语言，这种过程可以

是从高级语言到低级语言的转换，也可以是从一种高级语言到另外一种高级语言的翻

译。为了实现语言之间的转换，编译器需要完成的任务包括前端词法、语法、语义的分

析，中间过程的程序优化以及后端代码的生成。经过长时间的发展，当前编译技术的重

点是在中间过程的程序优化和后端代码的生成。无论是中间过程的优化还是后端代码的

生成，都与计算机体系结构的发展息息相关。随着异构计算体系结构的出现和日趋完善，

尤其是当前面向人工智能、大数据和图像处理等领域专用体系结构的大量涌现，过程优

化和代码生成的重要性显得更加突出。

为了更好地实现过程优化和代码生成，学术界提出了一种被称作多面体模型（polyhedral model）的数学概念，该模型主要面向循环嵌套实现过程优化和代码生成。

经过 30多年的发展，该数学模型有效地解决了编译技术中的依赖分析、并行性和局部

性发掘等一系列关键问题，成为许多现代优化编译器的重要组成部分。近年来，随着人

工智能、大数据和图像处理等领域专用体系结构的迅猛发展，多面体模型也受到学术界

和工业界的广泛关注，不仅理论本身日趋完善，实际应用也取得了巨大的成功。在这样

的背景下，作者受清华大学出版社的邀请，就多面体模型理论本身及其在相关领域中的

应用进行归纳总结，编写了本书。

本书主要内容分为 8章。第 1章从体系结构发展对编译技术的影响，引出多面体

模型及其研究意义。第 2章介绍了多面体模型的数学基础，包括相关的定义、定理和所

需要的数学方法。其中，在本书中提出的定理，给出了具体的证明过程，在其他参考文

献中已经证明的定理，我们只给出了相关结论。第 3章介绍了多面体模型对程序进行优

化和代码生成的基本前提，即依赖关系的定义、性质及其测试和分析方法。我们从传统

的依赖测试到多面体模型中基于整数线性规划的依赖分析方法都进行了详细的阐述，这

为在不同计算能力的机器上实现依赖分析提供了基础。第 4章描述了多面体模型中能够

实现的各种循环变换方法，我们对这些循环变换方法进行了分类，依次介绍了这些循环

变换方法在多面体模型中的表示及实现方式。第 4章还将介绍多面体模型中最经典的

Pluto调度算法。第 5章就多面体模型面向程序并行性的研究进行了梳理和归纳，对各

种不同的循环分块形状实现原理进行了阐述。在这一章中，我们介绍了多面体模型中更

早实现的 Feautrier调度算法。第 6章针对如何利用局部性原理在多面体模型中进行优

化进行了介绍，其中，如何在多面体模型中实现循环合并是这章的重点内容。在这一章

中，我们还对多面体模型的基本工具—— isl中的调度算法进行了详细描述。在第 7章

中，我们介绍了根据多面体模型的数学抽象描述生成抽象语法树表示的方法，这种抽象语法树表示可以转换成各种其他中间表示或高级语言。我们还在这一章中介绍了如何在代码生成阶段实现一些特定的循环变换。第 8章介绍了多面体模型及其相关理论的最新进展。通过分析多面体模型在当前面向深度神经网络应用和领域专用架构的编译技术中发挥的作用，我们罗列并简单分析了六个采用多面体模型的编译框架和代码生成工具。

本书由赵捷和李宝亮两位作者共同撰写完成。其中，赵捷负责第 3章至第 7章内容的编写，李宝亮完成了第 1章和第 8章内容的编写，第 2章内容由两位作者共同完成。虽然本书是由两位作者编写的，但这些内容是两位作者通过在编译技术领域长时间的学习和工程实践中对先辈和同行知识及经验的总结所提炼形成的。没有这些先辈和同行知识的积累，这本书将无法呈现在尊敬的读者面前。作者赵捷要特别感谢 Albert Cohen教授，在他的指导下，该作者完成了多面体模型研究的博士学位论文。两位作者还要感谢 Sven Verdoolaege，他一直维护着介绍这本书内容时所依赖的重要数学工具—— isl，我们在撰写相关内容时参考了 Sven Verdoolaege编写的大量相关资料。在本书的撰写过程中，作者还与许多科研单位及科技公司进行合作，这为本书的编写提供了非常宝贵的科学研究和工程实践基础。作者在此向这些科研单位和科技公司表示感谢。此外，作者还要感谢清华大学出版社的杨迪娜编辑在本书编写过程中给予的帮助。

本书的结构和内容是作者在 2020年初与清华大学出版社协商确定的，原计划在 2021年 4月提交初稿，但是由于作者时间和水平有限，推迟了近一年才完成初稿，在这里向清华大学出版社致歉，也对之前了解到此书正在撰写并催促我们尽快完成编写的读者深表歉意。在这期间，我们对本书内容结构进行了多次调整，也对相关内容进行了深入的思考。我们的目的是通过本书内容的介绍，让读者对多面体模型这一数学概念和相关编译技术有一个初步的了解，但限于作者的水平和经验，本书难免有错误和纰漏。如读者发现这些错误和纰漏，我们将虚心接受读者的批评，并非常愿意与读者进行深入的交流，以提高作者的知识水平并完善本书的内容。

..

作者

2022年 11月

目录

第 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