机群计算在基于有限元法电法勘探中的应用
|
摘要
高速计算机网络和不断提高的微处理芯片性能使得计算机网络成为吸引人的并行计算载体。仅依赖于商业化的硬件和软件，计算机网络能够提供高性价比、高可用性的计算。这种高性能计算潮流一般被称为机群计算。近年来，机群计算已经成为学术界和业界团体研究的热点。
并行虚拟机(PVM)是一个可以将异构的“机群计算机”集合虚拟成一台高性能并行机的软件包。这样大规模计算问题可以通过使用众多计算机聚集取来的计算能力和内存来低成本解决。PVM可移植性好，可运行在当今的多数平台上。PVM拥有着大量的用户，现已成为世界上分布式计算事实上的标准。
本文成功的将机群计算应用到解决在电法勘探中使用有限元方法(FEM)时产生的大规模线性方程组问题。有限元被证明为在许多科学和工程领域中连续物理系统模拟的一种普遍方法，但缺点是传统的串行计算机需要花费太多的计算时间。FEM需要对域进行离散化(一个网格或者模型)，FEM的这种思想和机群分而治之的思想相似。因此，有限元节点代码可以被并行化、在不同的基于PVM机群结点上运行。程序用C++编写，通过调用PVM库函数提供对并行虚拟机的访问。有限元法产生的线性方程组使用共轭梯度算法求解。共轭梯度(CG)法与有限元法联系的十分自然因为两者都是采用相似的最小化过程。共轭梯度算法不需要构造全局矩阵，它在大规模并行结构中能被有效地实现。
High speed network and improved microprocessor performance are making networks of computers an appealing vehicle for parallel computing. By relying solely on commodity hardware and software, network of computers can offer cost-effective high performance and high availability computing. This new wave in high performance computing is popularly called as Cluster Computing. In recent years, Cluster computing has become a hot topic research among academic and industry community.
Parallel Virtual Machine (PVM) is a software package that permits a heterogeneous collection of "cluster computers' to function as a single high-performance parallel machine. Thus large computational problems can be solved more cost effectively by using the aggregate power and memory of many computers. PVM is portable and runs on a wide variety of modern platforms. With tens of thousands of users, PVM has become the de facto standard for distributed computing world-wide.
This dissertation successfully uses cluster computing for solving large-scale linear algebraic equations problems when the finite element method (FEM) is applied in electrical prospecting. FEM has proven to be a versatile method for the simulation of continuous physical systems in many areas of science and engineering. But a disadvantage arises due to the very high computation times regarding conventional serial computers. FEM requires a discretization (a mesh or a model) of a domain. This thought of FEM is similar to that of cluster computing, which is divide and rule. Therefore, the finite element code can be parallelized and executed on different cluster nodes on which PVM is available. The program is written in C++, provided access to PVM through the use of calls to PVM library routines. The system of linear equations produced by the FEM is solved by conjugate gradient (CG) algorithm, which is associated naturally with finite element problems because both finite element and conjugate gradient use similar minimization procedures. The CG algorithm does not require construction of the global matrix. It can be implemented efficiently on a
Abstract
massively parallel architecture.
并行虚拟机(PVM)是一个可以将异构的“机群计算机”集合虚拟成一台高性能并行机的软件包。这样大规模计算问题可以通过使用众多计算机聚集取来的计算能力和内存来低成本解决。PVM可移植性好，可运行在当今的多数平台上。PVM拥有着大量的用户，现已成为世界上分布式计算事实上的标准。
本文成功的将机群计算应用到解决在电法勘探中使用有限元方法(FEM)时产生的大规模线性方程组问题。有限元被证明为在许多科学和工程领域中连续物理系统模拟的一种普遍方法，但缺点是传统的串行计算机需要花费太多的计算时间。FEM需要对域进行离散化(一个网格或者模型)，FEM的这种思想和机群分而治之的思想相似。因此，有限元节点代码可以被并行化、在不同的基于PVM机群结点上运行。程序用C++编写，通过调用PVM库函数提供对并行虚拟机的访问。有限元法产生的线性方程组使用共轭梯度算法求解。共轭梯度(CG)法与有限元法联系的十分自然因为两者都是采用相似的最小化过程。共轭梯度算法不需要构造全局矩阵，它在大规模并行结构中能被有效地实现。
High speed network and improved microprocessor performance are making networks of computers an appealing vehicle for parallel computing. By relying solely on commodity hardware and software, network of computers can offer cost-effective high performance and high availability computing. This new wave in high performance computing is popularly called as Cluster Computing. In recent years, Cluster computing has become a hot topic research among academic and industry community.
Parallel Virtual Machine (PVM) is a software package that permits a heterogeneous collection of "cluster computers' to function as a single high-performance parallel machine. Thus large computational problems can be solved more cost effectively by using the aggregate power and memory of many computers. PVM is portable and runs on a wide variety of modern platforms. With tens of thousands of users, PVM has become the de facto standard for distributed computing world-wide.
This dissertation successfully uses cluster computing for solving large-scale linear algebraic equations problems when the finite element method (FEM) is applied in electrical prospecting. FEM has proven to be a versatile method for the simulation of continuous physical systems in many areas of science and engineering. But a disadvantage arises due to the very high computation times regarding conventional serial computers. FEM requires a discretization (a mesh or a model) of a domain. This thought of FEM is similar to that of cluster computing, which is divide and rule. Therefore, the finite element code can be parallelized and executed on different cluster nodes on which PVM is available. The program is written in C++, provided access to PVM through the use of calls to PVM library routines. The system of linear equations produced by the FEM is solved by conjugate gradient (CG) algorithm, which is associated naturally with finite element problems because both finite element and conjugate gradient use similar minimization procedures. The CG algorithm does not require construction of the global matrix. It can be implemented efficiently on a
Abstract
massively parallel architecture.
引文
[1] Wilkinson, B., Allen, M..并行程序设计．陆鑫达 等译．北京：机械工业出版社，2001
[2] 李晓梅，莫则尧，胡庆丰 等．可扩展并行算法的设计与分析．北京：国防工业出版社，2000
[3] 沈志宇，缪湘科，胡子昂．并行程序设计．长沙：国防科技大学出版社，1997
[4] 刘晓明．异构机群系统环境下PVM并行程序的编程方法研究：硕士学位论文．广州：暨南大学图书馆，2001
[5] 章文，罗清磊，李璟．机群的可扩展性研究．安庆师范学院学报(自然科学版)，2003，9(1)：107～108
[6] 郑伟民，汤志忠．计算机体系结构．第2版．北京：清华大学出版社．1998
[7] 黄恺，徐志伟(HWANG Kai, XU Zhiwei)．可扩展并行计算技术、结构与编程(Scalable Parallel Computing Technology,Architecture, Programming)．陆鑫达，曾国荪，邓倩妮 等译．北京：机械工业出版社，2000
[8] Rajkumar Buyya．高性能集群计算：结构与系统(第一卷)(High Performance Cluster Computing: Architectures and Systems, Volume 1)．郑伟民，石威，王东升 等译．北京：电子工业出版社，2001
[9] Comer,D. E.. 计算机网络与因特网(Computer Networks and Internets，2nd Edition)．徐良贤，唐英，王勋 等译．北京：机械工业出版社，2000
[10] 邹晖，罗省贤．机群并行系统与网络并行计算环境．物探化探计算技术，2001，23(4)：375～379
[11] Stallings, W. Computer Organization and Architecture: Designing for Performance. 5th Edition影印版．北京：高等教育出版社·Pearson Education, 2001
[12] 纪珊珊．基于PVM的并行计算在PC机群上的实现：硕士学位论文．大连：大连理工大学图书馆，2000
[13] Rajkumar Buyya，高性能集群计算：编程与应用(第二卷)(High Performance Cluster Computing: Programming and Applications, Volume 2)．郑伟民，王东升，
石威 等译．北京：电子工业出版社，2001
[14] 章文，李代平，罗清磊 等．机群并行系统的设计．现代计算机，2003，157：16～18
[15] Tanenbaum, A.S.. Computer Networks. 3rd Edition影印版．北京：清华大学出版社·Prentice Hall，1996
[16] 缪湘科．网络并行计算中的负载平衡．小型微型计算机系统，1995，Vol．16No．9：32～36
[17] 蒋纯，潘志庚，石教英．PVM系统分析(4)——PVM消息机制．计算机工程与应用，1996，4：69～72
[18] Inmos LTD.. Occam Programming Manual. Englewood Cliffs, New Jersey: Prentice Hall, 1984
[19] Foster, I. Designing and Building Parallel Programs．北京：人民邮电出版社，2002
[20] Sunderam, V.. The PVM Concurrent Computing System: Evolution, Experiences, and Trend. Parallel Computing, 1994, 20:531～545
[21] Bwguelin, A., Dongarra, J.. Recent enhancements to PVM. Int J Supercomputer Applications, 1995, 9(2) : 108～127
[22] 李毅．基于PVM的研究任务迁移，C++对象分布并行及Capability实现：博士学位论文．成都：电子科技大学图书馆，2001
[23] 宋哲，顾宏，石教英．PVM结构分析(2)——PVMD协议和数据管理．计算机工程与应用，1996，4：60～65
[24] 孙家昶，张林波，迟学斌 等．网络并行计算与分布式编程环境．北京：科学出版社，1996
[25] Geist, A., Beguelin, A., Dongarra, J. et al. PVM: Parallel Virtual Machine. Boston: The MIT Press, 1994
[26] Kernighan, B.W., Ritchie,D.M..The C Programming Language．2nd Edition 影印版．北京：清华大学出版社·Prentice Hall，1997
[27] 傅良魁．应用地球物理教程——电法 放射法 地热．北京：地质出版社，1991
[28] 王勖成，邵敏．有限元法基本原理和数值方法．第2版．北京：清华大学出版社，1997
[29] Courant, R., Variational Methods for the Solution of Problems of Equilibrium and Vibration. Bull Am Math Soc., 1943, 49: 1～43
[30] Turner, M., Clough, R., H. Martin et al. Stiffness and Defection Analysis of Complex Structures. Aero Sci., 1956, 23. 805～823
[31] Clough, R.W.. The Finite Element Method in Plane Stress Analysis. Struct. Div., ASCE, Proc, 1960, 2d Conf. Electronic Computation: 345～348
[32] 罗延钟，张桂青．电子计算机在电法勘探中的应用．武汉：武汉地质学院出版社，1987
[33] 陈景良．并行算法引论．北京：石油工业出版社出版，1992
[34] 徐士良．计算机常用算法．北京：清华大学出版社，1989
[35] Hesrenses, M. R., Stiefel, E.. Method of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 1952, 49. 409～436
[36] 章文．物探数据处理网络并行计算环境的设计和实现．安庆师范学院学报(自然科学版)，2002，8(2)：66～68
[37] 章文，李代平，张信一．PVM on Win32平台上的PC集群技术．广东工业大学学报，2003，20(1)：40～43
[38] Microsoft Corporation. 中文Microsoft Windows2000培训教程．卓越，王红．北京：人民邮电出版社，2000
[39] 秦忠国，姜弘道．一种新的并行计算环境：PVM on Win32．计算机工程，1998，24(12)：17～19
[40] 杨华军，苏富德．基于Windows95/WT的PVM并行计算平台．计算机工程，1999，25(2)：24～25
[41] 李代平，罗寿文．CG法分布式并行计算的实现．计算机工程，2001，27(4)：56～57，60
[42] Comen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. et al. Introduction to Algorithms. 2nd Edition 影印版．北京：高等教育出版社·the MIT Press, 2002
[43] Baker M., Buyya R., Cluster Computing: The Commodity Supercomputing, Software～Practice and Experience, 1988, 1(1): 1～4
[44] Flynn, M. J., K.W. Rudd. Parallel Architectures. ACM Computing Surveys, 1996,
Vol.28, No.1 (March): 67～70
[45] Gill, S.. Parallel Programming. The Computer Journal, 1958, 1, April: 2～10
[46] Bathe K J, Wilson E.L.. Numerical Methods in Finite Element Analysis. Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1976
[47] C. T. E Ross. Finite element methods in engineering science. New York: Ellis Horwood Limited, 1990
[48] 史忠植．高级计算机网络．北京：电子工业出版社，2002
[49] 全惠云，高汉平，康立山 等．并行计算机程序设计导论．武汉：武汉大学出版社，1996
[50] 胡维华，潘志庚．微机环境下基于PVM的网络并行程序开发方法．计算机工程与设计，1999，20(2)：57～62
[51] 鞠九滨，王勇．调度PVM任务．计算机学报，1997，20(5)：470～474
[52] 秦忠国，姜弘道．消息传递界面PVM和MPI的现状与发展趋势．计算机研究与发展，1998，35(6)：496～499
[53] 周笑波，汲化，谢立．基于PVM的分布计算的研究．计算机学报，1997，20(6)：551～555
[54] 叶澄清，崔振乾．PVM环境中提高并行计算效率的途径．小型微型计算机系统，1996，17(4)：12～16
[55] 戴光明，戴晓明．基于PVM的微机网络并行计算及其应用．计算机工程与应用，2000，9：154～156
[56] 陶志良，顾宏，石教英．PVM结构分析(1)——配置管理和处理机启动．计算机工程与应用，1996，4：56～59
[57] 陈焰，潘志庚，石教英．PVM结构分析(3)——PVM监护进程与任务消息处理．计算机工程与应用，1996，4：65～69
[58] 周桂林，李三立．网络并行计算环境中的任务派生机制和进程调度策略．计算机研究与发展，1997，34(Suppl)：79～83
[59] 孙安香，宋君强，李晓梅．工作站网络并行计算的性能分析．国防科技大学学报，1997，19(1)：57～60
[60] 莫则尧，李晓梅．工作站网络环境下的并行计算．计算机学报，1997，20(6)：510～517
[2] 李晓梅，莫则尧，胡庆丰 等．可扩展并行算法的设计与分析．北京：国防工业出版社，2000
[3] 沈志宇，缪湘科，胡子昂．并行程序设计．长沙：国防科技大学出版社，1997
[4] 刘晓明．异构机群系统环境下PVM并行程序的编程方法研究：硕士学位论文．广州：暨南大学图书馆，2001
[5] 章文，罗清磊，李璟．机群的可扩展性研究．安庆师范学院学报(自然科学版)，2003，9(1)：107～108
[6] 郑伟民，汤志忠．计算机体系结构．第2版．北京：清华大学出版社．1998
[7] 黄恺，徐志伟(HWANG Kai, XU Zhiwei)．可扩展并行计算技术、结构与编程(Scalable Parallel Computing Technology,Architecture, Programming)．陆鑫达，曾国荪，邓倩妮 等译．北京：机械工业出版社，2000
[8] Rajkumar Buyya．高性能集群计算：结构与系统(第一卷)(High Performance Cluster Computing: Architectures and Systems, Volume 1)．郑伟民，石威，王东升 等译．北京：电子工业出版社，2001
[9] Comer,D. E.. 计算机网络与因特网(Computer Networks and Internets，2nd Edition)．徐良贤，唐英，王勋 等译．北京：机械工业出版社，2000
[10] 邹晖，罗省贤．机群并行系统与网络并行计算环境．物探化探计算技术，2001，23(4)：375～379
[11] Stallings, W. Computer Organization and Architecture: Designing for Performance. 5th Edition影印版．北京：高等教育出版社·Pearson Education, 2001
[12] 纪珊珊．基于PVM的并行计算在PC机群上的实现：硕士学位论文．大连：大连理工大学图书馆，2000
[13] Rajkumar Buyya，高性能集群计算：编程与应用(第二卷)(High Performance Cluster Computing: Programming and Applications, Volume 2)．郑伟民，王东升，
石威 等译．北京：电子工业出版社，2001
[14] 章文，李代平，罗清磊 等．机群并行系统的设计．现代计算机，2003，157：16～18
[15] Tanenbaum, A.S.. Computer Networks. 3rd Edition影印版．北京：清华大学出版社·Prentice Hall，1996
[16] 缪湘科．网络并行计算中的负载平衡．小型微型计算机系统，1995，Vol．16No．9：32～36
[17] 蒋纯，潘志庚，石教英．PVM系统分析(4)——PVM消息机制．计算机工程与应用，1996，4：69～72
[18] Inmos LTD.. Occam Programming Manual. Englewood Cliffs, New Jersey: Prentice Hall, 1984
[19] Foster, I. Designing and Building Parallel Programs．北京：人民邮电出版社，2002
[20] Sunderam, V.. The PVM Concurrent Computing System: Evolution, Experiences, and Trend. Parallel Computing, 1994, 20:531～545
[21] Bwguelin, A., Dongarra, J.. Recent enhancements to PVM. Int J Supercomputer Applications, 1995, 9(2) : 108～127
[22] 李毅．基于PVM的研究任务迁移，C++对象分布并行及Capability实现：博士学位论文．成都：电子科技大学图书馆，2001
[23] 宋哲，顾宏，石教英．PVM结构分析(2)——PVMD协议和数据管理．计算机工程与应用，1996，4：60～65
[24] 孙家昶，张林波，迟学斌 等．网络并行计算与分布式编程环境．北京：科学出版社，1996
[25] Geist, A., Beguelin, A., Dongarra, J. et al. PVM: Parallel Virtual Machine. Boston: The MIT Press, 1994
[26] Kernighan, B.W., Ritchie,D.M..The C Programming Language．2nd Edition 影印版．北京：清华大学出版社·Prentice Hall，1997
[27] 傅良魁．应用地球物理教程——电法 放射法 地热．北京：地质出版社，1991
[28] 王勖成，邵敏．有限元法基本原理和数值方法．第2版．北京：清华大学出版社，1997
[29] Courant, R., Variational Methods for the Solution of Problems of Equilibrium and Vibration. Bull Am Math Soc., 1943, 49: 1～43
[30] Turner, M., Clough, R., H. Martin et al. Stiffness and Defection Analysis of Complex Structures. Aero Sci., 1956, 23. 805～823
[31] Clough, R.W.. The Finite Element Method in Plane Stress Analysis. Struct. Div., ASCE, Proc, 1960, 2d Conf. Electronic Computation: 345～348
[32] 罗延钟，张桂青．电子计算机在电法勘探中的应用．武汉：武汉地质学院出版社，1987
[33] 陈景良．并行算法引论．北京：石油工业出版社出版，1992
[34] 徐士良．计算机常用算法．北京：清华大学出版社，1989
[35] Hesrenses, M. R., Stiefel, E.. Method of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 1952, 49. 409～436
[36] 章文．物探数据处理网络并行计算环境的设计和实现．安庆师范学院学报(自然科学版)，2002，8(2)：66～68
[37] 章文，李代平，张信一．PVM on Win32平台上的PC集群技术．广东工业大学学报，2003，20(1)：40～43
[38] Microsoft Corporation. 中文Microsoft Windows2000培训教程．卓越，王红．北京：人民邮电出版社，2000
[39] 秦忠国，姜弘道．一种新的并行计算环境：PVM on Win32．计算机工程，1998，24(12)：17～19
[40] 杨华军，苏富德．基于Windows95/WT的PVM并行计算平台．计算机工程，1999，25(2)：24～25
[41] 李代平，罗寿文．CG法分布式并行计算的实现．计算机工程，2001，27(4)：56～57，60
[42] Comen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. et al. Introduction to Algorithms. 2nd Edition 影印版．北京：高等教育出版社·the MIT Press, 2002
[43] Baker M., Buyya R., Cluster Computing: The Commodity Supercomputing, Software～Practice and Experience, 1988, 1(1): 1～4
[44] Flynn, M. J., K.W. Rudd. Parallel Architectures. ACM Computing Surveys, 1996,
Vol.28, No.1 (March): 67～70
[45] Gill, S.. Parallel Programming. The Computer Journal, 1958, 1, April: 2～10
[46] Bathe K J, Wilson E.L.. Numerical Methods in Finite Element Analysis. Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1976
[47] C. T. E Ross. Finite element methods in engineering science. New York: Ellis Horwood Limited, 1990
[48] 史忠植．高级计算机网络．北京：电子工业出版社，2002
[49] 全惠云，高汉平，康立山 等．并行计算机程序设计导论．武汉：武汉大学出版社，1996
[50] 胡维华，潘志庚．微机环境下基于PVM的网络并行程序开发方法．计算机工程与设计，1999，20(2)：57～62
[51] 鞠九滨，王勇．调度PVM任务．计算机学报，1997，20(5)：470～474
[52] 秦忠国，姜弘道．消息传递界面PVM和MPI的现状与发展趋势．计算机研究与发展，1998，35(6)：496～499
[53] 周笑波，汲化，谢立．基于PVM的分布计算的研究．计算机学报，1997，20(6)：551～555
[54] 叶澄清，崔振乾．PVM环境中提高并行计算效率的途径．小型微型计算机系统，1996，17(4)：12～16
[55] 戴光明，戴晓明．基于PVM的微机网络并行计算及其应用．计算机工程与应用，2000，9：154～156
[56] 陶志良，顾宏，石教英．PVM结构分析(1)——配置管理和处理机启动．计算机工程与应用，1996，4：56～59
[57] 陈焰，潘志庚，石教英．PVM结构分析(3)——PVM监护进程与任务消息处理．计算机工程与应用，1996，4：65～69
[58] 周桂林，李三立．网络并行计算环境中的任务派生机制和进程调度策略．计算机研究与发展，1997，34(Suppl)：79～83
[59] 孙安香，宋君强，李晓梅．工作站网络并行计算的性能分析．国防科技大学学报，1997，19(1)：57～60
[60] 莫则尧，李晓梅．工作站网络环境下的并行计算．计算机学报，1997，20(6)：510～517