曹 杭 袁 良 黄 珊 张云泉 徐勇军 陆鹏起 张广婷

1(计算机体系结构国家重点实验室(中国科学院计算技术研究所) 北京 100190)

2(中国科学院大学 北京 100049)

Stencil计算(模板计算)是科学工程应用中一类常见的嵌套循环算法，也被称为“结构化网格计算”，是13个伯克利核心计算模式之一.在动态规划、图像处理等领域的很多算法中也包含相似的依赖模式.Stencil定义了一种更新结点所需邻居结点的模式.Stencil计算在时间维度上迭代更新规则的d维网格(也称为数据空间)，数据空间沿着时间维度更新，产生的d+1维空间被称为迭代空间.

与其他的数值算法不同，例如稠密或稀疏矩阵计算类型的多样性主要来源于输入数据如稠密或稀疏矩阵的数据量,Stencil的计算类型本质上取决于问题的类型.Stencil可以从不同的角度进行分类，如格点维度(1维，2维，…)，邻居数目，即阶数(3点，5点，…)，形状(盒型，星型，…)，依赖类型(高斯-赛德尔,雅可比,…)和边界条件(常量的，周期的，…)等.

Stencil计算具有计算密集度低的特征，d维Stencil的简单实现由d+1个循环组成，其中最外层循环遍历时间维度，内层循环更新d维空间的所有格点.简单实现的数据重用度较差且典型的带宽受限.

分块是提高多重嵌套循环的数据局部性和并行度最有效的优化技术之一，目前有大量针对Stencil计算分块方案的研究.空间分块算法促进了2维至更高维度Stencil在一个时间步内的数据重用.为了进一步增强数据重用度，往往同时考虑时间维度和空间维度，后文将详细……