循环优化序列自动定制方法研究

现代计算机在体系结构和应用场景复杂性的增长使得程序性能的增长、保持程序性能的可移植性以及程序开发效率的提升越来越困难，程序自动调优(auto-tuning) 是解决此问题的一个可行途径。本文研究一种通过为循环嵌套自动定制循环优化序列来进行程序自动调优的方法，提高了被编译程序的性能和可移植性，也有助于提升开发效率。 在综述相关工作的基础上，本文首先分析了循环优化序列自动定制研究需要解决的几个关键问题：循环优化的形式化描述及实施、循环优化序列的性能评估、循环优化序列的自动定制方法以及相关的原型工具。本文围绕这几个问题进行研究。 本文采用了Polyhedron模型来描述循环优化，并基于此实施了循环优化的仿射变换。这一工作基于URUK/WRaP-IT开源软件包实现，并作出了若干重要改进。借助Polyhedron模型，本文还给出了部分常见循环优化之间的使能(enable)关系。循环优化之间的相互影响较为普遍，一个循环优化的执行可能会破坏后续优化的实施条件，也可能不破坏甚至创造相应条件。这一关系可以用于过滤循环优化序列定制过程中产生的无效序列从而加快定制速度。本文分析了两个循环优化以先后次序执行时，循环嵌套内所有依赖距离向量均得以保持的条件，给出了它们之间的使能关系。并且给出了使能关系在Polyhedron模型下的计算方法，以及在序列搜索过程中通过维护依赖距离向量状态计算使能关系的方法。 对于循环优化序列性能评估方法，本文采用了高速缓存失效率简化方程(CMES方程)以动态给出循环嵌套中的高速缓存失效率数据，提出了LoopCost模型以静态分析方式发现循环嵌套中对性能影响最大的维度，这两种评估方法分别适用于不同的序列定制方法。 给出了Cache 失效率简化方程(CMES, Cache Miss Equation Simplified)在Polyhedron 模型下的求解方法。CMES方程可在编译时给出循环嵌套中的Cache失效率数据，不需要实际编译运行目标程序，从而避免相关文献中使用运行时信息来评价优化序列带来的巨大编译开销。给出了CMES方程各个参数从循环嵌套的Polyhedron模型中提取的方法，并给出了具体计算过程。 提出了一种可发现循环嵌套中对性能影响最大维度的循环优化性能评估模型LoopCost。相关文献中所使用的性能评估模型可给出一个循环嵌套的整体性能，但无法给出哪个维度对其性能影响最大；而大多数循环优化实际上是对某一个维度所做的变换，因此这些评估模型不能直接指导优化序列的搜索，只能是在一个迭代过程中提供性能信息。LoopCost模型基于数据依赖关系对一个循环嵌套估算出其每个维度使用的cache行数，作为衡量局部性优劣的指标，适用于紧嵌套循环和非紧嵌套循环，并且其复杂度与循环嵌套个数和引用个数成线性关系。通过对SPEC CPU 2006中5,703个循环嵌套的实验，LoopCost模型对其中98.3%的循环嵌套都能给出正确的性能评估数据。 对于循环优化序列自动定制方法，本文首先提出了一种基于CMES方程的Custom方法，使用迭代方式搜索可行优化序列；为了进一步提升优化效率，又提出了一种基于LoopCost模型的快速定制方法FastCustom。 Custom方法使用CMES方程评估优化序列，使用遗传算法作为序列搜索方法。在遗传算法中的各个算子中利用循环优化的enable关系加速搜索速度。该方法可以避免使用运行时刻信息评估性能所带来的巨大编译开销，又可避免相关工作中利用Polyhedron模型中语句实例执行次序矩阵的性质来搜索带来的局限性，适用的循环优化范围广，编译效率高，同时能取得与相关工作基本相当的加速比。 FastCustom方法优化效率高，并且与Custom方法不同，适用于所有场合。它基于LoopCost模型寻找对性能影响最大的维度，并根据一个启发式策略给出一个循环优化序列。该方法编译速度快，优化效果与Custom方法基本相当。与Custom相比，该方法需要给出启发式策略，因此适用的循环优化范围不如Custom，适用于迭代编译无法进行的情形。 对于循环优化序列自动定制原型工具，本文设计并实现了原型工具CPOLO。该工具改进了URUK/WRaP-IT开源软件包，使其能够支持较为复杂的程序；增强了代码重生成的效率；并且实现了本文所提出的优化序列性能评估模型和自动定制方法。 最后，总结了全文并探讨了进一步的工作方向。