资源描述：
《并行计算稀疏矩阵乘以向量的负载平衡算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、CN4321258/TP计算机工程与科学2006年第28卷第3期ISSN10072130XCOMPUTERENGINEERING&SCIENCEVol128,No13,2006文章编号:10072130X(2006)03200762023并行计算稀疏矩阵乘以向量的负载平衡算法ALoad2BalancingAlgorithmforSparseMatrix2VectorMultiplicationonParallelComputers刘杰,迟利华,胡庆丰,李晓梅LIUJie,CHILi2hua,HUQing2feng,LIXiao2mei(国防科技大学计算
2、机学院,湖南长沙410073)(SchoolofComputerScience,NationalUniversityofDefenseTechnology,Changsha410073,China)摘要:稀疏矩阵乘以一个向量(SpM×V)的问题是许多大型应用问题的核心计算问题,文中提出了一种在并行计算机上并行计算SpM×V的负载平衡算法,计算复杂性为O(N)(N为稀疏矩阵的阶),而目前计算此类问题的最优负载平衡算法的计算复杂性为O(N·P)(P为处理机台数)。文章最后给出了并行数值实验。Abstract:Inthispaper,weconsiderth
3、eload2balancingmultiplicationofalargesparsematrixwithalargesequenceofvectorsonparallelcomputers.Weproposeaload2balancingalgorithmbasedonnon2zerovalueseventheallocationofthesequencerowsofsparsematrices.ThecomplexityofthisalgorithmisO(N),whereNisthenumberofrowsinthematrix.Incontra
4、sttothebestcur2rentalgorithmwiththecomplexityofO(N·P),wherePisthenumberofprocessors,theperformanceofourapproachismuchbet2ter.Especially,becauseouralgorithmisbasedonthesequencerowallocationofsparsematrices,wecanconvenientlycomposetheparallelcodeandoptimizethecommunications.关键词:并行
5、计算;稀疏矩阵乘以向量;负载平衡Keywords:parallelcomputing;sparsematrix2vectormultiplication;loadbalancing中图分类号:TP30116文献标识码:A不多。事实上,负载不平衡已经成为影响许多问题并行性能1引言的主要因素。对于此类问题的研究虽然很难,但又势在必行。由于稀疏矩阵元素分布的不均匀性,按行、按列或按块大量的实际应用领域需要求解大型稀疏线性方程组,平均分配的方式造成了处理机间的负载不平衡,有必要研究应用领域的复杂性使得稀疏线性方程组千差万别,很难在高效的负载平衡算法。目前只有两
6、篇这方面的文献:Aliaga[3]并行计算机上获得高性能。这使得如何在并行计算机上高和Hemandez给出了一种迭代负载平衡算法,算法计算复2[4]效求解稀疏线性方程组成为目前高性能并行计算中的一个杂性为O(N/P);Nastea等人给出了一种使用贪心算法研究热点与难点,而利用迭代法求解稀疏线性方程组的计的负载平衡算法,算法的计算复杂性为O(N·P)。我们通算量有90%集中在SpM×V上。因此,研究高效的SpM×过理论分析提出了基于连续行和将稀疏矩阵非零元素平均V并行算法就显得至关重要。分配到每台处理机的负载平衡算法,达到了很好的负载平衡设计好的并行算
7、法要注意两个问题:(1)数据分布的局效果,且算法的计算复杂性降为O(N)。部化,目的是尽量减少通信量和增加计算性能;(2)负载平衡问题,目的是充分利用计算资源。目前,对SpM×V计算问2负载平衡算法题的研究主要集中在针对某类特殊稀疏矩阵在特殊的并行机结构上如何提高计算性能,即数据分布的局部化与串行计SpM×V的计算量与稀疏矩阵非零元素的个数成正比,[1,2]算的优化,而对SpM×V并行计算的负载平衡问题研究下面的叙述中用非零元素的个数来表示负载。因为SpM×3收稿日期:2004202217;修订日期:2004207201基金项目:十五武器装备预研基金资
8、助项目;计算物理国家重点实验室基金资助项目(2000JS761411KG0119)作者简介:刘
