芯东西（公众号：aichip001）
文 | 心缘

芯东西10月23日报道，在刚刚落幕的国际计算机体系结构顶级会议MICRO中，国内研究再获最佳论文提名。

这是国内独立研究在MICRO过去53年历史中第三次获得最佳论文提名，也是国内研究团队连续第二年在MICRO上获最佳论文提名。

该论文旨在用Polyhedral模型来解决算子自动优化，通过研究循环分块和合并之间的更优组合，进一步利用芯片上的高速缓存，从而提升程序在CPU、GPU以及AI芯片华为昇腾910等不同芯片上的性能。

据悉，这项工作已进入产业化过程，如华为AI框架MindSpore中的akg优化工作，即是使用Polyhedral来完成昇腾910芯片上的代码生成，akg项目也正在全力支持GPU架构。

论文链接：https://www.microarch.org/micro53/papers/738300a427.pdf

在上一届MICRO大会中，清华大学微电子所魏少军、刘雷波团队关于新型并发控制算法的研究论文同样获得MICRO最佳论文提名，如感兴趣可参见芯东西报道（亚洲高校52年来唯二！清华团队入选芯片顶会MICRO最佳论文提名，新算法性能超英特尔8倍）。

有缘的是，本届MICRO入选最佳论文提名的论文一作赵捷也是清华校友，本科毕业于清华计算机系。

一、Polyhedral模型研究的核心难点

MICRO与ISCA、HPCA、ASPLOS并列为计算机体系架构四大顶会，被视作前沿芯片架构研究的风向标。神经网络加速器、专用加速器结构、DRAM、持久性内存、GPU加速器、近内存加速器等都在MICRO上被首次提出。

受疫情影响，本届MICRO会议在线举办。会议期间，赵捷、狄鹏团队提交的研究成果获得本届MICRO会议的最佳论文提名。根据论文，赵捷来自郑州数学工程与先进计算国家重点实验室，狄鹏来自华为。

论文题目为《Optimizing the Memory Hierarchy by Compositing Automatic Transformations on Computations and Data》，主要在Polyhedral模型中研究如何实现一种更好的循环分块和合并新组合，来优化存储进而提升程序在不同芯片上的执行效率。

该团队是国内少有的从事Polyhedral模型研究的团队之一。

基于Polyhedral模型的编译技术，主要研究通过程序中循环嵌套的变换和优化来提升程序性能。这种模型以开发程序的并行性和局部性为目的，将源程序编译或转换为能够在目标芯片上性能更高的等价程序或可执行代码。

Polyhedral模型不需要手动编写调度，因此需在编译器中构建一个非常好的数学模型来计算调度。这种数学模型底层是通过解决整数线性规划问题来得到最优解的，但证书现象规划问题的求解过程是一个NP完全问题。

所以，如何构建Polyhedral模型的整数线性规划问题，使其能够达到手工编写调度性能相当的结果，是当前研究的核心难点。

另一难点在于如何降低该模型求解的复杂度。

Polyhedral模型涉及大量的基础数学理论，包括但不限于线性代数、空间几何、最优化理论和矩阵论，以及基础计算机理论科学的知识如图论、数理逻辑等。这些知识点本不复杂，但将它们统一地表示在一个模型里，导致该模型的理解难度大，入门的“门槛”比较高。

过去，国内许多芯片厂商和研究团队对投入产出比较在意，没有重视这方面的知识。

即便在国外，Polyhedral相关研究也是一个相对小众的方向，不过近年因在深度学习中的应用，它开始被大量的研究人员注意起来。

如今异构计算架构正成为提升AI算力的关键基础，但市面上各类加速芯片的架构非常复杂，给深度学习算法在芯片上的部署和调度带来挑战。这使得深度学习编译器成为提高算法在异构架构上部署效率的有效手段。

谷歌TVM、英特尔Stripe、英伟达Diesel、Facebook TensorComprehensions、MIT Halide和Tiramisu等，均借助Polyhedral模型来实现算子层的循环优化。

二、新研究的三处关键创新

与Halide和TVM等采用“算法+调度”的方式需要手工编写调度不同，用Polyhedral模型来解决算子自动优化的过程完全自动化，这也是这篇新论文的研究重点。

与其他类似研究工作相比，这项工作的主要做了如下几处创新：

首先，这项工作自动化地实现了一种循环分块和合并的新组合。

这种组合在已有的基于Polyhedral的编译工作中没有被考虑到，因为现有的Polyhedral编译流程限定了这两种循环变换的组合顺序。

同时，这种组合在已有的基于手工编写调度的编译工作中也很难实现，因为手工编写调度的方式很难深入和系统地构建这种组合方式，其底层计算和数据之间的映射关系很难用手工编写的方式指定。

其次，这项工作在提升程序性能的同时，又有效地缓解了现有Polyhedral编译技术的时间复杂度问题。

通常性能和时间复杂度是矛盾的，但这项工作由于避开了使用整数线性规划问题来求解调度的过程，从而能降低编译时间复杂度，同时保证程序的性能有所提升。

第三，这项工作的代码生成支持包括通用芯片CPU、GPU和领域专用芯片华为昇腾910在内的多种不同架构，具有很好地可扩展性，也是现有工作中较少的能够支持特定领域专用芯片代码生成的工作。

三、在CPU/GPU/AI芯片均实现性能提升

通过对包括神经网络、图像处理、稀疏矩阵计算、线性代数等应用领域在内的11项基准测试实验，该研究证明其方法能在先进的CPU、GPU及AI芯片架构上获得有效的性能改进。

用于CPU和GPU的代码生成是在PPCG中实现的，PPCG是一个使用isl库工具的Polyhedral编译器；华为昇腾910芯片的代码生成可以在akg中实现。

在CPU上，其方法相较PolyMage和Halide分别平均性能提升了20%和33%。

在GPU上，其方法比Halide提供了17%的平均性能改进。

在AI芯片华为昇腾910上，该论文提出的方法可将ResNet-50模型整个执行时间提升16%。

结语

对于正研究张量编译技术的芯片厂商和研究机构来说，这项获得MICRO最佳论文提名的研究展现出Polyhedral技术在解决张量程序优化问题方面的前景。

当前国内从事Polyhedral模型研究的团队相对稀缺，我们期待看到更多研究人员投入相关领域的研究，也期待更多国内研究能在国际计算机体系结构顶级会议上收获认可。