主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公English
2020-2021年专刊出版计划 微信服务介绍 最新一期:2020年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
张纪林,狄鹏,蒋从锋,张伟,徐向华,万健,任永坚.一类基于迭代空间条块的并行有限差分Stencil 算法.软件学报,2010,21(zk):270-283
一类基于迭代空间条块的并行有限差分Stencil 算法
A Parallel Finite Difference Stencil Algorithm Based on Iterative Space Alternate Tiling
投稿时间:2010-06-15  修订日期:2010-12-10
DOI:
中文关键词:  有限差分Stencil  迭代算法  交错网格条块  多面体模型  数据局部性  通信优化
英文关键词:finite difference stencil  iterative method  alternate tiling  polyhedral model  data locality  communication optimization
基金项目: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 (浙江省教育厅科研项目)
作者单位E-mail
张纪林 杭州电子科技大学 计算机学院,浙江 杭州 310018 jilin.zhang@hdu.edu.cn 
狄鹏 北京科技大学 信息工程学院,北京 100083  
蒋从锋 杭州电子科技大学 计算机学院,浙江 杭州 310018  
张伟 杭州电子科技大学 计算机学院,浙江 杭州 310018  
徐向华 杭州电子科技大学 计算机学院,浙江 杭州 310018  
万健 杭州电子科技大学 计算机学院,浙江 杭州 310018  
任永坚 杭州电子科技大学 计算机学院,浙江 杭州 310018  
摘要点击次数: 3481
全文下载次数: 3858
中文摘要:
      高效的并行有限差分Stencil 算法对于求解大型线性方程组是十分重要的.针对并行有限差分Stencil 算法中数据局部性差、同步和通信开销大的问题.首先改进传统有限差分Stencil 算法,提出了多层对称遍历有限差分Stencil 算法.然后给出了以迭代空间条块序作为执行序的串行算法,通过沿时间轴对迭代空间进行时滞划分,在不改变迭代算法性质的同时,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行算法,该算法利用改进的多面体模型对迭代空间网格划分,并通过网格条块重排序减少了Cache 缺失率、通信启动和同步次数.理论分析和实验结果表明,该并行模型比传统的区域分解方法和红黑排序并行算法具有更好的数据局部性,并行效率和可扩展性.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利