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

Loop Fusion Strategy Based on Data Reuse Analysis in Polyhedral Compilation

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

Existing polyhedral compilation tools often use some simple heuristic strategies to find the optimal loop fusion decisions.It is necessary to manually adjust the loop fusion strategy to get the best performance for different programs.To solve this problem, a fusion strategy based on data reuse analysis is proposed for multi-core CPU platform.This strategy avoids unnecessary fusion constraints that affecting the mining of data locality.For different stages of scheduling, the parallelism constraint for diffe-rent parallel levels is proposed.And a tiling constraint for CPU cache optimization is proposed for statements with complex array accesses.Compared with the previous loop fuion strategies, this strategy takes into account the changes in spatial locality when calculating the fusion profits.This strategy is implemented based on the polyhedral compilation module Polly in the LLVM compilation framework, and some test cases in test suites such as Polybench are selected for testing.In the case of single-core testing, compared with the existing fusion strategies, the average performance is improved by 14.9%~62.5%.In the case of multi-core testing, compared with the existing fusion strategies, the average performance is improved by 19.7%~94.9%,and the speedup is up to 1.49 x~3.07 x.