前言

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