（计算机应用技术专业论文）基于mpich的并行计算系统负载平衡技术的研究.pdf

基t - m p i c h 的并行计算系统负载平衡技术的研究 摘要 随着大型复杂计算需求的扩大，人们把高性能计算更多的应用于数据挖掘、图像处理 业务、基因测序对比处理等数据处理领域。科学计算规模的迅速膨胀，传统的串行计算已 不能满足需求，从而提出了并行计算的概念。 并行计算是相对于串行计算来说的，它将进程相对独立的分配在不同的节点上，由各 自独立的操作系统调度，享有独立的c p u 和内存资源，进程间通过消息传递相互交换信息。 但是，除了近年来逐步完善并走向实用化的数据流计算机之外，5 0 年来计算机系统结构虽 取得重大进展，但并没有发生革命性的变化，现在实用化的计算机是以冯诺依曼机器为原 型，在此基础上加入并提高并行处理实现的手段和并行处理的能力。 m p i 是1 9 9 4 年5 月宣布的一种消息传递接口，为消息传递程序提供的标准程序库，m p i 以独立的语言形式来定义这个接口库，并提供了与f o r t r a n 和c 语言的绑定，是目前高效率 的超大规模并行计算最可信赖的并行计算平台。因此，本文从研究任务分配、负载平衡出 发，改进了m p i c h 任务分配上的缺点，构建了一个基于m p i c h 的负载平衡模型。模型使用 相对处理速度的概念，把每个节点的处理能力进行量化，调度节点根据每台节点处理能力 的权重值来分配任务，以达到整个系统的负载平衡。 为了充分利用i n t e r n e t 上广泛分布的空闲资源，目前已有多个分布式计算项目， 如：s e t i h o m e ，g i m p s 等等，这些项目己经证实了这种计算模型的可行性。但这些系统的 缺陷是：资源高度不稳定、用户信任度低、通信带宽有限、延迟大。为了弥补并行计算机 系统这个缺陷，负载均衡技术得到了人们的关注并迅速发展。 本文对变换关键路径算法进行改进，提出一种基于有向非循环图的任务调度算法，先 从理论上分析了调度思想的差异和调度结果的不同，然后借助并行计算环境对该算法与修 改关键路径算法作了比较与分析。 关键词：并行计算；m p i ；负载平衡；任务调度 基于m p l c h 的并行计算系统负载平衡技术的研究 a b s t r a c t a c c o r d i n gt ot h ee x p a n s i o no fs u p e rc o m p u t i n gr e q u i r e m e n t s ，h i 曲p e r f o r m a n c ec o m p u t i n g h a sh e l p e dp e o p l ei nd a t ap r o c e s s i n ga r e a ss u c ha s d a t am i m n ga p p l i c a t i o n s ，i m a g ep r o c e s s i n g b u s i n e s s ，g e n es e q u e n c i n gc o m p a r i n g h o w e v e r ，c o n s i d e r i n gt h er a p i de x p a n s i o no ft h es c i e n t i f i c c o m p u t i n gs c a l e ，t h et r a d i t i o n a ls e r i a lc a l c u l a t i o nh a sb e e nu n a b l et om e e tt h er e q u i r e m e n t s ，t h u s t h ec o n c e p to fp a r a l l e lc o m p u t i n gh a sb e e nc a r r i e do u t p a r a l l e lc o m p u t i n gi si nc o n t r a s tt ot h es e r i a lc a l c u l a t i o n ，i td i s t r i b u t e st h ep r o c e s s e st o s e v e r a li n d e p e n d e n tn o d e s ，w h i c ha r es c h e d u l e db yi n d e p e n d e n to p e r a t i n gs y s t e m ，a n dh a v e i n d e p e n d e n tc p ua n dm e m o r yr e s o u r c e s ；t h ee x c h a n g e so fi n f o r m a t i o nb e t w e e nn o d e sa r e t h r o u g hm e s s a g et r a n s m i s s i o n t h e r ea r es o m ei m p o r t a n ti m p r o v e m e n t so nc o m p u t e rs y s t e m a r c h i t e c t u r ei nt h er e c e n t5 0y e a r sa l t h o u g ht h e r ew a sn or e v o l u t i o n a r yc h a n g e se x c e p tt h ed a t a f l o wc o m p u t e rw h i c hg r a d u a li m p r o v e m e n tt o w a r dp r a c t i c a la p p l i c a t i o n t h ec o m p u t e r sh a v e b e e np u ti n t oa p p l i c a t i o n sa r ea l lb a s e do nv o nn e u m a n np r o t o t y p e ，a n di m p r o v et h em e a n sa n d c a p a b i l i t i e so fp a r a l l e lp r o c e s s i n go nt h i sb a s i s m p ii sa 虹n do fm e s s a g ep a s s i n gi n t e r f a c ew h i c hi sp u b l i s h e do nm a 弘19 9 4 ，i tp r o v i d e st h e s t a n d a r dl i b r a r yf o rm e s s a g ep a s s i n gp r o c e d u r e m p id e f i n e st h ei n t e r f a c el i b r a r yb yl a n g u a g e i n d e p e n d e n tf o r m , a n dp r o v i d e st h eb i n d i n gw i mca n df o r t r a nl a n g u a g e i ti st h em o s t r e l i a b l ep l a t f o r mf o rh i g he f f i c i e n c ya n du l t r a - l a r g e - s c a l ep a r a l l e lc o m p u t i n g t h i sp a p e rf r o m r e s e a r c ht a s ka l l o c a t i o n , l o a db a l a n c i n gs t a r t i n g ，i m p r o v e di nt h em p i c ht a s ka l l o c a t i o n s h o r t c o m i n g ，a n dc o n s t r u c t e do n eb a s e do nt h em p i c hl o a db a l a n c i n gm o d e l m o d e lu s i n gt h e c o n c e p to fr e l a t i v ep r o c e s s i n gs p e e d ，t h eh a n d l o c a l h o s tc a p a c i t yo fe a c hn o d ew e r eq u a n t i f i e d ， s c h e d u l i n gn o d e sa l l o c a t et a s ka c c o r d i n g t ot h ec a p a c i t yo fe a c h n o d ew e i g h t si no r d e rt oa c h i e v e t h ei o a db a l a n c i n gs y s t e ma saw h o l e i no r d e rt ou s et h ee x t e n s i v e l yd i s t r i b u t e di d l ec a l c u l a t i o nr e s o u r c e so nt h ei n t e r a c t ，t h e r ea r e a l r e a d yan u m b e ro fd i s t r i b u t e dc o m p u t i n gp r o j c o t sh a v eb e e ns e t u p ，f o re x a m p l e ：s e t i h o m e ， g i m p sa n ds oo n t h e s ep r o j e c t sh a v ec o n f i r m e dt h ef e a s i b i l i t yo fs u c hc a l c u l a t i o nm o d e l t h e s er e s o u r c e sa r eh i g l l l yu n s t a b l ea n dc a n n o tb et r u s t e db yu s e r s ，b a n d w i d t hi sl i m i t e da n df u l l o ft r e m e n d o u sd e l a y i no r d e rt oc o m p e n s a t ef o rt h ed e f i c i e n c i e so fp a r a l l e lc o m p u t e rs y s t e m s ， l o a db a l a n c i n gt e c h n o l o g yi st h ec o n c e r no fp e o p l ea n d r a p i d l yd e v e l o p e do f u 基于m p i c h 的并行计算系统负载平衡技术的研究 i nt h i sp a p e r , t h ec r i t i c a la l g o r i t h mo fm c pi si m p r o v e d ，a n da d v a n c e daa l g o r i t h mo ft p g s t a r t 州t ht h ei d e ai nt h e o r y ，a na n a l y s i so fd i f f e r e n c e si ns c h e d u l o c a l h o s ta n d d i s p a t c h i n go ft h e d i f f e r e n tr e s u l t s ，t h e ni k s et h ea l g o r i t h mf o rp a r a l l e lc o m p u t i n ge n v i r o n m e n t sa n dm o d i f yt h ek e y p a t ha l g o r i t h ma n da n a l y s i sw e r ec o m p a r e d k e y w o r d s ：p a r a l l e lc o m p u t i n g ；m p i ；l o a db a l a n c i n g ；t a s ks c h e d u l i n g 基于m p i c h 的并行计算系统负载平衡技术的研究 曲阜! j 币范大学博士硕士学位论文原创性说明 ( 在口划“) 本人郑重声明：此处所提交的博士口硕士彤论文基于m p l c h 的并 行计算系统负载平衡技术的研究，是本人在导师指导下，在曲阜师范大学 攻读博士口硕士日学位期间独立进行研究工作所取得的成果。论文中除注 明部分外不包含他人已经发表或撰写的研究成果。对本文的研究工作做出重 要贡献的个人和集体，均己在文中已明确的方式注明。本声明的算法律结果 将完全由本人承担。 作者签名：王廷羚 日期：刎 年占月3 o 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“ ) 基于m p i c h 的并行计算系统负载平衡技术的研究系本人在曲阜师范 大学攻读博士口硕士日学位期间，在导师指导下完成的博士口硕士囱学 位论文。本论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以 其他单位的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文 的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论 文被查阅和借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保 存论文，可以公开发表论文的全部或部分内容。 作者签名：王挺玲日期：力明年名月方日 刷磁各蟊如幺、 醐：岬，f 了 基于m p i c h 的并行计算系统负载平衡技术的研究 第一章绪论 随着计算技术和计算方法的飞速发展，计算学科各分支逐渐形成。并行计算机是促进 经济、科技发展，社会进步和国防安全的重要工具，并行计算技术水平是一个国家经济和 科技实力的综合体现，已成为世界各国竞相争夺的战略制高点。随着大规模集成电路技术 的不断提高，以多c p u 为基础的高性能并行计算机得到了迅速发展，其高端系统正向百万 亿次、千万亿次迈进。近十年来，我国对高性能并行计算的开发研究也给予了很高的重视， 取得了很大进步，研制出了具有相当水平的并行计算机系统【l 】。 并行计算同渐成为业内的研究热点，负载平衡技术也越来越受到人们的关注。本章对 论文选题的背景和意义进行了简要介绍，阐述了本论文主要的研究内容和组织结构。 1 1 研究背景 第一台计算机诞生以来，计算机的发展经历了从速度很慢的单处理器计算机到高性能 的多处理器计算机的过程。然而，人们对目前计算机系统所提供的计算能力水平并不满足， 特别是工程师和科学家，他们希望计算机能提供更强的计算功能，以满足科学和工程问题 中数据建模和模拟的需求，因为这些问题需要对大量数据进行多次重复计算才能得到有效 的结果。同时，某些问题的计算对时间有特定的限制，要求计算必须在合理的时间内完成， 例如天气预报，花两天时间来获取当地第二天精确的预报是没有意义的。其他一些研究领 域，如：飞行器设计、核爆炸模拟、大型d n a 结构建模以及全球天气预报等均属于巨大 挑战性问题，如果使用传统的单处理器计算机，这类问题在合理的时间内是无法解决的。 为了满足科学技术应用对高性能计算系统的需求，现代计算机的设计引入了并行的特 性。然而对于小规模的研究机构来说，购买并行机的花费巨大。如何在目前软硬件条件不 变的情况下，通过互联网上的计算机协作，将一个任务尽可能合理的分配给较多的处理器 去完成，即负载平衡任务分配问题，已成为研究的热点。 1 2 研究意义 高速发展的网络和不断提高的微处理器芯片性能使得计算网络成为吸引人的并行机 体。依赖于商业化的硬件和软件，计算机网络能够完成高性价比、高可用性的计算，这种 高性能计算潮流被称为机群计算。 当今，机群计算已经成为种解决许多大型科学和工程问题的十分有效的方式。影响 机群性能的因素有很多，诸如任务粒度、负载平衡、处理机的分配和网络拓扑等，其中负 基于m p i c h 的并行计算系统负载平衡技术的研究 载平衡任务调度策略是影响其性能的关键，已成为并行计算领域中的研究热点。 从计算机发展的历史看，在过去的四、五十年里产生了大量的硬件设计方案以提高计 算机速度，例如，提高c p u 主频，采用多级缓冲及指令预测，提高内存及磁盘的访问速度， 改进工艺以提高集成度和减小功耗等等。然而，由于硬件本身的物理特性限制，这种改进 不仅花费巨大，而且必将走到它的极限。同时，随着以太网的发展，网络上存在着大量的 空闲资源。因此，比较可行的方法是利用负载平衡技术，对已分配给各个节点的任务进行 重新调度，并通过进程迁移，使各节点负载大致相等，让所有节点的处理器连续执行任务， 以避免空闲与忙等待并存的情况，有效提高资源利用率，减少任务的平均响应时间，实现 执行时间最小的目标。其最大意义在于能够充分利用网络中现有的闲散c p u ，提供远远超 过同等串行计算机的计算能力，与此同时，价格又低于同等小型机。 1 3 研究现状 并行计算是一个很古老的想法，早在1 9 5 8 年g i l l 就写出了有关并行程序设计的论文， 1 9 6 3 年c o n w a y 叙述了并行计算机的设计及其编程，1 9 9 6 年f l y n n 和r u d d 更是明确提出 “并行是计算机的未来的论断。应运而生- 的负载平衡技术有两方面的含义：第一，大量 的并发访问或数据流量分摊到多台节点设备上分别处理，减少用户等待响应时间；第二， 单个重负载的运算分摊到多台节点设备上做并行处理，每个节点处理结束后，将结果汇总， 返回给用户，系统处理能力得到大幅度提高【2 】。 目前许多公司对负载平衡的实现提供了方案，给出了多种软件和硬件方面的解决策 略。纯软件解决策略是将负载平衡软件直接安装到服务器上，网络管理员可以通过g u i 或编写脚本程序对服务器机群进行管理。软件解决策略包括常用的r r d n s 、 m s w l n d o w s 2 0 0 0 系统自带的负载平衡部件n l b 、l v s 等等。这些策略的优点是不需要增 加额外的硬件，只需在原有的系统上安装软件，并进行合理的配置，就可起到负载平衡的 作用。一般说来，配置过程比较简单，对于机群系统的改动不大。实现负载平衡的硬件策 略是使用负载平衡器，这个负载平衡器直接安装在服务器和外部网络设备之间，因为它不 占用服务器的资源，并且有多种的负载平衡策略，负载平衡效果较好。但是这种负载平衡 的实现，成本昂贵，代价较大，并完全取决于硬件的价格。 1 4 论文组织结构 首先介绍了并行计算技术研究背景及意义，接着介绍了并行计算机相关的技术，然后 介绍提高并行计算环境的高可靠性和可用性的关键技术负载均衡技术，对负载均衡的 算法和策略作了详细的阐述。论文组织结构如下： 第一章主要阐述了课题的研究背景和意义。 2 基于m p i c h 的并行计算系统负载平衡技术的研究 第二章是对并行计算系统中所涉及到的关键技术和消息传递接口m p i 作了简要的介 绍，为第五章并行实验环境的搭建做基础。 第三章讨论了与负载平衡技术相关的理论知识，并引出本文核心内容负载平衡算 法，在本章中介绍了负载平衡的分类和算法。 第四章提出了一种基于任务优先图调度的静态负载平衡算法基于并行计算环境 的任务优先图调度算法的设计，对已有算法作了进一步的改进。 第五章是并行环境搭建与性能调度分析，通过试验来验证算法的可行性。 第六章总结了课题已经完成的工作，并指出了需要进一步完善和实现的部分，以及需 要更深入研究的方向。 3 基于m p i c h 的并行计算系统负载平衡技术的研究 第二章并行计算关键技术 基于消息传递模型的并行程序设计是基于多处理机的分布式存储的并行编程的一种 主要方式。由于它使用灵活、可移植性较强、易于编程等优点，且有p v m 、m p i 等较标准 的、成熟的消息传递接口，因而用c 、f o r t r a n 等语言编写的串行程序很容易改编成相 应的并行程序，因此这种并行程序设计方式应用前景广阔。 m p i 中引入了通信子的概念，支持并发库的开发，支持线程，应用程序可以移植到其 他品牌，并且有系统分配的一个附加的上下变量，缩小了用户错误使用t a g 标志的机率， m p i 是完全可移植的：更重要的是当今m p p 和机群日益成为并行算法研究的热点，而m p i 并行程序具有完全可移植性，其性能能够随网络带宽和延迟的改善而提高，因此，m p i 适 合m p p 和机群环境中的有效编程。尤其是m p i 2 最新版本增添了许多新特性和更多功能。 2 1 并行计算 并行计算( p a r a l l e lc o m p u t i n g ) ，通俗的说，就是在并行计算机上所做的计算，它和常说 的高性能计算( h i g hp e r f o r m a n c ec o m p u t i n g ) 、超级计算( s u p e rc o m p u t i n g ) 是同一个概念， 因为任何高性能计算和超级计算总离不开并行技术。并行计算是相对于串行计算来说的， 所谓并行计算分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而 空间上的并行则是指用多个处理器并发的执行计算。并行计算科学中主要研究的是空间上 的并行问题。 并行计算模型也可称为编程模式，是指将各种并行机( 至少是某一类的并行机) 的基 本特征抽取出来，形成一个处于具体并行机之上的抽象称为之并行计算机【3 j 。由于几类并 行系统有着巨大的差异，因此目前没有统一的并行计算模型，主要的并行计算模型可以分 为两大类：其中一类是模型是从共享内存的并行系统中提取，另一类则是从分布式消息传 递并行系统中提取。消息传递模型有较灵活的一面，而另一面，它也将各个并行执行部分 之间复杂的协调控制的任务和信息交换交给编程者，这在一定程度上增加了编程者的负 担。尽管如此，消息传递的基本通信模式是清楚且简单的，学习和掌握这些并不困难，这 也是消息传递的编程模式成为并行计算的计算模型的主要原因。 2 2 并行计算机的分类 空间上的并行导致两类并行机的产生，按照f l y n n 可把并行计算机分为：单指令流单数 据流( s i s d ，s i n g l e i n s t r u c t i o ns i n g l e d a t a ) 、多指令流单数据流( m i s d ，m u l t i p l e i n s t r u c t i o n m u l t i p l e d a t a ) 、单指令多数据流( s i m d ，s i n g l e i n s t r u c t i o nm u l t i p l e d a t a ) 和多指令流多数据 4 基于m p i c h 的_ 并行计算系统负载平衡技术的研究 流( m i m d ，m u l t i p l e i n s t r u c t i o nm u l t i p l e d a t a ) 。其中m i m d 类又可分为以下五类【4 】： ( 1 ) 并行向量处理机( p v p ，p a r a l l e l lv e c t o rp r o c e s s o r ) 并行向量处理机系统中包含了少量的高性能专门设计定制的向量处理器v p ，每个向量 处理机至少具有1 g f l o p s 的处理能力。系统中使用了专门设计的高带宽的交叉开关网络，将 v p 连向共享存储模块，存储器可以兆字节每秒的速度向处理器提供数据。这样的机器通常 不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器。 向量处理 向量处理向量处理 交叉开关 共享存储器 共享存储器共享存储器 图2 - 1并行向量处理机 ( 2 ) 对称多处理机( s m p ，s y m m e t r i cm u l t ip r o c e s s o r ) 对称多处理机系统使用商品微处理器( 具有片上或外置高速缓存) ，它们经由高速总 线( 或交叉开关) 连向共享存储器。这种机器主要用于商务，例如数据库、在线事务处理 系统和数据仓库等。重要的是系统是对称的，每个处理器可等同的访问共享存储器、i o 设 备和操作系统服务。 微处理器微处理器微处理器 高速缓存高速缓存高速缓存 i l 总线交叉开关 共享存储器共享存储器共享存储器 图2 - 2 对称多处理机 ( 3 ) 大规模并行处理机( m p p ，m a s s i v e l yp a r a l l e lp r o c e s s o r ) 一般是指超大型( v e r yl a r g e s c a l e ) 计算机系统，它具有如下特性： a 、处理节点采用商品微处理器； b 、系统中有物理上的分布式存储器； c 、采用高通信带宽和低延迟的互联网： d 、能扩放至成千上百乃至上万个处理器； e 、它是一种异步的m i m d 机器，程序系由多个进程组成，每个都有其私有的地址空间。 基1 - - m p i c h 的并行计算系统负载平衡技术的研究 图2 3大规模并行处理机 ( 4 ) 工作站机群( c o w ，c l u s t e ro fw o r k s t a t i o n ) 在有些情况下，机群往往是低成本的变形的m p p 。c o w 的重要界限和特征是： a 、c o w 的每个节点都是一个完整的工作站； b 、各节点通过低成本的商品网络互连： c 、各节点内总是有本地磁盘，m p p 没有； d 、节点内的网络是松散耦合到i o 总线上的，而m p p 内的网络接口是连到处理节点的 存储总线上的，因而可谓是紧耦合式的； e 、一个完整的操作系统驻留在每个节点中，而m p p 中通常只是个微核： 图2 4 工作站机群( c o w ) ( 5 ) 分布式共享存储处理机( d s m ，d i s t r i b u t e ds h a r e dm e m o d ，) 6 基于m p i c h 的并行计算系统负载平衡技术的研究 d s m 和s m p 的主要差别是，d s m 在物理上有分布在各个节点中的局部存储器，从而形 成了一个共享的存储器。对用户而言，系统硬件和软件提供了一个简单的地址的编程空间。 d s m 相对于m p p 的优越性是编程较容易。 图2 - 5 分布式共享存储处理机( d s m ) 从编程角度考虑，高性能计算机可以分为共享内存的计算机和分布式内存的计算机1 5 1 ， 主要以内存地址空间是否连续作为区别。p v p ，s m p ，d s m 都属于共享内存的计算机，而 m p p ，c l u s t e r 贝, l j 是分布式内存计算机。共享内存并行模式编程相对较为简单，程序员不用 考虑数据在内存中的位置，进程管理及同步操作由系统完成。但是用这种方式编制的程序 通常并行效率不高，因为它属于细粒度并行，主要针对循环进行并行处理。 2 3 并行算法的设计 一个并行处理系统应由三个部分组成：并行机系统结构、并行软件和并行算法【5 1 。尤 其是当一个并行处理环境已经提供，软件己基本配置好的情况下，如何充分发挥并行机的 效率，并行算法将是使用效率提高的一个决定性的因素。并行算法的好坏直接关系到并行 机的使用效率。 2 3 1 并行算法的概念 所谓算法就是解决问题方法的详细描述，它包括一组有穷的规则，这些规则规定了解 决某一特殊类型问题的一系列运算方法。并行算法就是适合于各种并行计算机上求解问题 和处理数据的算法。 并行算法1 6 1 是许多可同时执行众多进程的集合，这些进程相互作用和协调工作，实现 对给定问题的求解。并行算法按求解问题的类型可分为数值型并行算法和非数值型并行算 7 基于m p i c h 的并行计算系统负载平衡技术的研究 法。数值型并行算法是指基于代数运算的一类问题。例如矩阵运算、多项式求解、解线性 代数方程组等许多问题，它基本上是用于数值分析的范畴。研究数值型计算问题的并行算 法称为数值并行算法。非数值计算是指基于关系运算的一类非计算问题。例如排序、选择、 匹配以及图论等方面的问题，基本上是属于符号处理的范畴。研究非数值计算问题的并行 算法称为非数值并行算法。 2 4m p i 概述 对m p i 的定义是多种多样的，但不外乎下面三个方面，它们限定了m p i 的内涵和外 延以及它的基本实质【8 】： ( 1 ) m p i 是一个库，而不是- - 1 7 语言。许多人认为m p i 就是一种并行语言，这是不准 确的，但是按照并行语言的分类，可以把f o r t 凡+ m p i 或c + m p i 看作是一种在原来串 行语言基础之上扩展后得到的并行语言。m p i 库可以被f o r t 凡气n 7 7 c f o r t r a l l 9 0 c + + 调用。 从语法上说，它遵守所有对库函数过程的调用规则，和一般的函数过程没有什么区别。 ( 2 ) m p i 是一种标准或规范的代表，而不特指某一个对它的具体实现。迄今为止，所有 的并行计算机制造商都提供对m p i 的支持。可以在网上免费得到m p i 在不同并行计算机 上的实现，一个正确的m p i 程序，可以不加修改地在所有的并行机上运行。 ( 3 ) m p i 是一种消息传递编程模型，并成为这种编程模型的代表和事实上的标准。m p i 虽然很庞大，但是它的最终目的是服务于进程间通信这一目标的。在m p i 上很容易移植其 它的并行代码，而且编程者不需要去努力掌握许多其它的全新概念，就可以学习编写m p i 程序。当然，这并不意味着m p i 已经十分完美，必须承认m p i 自身还存在着一些缺点。 2 4 1 i 的特点 ( 1 ) m p i 的可移植性好，且易于使用 m p i c h 是并行机群系统间消息传递层的最常见的实现。消息传递【9 1 是相对于进程间通 信方式而言的，与具体并行机存储模型无关，任何支持进程间通信的并行机，均可支持消 息传递并行程序设计。几乎所有共享和分布存储并行计算环境均支持进程间的消息传递通 信 1 日o m p i 标准有两个版本，m p i 1 和m p i 2 。m p i 1 是m p i 消息服务内核，它提供了m p i 进程间消息传递的机制和抽象语义，同时提供了一些对通常并行计算的有帮助的附加特 性。m p i 2 提供了m p i 1 没有提供的功能扩展，如单边消息传递( o n es i d e dm e s s a g e p a s s i n g ) 、动态进程控制、和并行输入输出等。 ( 2 ) m p i 是被正式的详细说明的 m p i 是一种标准或规范的代表，而不仅指某一个对它的具体实现。迄今为止所有的并 行计算机制造厂商都可以提供对m p i 的支持。一个正确的m p i 程序可以不加任何修改地 8 基丁二m p i c h 的并行计算系统负载平衡技术的研究 在所有的并行机上运行。 ( 3 ) m p i 具有完备的异步通信机制 m p i 通信集的构造和管理能够在异步执行时保护用户的其它串行或并行进程不受影 响，高效地管理消息缓存空间，能实现真正的异步通信。m p i 具有完备的异步通信接口， 使得进程间接收和发送消息能与计算同时进行，能够满足m p m d 1 0 1 算法的完善的计算模式 的需求。 ( 4 ) m p i 编程很有效的用于m p p 上或c l u s t e r m p i 的虚拟拓扑结构反映了应用程序所申请的一组节点的通信模式，在m p p 上实现的 m p i 便可以利用这种信息来优化处理器间的通信路径。m p i 能采用的通信协议比较丰富， 有的协议并不需要调用操作系统提供的通信功能，因此效率得到提高。另外，m p i 程序的 执行不需要任何守护进程，其各个并行任务之间的信息传递是直接进行的，因此m p i 要比 p v m 的通信效率高。 2 4 2m p i 的基本接口函数 在m p i 1 中一共有1 2 8 个函数，而m p i 2 中共有2 8 7 个，从功能上分，它包括点点通信、 进程组、集合操作、环境管理以及请求。确切的说m p i 是比较庞大的，完全掌握这么多的 函数调用川是比较困难的。但是，从理论上而言，m p i 所需要的所有的通信概念可以用它 的6 个基本的调用来实现，掌握了这6 个基本的调用函数，就可以实现所有的消息传递并行程 序的概念。表2 1 为m p i 的基本函数调用： 功能目的 m p i r n i t 启动m p i m p i c o m m s i z e 找出进程的个数 m p i c o m m r a n k找出进程的r a n k 号 m p i s e n d 发送消息 m p i r e c v 接受消息 m p i f i n a l i z e终止m p i 表2 1m p i 的基本功能 用户可根据通信的要求，对不同的数据类型可以用相同的调用，对于任何并行计算都 会有六个基本的调用接口函数： ( 1 ) m p i 的初始化 9 基于m p i c h 的并行计算系统负载平衡技术的研究 2 - 6m p i i 周g 接口l 郴i - i n i t 0 m p i i n i t 是m p i 程序的第一个调用，它完成m p i 程序所有的初始化工作，所有m p i 程序 的第一条可执行语句都是这条语句。 ( 2 ) m p i 程序结束 图2 7m p i 调用接口2 郴if i n a l i z e m p if i n a l i z e 是m p i 程序的最后一个调用，它结束m p i 程序的运行，它是m p i 程序的 最后一条可执行语句否则程序的运行结果是不可预知的。 ( 3 ) 通信域包含的进程数 图2 8m p i 调用接口3 粕口ic o m ms i z e 该调用函数返回给定的通信域中所包括的进程的个数，每个进程通过这一调用便可得 知在给定的通信域中一共有多少个进程在并行执行。 1 0 基于m p i c h 的并行计算系统负载平衡技术的研究 ( 4 ) 当前进程标识 1 m p ic o m mr a n k ( c o m m r a n k ) 2 i nc o m m该进程所在的通信域句柄 3 o u tr a n k调用进程在c o m m 中的标识号 4 i n tm p ic o m m i _ r a n k ( m p lc o m mc o m mn t * r a n k ) 5 m p ic o m mr a n k ( c o m m ，r a n k ，i e r r o r ) 6 i n t e g e rc o m m ，r a n k i e r r o r 图2 - 9 m p i 调f f 接口4 一m p l c o m ms i z e 这一调用返回调用进程在给定的通信域中的进程标识号，有了这一标识号，不同的进 程就可以将自身和其它的进程区别开来，实现各进程的并行和协作。 ( 5 ) 消息发送 1 m p i s e n d ( b u f , c o u n t ，d a t a t y p e ，d e s t , t a g ，c o m m ) 2 i nb u f 发送缓冲区的起始地址( 可选类型) 3 i nc o u n t 将发送的数据的个数( 非负整数) 4 i n d a t a t y p e 发送数据的数据类型( 句柄) 5 i nd e s t 目的进程标识号( 整型) 6 i n t a g消息标志( 整型) 图2 10m p i 1 2 5 - - - - - m p i s e n d m p i _ s e n d 将发送缓冲区中c o u n t 个d a t a t y p e 数据类型的数据发送到目的进程目的 进程，在通信域中的标识号是d e s t ，本次发送的消息标志是t a g ，使用这一标志就可以把本 次发送的消息和本进程向同一目的进程发送的其它消息区别开来。 ( 6 ) 消息接收 1 m p i r e c v ( b u f , c o u n t ，d a t a t y p e ，s o u r c e ，t a g ，c o m m ，s t a t u s ) 2 o u t b u r 接收缓冲区的起始地址( 可选数据类型) 3 i nc o u n t最多可接收的数据的个数( 整型) 4 i n d a t a t y p e 接收数据的数据类型( 句柄) 5 i ns o u r c c接收数据的来源即发送数据的进程的进 6 程标识号f 整型1 图2 1lm p i 调用接口江m p ! r e c v m p i _ r e c v 从指定的进程s o u r c e 接收消息，并且该消息的数据类型和消息标识和本接收 进程指定的d a t a t y p e 和t a g 相一致，接收到的消息所包含的数据元素的个数最多不能超过 基于m p i c h 的并行计算系统负载平衡技术的研究 c o u n t 。 2 4 3m p i 的基本编程结构 下面是一段简单的程序代码12 1 ，这个例子将表现出m p i 应用程序的基本结构，程序代 码如下： 1 # i n c l u d e ”m p i h ” 2 m a i n ( a r g c ，a r g v ) 3 i n t a r g c ；变量初始化 4 c h a ra r g v ： 变量初始化 5 i n t m y r a n k ；变量初始化 6 i n t n u m p r o c s ； 变量初始化 7 m p i _ i n i t ( & a r g c ，& a r g v ) ； 启动m p i 8 m p i c 0 1 1 1 1 1 1 _ s i z e ( m p i _ c o m m _ w o r l d ，& m lr a n k ) ； 9 找出进程的标识号 10 m p i c 0 1 1 1 1 1 1s i z e ( m p l c o m m _ w o r l d ，& n u m p r o c s ) ； 11 找出进程的个数 1 2 i f ( m y r a n k = = 0 )主节点 13 c o m p u t i n ga n dc o m m u n i c a t i n g ； 14 i f ( f e t a le r r o rh a p p e n s ) m p i - a b o u t ( ) ； 1 5 1 6 ) 1 7 e l s e 从节点 l8 c o m p u t i n ga n dc o m m u n i c a t i o n ； 19 i f ( f e t a le r r o rh a p p e n s ) m p i - a b o u t ( ) ； 2 0 2 1 2 2 m p i f i n a l i z e ( ) ；退出m p i 并行环境 2 3 ) m p i - s a m p l e c 程序结 图2 1 2m p i 并行程序基本结构 此程序段是用c 编写的一段基本的m p i 应用程序，在任何一个基本的并行的程序段里 边，这些都是必不可少的部分，即2 2 2 中提到的六个并行接口在每个并行程序里都是是 必要的。 1 2 基于m p i c h 的并行计算系统负载平衡技术的研究 第三章负载平衡技术 负载平衡技术l l3 j 是高性能计算的关键技术之一，历史较长，几乎和并行计算同时产生， 甚至可以说它的思想比并行计算还要早，现实社会中人们的分工协作可看作负载平衡应用 的一种实例。 运算时间是衡量并行程序性能的重要指标之一。一个并行程序通常由多个进程组成， 通常一个计算节点上运行一个进程，这些进程可同时并行执行任务，并行程序的运行时间 取决于运行时间最长的进程。负载平衡是指在各计算节点间均匀分配任务，以使得各个进 程倾向于同时完成任务，从而减少进程的最长运算时间。在并行程序设计中实现负载平衡 可有效减少并行程序的运行时间，提高并行程序的性能【l4 1 。 3 1 负载平衡技术 把一个大型的计算问题分解为多个任务片，并根据处理器性能、活跃的任务数、网络 流量等相关信息，把各任务片分配到选出的节点上进行处理的过程，称作负载平衡、负载 分配或负载调度i l 引。时常控制网络负载平衡处理的工作都由外部设备实现，外部设备在机 群的计算节点中负责分配工作任务或网络流量。 负载平衡有两个内含：其一，大量的并发性访问或数据流量分担到多台节点设备上分 别处理，减少用户等待响应时间；其二，单个重负载的运算分担到多台节点上做并行处理， 每个节点设备处理结束后，将结果汇总返回给用户，系统处理能力和速度得到大幅度提高。 负载平衡1 1 6 1 建立在现有网络技术之上，提供一种廉价、有效、透明的方法，来扩展网络设 备和服务器带宽、增加系统吞吐量、加强数据处理能力、提高资源利用率。 3 2 负载平衡技术的分类 为满足不同用户的应用需求，目前有许多不同的负载平衡技术【1 7 】，如软硬件负载平衡、 本地全局负载平衡、更高网络层负载平衡，以及链路聚合技术。软硬件负载平衡：软件 负载平衡解决方案，是指在一台或多台服务器相应的操作系统上，安装一个或多个软件来 实现负载平衡，如d n s 负载平衡等。它的优点是基于特定环境、配置简单、使用灵活、 成本低廉，可以满足一般的负载平衡需求；硬件负载平衡解决方案，是直接在服务器和外 部网络间安装负载平衡设备，这种设备我们通常称之为负载平衡器。因专门的设备完成