基于数据重用分析的多面体循环合并策略

摘要

现有多面体编译工具往往使用一些简单的启发式策略来寻找最优的语句合并,对于不同的待优化程序,需要手工调整循环合并策略以获得最佳性能.针对这一问题,面向多核CPU目标平台,文中提出了一种基于数据重用分析的循环合并策略.该策略避免了不必要的且会影响数据局部性利用的合并限制:针对调度的不同阶段,提出了面向不同并行层次的并行性合并限制;对于数组访问关系较为复杂的语句,提出了面向CPU高速缓存优化的分块性合并限制.相较于以往的合并策略,该策略在计算合并收益时考虑到了空间局部性的变化.文中基于LLVM编译框架中的多面体编译模块Polly实现了这一策略,并选用Polybench等测试套件中的部分测试用例进行测试.实验结果表明,相较于现有的多种合并策略,在单核执行情况下,测试用例平均获得了14.9％～62.5％的性能提升;在多核执行情况下,多个测试用例平均获得了19.7％～94.9％的性能提升,在单个测试用例中最高获得了1.49x～3.07x的加速效果.