用户名: 密码: 验证码:
多项式——PCG并行算法研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
计算机网络的高速发展和微机处理芯片性能的不断提高,为并行计算提供了一个很好的网络平台。同时由于商业化的硬件和软件的不断发展,也为计算机网络提供了高性价比、高可用性的计算。这种高性能计算系统一般被称为机群计算系统。近年来,机群计算系统已经成为学术界、商业界和其它行业界研究的热点。
     PVM(Parallel Virtual Machine)并行虚拟机,是能使一群松散连接的计算机用来作为一台并行计算资源的软件系统。这就使大规模计算问题可以通过使用众多计算机聚集来的计算能力和内存来降低低成本地解决,PVM可移植性好、低性价比、编程环境的兼容性和运行平台的广泛性,使PVM拥有着大量的用户,现已成为世界上分布式计算事实上的标准。
     本文是将并行机群计算系统应用到解决电法勘探中,在使用有限元方法(FEM)时所产生的大型线性方程组求解问题上。有限元方法是工程学科的重要工具,被证明为在许多科学和工程领域中连续物理系统模拟的一种普遍方法,但缺点是随着工程结构分析问题越来越复杂,在结构分析中,为保证数值解的精度,在使用有限元方法离散处理时,往往要用大量的高阶单元将结构剖分得很密,这时相应的代数方程组的系数矩阵的阶数很高,即使用目前速度最快的串行机来进行求解,费时仍然太多且问题的规模受到内存容量的限制。FEM处理结构分析问题的最基本思想是需要对域进行离散化(一个网格或者模型),这和机群分而治之的思想相似。因此,有限元节点代码可以被并行化、并能在基于不同的PVM机群结点上运行。可用C++编写程序,通过调用PVM库函数提供对并行虚拟机的访问。有限元法产生的线性方程组使用多项式预处理共轭梯度(P—PCG)算法求解,多项式预处理共轭梯度(P—PCG)法与有限元法联系的十分自然,因为两者都是采用相似的最小化过程。多项式预处理共轭梯度算法的高度向量化,且不需要构造全局矩阵,它在大规模并行结构中能被有效地实现。
The improvement of the function of microcomputer processing chip and the high-speed development of computer network provided a good network base for parallel computation. Meanwhile, with the development of commercial hardware and software, computer network was provided with computation of high price ratio and high usability. This is called parallel computers system. It has been a hot spot of studies in academic, commercial and other fields.
    Parallel Virtual Machine (PVM) is a kind of software system combining a group of loose connected computers into one to do parallel computation. With this kind of computing power and internal storage, many computation problems can be solved with lower cost. PVM has owned large quantity of users and has become a standard of distributed computing of the world because of its transplantability, low price ration, compatability and wide-range of operation.
    This article tried to apply parallel computing system to solving electrical prospecting and large-scale linear equations caused by using Finite Element Method. Finite Element Method is an important means of engineering subject and has been proved to be a common method in many subjects. However, disadvantages still remained. During the structural analysis, large amount of high-order units were used in order to ensure the precision of arithmetic solution when using Finite Element Method to do discrete processing. This will cause high order of coefficient matrix of corresponding equation group. The basic point of analyzing by Finite Element Method processing structure is to discretize the field (lattice or model). This is similar to that of parallel computing system. Thus, nodal code of Finite Element Method can be parallelized and operated in the connecting point of different groups of PVM. Programming can be done with C++, PVM can be accessed through calling functions in PVM base. Linear equations caused by F
    inite Element Method can be solved by Multinomial Preprocessing Conjugate
    
    
    Gradient Method. There is natural link between these two, both of them use similar minimizing process. The high-vectorization of Multinomial Preprocessing Conjugate Gradient Method makes it be effectively realized in large-scale parallel structure.
