基于数据局部性的循环分块选择算法

Tile Selection Algorithm Based on Data Locality

现有的多面体编译框架(如Pluto,LLVM/Polly和GCC/Graphite)在进行循环分块时,都采用了固定分块大小,无法充分发挥不同硬件的缓存特性,导致存在较大的性能差异。针对这一问题,涌现了许多基于多级缓存和数据局部性的循环分块算法,但这些算法往往只能优化特定循环程序或者缺乏综合考虑,不适合移植到通用编译器中。文中提出了一种基于数据局部性的循环分块选择算法,该算法不仅考虑了缓存替换策略的影响,还考虑了多核环境下的负载均衡问题。算法基于LLVM中的Polly模块实现,并选用Pluto和PolyBench中的部分测试用例进行单核和多核测试。实验结果表明,单核环境下,相比LLVM/Polly的默认分块方法,该算法在两种硬件平台下分别获得了平均2.03和2.05的加速比,且在多核环境下具有良好的并行可扩展性。

The existing polyhedral compilation frameworks(such as Pluto,LLVM/Poly and GCC/Graphite)use fixed block sizes when performing loop tiling,which cannot fully utilize the caching characteristics of different hardware,resulting in significant performance differences.In response to this issue,many loop tiling algorithms based on multi-level caching and data locality have emerged,but these algorithms often only optimize specific loop programs or lack comprehensive consideration,and are not suitable for transplantation into general compilers.This paper proposes a tile size selection algorithm based on data locality,which not only considers the impact of cache replacement strategy,but also considers the load balancing problem in multi-core environments.The algorithm is implemented based on the Polly module in LLVM,and some test cases from Pluto and PolyBench are selected for single core and multi-core testing.The experimental results show that compared to the default partitioning method of LLVM/Polly,the proposed algorithm achieves an average acceleration ratio of 2.03 and 2.05 on two hardware platforms in a single core environment,and has good parallel scalability in a multi-core environment.