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

摘要：

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

关键词：多面体模型、循环分块、分裂分块、stencil计算、并行计算

所属期刊栏目：43

分类号：TP312(计算技术、计算机技术)

资助基金：本课题得到国家自然科学基金61702546

在线出版日期：2020-07-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：1038-1051