核外并行求解线性方程组的设计与实现
|
摘要
由于大型线性方程组在化学工程、天气预报、数值方法等领域中都有广泛应用,使得对其求解的研究一直是个热点。随着科学技术的迅猛发展,人们所需要处理的数据量迅速增长。虽然近些年来计算机硬件迅猛发展,但是内存容量常常不能满足涉及到大数据量计算问题的存储需求。目前各种类型的并行处理系统已成为科研或求解重大规模问题的主流计算环境。为了适应新的计算环境、追求更高的求解速度和更大的求解容量,集群系统因其是具有良好性价比的并行处理机系统已被广泛用于科研和应用中。因此在集群环境下对大型线性方程组的并行求解方法的研究和设计,就具有非常重要的理论和实际意义。求解线性方程组的方法有很多,由于本文求解的线性方程组的系数矩阵是对称的,我们采用Cholesky分解的方法求解。本文对基于集群系统下线性方程组的串并行算法进行了细致的研究和分析,主要内容包括:
(1)实现了MPI编程环境下求解线性方程组的Cholesky分解的串并行核内算法。
(2)通过分析串并行Cholesky分解核内算法,给出了存在的问题及优化方法。
(3)在核内并行算法的基础上,提出了核外预取算法的并行方案;不仅成功的解决了内存容量小的问题,而且还有效的缩短了I/O与CPU速度间的差距,提高了Cholesky分解的效率。
(4)在核外并行算法的基础上,提出了数据重用的方法;通过将当前已经读入内存而下一次仍需用到的数据继续的留在内存,来降低I/O操作的时间,实现了对核外数组的合理调度与高效访问。
本文搭建了基于Linux的并行计算平台,构建了此平台下的MPI并行程序设计环境。同时将本文提出的核外预取和数据重用算法在此平台上进行了测试,并对实验结果进行了性能分析。结果表明,本文设计的算法能够很好的在小内存的集群上运行大规模线性方程组的Cholesky求解程序。
Because of the large-scale system of linear equations having widespread applications in some fiels such as chemical engineering,weather forecast and numerical methods and so on,the research on its solution has been a hot topic.With the rapid development of science and technology,the amount of data that people need to deal with is the rapid growth.Computer hardware has a rapid development in recent years,but memory capacity usually can not meet the storage needs of a large amount of data calculation.Now,various types of parallel processing system has become the mainstream computing environment of scientific research or solving the problem of signification scale.
In order to adapt to the new computing environment,pursuit the solving of higher speed and greater capacity,cluster system is widely used in scientific research and application because it is a parallel processor system with good cost-effective.Therefore the research and design of parallel solution of the larger linear equations in the cluster environment have an important significance of theoretical and practical.There are many methods to solving linear equations,because the symmetry of coefficient matrix which solves linear equations in this paper,so the method of cholesky decomposition has been used to solve linear equations.
This article carefully researches and analysises the Serial and Parallel Algorithms of linear equations based on the cluster system, the content including:
(1) To achieve the cholesky decomposition algorithms of serial and parallel in core to solve linear equations in MPI environment.
(2) Analysis cholesky decomposition algorithm of serial and parallel in core,then given the problems and optimization.
(3) We proposed a parallel method of out-of-core prefetching algorithm based on parallel method in core.The method not only sove the problem of small memory capacity,but also shorten the speed gap between I/O and CPU effectively and improved the efficiency of cholesky decomposition.
(4) We proposed a parallel method of data reuse based on out-of-core parallel algorithms. The algorithm reduced the time of I/O operation and achieved reasonable schedule and efficient access to out-of-core array by the data remaining in memory which has been read into memory now and still be used in next time.
This article built a parallel computing platform based on Linux and constructed MPI environment of parallel programming.At the same time,test the algorithm of out-of-core prefetching and data reuse on Linux platform, then analysis the performance of experimental results.The results show that this algorithm can run cholesky decomposition program of large-scale linear equations on cluster in a small memory.
(1)实现了MPI编程环境下求解线性方程组的Cholesky分解的串并行核内算法。
(2)通过分析串并行Cholesky分解核内算法,给出了存在的问题及优化方法。
(3)在核内并行算法的基础上,提出了核外预取算法的并行方案;不仅成功的解决了内存容量小的问题,而且还有效的缩短了I/O与CPU速度间的差距,提高了Cholesky分解的效率。
(4)在核外并行算法的基础上,提出了数据重用的方法;通过将当前已经读入内存而下一次仍需用到的数据继续的留在内存,来降低I/O操作的时间,实现了对核外数组的合理调度与高效访问。
本文搭建了基于Linux的并行计算平台,构建了此平台下的MPI并行程序设计环境。同时将本文提出的核外预取和数据重用算法在此平台上进行了测试,并对实验结果进行了性能分析。结果表明,本文设计的算法能够很好的在小内存的集群上运行大规模线性方程组的Cholesky求解程序。
Because of the large-scale system of linear equations having widespread applications in some fiels such as chemical engineering,weather forecast and numerical methods and so on,the research on its solution has been a hot topic.With the rapid development of science and technology,the amount of data that people need to deal with is the rapid growth.Computer hardware has a rapid development in recent years,but memory capacity usually can not meet the storage needs of a large amount of data calculation.Now,various types of parallel processing system has become the mainstream computing environment of scientific research or solving the problem of signification scale.
In order to adapt to the new computing environment,pursuit the solving of higher speed and greater capacity,cluster system is widely used in scientific research and application because it is a parallel processor system with good cost-effective.Therefore the research and design of parallel solution of the larger linear equations in the cluster environment have an important significance of theoretical and practical.There are many methods to solving linear equations,because the symmetry of coefficient matrix which solves linear equations in this paper,so the method of cholesky decomposition has been used to solve linear equations.
This article carefully researches and analysises the Serial and Parallel Algorithms of linear equations based on the cluster system, the content including:
(1) To achieve the cholesky decomposition algorithms of serial and parallel in core to solve linear equations in MPI environment.
(2) Analysis cholesky decomposition algorithm of serial and parallel in core,then given the problems and optimization.
(3) We proposed a parallel method of out-of-core prefetching algorithm based on parallel method in core.The method not only sove the problem of small memory capacity,but also shorten the speed gap between I/O and CPU effectively and improved the efficiency of cholesky decomposition.
(4) We proposed a parallel method of data reuse based on out-of-core parallel algorithms. The algorithm reduced the time of I/O operation and achieved reasonable schedule and efficient access to out-of-core array by the data remaining in memory which has been read into memory now and still be used in next time.
This article built a parallel computing platform based on Linux and constructed MPI environment of parallel programming.At the same time,test the algorithm of out-of-core prefetching and data reuse on Linux platform, then analysis the performance of experimental results.The results show that this algorithm can run cholesky decomposition program of large-scale linear equations on cluster in a small memory.
引文
[1]刘青昆,聂小娜,马丽的等,Cholesky分解并行算法的性能评测,辽宁师范大学学报,2009,32(1):58-60
[2]杨忠志,刘娇,宫利东等,并行程序实现ABEEMσπ模型电荷分布计算,辽宁师范大学学报,2008,31(2):177-180
[3]张艺,线性方程组求解的一个迭代算法,宁波大学学报,2001,14(1):51-55
[4]陈丽红,周志刚,万立,求解线性方程组的一种迭代法的改进,武汉科技学院学报,2010,23(2):33-35
[5]樊艳红,吕全义,块三对角线方程组的一种并行迭代算法,计算机仿真,2011,28(2):109-112
[6]段治健,杨永,马欣荣等,求解带状线性方程组的一种并行算法,计算机科学,2010,37(3):242-245
[7]国现华,线性方程组的求解,邢台学院学报,2006,21(2):92-94
[8]栾林,关于线性方程组AmnXn1=Bm1相关问题的探讨,辽宁师范大学学报,2010,33(2):165-167
[9]徐晓飞,曹祥玉,姚旭等,一种基于Doolittle LU分解的线性方程组并行求解方法,电子与信息学报,2010,32(8):2019-2022
[10]常志巧,郝金明,陈刘成等,一种基于排序和乔列斯基分解的模糊度降相关方法,测绘科学技术学报,2009,26(6):410-413
[11]郭丽杰,周硕,秦万广,对称矩阵的改进Cholesky分解在特征值问题中的应用,东北电力学院学报,2003,23(2):50-54
[12] Hanjoon Cho, Jinyong Lee, Younglok Kim, Efficient Implementation of Linear System Solution Block using LDLT Factorization, 2008, 3:19-20
[13]蒋作,高毅,关于串行程序并行化,云南民族大学学报,2007,16(3):274-276
[14]王顺绪,周树荃,卷帘行存储下的一种并行Cholesky分解及其在PAR95上的实现,南京航空航天大学学报,1999,31(4):428-432
[15]迟学斌,Transputer上Cholesky分解的并行实现,计算数学,1993(3):289-294
[16]梁维泰,周树荃,对称带状矩阵的并行Cholesky分解及相应线性方程组的并行计算,南京航空学院学报,1991,23(2):133-137
[17]顾耀林,刘万龙,刘强等,并行J-变量块Cholesky分解算法的仿真研究,计算机仿真,2006,23(8):82-85
[18]张学波,高佳,高立梅,分块求解三角形线性方程组的一种分布式并行算法,装备指挥技术学院学报,2010,21(1):114-117
[19]陈建平, Jerzy Wasniewski , Cholesky分解递归算法与改进,计算机研究与发展,2001,38(8):923-926
[20] Michael D. Adams, David S. Wise, Seven at One Stroke: Results from a Cache-Oblivious Paradigm for Scalable Matrix Algorithms, Workload optimization, 2006:41-50
[21] K. Patrick Lorton, David S. Wise, Analyzing Block Locality in Morton-Order and Morton-Hybrid Matrices, Medea 2006 workshop, 2007, 35(4):5-12
[22] BJARNE S. ANDERSEN, JOHN A. GUNNELS, FRED G. GUSTAVSON etal, A Fully Portable High Performance Minimal Storage Hybrid Format Cholesky Algorithm, ACM Transactions on Mathematical Software, 2005, 31(2):201-227
[23] [GustavsonKK09] FRED G. GUSTAVSON, LARS KARLSSON, BO KAGSTROM, Distributed SBP Cholesky Factorization Algorithms with Near-Optimal Scheduling, ACM Transactions on Mathematical Software, 2009, 36(2):1-25
[24] EUNICE E. SANTOS, PEI-YUE CHU, Efficient and Optimal Parallel Algorithms for Cholesky Decomposition, Journal of Mathematical Modelling and Algorithms, 2003, 2:217–234
[25] FRED G. GUSTAVSON, JOHN K. REID, JERZY WASNIEWSKI, Algorithm 865: Fortran 95 Subroutines for Cholesky Factorization in Block Hybrid Format, ACM Transactions on Mathematical Software, 2007, 33(1):1-5
[26]龚雪容,陆林生,赵荣彩,并行识别中的依赖关系与通信优化研究,计算机应用,2007,27:9-11
[27] Han S. Kim, Scott B. Baden, A Study on the Performance of Cholesky-Factorization using MPI, 2008:1-13
[28] O.MASLENNIKOW, P.RATUSZNIAK, A.SERGYIENKO, IMPLEMENTATION OF CHOLESKY LLT-DECOMPOSITION ALGORITHM IN FPGA-BASED RATIONAL FRACTION PARALLEL PROCESSOR, 2007, 21–23 June:287-292
[29] Suleyman S Demirsoy, Martin Langhammer, Cholesky Decomposition using Fused Datapath Synthesis, CAD tools 1, 2009, 22–24 February:241-244
[30]王维,胡铭曾,核外计算中I/O优化策略的研究,哈尔滨商业大学学报,2005,21(5):600-603
[31]唐剑琪,方滨兴,胡铭曾,王威,核外计算中的几种I/O优化方法,计算机研究与发展,2005,42(10):1820-1825
[32]丁文魁,汪剑平,向华等,p-HPF并行编译系统核外计算的实现及优化策略,计算机学报,1999,22(10):1042-1049
[33]姚维,Linux下一种磁盘节能的预取算法,计算机系统应用,2010,19(7):91-94
[34]连瑞琦,张兆庆,乔如良,指令级并行编译器的数据预取及优化方法,计算机学报,2000,23(6):576-584
[35]刘陶刚,赵荣彩,姚远等,分块存储的滑动窗口数据重用计算,计算机应用,2010,30(5):1371-1375
[36]丁永华,原庆能,臧斌宇等,多处理机系统循环间数据重用的Cache优化,软件学报,1998,9(8):580-585
[2]杨忠志,刘娇,宫利东等,并行程序实现ABEEMσπ模型电荷分布计算,辽宁师范大学学报,2008,31(2):177-180
[3]张艺,线性方程组求解的一个迭代算法,宁波大学学报,2001,14(1):51-55
[4]陈丽红,周志刚,万立,求解线性方程组的一种迭代法的改进,武汉科技学院学报,2010,23(2):33-35
[5]樊艳红,吕全义,块三对角线方程组的一种并行迭代算法,计算机仿真,2011,28(2):109-112
[6]段治健,杨永,马欣荣等,求解带状线性方程组的一种并行算法,计算机科学,2010,37(3):242-245
[7]国现华,线性方程组的求解,邢台学院学报,2006,21(2):92-94
[8]栾林,关于线性方程组AmnXn1=Bm1相关问题的探讨,辽宁师范大学学报,2010,33(2):165-167
[9]徐晓飞,曹祥玉,姚旭等,一种基于Doolittle LU分解的线性方程组并行求解方法,电子与信息学报,2010,32(8):2019-2022
[10]常志巧,郝金明,陈刘成等,一种基于排序和乔列斯基分解的模糊度降相关方法,测绘科学技术学报,2009,26(6):410-413
[11]郭丽杰,周硕,秦万广,对称矩阵的改进Cholesky分解在特征值问题中的应用,东北电力学院学报,2003,23(2):50-54
[12] Hanjoon Cho, Jinyong Lee, Younglok Kim, Efficient Implementation of Linear System Solution Block using LDLT Factorization, 2008, 3:19-20
[13]蒋作,高毅,关于串行程序并行化,云南民族大学学报,2007,16(3):274-276
[14]王顺绪,周树荃,卷帘行存储下的一种并行Cholesky分解及其在PAR95上的实现,南京航空航天大学学报,1999,31(4):428-432
[15]迟学斌,Transputer上Cholesky分解的并行实现,计算数学,1993(3):289-294
[16]梁维泰,周树荃,对称带状矩阵的并行Cholesky分解及相应线性方程组的并行计算,南京航空学院学报,1991,23(2):133-137
[17]顾耀林,刘万龙,刘强等,并行J-变量块Cholesky分解算法的仿真研究,计算机仿真,2006,23(8):82-85
[18]张学波,高佳,高立梅,分块求解三角形线性方程组的一种分布式并行算法,装备指挥技术学院学报,2010,21(1):114-117
[19]陈建平, Jerzy Wasniewski , Cholesky分解递归算法与改进,计算机研究与发展,2001,38(8):923-926
[20] Michael D. Adams, David S. Wise, Seven at One Stroke: Results from a Cache-Oblivious Paradigm for Scalable Matrix Algorithms, Workload optimization, 2006:41-50
[21] K. Patrick Lorton, David S. Wise, Analyzing Block Locality in Morton-Order and Morton-Hybrid Matrices, Medea 2006 workshop, 2007, 35(4):5-12
[22] BJARNE S. ANDERSEN, JOHN A. GUNNELS, FRED G. GUSTAVSON etal, A Fully Portable High Performance Minimal Storage Hybrid Format Cholesky Algorithm, ACM Transactions on Mathematical Software, 2005, 31(2):201-227
[23] [GustavsonKK09] FRED G. GUSTAVSON, LARS KARLSSON, BO KAGSTROM, Distributed SBP Cholesky Factorization Algorithms with Near-Optimal Scheduling, ACM Transactions on Mathematical Software, 2009, 36(2):1-25
[24] EUNICE E. SANTOS, PEI-YUE CHU, Efficient and Optimal Parallel Algorithms for Cholesky Decomposition, Journal of Mathematical Modelling and Algorithms, 2003, 2:217–234
[25] FRED G. GUSTAVSON, JOHN K. REID, JERZY WASNIEWSKI, Algorithm 865: Fortran 95 Subroutines for Cholesky Factorization in Block Hybrid Format, ACM Transactions on Mathematical Software, 2007, 33(1):1-5
[26]龚雪容,陆林生,赵荣彩,并行识别中的依赖关系与通信优化研究,计算机应用,2007,27:9-11
[27] Han S. Kim, Scott B. Baden, A Study on the Performance of Cholesky-Factorization using MPI, 2008:1-13
[28] O.MASLENNIKOW, P.RATUSZNIAK, A.SERGYIENKO, IMPLEMENTATION OF CHOLESKY LLT-DECOMPOSITION ALGORITHM IN FPGA-BASED RATIONAL FRACTION PARALLEL PROCESSOR, 2007, 21–23 June:287-292
[29] Suleyman S Demirsoy, Martin Langhammer, Cholesky Decomposition using Fused Datapath Synthesis, CAD tools 1, 2009, 22–24 February:241-244
[30]王维,胡铭曾,核外计算中I/O优化策略的研究,哈尔滨商业大学学报,2005,21(5):600-603
[31]唐剑琪,方滨兴,胡铭曾,王威,核外计算中的几种I/O优化方法,计算机研究与发展,2005,42(10):1820-1825
[32]丁文魁,汪剑平,向华等,p-HPF并行编译系统核外计算的实现及优化策略,计算机学报,1999,22(10):1042-1049
[33]姚维,Linux下一种磁盘节能的预取算法,计算机系统应用,2010,19(7):91-94
[34]连瑞琦,张兆庆,乔如良,指令级并行编译器的数据预取及优化方法,计算机学报,2000,23(6):576-584
[35]刘陶刚,赵荣彩,姚远等,分块存储的滑动窗口数据重用计算,计算机应用,2010,30(5):1371-1375
[36]丁永华,原庆能,臧斌宇等,多处理机系统循环间数据重用的Cache优化,软件学报,1998,9(8):580-585