迭代空间交错条块并行Gauss-Seidel算法
DOI:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:

Supported by the National Natural Science Foundation of China under Grant No.60373008 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z105 (国家高技术研究发展计划(863)); the Key Project of the Ministry of Education of China under Gran No.106019(国家教育部科学技术研究重点项目)


Iterative Space Alternate Tiling Parallel Gauss-Seidel Algorithm
Author:
Affiliation:

Fund Project:

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

    针对并行GS(Gauss-Seidel)迭代算法中数据局部性差、同步和通信开销大的问题,首先改进传统GS迭代,提出了多层对称GS迭代算法.然后给出了以迭代空间条块序作为执行序的串行执行模型.该模型通过对迭代空间进行"时滞"划分,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行执行模型.该模型改进了迭代空间网格划分,并通过网格条块重排序减少了cache缺失率、通信启动和同步次数.实验结果表明,迭代空间交错条块并行算法比传统的区域分解方法和红黑排序并行算法具有更好的并行效率和可扩展性.

    Abstract:

    In order to optimize data locality, communication and synchronization overhead, this paper proposes a multi-layers symmetric Gauss-Seidel method. Then the serial execution model of this iterative method is given, which introduces the sequence of iterative space tile as the sequence of execution, and divides iteration space by time skewing. In this model, nodes of the tile can be updated many times to improve data locality. The parallel GS execution model based on iteration space tiling is presented, which uses an improved iteration space partition algorithm and reorders the tiles of iteration space to reduce cache misses, communication and synchronization cost. Finally the numerical results are presented to confirm the effectiveness of Gauss-Seidel parallelized with alternate tiling method, specifically compared with owner-computing and red-black Gauss-Seidel methods, and show that the new parallel iterative method has better parallel efficiency as well as scalability.

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

胡长军,张纪林,王 珏,李建江.迭代空间交错条块并行Gauss-Seidel算法.软件学报,2008,19(6):1274-1282

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

京公网安备 11040202500063号