数值计算与计算机应用
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  联系我们 |  在线办公 | 
数值计算与计算机应用  2015, Vol. 36 Issue (1): 31-41    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
基于MIC的GaBP并行算法
郑汉垣1,2, 宋安平2, 张武2
1. 龙岩学院计算机系, 福建龙岩 364012;
2. 上海大学计算机工程与科学学院, 上海 200072
MIC-GaBP: A NEW ALGORITHM TO SOLVE LARGE SCALE SPARSE LINEAR SYSTEM
Zheng Hanyuan1,2, Song Anping2, Zhang Wu2
1. Department of Computer Science, Longyan College, Longyan 364012, China;
2. School of Computer Engineering and Science, Shanghai University, Shanghai 200072, China
 全文: PDF (599 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 GaBP(Gaussian Belief Propagation)是一种解线性代数方程组的迭代算法, 它是基于递归更新的概率推理算法, 具有低复杂性和高并行性. MIC是英特尔的至强融核Xeon Phi的Many Integerated Core架构. 它提供数百个同时运行的硬件线程, 能充分满足对高并发度的大量需求. 本文研究了如何高效地求解大规模稀疏线性方程组的并行算法, 通过挖掘GaBP算法特性, 优化算法存储结构和加速迭代, 同时 给出了一种求解大规模稀疏对称线性方程组的基于MIC的GaBP并行算法; 并从美国Florida大学开发的稀疏矩阵库(UFget)中抽取了部分大规模对称稀疏矩阵作为算例进行测试, 计算结果表明, 在相同精度下,基于MIC的GaBP并行算法相对于GaBP算法具有更显著的高效率.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词大规模稀疏线性代数方程组   GaBP算法   MIC   并行算法     
Abstract: A new algorithm named MIC-GABP algorithm is proposed for solving large scale symmetric sparse linear system. This algorithm is based on GaBP(Gauss Belief Propagation) and MIC(Many Integerated Core). We take several large scale sparse matrices from The University of Florida Sparse Matrix Collection as examples to observe the performance of our algorithm. The experimental result shows that MIC-GaBP algorithm has a higher efficiency than traditional GaBP algorithm under the same accuracy.
Key wordsLarge Scale Sparse Linear System   GaBP   MIC   Parallel Algorithm   
收稿日期: 2014-08-22;
基金资助:

国家自然科学基金(91330116).

引用本文:   
. 基于MIC的GaBP并行算法[J]. 数值计算与计算机应用, 2015, 36(1): 31-41.
. MIC-GaBP: A NEW ALGORITHM TO SOLVE LARGE SCALE SPARSE LINEAR SYSTEM[J]. Journal of Numerical Methods and Computer Applicat, 2015, 36(1): 31-41.
 
[1] 约翰D. 安德森等. 计算流体力学基础及其应用[M]. 北京: 机械 工业出版社, 2007.
[2] Em Karniadakis G, Sherwin S. Spectral/hp Element Methods for Computational Fluid Dynamics[M]. Oxford Univ. Press,. Oxford, etc., 2nd edt. 2005.
[3] Yousef Saad. 系数线性系统的迭代方法(第2版)[M]. 北京: 科学 出版社, 2009.
[4] Sun X H, Zhang W. A parallel two-level hybrid method for tridiagonal systems and its application to fast poisson solvers[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15: 97-106.
[5] Thomas J. Ashby, Pieter Ghysels, Wim Heirman, Wim Vanroose. The Impact of Global Communication Latency at Extreme Scales on Krylov Methods[C]. 12th International Conference on Algorithms and Architerctures for Parallel Processing(ICA3PP-12), Fukuoka, Japan 2012: 428-442.
[6] Rao S C S, Sarita. Parallel solution of large symmetric tridiagonal linear systems[J]. Parallel Computing, 2008, 34: 177-197.
[7] Hirshman S, Perumalla K, Lynch V, et al. BCYCLIC: A parallel block tridiagonal matrix cyclic solver[J]. Journal of Computational Physics, 2010, 229: 6392-6404.
[8] Manguoglu M, Saied F, Sameh A, Grama A. Performance models for the Spike banded linear system solver[J]. Scientific Programming, 2011, 19(1): 13-25.
[9] Zheng H Y, Song A P, Liu Z X, et al. Research of Multicore-based Parallel GaBP Algorithm with Dynamic Load-balannce[J]. International Journal of Numerical Analysis \& Modeling, Series B, 2014, 5(1-2): 123-135.
[10] ET AL. J A. Exploiting thread-level parallelism in the iterative solution of sparse linear systems[J]. Parallel Comput, 2011, doi:10.1016/j.parco.2010.11.002.
[11] Pashos G, Kavousanakis M E, et al. Simultaneous solution of large-scale linear systems and eigenvalue problems with a parallel GMRES method[J]. Journal of Computational and Applied Mathematics, 2009, 227: 196-205.
[12] Ori Shental, Paul H. Siegel, Jack K. Wolf, Danny Bickson, Danny Dolev: Gaussian belief propagation solver for systems of linear equations[C]. ISIT 2008: 1863-1867.
[13] Yousef El-Kurdi, Warren J. Gross, and Dennis Giannacopoulos. Efficient implementation of Gaussian Belief Propagation Solver for Large Sparse Diagonally Dominant linear systems[J]. IEEE Transactions on magnetics, 2012, 48(2): 471-474.
[14] Zhang Heng, Zhang, Wu. A Parallel multi-layer hybrid algorithm for solving block-tridiagonal systemes[C]. Proc. Int. Conf. Transp., Mech., Electr. Eng., TMEE, 2011, 1415-1418.
[15] Davis A, Hu Y. The University of Florida Sparse Matrix Collection[J]. ACM Transactions on Mathematical Software, 2011, 38(1): 1-28.
[16] Weiss Y, Freeman W T. Correctness of belief propagation in Gaussian graphical models of arbitrary topology[J]. Neural Computation, 2001, 13(10): 2173-2200.
[1] 胡伟. 常微分方程初值问题的完全三阶并行块算法及实验阶研究[J]. 数值计算与计算机应用, 2014, 35(3): 163-170.
[2] 王玉柱, 姜金荣, 迟学斌, 岳天祥. 并行准高斯高阶递归滤波算法研究[J]. 数值计算与计算机应用, 2014, 36(2): 179-194.
[3] 王玉柱, 姜金荣, 蔡长青, 迟学斌, 岳天祥. 三维变分资料同化系统并行算法设计与实现[J]. 数值计算与计算机应用, 2013, 34(3): 231-240.
[4] 吴洋, 赵永华, 纪国良. 一类大规模稀疏矩阵特征问题求解的并行算法[J]. 数值计算与计算机应用, 2013, 34(2): 136-146.
[5] 张学波, 李晓梅. 快速求解一类Toeplitz循环三对角线性方程组的分布式并行算法[J]. 数值计算与计算机应用, 2009, 30(3): 161-169.
[6] 金君,乔楠,梁德旺. NAPA软件的并行优化[J]. 数值计算与计算机应用, 2008, 29(1): 65-72.
[7] 肖曼玉,吕全义,汪保,欧阳洁. 块三对角线性方程组的一种并行算法[J]. 数值计算与计算机应用, 2007, 28(4): 241-249.
[8] 朱君,赵宁. Euler方程非结构网格分布式并行计算[J]. 数值计算与计算机应用, 2007, 28(3): 161-166.
[9] 郑芳英,韩丛英,贺国平. 一个无约束优化问题并行算法的异步执行[J]. 数值计算与计算机应用, 2007, 28(1): 63-70.
[10] 张学波,李晓梅. 一类Toeplitz三对角方程组的有效分布式并行算法[J]. 数值计算与计算机应用, 2005, 26(2): 101-109.
[11] 吴建平,李晓梅. 块三对角阵分解因子的估值与应用[J]. 数值计算与计算机应用, 2002, 24(3): 283-290.
[12] 陈丽容,刘德贵. 求解刚性常微分方程的并行Rosenbrock方法[J]. 数值计算与计算机应用, 1998, 20(3): 251-260.
[13] 谷同祥,刘兴平. 并行二级多分裂迭代方法[J]. 数值计算与计算机应用, 1998, 20(2): 153-.
Copyright © 2008 数值计算与计算机应用 版权所有
中国科学院数学与系统科学研究院 《数值计算与计算机应用》编辑部
北京2719信箱 (100190) Email: szjs@lsec.cc.ac.cn
Support by Beijing Magtech Co.ltd   E-mail:support@magtech.com.cn
京ICP备05002806号-10