引文
[1] Wilkinson,B.,Allen,M..并行程序设计.陆鑫达 等译.北京:机械工业出版社,2001
    [2] 李晓梅,莫则尧,胡庆丰 等.可扩展并行算法的设计与分析.北京:国防工业出版社,2000
    [3] 沈志宇,缪湘科,胡子昂.并行程序设计.长沙:国防科技大学出版社,1997
    [4] 章文,罗清磊,李璟.机群的可扩展性研究.安庆师范学院学报(自然科学版),2003,9(1):107~108
    [5] 黄恺,徐志伟(HWANG Kai,XU Zhiwei).可扩展并行计算技术、结构与编程(Scalable Parallel Computing Technology,Architecture,Programming).陆鑫达,曾国荪,邓倩妮 等译.北京:机械工业出版社,2000
    [6] 郑伟民,汤志忠.计算机体系结构.第2版.北京:清华大学出版社.1998
    [7] Rajkumar Buyya.高性能集群计算:结构与系统(第一卷)(High Performance Cluster Computing:Architectures and Systems,Volume 1).郑伟民,石威,王东升等译.北京:电子工业出版社,2001
    [8] Comer,D.E..计算机网络与因特网(Computer Networks and Internets,2nd Edition).徐良贤,唐英,王勋 等译.北京:机械工业出版社,2000
    [9] 邹晖,罗省贤.机群并行系统与网络并行计算环境.物探化探计算技术,2001,23(4):375~379
    [10] 章文,李代平,罗清磊 等.机群并行系统的设计.现代计算机,2003,157:16~18
    [11] 李继民,马力,王凤先.PC机群系统的关键技术.河北大学学报,2002,3:57~58
    [12] 蒋纯,潘志庚,石教英.PVM系统分析(4)——PVM消息机制.计算机工程与应用,1996,4:69~72
    [13] Inmos LTD.. Occam Programming Manual. Englewood Cliffs, New Jersey: Prentice Hall, 1984
    [14] Foster, I.. Designing and Building Parallel Programs. 北京:人民邮电出版社,2002
    [15] Sunderam, V.. The PVM Concurrent Computing System: Evolution, Experiences, and Trend. Parallel Computing, 1994, 20:531~545
    [16] Bwguelin, A., Dongarra, J.. Recent enhancements to PVM. Int J Supercomputer
    
    Applications, 1995, 9(2):108~127
    [17] 李毅.基于PVM的研究任务迁移,C++对象分布并行及Capability实现:博士学位论文.成都:电子科技大学图书馆,2001
    [18] 宋哲,顾宏,石教英.PVM结构分析(2)——PVMD协议和数据管理.计算机工程与应用,1996,4:60~65
    [19] 傅良魁.应用地球物理教程——电法 放射法 地热.北京:地质出版社,1991
    [20] 王勖成,邵敏.有限元法基本原理和数值方法.第2版.北京:清华大学出版社,1997
    [21] Courant, R., Variational Methods for the Solution of Problems of Equilibrium and Vibration. Bull Am Math Soc., 1943, 49:1~43
    [22] Turner, M., Clough, R., H. Martin et al. Stiffness and Defection Analysis of Complex Structures. Aero Sci., 1956, 23:805~823
    [23] Clough, R.W.. The Finite Element Method in Plane Stress Analysis. Struct. Div., ASCE, Proc, 1960, 2d Conf. Electronic Computation: 345~348
    [24] 973简报2 , http://lsec.cc.ac.cn/~973/Internal/973jb-2.htm
    [25] 陈其安,共轭梯度法,重庆大学硕士学位论文。
    [26] 周树荃等,有限元结构分析并行计算,科学出版社:北京,1997。
    [27] 施妙根等,科学和工程计算基础,清华大学出版社:北京,2002。
    [28] 程云鹏主编,矩阵论(第二版),西北工业大学出版社:西安,2003。
    [29] Microsoft Corporation.中文Microsoft Windows 2000培训教程.卓越,王红.北京:人民邮电出版社,2000
    [30] 秦忠国,姜弘道.一种新的并行计算环境:PVM on Win32.计算机工程,1998,24(12):17~19
    [31] 杨华军,苏富德.基于Windows 95/NT的PVM并行计算平台.计算机工程,1999,25(2):24~25
    [32] 刘晓明.异构机群系统环境下PVM并行程序的编程方法研究:硕士学位论文.广州:暨南大学图书馆,2001
    [33] Stallings,W.Computer Organization and Architecture:Designing for Performance.5th Edition影印版.北京:高等教育出版社·Pearson Education,2001
    [34] 纪珊珊.基于PVM的并行计算在PC机群上的实现:硕士学位论文.大连:大
    
    连理工大学图书馆,2000
    [35] Rajkumar Buyya.高性能集群计算:编程与应用(第二卷)(High Performance Cluster Computing:Programming and Applications,Volume 2).郑伟民,王东升,石威 等译.北京:电子工业出版社,2001
    [36] Tanenbaum,A.S..Computer Networks.3rd Edition影印版.北京:清华大学出版社·Prentice Hall,1996
    [37] 孙家昶,张林波,迟学斌 等.网络并行计算与分布式编程环境.北京:科学出版社,1996
    [38] Geist, A., Beguelin, A., Dongarra, J. et al. PVM: Parallel Virtual Machine. Boston:The MIT Press, 1994
    [39] Kemighan,B.W., Ritchie,D.M..The C Programming Language.2nd Edition影印版.北京:清华大学出版社·Prentice Hall,1997
    [40] 罗延钟,张桂青.电子计算机在电法勘探中的应用.武汉:武汉地质学院出版社,1987
    [41] 章文.物探数据处理网络并行计算环境的设计和实现.安庆师范学院学报(自然科学版),2002,8(2):66~68
    [42] 章文,李代平,张信一.PVM on Win32平台上的PC集群技术.广东工业大学学报,2003,20(1):40~43
    [43] 李代平,罗寿文.CG法分布式并行计算的实现.计算机工程,2001,27(4):56~57,60
    [44] Comen, Thomas H., Leiserson, Charles E., Rivest, Ronald L. et al. Introduction to Algorithms. 2nd Edition 影印版.北京:高等教育出版社·the MIT Press, 2002
    [45] Baker M., Buyya R., Cluster Computing: The Commodity Supercomputing, Software-Practice and Experience, 1988, 1(1): 1~4
    [46] Flynn, M.J., K.W.Rudd. Parallel Architectures. ACM Computing Surveys, 1996, Vol.28, No.1 (March): 67~70
    [47] Gill, S.. Parallel Programming. The Computer Journal, 1958, 1, April: 2~10
    [48] Bathe K J, Wilson E.L.. Numerical Methods in Finite Element Analysis. Englewood Cliffs, N.J.: Prentice-Hall, Inc., 1976
    [49] C. T. E Ross. Finite element methods in engineering science. New York: Ellis Horwood
    
    Limited, 1990
    [50] 史忠植.高级计算机网络.北京:电子工业出版社,2002
    [51] 全惠云,高汉平,康立山等.并行计算机程序设计导论.武汉:武汉大学出版社,1996
    [52] 胡维华,潘志庚.微机环境下基于PVM的网络并行程序开发方法.计算机工程与设计,1999,20(2):57~62
    [53] 鞠九滨,王勇.调度PVM任务.计算机学报,1997,20(5):470~474
    [54] 秦忠国,姜弘道.消息传递界面PVM和MPI的现状与发展趋势.计算机研究与发展,1998,35(6):496~499
    [55] 周笑波,汲化,谢立.基于PVM的分布计算的研究.计算机学报,1997,20(6):551~555
    [56] 叶澄清,崔振乾.PVM环境中提高并行计算效率的途径.小型微型计算机系统,1996,17(4):12~16
    [57] 戴光明,戴晓明.基于PVM的微机网络并行计算及其应用.计算机工程与应用,2000,9:154~156
    [58] 陶志良,顾宏,石教英.PVM结构分析(1)——配置管理和处理机启动.计算机工程与应用,1996,4:56~59
    [59] 陈焰,潘志庚,石教英.PVM结构分析(3)——PVM监护进程与任务消息处理.计算机工程与应用,1996,4:65~69
    [60] 章文.机群计算在基于有限元电法勘探中的应用:硕士学位论文.广州,广东工业大学图书馆,2003,5
    [61] 周桂林,李三立.网络并行计算环境中的任务派生机制和进程调度策略.计算机研究与发展,1997,34(Suppl):79~83
    [62] 孙安香,宋君强,李晓梅.工作站网络并行计算的性能分析.国防科技大学学报,1997,19(1):57~60
    [63] 莫则尧,李晓梅.工作站网络环境下的并行计算.计算机学报,1997,20(6):510~517
    [64] 刘红.有限元基本概念和原理.计算机世界日报,2001,4,14
    [65] 吴维刚,董小社,何戈.基于机群系统的PVM并行编程技术研究.计算机应用研究,2003,2:21~23
    
    
    [66] 乐志华,程建钢,姚振汉.网络机群下多项式预处理EBE-PCG并行算法设计与实现.工程力学,2002,10:150~154
    [67] 王鼎兴,郑纬民,沈美明.并行机群的若干关键技术.清华大学学报(自然科学版),1998,38(S1):15~22
    [68] 李跃新,邓芳,秦莉.PVM并行计算(处理)的基础方法.湖北大学成人教育学院学报,2003,2:71~74
    [69] 耿新民.PVM——基于网络的并行计算系统.上海电力学院学报,1997,3:46~50
    [70] 陈国良,章锋,章隆兵等.并行计算机体系结构.北京:高等教育出版社,2002

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700