一类基于迭代空间条块的并行有限差分Stencil算法

摘要：

　　高效的并行有限差分Stencil 算法对于求解大型线性方程组是十分重要的。针对并行有限差分Stencil 算法中数据局部性差、同步和通信开销大的问题。首先改进传统有限差分Stencil 算法，提出了多层对称遍历有限差分 Stencil 算法。然后给出了以迭代空间条块序作为执行序的串行算法，通过沿时间轴对迭代空间进行时滞划分，在不改 变迭代算法性质的同时，对迭代空间条块内部多次迭代计算，提高算法的数据局部性。最后提出一种基于迭代空间条 块的并行算法，该算法利用改进的多面体模型对迭代空间网格划分，并通过网格条块重排序减少了Cache 缺失率、通信启动和同步次数。理论分析和实验结果表明，该并行模型比传统的区域分解方法和红黑排序并行算法具有更好的数据局部性，并行效率和可扩展性。

关键词： 有限差分Stencil 迭代算法 交错网格条块 多面体模型 数据局部性 通信优化

作者: 张纪林 狄鹏 徐向华 万健

作者单位: 杭州电子科技大学计算机学院, 浙江杭州 310018 北京科技大学信息工程学院, 北京,100083

会议类型: 国内会议

会议名称: 2010年全国高性能计算学术年会(HPC china2010)

会议地点: 北京

会议语种:中文

页码: 507-519

在线出版日期: 2010-10-27（万方平台首次上网日期，不代表论文的发表时间）