资源描述：
《Cholesky分解并行算法的性能评测》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第32卷第1期辽宁师范大学学报(自然科学版)Vol.32No.12009年3月JournalofLiaoningNormalUniversity(NaturalScienceEdition)Mar.2009文章编号:1000-1735(2009)01-0058-03Cholesky分解并行算法的性能评测1112刘青昆,聂晓娜,马丽,宫利东(1.辽宁师范大学计算机与信息技术学院,辽宁大连116029;2.辽宁师范大学化学化工学院,辽宁大连116029)摘要:完成对
2、ABEEM模型电荷分布计算的Cholesky分解并行算法的性能评测.在评测过程中,利用通信性能基准测试工具MPBench及其改进后的测试程序分析了该算法中的通信对并行性能的影响.分析结果表明在cpu增长到一定数目后,此算法的通信开销严重影响了并行性能的提高,应该采取相应的解决措施.关键词:Cholesky分解;加速比;MPBench中图分类号:TP316文献标识码:A21世纪高性能计算受到全世界的高度重视,它在科学研究、工程技术以及军事技术等方面取得了巨大成就.以高性能计算机为平台的大规模并行
3、计算已成为研究科学与工程技术的一种重要的手段和方式.对一个问题进行并行计算时,选择一个好的并行算法是很重要的,它的性能好坏直接决定了并行程序的性能好坏.只有对并行算法性能进行有效评测才能准确衡量一个算法的好坏.而对于算法设计者来说,通过对并行算法性能的评测还可以找出算法的缺点,进而改进以提高并行程序的性能.笔者主要对ABEEM模型[1-2]电荷分布计算[3]的Cholesky分解并行算法的性能进行了评测.在评测过程中,通过通信性能基准评测程序MPBench及其改进后的程序分析了通信对Cholesky
4、分解并行算法性能的影响,并根据评测结果对算法性能的提高提出了相应的改进建议.1Cholesky分解并行算法在ABEEM模型电荷分布计算中,我们采用了Cholesky分解,将对称正定n阶矩阵A=[aTij]分解为A=LDL,其中L为对角元素为1的下三角矩阵,D为对角矩阵,LT为对角元素为1的上三角矩阵.Cholesky分解并行算法具体步骤如下(假设P为参与计算的进程数):(1)把矩阵A的上三角部分分别发送到各个进程,按照循环带状划分确定每个进程的任务;(2)对i=0,1,,n-1依次计算,由进程
5、m(m=i%P)进行如下操作:aik/aiiaik(k=i+1,,n-1)广播aij(j=i,,n-1)对j=i+1,,n-1计算.由进程m1(m1=j%q)进行如下操作:(ajk-aijaikai)ajk(k=j,,n-1)T根据以上公式,通过P个进程把矩阵A转换成单位下三角矩阵L乘以一个对角矩阵D再乘以L的形式.(3)回代求解(由进程0负责).令DLTX=Y,则由LY=B可以解出Y,因为DLTX=Y,所以LTX=D-1*Y,由于D是一个对角矩阵,D-1*Y容易求出,继而可以求
6、出X.2Cholesky分解并行算法的性能评测在并行算法性能评测中,常常使用的一项重要指标是加速比,它是评价算法的并行性对运行时间改进的程度.从分子模型中提取系数矩阵,阶数为68756875时,Cholesky分解并行算法的加速比性能与cpu数的关系如图1所示.当cpu小于32时,加速比随着cpu数的增加逐渐增大,但是显然加速比并不是随着cpu数的增加而一味地增大,当cpu大收稿日期:2008-06-27基金项目:国家自然科学基金资助项目(20633050);辽宁省博士科研启动基金(200510
7、58)作者简介:刘青昆(1971-),男,河北清苑人,辽宁师范大学副教授,博士.E-mail:zhengkun@lnnu.edu.cn第1期刘青昆等:Cholesky分解并行算法的性能评测59于32以后加速比开始逐渐减少,当cpu等于64时加速比陡然升到最大值.总体来说,图1说明当cpu等于64时Cholesky分解并行算法的性能最好,cpu等于32时次之.在Cholesky分解并行算法中,随着cpu数的增加,每个处理器分配的矩阵计算任务逐渐减少,计算时间越来越小.但随着cpu数目的增加,通信开销则
8、越来越大,通信性能成为影响算法并行效率进一步提高的主要因素.(测试环境为64位Altix3700服务器(64个IntelItan-iumCPU,主频为1.54GHz),64GB内存,2.6TBSCSI硬盘,网络采用SGIGigabitEthernet.操作系统为SUSELinux(核心版本2.6.16),并行编[4]程环境采用MPICH-1.2.5.)2.1Cholesky分解并行算法通信性能分析图1加速比与cpu数的关系在Choles
