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

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

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

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

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

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

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

1 1并行性发掘 1 

1 2存储层次结构 3 

1 3领域专用架构 4 

2编译器面临的挑战 7 

2 1并行性发掘 8 

2 2局部性发掘 10 

2 3编程模型和抽象层次 11 

3循环优化的数学抽象 12 

3 1多面体模型的基本概念 12 

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

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

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

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

2整数集合与仿射函数 28 

2 1静态仿射约束 28 

2 2 2整数集合 29 

2 2 3仿射函数 32 

2 4集合与映射的运算 34 

2 3 
Fourier-Motzkin消去法 38 

2 4调度树 41 

4 1调度的表示方式 41 

4 2调度树的结点 44 

4 3调度树的操作 47 

4 4调度表示的比较 49 

2 5抽象语法树 50 

2 5 1被执行关系 50 

 25 2上下文信息 51 

2 5 3结点和表达式 52 

 26各种抽象的工程实现 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

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