一类基于迭代空间条块的并行有限差分Stencil 算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported by the National Natural Science Foundation of China under Grant Nos.60873023, 60973029, 61003077 (国家自然科学基金); the National Basic Research Program of China under Grant No.2007CB310906 (国家重点基础研究发展计划(973)); the Zhejiang Provincial Natural Science Foundation of China under Grant Nos.Y1101104, Y1101092, Y1090940 (浙江省自然科学基金); the Zhejiang Provincial Education Department Research Foundation of China under Grant No.2010000711 (浙江省教育厅科研项目)


A Parallel Finite Difference Stencil Algorithm Based on Iterative Space Alternate Tiling
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    Abstract:

    Difference stencils are fundamental computations throughout a broad range of scientific and engineering computer programs. In order to optimize data locality and communication overhead, this paper proposes a novel alternate tiling stencil algorithm on distributed memory machines by exploiting the property of the iterative algorithm. The serial execution process of this iterative method is given, which introduces the sequence of iterative space tile as the sequence of execution, and uses time skewing technique to divide iteration space. In this process, nodes of the tile can be traversed many times to improve data locality. The parallel algorithm based on iteration space tile technique is presented, which uses an improved polyhedral model to implement the iteration space tiling algorithm and reorders the tiles of iteration space to reduce cache misses, and the cost of communication and synchronization. The theoretical comparison is given between alternate tiling and other parallelization techniques. Finally numerical results are presented to confirm the effectiveness of serial and parallel execution models of alternate tiling finite difference stencil algorithm, specifically compared with domain-decomposition and red-black iterative methods, and show that the new parallel iterative method has a good data locality, parallel efficiency and scalability.

    参考文献
    相似文献
    引证文献
引用本文

张纪林,狄鹏,蒋从锋,张伟,徐向华,万健,任永坚.一类基于迭代空间条块的并行有限差分Stencil 算法.软件学报,2010,21(zk):270-283

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2010-06-15
  • 最后修改日期:2010-12-10
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号