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

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

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 

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

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

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