并行PCG算法在电法勘探中的应用研究.pdf

技 术 创 新 中文核心期刊 微计算机信息管控一体化 2 0 0 7年第2 3卷第3 -3期 3 6 0元/年 邮局订阅号8 2 - 9 4 6 现场总线技术应用2 0 0 例 软 件 时 空 并行 P C G算法在电法勘探中的应用研究 R e s e a r c ho nA p p l i c a t i o no fP a r a l l e l P C GA l g o r i t h m i nE l e c t r i c a l S u r v e y i n g 1 .广东工业大学; 2 .广东外语外贸大学陈荣征 1 李代平 1 何驰 2 黄健 1 C H E NR O N G Z H E N G L I D A I P I N G H EC H IH U A N GJ I A N 摘要采用有限元法进行电法勘探时, 会产生大型稀疏线性方程组, 如何提高方程组的求解效率成为物探研究的关键。针对 传统直接法难以实现并行求解的缺点, 提出了在B e o w u l f集群环境下, 采用并行P C G算法求解物探系统线性方程组。在集群 环境下, 该算法具有机器间相互通讯少、 时间复杂度低等优点, 并且易于并行实现。实验结果表明, 采用P C G算法获得了良 好的并行效果。 关键词有限元法;B e o w u l f集群; 预处理共轭梯度法; 并行虚拟机 中图分类号 T P 3 0 1 . 6文献标识码 A A b s t r a c t T h es p a r s es e t so fl i n e a re q u a t i o n sa r ep r o d u c e di ne l e c t r i c a ls u r v e y i n gu s i n gf i n i t ee l e m e n tm e t h o d,h o wt or a i s et h ee f f i - c i e n c yo f t h es o l u t i o no f e q u a t i o n si st h ek e yt oO b j e c t - p r o b e d . I no r d e rt oo v e r c o m et h ed e m e r i t t h a t t r a d i t i o n a l d i r e c t m e t h o di sd i f - f i c u l t t op a r a l l e l i z e , P C Ga l g o r i t h mb a s e do nB e o w u l f c l u s t e ri sp u t f o r w a r dt os o l v el i n e a re q u a t i o n s . T h ea l g o r i t h mh a st h em e r i t so f l e s sc o m m u n i c a t i o n, l o w e rt i m ec o m p l e x i t ya n dp a r a l l e l i m p l e m e n t a t i o ni sa l s ov e r ye a s yu n d e rt h ee n v i r o n m e n t o f B e o w u l f C l u s t e r . E x p e r i m e n t a l r e s u l t ss h o wt h a t g o o dp a r a l l e l r e s u l t sh a v eb e e no b t a i n e du s i n gt h ea l g o r i t h m . K e yw o r d s f i n i t e e l e me n t me t h o d;B e o w u l f C l u s t e r,p r e c o n d i t i o n e dc o n j u g a t e g r a d i e n t me t h o d,P V M 文章编号 1 0 0 8 - 0 5 7 0 2 0 0 7 0 3 -3- 0 2 5 4 - 0 3 1引言 勘探地球物理的正、 反演问题, 通常会涉及复杂的数学问 题与计算方法, 又具有很强的实用性。由于对地球物理现象的 描述大多采用各种数学物理方程, 从数学物理方程的求解方法 会推导出大型稀疏线性方程组。因此, 在进行地球物理的电法 勘探时, 如何对采用有限元法产生的线性方程组进行求解变得 至关重要。采用合理的算法, 不仅会降低求解的复杂度, 还将大 大缩短电法勘探的时间, 从而提高物探开发的效率。 本文作者采用常见的硬件设备和廉价且广为传播的软件, 组建出B e o w u l f集群环境。 基于这一网络并行环境, 采用预处理 共轭梯度法并行求解大型稀疏线性方程组, 有效地克服了传统 的直接法 如高斯消去法、L U分解法 由于前推回代依赖关系 和稀疏性所导致的难以并行求解的缺点。 2问题的提出 在进行电法勘探时,通常会采用有限单元法进行数据处 理, 该方法主要用来求解各个结点的电位值, 一般要经过以下 三个步骤 ①首先, 根据给定的边值条件, 将求解电位U的微分方程 等价地转换成求解相应的变分方程; ②然后, 按一定的规则将求解区剖分为一些在节点处相互 连接的网格单元, 即要使连续的求解区离散化, 进而在各单元 上近似地将变分方程离散化, 从而得出以各节点电位值为未知 量的高阶线性方程组; ③最后, 求解此方程组,计算出各节点的电位值。再根据电 位值,求出电场区的视电阻率, 并描绘出曲线, 通过曲线拟合以 判断测量体的形状、 大小、 密度。 利用有限单元法导出的高阶线性有限元方程组为 [ K ]{ U } { I }。 其中, 系数矩阵[ K ]为三维场区划分各点的刚度矩阵, 是由变 分问题离散化所得。 刚度矩阵[ K ]的元素由节点坐标及电导率的 分布决定, 是已知量, 并且[ K ]是一个大型、 稀疏和带状的对称、 正定矩阵; 右端项为场源列矢量{ I } ,其元素取决于供电极位置和 电流强度, 也是已知值。求解此线性方程组, 便可得出各节点的 电位, 从而获得问题的求解。最终, 原问题归结为对形如A x f 的线性方程组的求解。 共轭梯度法C o n j u g a t eG r a d i e n t M e t h o d 是一种特殊的共 轭方向法, 求解线性方程组A x f时, 它能有效生成与A共轭的 方向向量。该方法尤其适用于求解A为大型、 稀疏、 对称、 正定 矩阵的线性方程组。共轭梯度法对矩阵的元素结构没有特殊要 求, 而且占用存储空间小, 不必事先估计某些参数, 又利用了迭 代算子的特征值分布, 对系数矩阵限制少, 程序编制简单。但 是, 当方程组A x f的系数矩阵A的条件数很大时, 此时若仍采 用共轭梯度法求解, 收敛速度会非常慢。若先降低系数矩阵A 的条件数, 再用共轭梯度法来解这一方程组, 收敛速度将得到 很大改善, 这就是预处理共轭梯度法 P r e c o n d i t i o n e dC o n j u g a t e G r a d i e n t M e t h o d 简记为P C G方法。由于电法勘探中产生的线 性方程组是对称正定的,故笔者尝试在B e o w u l f集群环境下采 用并行P C G法对其进行求解。 3 B e o w u l f集群系统 B e o w u l f集群系统实际上是一种分布式系统结构,它通过 以太网将多台P C连接起来组成一个系统,该系统可以对大量 数据进行并行处理, 从而实现并行机的功能。B e o w u l f集群系统 陈荣征硕士研究生 基金项目广西自然科学基金资助项目桂科自0 2 2 9 0 0 9 2 5 4 -- 邮局订阅号8 2 - 9 4 63 6 0元/年 技 术 创 新 软 件 时 空 P L C技术应用2 0 0例 您的论文得到两院院士关注 最大优点是使用普通的、 相对廉价的计算机软硬件构建出能够 处理繁重计算的集群。硬件方面,B e o w u l f集群通常由最常见的 硬件设备组成, 如P C和以太网交换机, 一般很少包含用户定制 的特殊设备; 软件方面,B e o w u l f集群通常采用那些廉价且应用 较 广 的 软 件 , 如Wi n d o w s操 作 系 统 和 并 行 虚 拟 机P V M或 WP V M。 其中,P V M是目前最为流行的一种消息传递软件之一, WP V M是P V M的F o r Wi n d o w s的版本。WP V M提供了一个可 视化的控制台,用它可以很方便地组建一个并行计算的环境。 另 外, 它还是免费软件不会涉及版权问题, 从网站下载后就可以 直接使用。 4并行P C G算法 4 . 1算法描述 设线性方程为[ A ]{ x } { b }, 把系数矩阵[ A ]、 向量{ b }均划分为 m个子矩阵、 子向量, 称为划分为m个单元块。其中,[ A ]由m个 子矩阵[ A k ] k 1 , . . . , m 组成,{ b }由m个子向量{ b k } k 1 , . . . , m 组成。 预处理矩阵[ C ]为[ A ]的对角阵, 它由m个子矩阵[ C k ] k 1 , . . . , m 组 成。[ A k ]、{ b k }、{ x { k } }分别表示第个单元块的系数矩阵、 子向量和 未知向量, 它们存储在第台处理机上。 首先, 进行初始化。 取{ x { k } } 初值{ x { k } } 0, 计算 在B e o w u l f集群系统上,每台处理机同时执行的P C G算 法如下 4 . 2算法分析 与并行直接法相比,并行P C G法不需要合成总体刚度矩 阵,从而大大减少了处理机间协调同步所需的等待时间。在 B e o w u l f集群环境下,P C G法可在单元块上实现, 故只需要合成 单元块的刚度矩阵, 这个过程易于通过并行实现。 这里, 再对该算法的通讯开销做一简单分析。算法的通讯开 销主要来源于向量内积和矩阵与向量的乘积。在计算向量内积 时, 每个处理器计算它的局部积之和。为了计算总的内积之和, 要花费对数级时间, 因此向量内积的时间复杂度为。 在计算矩阵与向量乘积时, 每个处理器均需与相应的向量分量 集中在一个处理器中, 总的时间复杂度为O n l o g m 。而采用直 接法时, 时间复杂度至少为O n 2 。可见, 在并行迭代过程中, 由 于大量计算局限在单元块内进行, 处理器间通讯耗时较少。 5算法在P V M环境下的实现 编程模式采用P V M的主/从 M a s t e r / S l a v e 模式。并行处理 由一个控制块M a s t e r和若干从属块S l a v e组成, 主/从方式中有 M a s t e r和S l a v e两种进程,M a s t e r主要负责接受任务、 划分任务、 启动计算和回收结果。每台S l a v e负责接受任务、 处理任务、 完 成进程间的数据通信, 最后把处理结果返回给M a s t e r。下面给 出算法实现的关键代码及说明。 1M a s t e r主程序 l o o p G b d a t a . m _ x P o i n t N u m / P r o c N u m ; / /将待处理点数按处理 机个数均分 f o r i 0 ; i P r o c N u m ; i l o o p s [ i ] l o o p ; / /为每台S l a v e机分配 相等的待处理点数 f o r i 0 ; i P r o c N u m - G b d a t a . m _ x P o i n t N u m / P r o c N u m * P r o c N u m ; i l o o p s [ i ] ; / /将均分后剩余的点再一次分配给处理机, 使各 台处理机任务大致相同 p v m i n i t s e n d P v m D a t a D e f a u l t ; / /初始化发送缓冲区 p v m _ p k i n t / /打包变量处理机的个数 p v m _ p k i n t t i d s , P r o c N u m , 1 ; / /打包变量为每台S l a v e机分配 i d的数组 p v m _ p k i n t l o o p s , P r o c N u m , 1 ; / /打包变量每台S l a v e机需处 理任务数的数组 p v m _ m c a s t t i d s , P r o c N u m , m s g _ s p a w n ; / /把上打包的数据以组 播形式发送给每台S l a v e机 2 S l a v e从程序 f o r i 0 ; i n p r o c ; i i f m y t i d t i d s [ i ] {m e i ;b r e a k ;} / /根据自己的i d号,获得自己的序号i m y l o o p l o o p s [ m e ] ; / /得到自己的任务数 u n s i g n e di n t P o s i t i o n , P o s 0 ; f o r j 0 ; j m e ; j P o s l o o p s [ j ] ; / /计算出本机的任务开始点 的位置 f o r i 0 ; i G b l d a t a . m _ x P o i n t N u m b r e a k ; / /判断是否处理完 自己的任务 G e t U P o s i t i o n , i ; / /回代以计算各点电位值,求得结果矩阵 } 6实验及结果分析 本文作者用5台P C组建了一个B e o w u l f集群系统, 微机配 置为 P 42 . 4 G H z的C P U,2 5 6 M B的内存,它们由1 0 0 M b / s高速 交换式以太网相连接, 每台微机上运行Wi n d o w s X P操作系统, 采用WP V M3 . 4版本作为并行计算的支撑平台, 如图1所示。 15 r r α 16 }{}{}{ sprp end for m m n Olog 2 5 5 -- 技 术 创 新 中文核心期刊 微计算机信息管控一体化 2 0 0 7年第2 3卷第3 -3期 3 6 0元/年 邮局订阅号8 2 - 9 4 6 现场总线技术应用2 0 0 例 软 件 时 空 图15台P C组成的P V M平台 利用上述算法,在电法勘探中依次取不同的三维电场空 间, 分别进行了串/并计算对比, 对比结果如表1所示。 表1计算结果比较 分析可知, 并行效率随三维电场规模的增大显著提高。原 因在于当电场的计算规模较小时, 由于串行分量的计算在总的 计算中占用的比重较大, 加上受并行程序运行时额外开销的影 响, 加速比和并行效率较低; 随着求解规模的逐渐扩大, 串行部 分所占比例缩小, 并行部分逐渐增大, 加速比和并行效率迅速 提高。这同加速比定律的G u s t a f s o n修正相吻合。 7结语 在B e o w u l f集群环境下,采用并行P C G算法求解电法勘探 中产生的线性方程组。实验结果表明,该算法在计算规模较小 时, 效果不明显; 当处理有关三维场空间的大计算量问题时, 效 果良好。 这就为提高物探开发的效率提供了一条新的可行途径。 本文的创新点采用有限元法进行电法勘探时, 会产生大型 稀疏线性方程组, 如何提高方程组的求解效率成为物探研究的 关键。针对采用传统直接法, 如高斯消去法、L U分解法等, 存在 难以实现并行求解并导致求解效率偏低的缺点, 本文创造性的 提出在B e o w u l f集群环境下, 采用并行P C G算法求解物探系统 线性方程组,并给出了具体的算法描述与分析。 最后, 在P V M环 境下编程实现了该算法, 并根据实验结果得出结论。 参考文献 [ 1 ] 罗延中. 电子计算机在电法勘探中的应用[ M ] . 武汉 武汉地质 学院出版社， 1 9 8 7 . [ 2 ] 周树荃， 梁维泰， 邓邵忠. 有限元结构分析并行计算[ M ] . 北京 北京科学出版社， 1 9 9 7 . [ 3 ] 李种， 罗家融， 王华忠. 基于 B E O WU L F 的 P C集群系统设计及 并行编程的研究[ J ] 微计算机信息， 2 0 0 5 ， 8 - 3 6 4 - 6 7 . [ 4 ] 陆鑫达. 并行程序设计 第二版 [ M ] . 北京 机械工业出版社, 2 0 0 5 . [ 5 ] 陈国良. 并行算法实践[ M ] . 北京 高等教育出版社， 2 0 0 4 . 作者简介陈荣征1 9 7 9 - , 男, 汉族, 山东临沂人, 硕士研究生, 计算机应用专业,主要研究方向为网络并行计算。E - m a i l r o n g z h e n g c h e n 2 0 0 5 1 6 3 . c o m; 李代平1 9 5 5 - , 男, 汉族, 湖北荆 州人, 博士学历, 教授, 硕士生导师, 主要研究方向为网络并行 计算, 软件体系结构; 何驰 1 9 8 4 - , 女, 学士。 黄健 1 9 7 6 - , 男, 硕 士研究生。 B i o g r a p h y C h e nR o n g z h e n g 1 9 7 9 - , m a l e , t h eH a nn a t i o n a l i t y , m a s t e rd e g r e e , m a j o ri nc o m p u t e ra p p l i c a t i o n , r e s e a r c hs o m e t h i n g a b o u tn e t w o r kp a r a l l e lc o m p u t i n g . L iD a i p i n g 1 9 5 5 - , m a l e , t h e H a nn a t i o n a l i t y , d o c t o rd e g r e e . H ei sp r o f e s s o ra n dt u t o ro fm a s - t e r , h i sr e s e a r c hf o c u s e so nn e t w o r kp a r a l l e lc o m p u t i n ga n ds o f t - w a r ea r c h i t e c t u r e . 5 1 0 0 0 6广州 广东工业大学计算机学院陈荣征 李代平 黄健 5 1 0 4 2 0广州 广东外语外贸大学国际经济与贸易学院 何驰 C o mp u t e rD e p a r t me n to fG u a n g d o n gU n i v e r s i t yo fT e c h - n o l o g y , G u a n g z h o u , 5 1 0 0 0 6C h e n , R o n g z h e n g L i ,D a i p i n g H u a n g , J i a n I n t e r n a t i o n a l T r a d e a n dE c o n o mi c D e p a r t me n t o f G u a n g d o n g U n i v e r s i t yo f F o r e i g nS t u d i e s,G u a n g z h o u , 5 1 0 4 2 0H e , C h i 通讯地址 5 1 0 0 0 6广州广州市大学城广东工业大学计算机 学院陈荣征 收稿日期 2 0 0 7 . 2 . 3 修稿日期 2 0 0 7 . 3 . 5 上接第2 6 1 页 [ 5 ] 潘志庚. 马小虎. 石教英. 虚拟现实中多细节层次模型自动生成 技术综述[ J ] . 中国图象图形学报, 1 9 9 8 , 4 7 5 4 7 5 9 [ 6 ] 邹经宇. 薛玉彩. 基于城市虚拟三维环境的城市公共空间视觉 延续性的比较研究[ A ] . 第二届“ 虚拟现实与地理学“ 学术研讨会 学术论文集[ C ] . 2 0 0 2 . [ 1 ] 黄铁军, 柳建. V R M L国际标准与应用指南[ M ] . 北京 电子工业 出版社, 1 9 9 9 . 4 - 6 . [ 2 ] 刘浩, 戴居丰, 杨磊, 杜忠友, 刘秀婷, 孙翠娟. 虚拟现实技术及其 应用研究[ J ] . 微计算机信息, 2 0 0 5 , 1 2 0 0 - 2 0 1 [ 3 ] 杨宝民. 朱一宁. 分布式虚拟现实技术及其应用[ M ] . 北京 科学 技术出版社, 2 0 0 0 . 1 - 1 0 . [ 4 ] M a r kP e s c e . H i s t o r yo f V i r t u a l R e a l i t yM o d e l i n gL a n g u a g e . [ O L ] . h t t p / / w e b s p a c e . s g i . c o m . [ 5 ] I t J u s t Wo r k s T e c h n o l o g yf o r O n l i n e3 DP r o f e s s i o n a l s [ O L ] . h t t p / / w w w . e y e m a t i c . c o m / p r o d u c t s _ s h o u t 3 d . h t m l . [ 6 ] C u l t 3 dt e c h n i c a lw h i t ep a p e r . [ O L ] . h t t p / /w w w . c u l t 3 d . c o m / c u l t 3 d / c 3 d _t e c h _ w h i t e . p d f . [ 7 ] A b o u t B l a x x u nC o n t a c t[ O L ] . h t t p / / d e v e l o p e r . b l a x x u n . c o m / d o w n l o a d / i n d e x . h t m l . 作者简介丘威1 9 7 4 - , 男, 汉族, 广东省蕉岭人, 讲师, 硕士。 研究方向为虚拟现实技术和软件工程, E - m a i l q i u w e i j y u . e d u . c n ;钟治初1 9 6 4 - , 男, 汉族, 广东五华人, 嘉应学院计算机科学 与技术系,副教授, 硕士,研究方向 软件工程;张立臣1 9 6 2 - , 男, 吉林长春人, 教授, 博士。研究方向为软件工程。 5 1 4 0 1 5广东 梅州 嘉应学院 计算机科学与技术系丘威 钟治初 5 1 0 0 9 0广东广州 广东工业大学计算机学院 张立臣 5 1 4 0 1 5 , C h i n a D e p a r t me n to fC o mp u t e rS c i e n c ea n dT e c h - n o l o g y , J i a y y i n gU n i v e r s i t y , Me i z h o u Q i uWe i Z h o n gZ h i c h u 5 1 0 0 9 0 , C h i n aF a c u l t yo f C o mp u t e r S c i e n c e ,G u a n g d o n gU - n i v e r s i t yo f T e c h n o l o g y , G u a n g z h o u Z h a n gL i c h e n 投稿日期 2 0 0 5 . 1 2 . 1 8 修稿日期 2 0 0 6 . 1 . 2 8 2 5 6 --