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

作者：李颖颖; 赵捷^*; 庞建民

来源：计算机学报, 2020, 43(06): 1038-1051.

• 多面体模型
• 循环分块
• 分裂分块
• stencil计算
• 并行计算

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

• 单位
  信息工程大学