摘要
网络技术的迅速发展为网络并行计算提供了很好的条件,基于局域网的机群并行计算和基于Internet的网格计算是其典型代表。机群并行计算以其易可扩展性、高性价比等优点成为当今高性能计算(High Performance Computing,HPC)领域的一个研究热点。在机群并行计算中,任务调度和动态负载平衡是进行网络并行计算的关键。在并行程序设计中,如果能准确衡量和预测结点负载,将会有效提高并行程序的执行效率,对其进行研究具有重要的理论和应用价值。
论文首先介绍了并行计算技术和MPI(Message Passing Interface,消息传递接口)并行程序设计的相关内容,并对并行程序设计中出现的负载问题进行了研究。
其次分析了负载的特性,为负载预测提供了依据。结合MPI并行编程标准在Windows系统上建立基于误差反向传播(error Back Proragation,BP)算法预测的负载平衡系统,给出了系统的规划方案和设计架构。采用自适应、主动的负载收集策略,建立负载收集模块,及时、准确地收集结点负载信息,为负载预测提供信息基础。采用BP神经网络预测结点的负载变化情况,并建立BP神经网络预测模型。
最后在局域网内构建了基于MPI的并行计算平台,对系统模型进行了测试验证。实验结果表明,与MPI直接分配方式相比,基于BP算法负载预测设计的调度系统的性能有了一定的提高。
The rapid development of network technology provides the proper conditions for the network parallel computing,and the typical representative is the Parallel computing based on LAN cluster and the grid computing based on the Internet.Parallel computing cluster for the excellent scalability and the high performance-price ratio has become a hot research topic in the High Performance Computing field at present.The task scheduling and dynamic load balancing are the key to network parallel computing.We can improve the efficiency of parallel program effectively if we can measure and predict node's load accurately in the parallel programming,and conducts the research to have the important theory and the application value.
In this paper,the content of parallel computing technology and the MPI(Message Passing Interface) parallel programming are introduced firstly,and the load balancing problem of parallel programming is researched.
Secondly,the load characteristics are analyzed,which are the basis of load prediction.Establishing a load balancing system based on BP algorithm combined with the MPI parallel programming standard on the Windows system,and putting forward the plan and framework.Building the load collection module take advantage of the self-adaptive and initiative strategy of load collection,which can collect the node load information accurately and promptly,and providing the sources of data for the load prediction.Predicting the node's load information changes using the BP neural network, and establishing the prediction model based on BP neural network.
Finally,building a parallel computing platform based on MPI in LAN,and tesing the system model.Result shows that the load scheduling system based on the BP algorithm prediction improves performance certainly compared with the way of MPI direct allocation.
引文
[1]R.Buyya.High Performance Cluster Computing Programming and Application[M].Prentice-Hall,Inc.,1999:41-45
[2]C.Xavier,S.Iyengar.Introduction to Parallel Algorithms[M].John Wiley&Sons.Inc,2004
[3]陈国良,安虹,陈崚,郑启龙,单久龙.并行算法实践[M].北京:高等教育出版社,2004:24-25
[4]Charmpis D,Papadrakakis M,Improving the computation efficiency in finite element analysis of shells with uncertain properties[J].Comp.Methods Appl.Mech.Eng.2005,194:1447-1478
[5]Fournier L,Lanteri S.Multiplicative and additive parallel multigrid algorithms for the acceleration of compressible flow computations on unstructured meshes[J].Applied Numerical Mathematics,2001,36:401-426
[6]黄铠,徐志伟著,陆鑫达,曾国荪,邓倩妮等译.可扩展并行计算—技术、结构与编程[M].北京:机械工业出版社,2000
[7]都志辉.高性能计算并行编程技术—MPI并行程序设计[M].北京:清华大学出版社,2001
[8]王丽,李敬有,王岩.面向工作站群机系统的网络负载预测[J].齐齐哈尔大学学报,2000,16(3):63-65
[9]Rich Wolski.Dynamically forecasting network performance using the network weather service[J].Cluster Computing,1998,1(1)
[10]Martin Quinson.Dynamic Performance Forecasting for Network-Enabled Services in a Metacomputing Environment[C].PMEO-PDS'02,April,2002
[11]P.Dinda,David R.O'Hallaron.The statistical properties of host load[M].CMU-CS-TR-98-175
[12]P.Dinda,David R.O'Hallaron.An Evaluation of Linear Models for Host Load Prediction[M].CMU-CS-98-148
[13]P.Dinda,David R.O'Hallaron.An Extensible Toolkit for Resource Prediction In Distributed Systems[M].CMU-CS-99-138
[14]Rich Wolski,Neil Spring,Jim Hayes.Predicting the CPU availability of time-shared Unix systems[C].HPDC,August,1999:35-51
[15]S.Vazhkudai,Jennifer M.Schopf,Ian Foster.Predicting the Performance of Wide Area Data Transfers[C].IPDPS,April,2002:15-19
[16]Lingyun Yang,Ian Foster,Jennifer M.Schopf.Homeostatic and Tendency-based CPU Load Predictions[C].IPDPS,April,2003:22-26
[17]李庆华,郭志鑫.一种面向工作站网络的系统负载预测方法[J].华中科技大学学报(自然科学版),2002,6(30)
[18]张建军,蒋廷耀,郭志鑫.PVM中动态负载平衡的设计和实现[J].计算机工程,2005,31(7)
[19]许建峰,朱晴波,胡宁等.分布式实时系统中的预测调度算法[J].软件学报,2000;11(1)
[20]Rich Wolski et al.Predicting the CPU availability of time-shared Unix systems[C].In:HPDC'99
[21]V.Kumar,A.Grama,A.Gupta,G.Karypis.Introduction to Parallel Computing[M],Addison-Wesley,2003:233-236
[22]陈国良.并行算法的设计与分析(修订版)[M].北京:高等教育出版社,2002
[23]Message Passing Interface Forum.http://www.mpi-forum.org/
[24]杨爱民,陈一鸣.MPI并行编程环境及程序设计[J].河北理工学院学报,2005,27(3):41-43
[25]许宏,蔡瑞英.PC机群技术与并行计算[J].南京化工大学学报,2001,23(5):100-112
[26]唐丹,金海,张永坤,机群动态负载平衡系统的性能评价[J].计算机学报,2004,27(6):803-811
[27]P.Dinda,D.R.O'Halloran.The statistical properties of host load[C].Fourth Workshop on Languages,Compilers,and Run-Time Systems for Scalable Computers,1998:1-23
[28]刘振英,方滨兴,胡铭曾等.一个有效的动态负载平衡方法[J].软件学报,2001,12(4):563-569
[29]何炎祥等.对三种典型分布式任务分配算法的分析[J].小型微型机算机系统,1997,18(11)
[30]Keren A,Barak A.Adaptive Placement of Parallel Java Agents in a Scalable Computing Cluster[C].Proc.of the Workshop on Java for High Performance NetWork Computing,Standford University,Palo ALto,CA,USA.1998
[31]Jie Wu著,高传善等译.分布式系统设计[M].北京:机械工业出版社,2001
[32]陈华平,计永昶,陈国良.分布式动态负载平衡调度的一个通用模型[J].软件学报,1998,9(1):25-29
[33]Zaki,Wei Li,Parthasarathy S.Customized Dynamic Load Balancing for a Network of workstations[J].Journal of Parallel and Distributed Computing,1997,43(2):156-162
[34]周佳祥,郑纬民,杨文广.一种基于进程迁移的自适应双阈值负载平衡系统[J].清华大学学报(自然科学版),2000,40(3):121-125
[35]郭志鑫.并行任务调度系统LDPVM的设计与实现[D].华中科技大学,2002
[36]尚月强.微机网络环境下提高PVM并行程序性能的策略[J].计算机工程与设计,2007,28(13):3101-3102
[37]Zhou S.A trace driven simulation study of dynamic load balancing[C].IEEE Transactions of Software Engineering,1988,14(9):1327-1341
[38]Bonomi F.,A.Kumar.Adaptive optimal load balancing in a non-homegeneous multi-server system with a central task scheduler[C].IEEE Transactions on Computers,1989,38(8):1232-1250
[39]马艳琨,马胜甫,田俊峰等.一种用于PC存储机群的动态负载平衡策略[J].计算机工程与应用,2004(29):119-121
[40]Alex Vrenios著,马朝晖等译.Linux机群体系结构[M].北京:机械工业出版社,2003:34-47
[41]王鹏.基于Linux机群的并行计算[J].喀什师范学院学报.2005年5月,26(3):73-75
[42]韩力群著.人工神经网络教程[M].北京:北京邮电大学出版社,2006
[43]V.Saletore.A distributed and adaptive dynamic load balancing scheme for parallel processing for medium grain tasks[C].In:Proceedings of the Fifth Distributed Memory Computing Conference.Portland,Oregon,1990.Portland:IEEE Comput.Soc.Press,1990:994-999
[44]袁曾任.人工神经元网络及应用[M].北京:清华大学出版社第一版,2000:118-131
[45]刘红霞,李东,胡铭曾.工作站网络中负载参数的一种收集方法[J].小型微型计算机系统,2000,21(3):261-263
[46]王鼎兴,郑纬民,沈美明.并行机群的若干关键技术[J].清华大学学报(自然科学版),1998,38(s1):15-22
[47]Official website of MPICH2.http://www.mcs.anl.gov/research/projects/mpich2/index.php
[48]汪梅婷.基于MPI的并行计算中矩阵传输协议及负载平衡算法的研究与设计[D].燕山大学,2006
[49]David E.Rumelhart,Bernard Widrow,Michael A.Lehr.The basic ideas in neural networks[J].Communications of the ACM,1994,37(3):87-92
