压缩存储的并行高斯-约当消元法及性能优化
2016年6月
第37卷一第6期计算机工程与设计COMPUTER ENGINEERING AND DESIGN June 2016Vol .37一No .6
??????????????????????????????????????????????????压缩存储的并行高斯-
约当消元法及性能优化熊壬浩1,刘一羽2+(1.桂林理工大学信息科学与工程学院,广西桂林541006;
2.桂林理工大学机械与控制工程学院,广西桂林541006)
摘一要:为加速Occam 反演算法中对称带状系数矩阵上的高斯-约当消元法,研究二维等带宽存储方法,提出一种基于对分策略的并行算法,解决顺序策略中因工作三角形上各行的计算量不同导致的负载不均衡问题三在共享内存并行系统上验证该算法的效果,着重研究该平台上算法性能的优化三与串行算法进行对比,对比结果表明,优化方法大幅提升了算法的时间性能,在此基础上并行高斯-约当算法的加速比可达3.72,基于该并行算法的反演算法加速性能良好三
关键词:高斯-
约当消元法;二维等带宽存储;高性能计算;算法优化;共享存储并行程序设计中图法分类号:TP301.6;TP311.1一文献标识号:A一文章编号:1000-7024(2016)06-1526-05doi :10.16208/j .issn1000-7024.2016.06.020收稿日期:2015-07-18;修订日期:2015-09-27基金项目:国家自然科学基金项目(41264005)作者简介:熊壬浩(1987),男,河南周口人,硕士研究生,研究方向为并行计算;+通讯作者:刘羽(1961),男,广西桂林人,博士,教授,研究方向为并行计算二数据挖掘三E -mail :lewis _5709@https://www.wendangku.net/doc/152186320.html, Parallelization and p erformance im p rovement of Gauss -Jordan elimination on com p ressed stora g e
XIONG Ren -hao 1,LIU Yu 2+(1.Colle g e of Information Science and En g ineerin g ,Guilin Universit y of Technolo gy ,Guilin 541006,China ;
2.Colle g e of Mechanical and Control En g ineerin g ,Guilin Universit y of Technolo gy ,Guilin 541006,China )Abstract :Aimin g at acceleratin g Gauss -Jordan elimination in Occam inversion al g orithm on s y mmetrical banded matrix ,two -di -mension constant bandwidth stora g e was researched ,one kind of p aired distribution strate gy based p arallel al g orithm was p resen -ted to solve load imbalance p roblem caused b y different calculation amounts on lines of work trian g le in se q uential distribution strate gy .Performance of this al g orithm was verified on shared memor y p arallel s y stem ,in which o p timization methods of al g o -rithm p erformance were em p haticall y studied.Ex p erimental results show that com p ared to serial al g orithm ,these methods im -p rove the p erformance of al g orithm shar p l y ,which contributes to a s p eedu p of
3.72of p arallel Gauss -Jordan al g orithm as a whole ,while inversion al g orithm based on this p arallel al g orithm has g ood s p eedu p p erformance.
Ke y words :Gauss -Jordan elimination ;two -dimension constant bandwidth stora g e ;hi g h p erformance com p utin g ;al g orithm o p -timization ;shared memor y p arallel p ro g rammin g 0一引一言
在线性方程组的解法中,基于高斯消元法的一类方法
属于直接解法,在方程阶数不是很高时,求解效率高[1]三由于高斯-约当消元法的时间复杂度高,使用此方法的应用往往时间性能很差三高斯-约当消元法是应用广泛的传统算法,除线性方程组的求解外,还可用于矩阵求逆等典型场
景;而有时出于开发效率和成本等原因,高斯-约当消元法的直接并行化也是不二选择三因此高斯-
约当消元法的并行化研究得到了广泛关注,但基于分布式存储环境的居多,基于共享存储环境的较少三例如段治健等[2]提出了一种分布式存储环境下的交替方向迭代并行算法,徐磊等[3]提出了一种基于多粒度混合编程模型的分层并行算法,马欣荣
等[4]提出了一种分布式存储环境下三参数交替方向迭代并行算法三在共享内存系统上,对称带状矩阵的二维等带宽存储方式节约了空间,虽然给算法的设计增加了一定难度[2],但由于矩阵的对称性,消元的效率提高,且消元过程仍具