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

本书利用多面体模型描述了如何实现不同阶段循环变换技术，是国内s个详细介绍该模型和循环优化技术的特殊编译参考书籍。

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

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

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

目录

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

1

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

1

11并行性发掘 1

1

12存储层次结构3

1

13领域专用架构4

1

2编译器面临的挑战7

1

21并行性发掘 8

1

22局部性发掘 10

1

23编程模型和抽象层次11

1

3循环优化的数学抽象 12

1

31多面体模型的基本概念 12

1

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

1

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

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

2

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

2

2整数集合与仿射函数 28

2

21静态仿射约束28

222整数集合

29

223仿射函数

32

2

24集合与映射的运算 34

23

Fourier-Motzkin消去法38

24调度树

41

2

41调度的表示方式 41

2

42调度树的结点44

2

43调度树的操作47

2

44调度表示的比较 49

25抽象语法树

50

2

51被执行关系 50

2

52上下文信息 51

2

53结点和表达式52

2

6各种抽象的工程实现 53

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

262调度树的实现58

263抽象语法树的实现 59

第 3章依赖关系分析 61

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

32依赖及其性质 62

321依赖的分类 65

322距离向量与方向向量66

323循环无关依赖和循环携带依赖 67

324依赖与变换 68

325依赖的复杂性69

33依赖测试 72

331精确测试与保守测试73

332 ZIV测试 74

333 SIV测试 74

334 GCD测试 78

335 Banerjee测试 79

336 I测试80

34耦合下标依赖测试82

341扩展的 GCD测试 83

342 ζ测试 84

343 Delta测试 85

344 Omega测试86

35特殊的依赖测试 89

351 D测试 89

352 Range依赖测试 90

36数据流分析91

361精确数据流分析 93

362近似数据流分析 96

363带标记的数据流分析98

37依赖与并行化 99

第 4章循环变换103

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

42预处理 104

421循环正规化 104

422死代码删除 105

423别名分析 106

424迭代空间分裂 106

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

431循环变换分类 108

432循环变换的复杂性 109

433 Pluto调度算法 113

44仿射循环变换 124

441循环交换 124

442循环反转 126

443循环延展 127

444循环倾斜 128

445循环合并 130

446循环分布 131

45近似仿射循环变换 133

451循环分块 133

452循环分段 135

453循环展开压紧 137

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

461分块分离 139

462循环展开 140

463其他循环变换 141

47循环压紧 141

第 5章开发并行性 143

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

52复杂的分块形状 144

521交叉分块 144

522分裂分块 146

523钻石分块 149

524六角形分块 151

53 Feautrier调度算法 153

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

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

54开发向量化 164

541可向量化 Codelet 165

542利于向量化的调度算法 166

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

551构造通信数据集 173

552通信优化 176

第 6章挖掘局部性 179

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

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

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

622拆分弱连通图 183

623合并强连通分量 184

63循环合并与循环分块的组合 185

631先合并后分块 186

632分块后再合并 189

633提升高速缓存的使用率 192

64数据空间变换 195

641间接数据空间变换 195

642显式数据空间变换 198

65提升局部性的调度优化 202

651循环分块后的重新调度 202

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

66数组压缩 213

661内存竞争关系 213

662划分数据空间 215

663代价模型 218

第 7章代码生成221

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

72代码生成方法 222

721凸包算法 222

722分割算法 224

73分割代码生成 227

731 for循环生成 228

732 if语句的生成位置 234

733循环展开 234

734分块分离 236

735循环退化 237

736带偏移的跨步循环 238

74 if控制流优化 239

75内存管理 240

751 CPU与 GPU间的传输 241

752内存提升 243

76同步指令 245

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

81 MLIR 247

811 MLIR基本概念 249

812与多面体模型的集成 253

82 Halide 258

821 Halide设计理念 259

822 Halide调度树 260

83 Tiramisu 265

84 Tensor Comprehensions 270

85 AKG 275

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

参考文献 285

前言

编译技术是计算机科学领域的一个重要分支，其发展历史可追溯至 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月