首页 | 本学科首页   官方微博 | 高级检索  
     

迭代空间交错条块并行Gauss-Seidel算法
引用本文:胡长军,张纪林,王 珏,李建江.迭代空间交错条块并行Gauss-Seidel算法[J].软件学报,2008,19(6):1274-1282.
作者姓名:胡长军  张纪林  王 珏  李建江
作者单位:北京科技大学,信息工程学院,北京,100083
基金项目: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(国家教育部科学技术研究重点项目)
摘    要:针对并行GS(Gauss-Seidel)迭代算法中数据局部性差、同步和通信开销大的问题,首先改进传统GS迭代,提出了多层对称GS迭代算法.然后给出了以迭代空间条块序作为执行序的串行执行模型.该模型通过对迭代空间进行"时滞"划分,对迭代空间条块内部多次迭代计算,提高算法的数据局部性.最后提出一种基于迭代空间条块的并行执行模型.该模型改进了迭代空间网格划分,并通过网格条块重排序减少了cache缺失率、通信启动和同步次数.实验结果表明,迭代空间交错条块并行算法比传统的区域分解方法和红黑排序并行算法具有更好的并行效率和可扩展性.

关 键 词:Gauss-Seidel算法  交错网格条块  数据局部性  通信优化
收稿时间:2007/9/10 0:00:00
修稿时间:2007年9月10日

Iterative Space Alternate Tiling Parallel Gauss-Seidel Algorithm
HU Chang-Jun,ZHANG Ji-Lin,WANG Jue and LI Jian-Jiang.Iterative Space Alternate Tiling Parallel Gauss-Seidel Algorithm[J].Journal of Software,2008,19(6):1274-1282.
Authors:HU Chang-Jun  ZHANG Ji-Lin  WANG Jue and LI Jian-Jiang
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.
Keywords:Gauss-Seidel algorithm  alternate tiling  data locality  communication optimization
本文献已被 CNKI 维普 万方数据 等数据库收录!
点击此处可从《软件学报》浏览原始摘要信息
点击此处可从《软件学报》下载全文
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号