期刊发表网电话

全国热线
022-83699069

基于OpenMp并行共轭梯度算法应用及实现的概述

作者: 发布时间:2020-02-03 09:02:46 阅读: 55 次

摘要:现阶段并行计算依靠高性能并行计算机来实现已成为主流,充分利用多核的计算能力,实现算法的并行计算,是提高我们生活中需要求解线性方程组效率的有效途径,并能快速解决大型且复杂的计算问题。本文主要基于OpenMp这个平台,实现并行共轭梯度算法的应用意义及实现进行探讨分析。

关键词:并行计算,线性方程组,共轭梯度法,预处理

1定义及概念

 并行计算:并行计算或称平行计算是相对于串行计算来说的。所谓并行计算可分为时间上的并行和空间上的并行。 时间上的并行就是指流水线技术,而空间上的并行则是指用多个处理器并发的执行计算。

共轭梯度法:介于最速下降法与牛顿法之间的一个方法,它仅需利用一阶导数信息,克服了最速下降法收敛慢的缺点,又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点,共轭梯度法不仅是解决大型线性方程组最有用的方法之一,也是解大型非线性更优化最有效的算法之一。

OpenMp:用于共享内存并行系统的多线程程序设计的一套指导性的编译处理方案(Compiler Directive)OpenMP支持的编程语言包括C语言、C++Fortran

2研究的应用意义

1)求解线性方程组的作用与意义

在工程技术,自然科学和社会科学中,经常遇到的很多问题最终都可归结为解线性方程组,如电学中网络问题、用最小二乘法求实验数据的求实验数据的曲线拟合问题,工程中的三次样条函数问题以及大地测量、机械与建筑结构的设计计算问题等等,因此,在生活中线性方程组的求解是极其重要的。通过对线性方程组的研究,提高对其的求解效率,来满足现代工程生产中大规模运算的需求。

2)求解线性方程组的方法:

经典的求解线性方程组的方法一般分为两类:直接法和迭代法。前者例如高斯消去法,LU分解等,后者的例子包括Jacobi迭代法(J)Gauss-Seidel迭代法(GS),逐次超松弛法(SOR),共轭梯度法(CG)等。一般来说,直接法对于阶数比较低的方程组(少于2000030000个未知数)比较有效,而后者对于比较大的方程组更有效。在实际计算中,几十万甚至几百万个未知数的方程组并不少见,而在这些情况下,迭代法有无可比拟的优势。另外,使用迭代法可以根据不同的精度要求选择终止时间,因此比较灵活。在问题特别大的时候,计算机内存可能无法容纳被操作的矩阵,这给直接法带来很大的挑战。而对于迭代法,则可以将矩阵的某一部分读入内存进行操作,然后再操作另外部分。

同时,在迭代法中,Jacobi迭代法(J)Gauss-Seidel迭代法(GS),逐次超松弛法(SOR)这些方法收敛太慢,甚至不收敛。其中更优方法SOR依赖于参数的选取,一般无法得到更优参数,从而限制了方法的有效性。并且在初始向量、误差界等条件相同的情况下,共轭梯度法比Jacobi迭代法、Gauss-Seidel迭代法、逐次超松弛法在解的精度和收敛性上都有优势。

3)并行计算方法的优势及意义

并行计算主要依靠高性能并行计算机来实现,目前较为流行的高性能计算系统大体可分为共享内存系统和分布存储系统,包括SMPMPPCOWDSM等。在SMP架构中,多个处理器运行操作系统的单一副本,并共享内存和一台计算机的其他资源。在MPP系统中,通过编写专用操作系统和相应软件,就可以把一项庞大的任务分成多个子任务,使得每个CPU处理相应的子任务。充分利用多核的计算能力,实现算法的并行计算,是提高求解线性方程组的效率的有效途径,并能快速解决大型且复杂的计算问题。

3线性方程组和并行计算平台的发展现状

1)求解线性方程组方法的研究现状及比较:

