多面体模型中分裂分块算法的设计与实现

Split Tiling Design and Implementation in the Polyhedral Model

循环分块是一种提升程序局部性的循环变换技术.多面体模型中实现了简单的平行四边形分块,但这种分块形状无法有效进行分块之间的并行.为了解决循环分块的块间并行问题,研究人员提出了分裂分块、钻石分块等各种复杂的分块形状.其中,钻石分块已经在多面体模型编译器中得到了实现,但分裂分块由于设计复杂,目前还没有一个有效的实现算法.本文设计了一种分裂分块算法,基于平行四边形分块实现分裂,避免了传统分裂分块依赖于非仿射表达式的问题,并在多面体模型编译器PPCG中对该算法进行了实现.实验对涵盖各种情况的stencil计算进行了测试,并分别在CPU和GPU架构上生成分裂分块代码.结果表明,本文提出的算法能在CPU架构上与当前最先进的钻石分块性能相当;同时,分裂分块将PPCG在GPU上生成的代码性能提高2.7倍~5.6倍.

Loop tiling is an essential transformation for improving locality in programs.The polyhedral model implements parallelogram tiling,but it fails to exploit full tile-level parallelism with such tile shape.The research community designed some complex tiles shapes,including split tile shape,diamond shape,etc.,to enable full tile-level parallelism.Unfortunately,only part of the proposed tile shapes,e.g.,diamond tiling,were implemented in existing polyhedral compilers.Split tiling is still considered as foreign to the polyhedral model,since its implementation has to resort to non-affine expressions which are out of the scope of the polyhedral model.In this paper,we design a split tiling algorithm and implement the algorithm in a polyhedral compiler,PPCG,by splitting a parallelogram tile which has already been integrated in most existing polyhedral compilers,avoiding the difficulty of implementation in the polyhedral model due to non-affine expressions.We conduct experiments on a suite of iterated stencil computations,targeting on both CPU and GPU platforms,to validate the performance of the algorithm.The experimental results show that the generated code of split tiling performs similarly with that of diamond tiling,the state-of-the-art tiling technique,on CPU.More importantly,split tiling may speed up the generated code of PPCG by 2.7x to 5.6x on GPU.