现阶段,由于解线性方程组的直接法具有局限性,目前的研究对经典直接法的改进又相对较少。相比之下对迭代法的改进相对活跃,归纳出大体为两方面的改进,一是通过改进预条件处理和迭代格式,发展出基于经典迭代法的新的Jacobi迭代法[1]Gauss_Seidel迭代法[2]USSOR迭代法[3]AOR_BAOR_迭代法[4]和共轭梯度法[5]等,相较于经典迭代法,可以通过减小迭代矩阵的谱半径,减少收敛时间,加快收敛速度;另一种是通过结合多种算法的特点形成新算法,比如结合了统计类方法和迭代法的随机共轭梯度法[6],消除了迭代法依赖于初始猜测,容易陷入局部极值的缺点,还有结合Krylov子空间方法和SOR迭代的变预处理子SOR-双共轭残量法,能减少迭代次数,并通过不同的松弛因子减少迭代的运行时间等。

 

2)并行计算平台及方法的研究现状及比较:

按存储结构,并行平台主要分为共享内存和分布式内存。后者例如机群,超级计算机。超级计算机运行效率高,在解决超大规模计算中,发挥不可代替作用,但是代价特别高。机群平台的研究也很多。例如机群环境下基于PCG法的有限元并行算法,基于工作站机群的有限元结构分析并行计算;共享内存平台,如基于GPU平台,CPU平台的研究。如基于GPU的混合精度平方根共轭梯度算法、CUDA架构下大规模稠密线性方程组的并行求解,该平台虽然代价少,但是由于GPU构造复杂,编程难度很大。还有基于CPU的,目前推出的个人PC机处理器已经是双核或四核,充分利用多核处理器的优势已经势在必行,因此该平台也越来越受到人的青睐。并且已有很多这方面研究。如多核平台稀疏矩阵向量乘优化研究综述、多核多线程并行求解线性方程组。

4求解实现的过程

1)用C语言实现串行共轭梯度算法

进行了一系列的选择,我们认为在C/C++FORTRAN语言中C进行基于OpenMP的串行程序设计更优语言。

2)共轭梯度算法预处理

对条件数的学习和研究,了解到病态矩阵对计算过程的影响。于是我们希望通过寻找合适的预处理方法减少矩阵的条件数,去除矩阵的病态性,从而达到减少迭代次数,提高计算精度的目的。我们考虑采用不完全cholesky分解法。

3)引入压缩存储的共轭梯度算法

采用了三元组表法对矩阵进行存储,略过了零元素,仅保存非零元元素的数值、行号和列号。之后发现了线性表法,它改变了存储的内容,存储了非零元数值、每个元素的列号、每个元素与该行头的距离以及每行中的个非零元在DATA数组中的位置。最后采用了全稀疏矩阵存储方案,采用动态链表存储矩阵,能真正的节省存储空间。

4)通过Matlab编程生成测试矩阵

      为了获得足够可供测试的数据,我们采用随机生成下三角矩阵并与其转置矩阵相乘的方法,得到符合共轭梯度算法要求的对称正定矩阵,然后通过Matlab对随机生成矩阵进行求解,然后就生成一组Abx矩阵。

5)改良测试方法

为了较为地监测程序的运行情况,我们计划制作了专门测试用的软件来获取程序运行时间、迭代次数、结果误差等详细信息,并做出分析和评价,提高了测试的效率,加快了代码的改进进度。

5结束语

并行计算具有非常广阔的应用前景,相关的关键技术也发展迅速。虽然现阶段还有很多问题需要解决,但是并行共轭梯度算法的使用成为炙手可热的趋势不可改变。

 

参考文献:

[] 田秋菊 宋岱才 新的预条件的Jacobi迭代法及比较性定理[J] 科学技术与工程,20101032),7875-7877

[2] 闫浩 郑全录 一种循环分布的GuassSeidel迭代算法求解线性方程组[J] 计算机应用与软件,2011287),262-263

[3] 田秋菊 李金秋 预条件USSOR迭代法及比较定理[J]  辽宁石油化工大学学报,2011314),91-94

[4] 杨顺枫 李耀堂 程 军 Z-矩阵的预条件块AOR[BAOR)迭代法[J] 曲靖师范学院学报,2011303),1-7

[5] Fei Chen Kevin B. TheobaldGuang R. Gao Implementing Parallel Conjugate Gradient on the EARTH Multithreaded[J]  CLUSTER 2004459-470

[6] 朱培民 王家映 共轭梯度法[J] 工程地球物理学报 ,200854),381-386