（计算机应用技术专业论文）一种改进的nhbl并行计算模型及其性能评测.pdf

韭塞銮煎叁堂亟翌建j 幺塞摘垩 摘要 论文以并行计算模型为核心展丌研究。并行计算模型为并行算法和并行计算 机系统结构的分析与设计提供了具有指导意义的理论界面和模型框架，它是并行 计算研究的重要领域。目前在并行计算中尚未有一个如冯诺伊曼模型般在顺 序计算中取得成功的真j 下统一通用的并行计算模型，来保证硬件设计者设计多种 计算机结构而无须考虑被执行的软件，软件设计者编写各种有效执行的程序而无 须考虑所使用的硬件。因此论文以并行计算模型为课题展开研究。 论文首先对非独占、异构、同步的n h b l ( n o n d e d i c a t e dm e t e r o g e n e o u sb a g g i e r l o g g p m o d e l ) 模型做了详细地介绍，n h b l 是基于l 0 9 g p 模型提出的，l o g o p 模型没有考虑到节点的异构和非独占性，不能很好的对并行计算的时间开销进行 描述。n h b l 模型在l o g g p 模型基础上，考虑了节点计算资源的异构性、节点计 算资源的非独占性，但对节点间通信的损耗没有进行描述。本文基于这点，提出 了考虑网络拥塞的菲独占、异构、同步的l o g g p 模型，即n p m c l ( n o n d e d i c a t e d h e t e r o g e n e o u s b a r r i e r c o n g e s t i o n h 帕p m o d e l ) 模型n h b c l 模型通过引入网络 阻塞指数对节点问通信的损耗性进行了细致的描述。 论文描述了n h b l 模型和n h b c l 模型和它们各自的计算开销和通信开销， 并对求p 值的并行计算时剜进行预测然后在m p i 环境下的实验集群上实现了计 算p 值的并行算法，最后用实验结果与预测结果进行7 比较，实验结果表明， n h b c l 模型很好地刻画了基于集群的并行计算的特征，对基于集群的并行计算是 实用的和正确的，同时进一步证明n h b c l 模型相比于n h b l 模型更具有可用性。 关键词：并行计算模型、n h b c l 、性能评测、m p i a b s t r a c t 1 r h ck e m e io ft i t i st h e s i si sp a r a l l e lc o m p u t i n gm o d e l s a sa ni m p o r t a n tr e s e a r c h a r e ao fp a r a l l e lc o m p u t i n g , w h i c hp r o v i d ead i r e c t i v et h e o r e t i c a li n t e r f a c ea n dm o d e l f r a m e w o r kf o ra n a l y s i sa n d d e s i g n i n go f b o t hp a r a l l e la l g o r i t h m sa n ds y s t e m s a r c h i t e c t u r e s i nt h er e a l mo fs e q u e n t i a lc o m p u t i n gv o nn e u m a n nm a c h i n eh a s s u c c e s s f u l l yp r o v i d e da nu n i f y i n ga n du n i v e r s a lm o d e lo f c o m p u t a t i o n i nt h er e a l mo f p a r a l l e lc o m p u t i n g , h o w e v e r , t h e r eh a sb e e nr i os i m i l a rs u c c e s s s oie x p a n dt h i s r e s e a r c hb a s e do np a r a l l e lc o m p u t i n gm o d e l f i r s tt h en h b lm o d e l ( n o n d e d i c a t e dh e t e r o g e n e o u sb a r r i e rl o g o pm o d e l ) h a s b e e ni n t r o d u c e d ，a n di ti sb a s e do l ll o g g pm o d e i b u tl o g g pd o e s n tb ec o n s i d e r e d n o n d e d i c a t i o na n dh e t e r o g e n e i t yb e t w e e nn o d e s ，s oi t , c a n tb eu s e dt od e s c r i b et h e p a r a l l e lc o m p u t i n gt i m ea c c u r a t e l y n h b lw h i c hb a s e do nl o g g pm o d e lc o n s i d e r s t h e s e ，b u ti td o e s n tr e f l e c tw a s t et oc o m m u n i c a t i o nb e t w e e nn o d e s b a s e dt h i s an e w m o d e ln h b c l ( n o n d e d i c a t e dh e t e r o g e n e o u sb a r r i e rc o n g e s t i o nl o g g pm o d e l ) h a s b e e np u tf o r w a r d 啦m o d e lu s e st h ec o n g e s t i o ne x p o n e n tt od e s c r i b et h en e t c o n g e s t i o n f r s tn h b la n dn h b c lm o d e lh a v eb e e n d e s c r i b e da n dd e f i n e dt h e i r c o m p u t a t i o na n dc o m m u n i c a t i o nc o s tm o d e l si nd e t a i l s t h e nif o r e c a s tt h ep a r a l l e i c o m p u t i n gv a l u eo fp 。t h e nu n d e rt h em p le n v i r o n m e n t ，ig e tt h et r u ev a l u eo fpv i a e x p e r i m e n t a tl a s t , ih a v eac o m p a r i s o nb e t w e e nt h et r u ev a l u ea n da n a l y z i n gv a l u co f p t h ee x p e r i m e n t a lr e s u i t ss h o wt h en h b c l m o d e lc o m m e n d a b l yd e p i c t st h ef e a t u r e s o ft h ep a r a l l e lc o m p u t i n gb a s e do nc l u s t e r , a n di ti sp r a c t i c a la n dc o r r e c tf o rt h ep a r a l l d c o m p u t i n gb a s e do nc l u s t e r k e y w o r d s ；p a r a l l e l c o m p u t a t i o n a lm o d e l 、n h b c l 、p e r f o r m a n c e e v a l u a t i n g 、m p i 致谢 首先感谢我尊敬的导师于双元副教授，在两年半的研究生学习期间，导师在 为人、为学两方面，都给了我无微不至的关怀，在我遇到困难的时候鼓励我，并 且为我提供了一个又一个难得的学习和锻炼机会，使我在理论和实践各方面都得 到了很大的提高。本论文从选题、字斟旬酌的修改，一直到最后定稿，更是倾注 了于老师大量的心血。她渊博的知识，创新的思维、严谨的治学态度和精益求精 的工作精神使我获益菲浅。 在实验室工作及撰写论文期间，王瑞昌、王洁等同学对我论文中的校对工作 给予了热情帮助，在此向他们表达我的感激之情。 同时，也感谢所有在研究生期间曾给予我支持、关心和帮助的各位同学和亲 朋好友，感谢他们对我的学习和论文工作所给予的无私帮助，攻读硕士期间我所 获得的每一点进步都是与他们深切的关怀和热情帮助分不开的。 1 1 研究背景 1引言 随着现代科学技术的发展，大规模数据处理向人们提出了新的挑战。典型的 问题如g c a ( g r a n dc h a l l e n g i n ga p p l i c a t i o n s ) 。g c a 包括大规模结晶和微断层摄 影结构问题、蛋自动力学及生物催化剂、虚拟物质设计及处理、全球气候模型和 离散事件模拟等，是科学界和工程界的一类基本问题，在科学上和经济上有很大 的影响。并行计算的出现为成功地解决这些问题开辟了一个可行的途径。在对并 行计算的广泛需求中，归纳起来主要有三种类型的应用1 1 】： ( 1 ) 计算密集( c e m p u t e - l m e n s i v e ) 型应用，如大型科学工程计算与数值模 拟： ( 2 ) 数据密集( d a t a i n t e n s i v e ) 型应用，如数字图书馆、数据仓库、数据采 集和计算可视化等； ( 3 ) 网络密集( n e t w o r k i n t e n s i v e ) 型应用，如协同工作、遥控和远程医疗 诊断等。 从另一方面讲，也正是这些重大的应用需求推动了当代并行计算技术的迅速 发展。 并行计算的出现源于实际应用程序存在内在并行度这一个基本事实。同时性 和并行性是物质世界的一种普遍属性，具有实际物理背景的计算问题在许多情况 下都可以划分为能够并行计算的多个子任务。针对某一具体应用问题，可以利用 它们的内在并行度，设计并行算法，将其分解成相互独立、但彼此又有一定联系 的若干个子问题，分别交给各台处理机，而所有处理机按照并行算法完成初始应 用问题的求解。 可以看到，应用程序中是否存在可挖掘并行度是并行计算机应用的关键嗍，而 并行算法作为应用程序开发的基础，自然在并行计算机应用中具有举足轻重的地 位。 在使用并行计算机解决一个实际问题时，并行算法的设计是很重要的，而且 最终它要成为一个由程序实现的结构依赖性的算法。这就需要有一个抽象的并行 计算机结构作为研究高效的结构依赖性算法的基础，以保证所设计的并行算法适 应广泛的并行计算机结构，并能依照抽象的结构来分析并行算法的效率，从而指 导与并行结构相匹配的并行算法设计。 从并行算法的设计和分析出发，从各种具体的并行机中抽象出来，并在一定 程度上反映出具体并行机的属性，可以使算法的研究不再局限于某一具体的并行 机的模型，称之为并行计算模型( 或抽象机器模型) 。从更广阔的意义来说，并行 计算模型为并行计算提供了硬件与软件的界面。在该界面的约定下，并行系统的 硬件设计者和软件设计者可以丌发对并行性的支持机制，从而提高系统的性能。 并行计算模型的主要作用如下： ( 1 ) 并行计算模型是并行算法实现的基础。并行算法设计与分析依赖于并 行计算模型，通常人们针对统一问题可以设计出多种不同算法以适应在不同模型 上对该问题的求解，并分析和评价并行算法的优劣 ( 2 ) 并行计算模型给并行计算设计与分析提供了一个简单方便的框架。由 于并行计算模型抽象了一类并行计算机的基本特征，避开了硬件结构过多的繁琐 细节的限制，从而保证了它在相当范围内的通用性，同时又能反映出不同算法的 主要特征，为算法设计提供启发、指导和评价的依据。 ( 3 ) 并行计算模型使并行算法设计具有一定的生命力。算法设计者避开了 多种多样的具体的并行计算机结构，依据并行计算模型来设计算法。这样，一方 面可以使算法研究者集中精力在开发应用问题本身固有的并行性，分析算法性能 上；另一方面设计出的算法具有通用性，从而使并行算法的研究成为一项相对独 立的活动。 因此，研究并行计算模型具有重大意义。 1 2 并行计算模型研究现状 对于并行计算模型，以前国内外提出了很多( p r a m ，a p r a m ，b s p ，l o g p ， c 3 等) ，但因为提出得较早，当时流行的还是大型并行计算机，所以它们都是针对 基于大型并行计算机的并行计算的。而基于集群的并行计算系统与以往的基于大 2 型并行计算机的并行计算系统相比，有着显著的不同，使用这些模型不能比较准 确地分析基于集群的并行计算算法。 目前国内外在这方面的研究中，较为成功的是计永昶老师提出的基于l o g g p 模型提出的非独占异构同步模型n h bl 1 2 i ( n o n d e d i c a t e dh e t e r o g e n e o u sb a r r i e r l o g g pm o d e l ) 。n h b l 比较准确地刻画了基于集群的并行计算的节点的可扩展性 和节点的异构性、节点计算资源的非独占性对计算时间的影响，但n h b l 在刻画 节点通信时采用i j d g g p 模型，使其不能比较准确地刻画计算对节点间通信的损耗 性、节点问通信存在的潜在拥塞、节点的异构性以及节点计算资源的非独占性对 通信时间的影响。 1 3 论文研究内容 本文对现有的并行计算模型进行研究、分析和扩展，提出一个能够比较全面 地刻画基于集群的并行系统的特征的并行计算模型，即提出一个基于集群的并行 计算模型。其目的和意义在于支持基于集群的并行计算，用于基于集群的并行算 法的分析、设计和移植。建立的模型命名为考虑网络拥塞的非独占、异构、同步 l o g o e 模型n i - i b c l ( n o n d e d i c a t e dh e t e r o g e n e o u sb a r r i e rc o n g e s t i o nt o g , o f m o d e l ) 。然后结合m p i 的通信模式以n l 吼并行计算模型为核心展开研究，对 n h b l 模型进行改进n h b c l ，即提出了n h b c l 。并对模型改进前后的参数和通 信开销进行评估并根据m p i 程序设计的特点，制定通信时间测量规范和通信时 间测量方法，然后在p c 集群服务器进行实际测量，根据测试数据对n h b c l 模型 改进前后的通信性能进行分析。 1 4 论文组织结构 论文的组织结构如下： 第一章简要介绍了论文的研究背景，并行计算模型研究现状和研究内容。 第二章主要介绍了集群以及并行计算模型的的基本理论，首先对集群的发 展，特点，构成以及消息传递机制进行了基本的介绍，重点介绍了m p i 的并行编 程方法。其次对现在较为流行的并行计算模型进行了分析和讨论。 第三章提出了n h b l 模型改进的目标，给出了改进模型的方法，并分析了改 进后模型的通信开销。 3 垃瘟窑通厶望亟鲎位论塞 i 瞎 第四章设计了并行测试程序，制定了计算、通信时日j 测量规范和计算、通信 时日j 测量方法，在p c 集群服务器上对改进前后n h b c l 模型的参数进行了实际的 测量，对测量结果进行了详细的分析，得到了结论。 第五章论文的总结和所得出的结论。 4 2 集群系统及并行计算模型分析 2 1 集群系统概述 2 1 1 集群系统产生和发展 并行计算系统是人们为应对大规模数掘处理提出的挑战而努力的结晶。 在集群投入研究及应用之前，并行计算系统的发展基本上可以分为四个阶段： 阵列机、向量多处理机系统、基于共享存储的多处理机系统、基于分布存储的大 规模并行处理系统( m p p ) 在研制上述并行计算系统的过程中，人们逐渐认识到，系统的规模可伸缩性 和可编程性已成为促使这两者进一步发展的关键问题。系统规模只有在具有可伸 缩性的前提下，并行计算系统才可能以尽可能低的成本向用户提供尽可能商的性 能。虽然专用的m p p 系统般都是基于市场上的微处理器，但支持通信和同步的 机制却是高性能超级计算机专用的部件，这使得m p p 系统性能非常卓越但价格也 十分昂贵。另外，由于高性能工作站和高性能网络设旌的出现，为集群的发展提 供了新的契机。 集群是利用通用的高速网络将一组高性能工作站或高档p c 机，按某种结构连 接起来，在并行程序设计以及可视化人机交互集成开发环境的支持下，统一调度， 协调处理，实现高效著行处理的系统。系统的资源管理及相互协作一般由操作系 统之上的并行编程环境完成，因而如果设计合理，系统就可以屏蔽底层硬件( 包 括工作站和网络) 的异构性，从而具有相当好的跨平台性能，同时也使得集群系 统的可扩展性更强。目前，集群已经成为了并行计算技术发展的主流。 集群的发展与兴起，是与现代体系结构、r i s c 技术、网络技术以及并行编程 环境的发展直接相关的嘲【4 l 。 ( 1 ) 计算机体系结构的发展已经比较成熟 从向量多处理机系统、共享存储的多处理机( 包括对称和非对称两种) 到m p p 结构，人们积累了相当丰富的经验，发展了一套比较完整的理论，这都为集群的 发展提供了理论基础。 ( 2 ) 由于r i s c 技术的发展，使得微处理器的性能不断提高 高档芯片的运算能力平均每年增长3 0 ，而价格不断降低，直接使用商用工 作站或p c 机作为运算节点的集群系统在节点性能上能够同处理器的发展保持同 步增长。 ( 3 ) 网络技术的进步使得松散耦合系统的通信瓶颈逐步得到缓解 网络传输速度的提高，有效地提高了应用程序之间的通信带宽。而交换技术 的发展则大幅度地降低了传输延迟，使得许多高速局域网的性能和m p p 专用互连 网络的性能相当。 ( 4 ) 并行编程环境的丌发使得编制并行程序更为容易 并行应用程序的开发和在不同平台之间的可移植性一直是传统并行系统能否 广泛应用的一个关键。由于集群系统的发展，近年来出现了很多并行程序开发及 运行系统，比如p v m 、m p i 、e x p r e s s 、i a n d a ，p 4 等。这些系统可以适应很多平 台，应用程序在这些系统上的可移植性也比较好，特别是p v m 和m p i ，由于其开 放性，受到了许多大学和研究机构的重视，并且在这些环境下开发了许多应用程 序。 2 1 2 集群系统优点 集群系统的广泛应用源白其以下优点： ( 1 ) 性能价格比高 由高性能节点处理杌组成的并行系统，具有很强的处理能力而组成集群的 各节点可以为各种工作站、p c ，网络硬件为标准化的商业产品，操作系统和并行 环境及编译系统都是通用软件，整体价格较低、通用硬件维护成本低。例如，美 国o a kr i d g e 国家实验室的一组并行程序测试表明，基于网络的1 1 台m mr s 6 0 0 0 工作站组成的并行系统，其性能达到0 7 g f l o p s 。但相对同等性能的m p p 等系统来 说，价格要便宜的多。 ( 2 ) 可复用性强 系统中的机器既是普通的工作站，又是并行系统中的一个节点，在没有并行 任务时，可以当作独立的工作站使用。同时，原有的一些性能较低或型号较旧的 机器也可以加入集群，只要在并行工作时给它分配较少的任务，它仍可发挥一定 的作用。这样可以资源共享，充分利用现有的机器设备。 ( 3 ) 同时可以支持多种平台 由于集群系统一般是靠高层的软件提供并行计算环境，在异构的支持方面具 有得天独厚的优势。因此用户可以根据应用要求选择不同的节点处理机( 如工作 站、m p p 系统等) 来构造集群。 “) 可扩展性 这也是集群系统的一个非常突出的优势。一般来说，在系统通信允许的情况 下，增加系统中节点的个数，就能提高集群的整体性能。 ( 5 ) 用户编程方便 集群系统中，程序的并行化只是在原有的c 、c + + 或f o r t r a n 串行程序中，插 入相应的通信原语。用户使用的仍然是熟悉的编程环境，不用适应新的环境，这 6 样就可以继承原有的软件财富。 讵是由于集群的这些优点，许多公司和研究部门都推出了基于集群结构的并 行计算机。如i b m 的s p ，中国曙光公司刚刚推出的超级服务器d a w n 2 o ，都 是基子集群结构的。集群作为重要的并行计算系统，在大学、研究所和重点实验 室广泛安装，得到了越来越多的应用。 当然，集群系统也有一个较大的弱点，就是处理机之日j 的通信速度相对较慢1 5 】， 延迟大，限制了其应用范围。但我们可以通过并行软件的设计降低其限制的影响。 而且，随着网络技术的迸一步发展，这个弱点会越来越小。 2 1 3 集群系统构成 集群是将一组节点计算机通过高性能网络连接起来，作为一个单一系统向用 户提供高性能、高可用性服务的系统1 4 j 。它从体系结构上说具有下列特征1 6 l ： 1 ) 构成系统的所有节点都是完整的商用计算机系统。节点机可以是高档p c 、 工作站，也可以是s m p 每个节点机上都安装有一份完整的商用操作系统。 ( 2 ) 连接各个节点的互连网络提供节点间高性能、高可靠和可扩展的通信服 务，人们将这种网络称为系统域网( s y s t e ma r e an e t w o r k + 简称s a n ) 。这种网络 通常通过网络接口卡( n e t w o l l 【i n t e r f a c e ，简称n i ) 连接到节点机的i o 总线上。 其中，少数专用网卡连到系统的内部总线。 ( 3 ) 整个系统呈现给用户的是一个单一的系统映像( s i n g l es y s t e mi m a g e ，简 称s s i ) 。系统中所有分布的资源被组织成一个统一的整体由用户管理和使用，用 户感受不到单个节点计算机的存在。从用户的角度看，一个集群系统就如同一个 具有巨大配置的单一计算机系统。s s i 由几个方面的内容构成，主要包括单一登录 点( s i n g l ee n u yp o i n t ) 、单一控制点( s i n g l ec o n t r o lp o i n t ) 、单一文件系统( s i n g l e f i l es y s t e m ) 、单一内存空闻( s i n g l em e m o r ys p a c e ) 、单一作业管理( s i n g l ej o b m a n a g e m e n t ) ，此外，还有单一用户界面( s i n g l eu s e ri n t e r f a c e ) 、单一进程空间 ( s i n g l ep r o c e s ss p a c e ) 等等。s s i 是集群系统中的关键技术之一。 ( 4 ) 整个系统具有高可用性( a v a i l a b i l i t y ) 。由于集群系统中的每个节点都是一 个完整的计算机系统，都有一个完整的操作系统映像，因此一个或几个节点的崩 溃不会导致整个系统停机，当节点出现故障时，这个系统可以降级使用直至崩溃 的节点得到修复。 7 一个典型的集群系统的体系结构如图2 1 所示： 图2 1 集群系统的体系结构 f i g u r e2 - 1c l u s t e d s y s t e mc o n f t g u r a t i o n 高速互联网络是连接一个集群系统内部所有节点并且向用户提供高性能、高 可靠通信服务的网络软硬件设施的总和一般来说，高速互联两络只是用于系统 内部互连，无需考虑对异种节点间通讯的支持，而且节点问也是互相信任的( 可 能牺牲安全以换取速度) ，这是高速互联网络实现高性能的一个重要前提目前人 们讨论系统域网时多是指网络硬件( 包括n i ) ，而不涉及节点上所采用的通讯软件。 从集群节点互连的需求考虑，高速互联网络一般具备下列特征【7 j ： 1 ) 高速互联网络应该能提供高通信带宽和低通信延迟。 ( 2 ) 高速互联网络应能保证数据传输的可靠性。如对t c p n 协议的性能分析表 明，大约4 0 的软件开销用于提供这种可靠性。所以，由网络硬件支持数据的可 靠传输就显得有益并且必要。 ( 3 ) 高速互联网络网应该具备良好的可扩展性，以适应不同规模的系统通信要 求，保证集群在不同的软硬件配置下均能提供高性能的服务。 ( 4 ) n l 智能化，由网卡自主完成尽可能多的通信控制功能，从而减轻节点c p u 的负担。 2 2 消息传递机制 并行计算中各并行子进程分布在各节点之上，它们之间要进行通信。这些并 行子进程之问的通信目前主要采用两种通信机制消息传递机制和共享存储机 制。 集群的节点之b j 是通过通用网络连接的，使用的是分布式存储方式，因此基 于集群的并行计算采用的通信机制是消息传递机制。 8 2 2 1 消息传递机制概述 在分布式存储的并行机中，消息传递( m e s s a g ep a s s i n g ) 是一种被广泛使用的 节点通信机制1 7 n 射。在这种通信机制下，一个程序被分成几个子程序分别在各个节 点上运行，并通过相互传递消息来保持整个程序的协调和同步对起初的分布式 存储的并行机，节点就是各c p u 。现在，随着集群的大量使用，节点不仅可以是 多c p u 机的各个c p u ，还可以是一个网络上的各个节点计算机。但这时程序员必 须直接与网络打交道，编制与两络的接口程序；同时要负责网络上计算机蚓数据 格式的转换，防止网络时延给它的程序可能造成的不可靠性，最后。由于程序分 布在整个网络上执行，还必须考虑一旦某个节点机失败后的容错问题。 在分布式存储的并行计算机系统( 包括集群) 中，由于各节点机之闻通过计 算机网络进行连接，节点机之间没有共享内存供数据传递，因此，都通过消息传 递的通信机制来完成各处理机之间的数据传递操作i l o l 。在并行程序设计环境中， 依据节点机闯的消息传递机制，必须为程序员提供不同模式的以及多种层次的系 统通信原语，以使用户能方便、灵活地通过此环境进行并行程序设计，完成并行 计算任务。 消息传递通信系统是围绕消息的概念来建立的1 1 2 1 。在并行程序设计环境中， 一个消息即是由一个发送数据操作所产生的结果，其中数据为一些没有结构定义 的字节流。每个消息由一个读取操作来使用，如果消息字节数大于读取操作所需 要的字节数，则多余字节将被丢掉，反之，则读取操作将读取所有此消息中的字 节，同时返回消息字节数不够的指示。 2 2 2 阻塞通信与非疆塞通信 在并行程序设计环境中提供了多种模式及多神层次的通信程序包。按通信的 机制不同，主要分为阻塞( b l o c k i n g ) 通信和非阻塞( n o n b l o c k i n g ) 通信两类【9 1 1 1 1 j ( 1 ) 阻塞通信机制 阻塞通信机制主要指，当调用此通信原语时，用户程序将被挂起，直到相应 的操作完成为止。如果是发送数据，则数据从用户程序空间拷贝至节点的系统消 息缓冲区，等待系统根据发送目的节点的地址，选择占用相应的通信链路将数据 从系统缓冲区发送出去之后，用户程序调用才能返回，接着完成后面的操作。如 果是接收数据，则在用户程序调用此系统通信原语之后，直到在本节点的系统消 息缓冲区中有相应类型的消息到达之后，该调用函数才能返回，同时，将消息从 系统接收消息缓冲区中拷贝至用户程序空间。 在阻塞通信系统中，最基本的两个系统调用为e x w r i t e 操作和e x r e a d 操作， 9 分别完成发送消息和接收消息的功能。在此基础上，为了满足不同应用程序的需 要。并行程序设计环境还应提供多种阻塞通信函数。 ( 2 ) 非阻塞通信机制 对于阻塞通信，接收节点将消息进行缓冲等待相应的读取操作取走数据消 息。但对于实时性要求强的实时处理系统，这样的通信函数就无法满足实际应用 的需要。这种应用要求消息在到达目标节点之后，立即进行处理。而对于像流水 线式地从一节点产生的数据到另一节点进行的处理，则更需要有消息驱动的通信 函数支持。因而，在并行程序设计环境的消息传递系统中，提供了对于非阻塞通 信机制的支持，以满足消怠立即处理的需要。 在实时处理系统中，应用程序可以设置一个处理进程用于处理接收到的消息， 而另一部分程序可以继续完成其它的并行计算以及处理其它来源的通信消息，它 不会像阻塞通信那样在调用时被挂起。 对于流水线数据的处理，则可以设霄处理进程来接收并处理当前已经到达的 通信消息，如果消息未到达，贝l j 等待。在这种工作方式中，不会对节点的正常处 理进行挂起，保证了并行计算的流畅进行 在这种通信模式中，系统接收缓冲区所接收到的消息不会拷贝至用户程序空 间中，而是直接由处理进程进行处理。 对于消息发送操作，并行程序设计环境也同样提供了非阻塞通信原语。在这 一通信原语中，消息不再从用户程序空间拷贝至系统消息缓冲区中，而是当系统 占用了通信链路之后，直接从用户程序空间发送出去。这一方式的消息传递通信， 由于减少了消息从用户空间到系统缓冲区的拷贝，因而，通信延时最小。但在使 用时，由于调用函数的立即返回，不再阻塞，要求在函数调用完成之后，用户程 序空间中的消息缓冲不能改变，直到发送操作完成为止。否则将发送出去改变后 的消息数据。 非阻塞通信原语为实时处理等追求快速计算的实际应用，在通信系统中提供 了最小的通信延时，满足了快速计算的实际需要。 2 2 3 消息传递同步 在基于消息传递的通信过程中，同步的问题比较复杂，因为常常要考虑缓冲 的时延。消息传递1 1 0 1 分为同步消息传递和异步消息传递两类。 ( 1 ) 同步消息传递 在这种通信方式中，需要等待接收者的应答后才能继续，接收进程接收到的 消息能反映发送进程的当前状态。 ( 2 ) 异步消息传递 1 0 在这种通信方式中，不需要等待接收者的应答就可以继续利用发送和接收 命令，可以在任意时刻实现同步要求。由于发送进程一般先于接收进程，因此接 收进程接收到的消息不能反映发送进程的当前状态。 2 3 并行机系统软件包 如果单单把多台计算机用网络连接起来，而不提供软件支撑，是不能构成高 性能并行计算系统的。那和普通计算机构成的局域网没有本质区别。根据调查， 在普通局域网中，一般有9 5 的机器处于空闲状态。为了充分利用这些空闲机， 实现计算能力共享【1 3 l ，研究人员开发了多种并行程序开发环境和并行程序设计语 言。 目前，集群上的并行机系统软件包主要有支持消息传递机制的p v m ( p a r a l l e l v i r t u a lm a c h i n e ) 、e x p r e s s 、m p l ( m e s s a g ep a s s i n gi n t e r f a c e ) ，支持共享存储的l i n d a 等等1 1 3 l 。m p l 和p v m 是其中应用最广泛的两个。 2 3 1m p i 基本介绍 m p | 是一个消息传递接口的标准1 1 9 1 ，用于开发基于消息传递的并行程序。其 目的是为了提供一个实际可用的，可移植的、高效的和灵活的消息传递接口标准。 m p i 以语言独立的形式来定义这个接e l 库，并提供了与c 和f o r t r a n 语言的绑定。 这个定义不包含任何专用于某个特剐的制造商、操作系统或硬件的特性。由于这 个原因，m p i 在并行计算界被广泛地接受。 m p i 已经被实现在p c w i n d o w s 、所有主要的u n i x 工作站以及所有主要的并 行机上。这就意味着用标准的c 或f o r t r a n ，加上m p i 实现的消息传递并行程序， 可以不作修改地运行在单台p c 机、单台工作站、工作站网络和m p p 系统上，无 论这些机器由谁制造，用的是什么操作系统。因此本文采用m p l 作为开发环境。 2 3 2p v m 基本介绍 p v m 是一个在网络上的虚拟并行机系统软件包【1 4 】。它允许将网络上的并行机 和单处理机的集合当成一台单一的“并行虚拟机”来使用。 p v m 支持消息传递，节点机可以是标量机、共享存储多处理机、分布式存储 多处理机、专用的图形引擎等，从而允许应用的每个组成部分使用最适合的计算 资源。 p v m 支持c 和f o r t r a n 两种语言，目前已发展到3 4 版，由于它是免费的，因 此使用范围非常广泛。 1 1 2 3 3m p i 并行编程方法 2 3 3 1m p i 数据类型 m p i 川由于要与f o r t r a n 和c 两种语言交互，因此m p i 标准自定义了 数据类型，分别对应了f o r t r a n 和e 的基本数据类型。如下图所示： m p ! 预定义数据类型相应的c 数据类型 m p i _ c h a rs i g n e dc h a r m p i _ s h o r ts i g n e ds h o r tj u t m p i _ i n ts i g u e dt o t m p i _ l o n gs i g n e dl o n gi n t m p i u n s i g n e d _ c h a r u n s i g n e dc h a r m p iu n s i g n e d _ s h o r t u n s i g n e ds h o r ti n t m p iu n s i g n e d u m s i g n e di m m p iu n s i g n e d _ l o n g u n s i g n e dl o n gi n t m p if l o a t f l o a t m p l d o u b l e d o u b l e m p i _ l o n g _ d o u b l e l o n gd o u b l e m p l b y t e 无对应类型 m p ip a c k e d 无对应类型 图2 - 2 m p i 的c 对应的数据类型 f i g u r e2 - 2m p ld a t at y p ec o r r e s p o n d i n g t oc 在m p i 进行消息传递的过程中，需要指定传递的数据类型，这个时候就需要 对数据做类型匹配和转换。 数据接收缓冲区 图2 - 3 m p i 消息传递过程 f i g u t e2 - 3m p im e s s a g ep a s s i n gp r o c e s s mp i 的消息传递过程可以分为三个阶段1 1 5 l ： 1 、消息装配将发送数据从发送缓冲区中取出加上消息信封等形成一个完整的 消息 2 、消息传递将装配好的消息从发送端传递到接收端 3 、消息拆卸从接收到的消息中取出数据送入接收缓冲区 在这三个阶段都需要类型匹配1 、在消息装配时发送缓冲区中变量的类型必 须和相应的发送操作指定的类型相匹配；2 、在消息传递时发送操作指定的类型必 须和相应的接收操作指定的类型相互匹配；3 、在消息拆卸时接收缓冲区中变量的 类型必须和接收操作指定的类型相匹配。 以上指出了在什么时候需要类型匹配，进一步类型匹配到底包括哪些方面 呢? 在m p i 中类型匹配有两个方面的意思，1 、宿主语言的类型和通信操作所指 定的类型相匹配：2 、发送方和接收方的类型相匹配。 对于类型匹配的第一个方面，比如在f 0 l 盯ra n 7 7 中声明为i n t e g e r 类型 的变量在发送和接收时要使用m p i i n t e g e r 与之相对应，声明为r e a l 类型 的变量在发送和接收时要使用m p i 与之相对应。同样在c语占中int类_real 型要和m p l i n t 相对应f l o a t 要和m p if l o a t 相对应。前面部分给出的c 与 m p i 类型的对应关系就是为了满足类型匹配的要求。 对于类型匹配的第二个方面要求在发送方和接收方对数据类型的指定必须是 一样的。即发送方用m p i则接收方也必须使用发送_integer m p i _ i n t e g e r 方用m p i则接收方也必须用 ， 对于c 语言虽然有些系统中_ r e a lm p lr e a l i n t 和l o n g 有相同的表示。但是m p ! 认为m p i _ i n t 和m p il o n g 是不同的 类型即m p ii n t 和m p il o n g 是不匹配的。发送方和接收方必须同时使用 m p ii n t 或i m p l o n g 。 2 3 3 2m p i 通信方式 利用m p i 进行并行程序设计的关键是在各个并行进程间进行数据通信，即消 息传递。也即数据的发送和接收，也就是怎样发送和接收消息。m p l 有提供了多 种消息传递方式。m p i 共有四种通信模式【垌，它们是标准通信模式( s t a n d a r d m o d e ) 、缓存通信模式( b u f f e r e d m o d e ) 、同步通信模式( s y n c h r o n o u s - m o d e ) 和就 绪通信模式( r e a d y m o d e ) 。 2 3 3 3m p i 并行程序设计的基本模式 m p i 由一组库函数组成，并行程序的各任务通过这些函数进行通信。一个m p i 并行程序出m p i 任务组成，这些任务可以相同也可以不同。每个m p i 任务在使 用m p i 库之前必须在m p i 环境中登记。一旦m p i 任务在m p i 环境中登记， 就可以和其他m p ! 任务进行通信。其本身和目标任务之间可以采用原始的点到点 通信，一组中的所有成员则可以采用集中式通信方式 m p i 1 标准基于静态加引1 羽，即所有进程在加载完以后就全部确定，直至整 仑程序结束才终止，在程序运行期间没有进程的创建和结束。一个m p i 程序的所 有进程形成一个缺省的组，这个组被m p i 预先规定的 c o m m u n i c a t o r , m p lc o m m w o r l d 所确定。在m p l 2 标准中，增加了动态生成 进程的功能，但是m p l 2 目前还没有具体的实现版本。 m p i 环境的初始化和结束流程如下1 1 2 l ：在调用m p i 例程之前，各个进程都应 该执行m p li n i t ，接着调用m p i _ c o m m $ 1 z e 获取缺省组( g r o u p ) 的大小，调用 m p ic o m mr a n k 获取调用进程在缺省组中的逻辑编号。然后，进程可以根据 需要，向其它节点发送消息或接收其它节点的消息，经常调用盼函数是m p l s e n d 和m p ir e c v 。最后，当不需要调用任何m p i 例程后，调用m p if i n a l i z e 消 除m p i 环境，进程此时可以结柬，也可以继续执行与m p i 无关的语句。这就是 一般的m p i 并行计算的流程。 对等模式和主从模式是m p i 并行程序的两种最基本的设计模式。大部分的 m p i 程序都是这两种模式之一或二者的组合。掌握了这两种模式，就掌握了并行 程序设计的主线。m h 程序一般是s p m d 程序，当然也可以用m p i 来编写 m p m d 程序，但是所有的m p m d 程序都可以用s p m d 程序来表达，二者的表 达能力是相同的。s p m d 程序有很强的表达能力，s p m d 只是形式上的表现，其 内容是很丰富的。本论文中涉及的m p i 程序均是s p m d 程序。 2 3 3 4m p i 基本函数 m p i 的目标是制定一个编写消息传递程序而广泛使用的标准，为此，这组接口 应制定一个实用、高效、灵活的消息传递标准它有如下几个特征：设计一个应编 程接口；提供高效的通信；接口应提供方便的c 和f o r t r a n 绑定；提供一个可靠的 通信接口；定义的接口与现有p v m ，n x ，p 4 等的接口不能相差太大；定义的接口在 基本通信和系统软件无重大改变时，能在不同厂商的平台上实现；接口的设计应是 线程安全的m p i 定义了一个库函数，它是m p i 的核心根据1 9 9 4 年发布的 1 4 m p l l 0 标准，该库函数包含了1 2 9 个函数，在m p l 2 0 标准中有2 0 0 多个库函数 而编写一个简单的m p i 程序只使用其中最基本的6 个函数即可，这6 个函数为1 1 7 l ： 0 ) m e l i n i t 启动m p i 计算： (2)mpicomms i z e 确定进程个数： ( 3 ) m l i c o m m r a nk 确定进程标识符： o ) m p i s e n d 发送数据： ( 5 ) m p l r e c v 接收数据； ( 6 ) m p l f i n a li z e 结束m p i 计算 目前比较流行的可移植并行程序编程环境有消息传递接m p i c h 、p v m 、 l i n d a 等，它们实际上都是一些函数库的集合，可以被嵌入到f o r t r a n 9 0 9 5 、c 、c + + 等高级语言程序中。本文主要侧重m p i c h l 3 l 及其在p c 集群计算机系统中的主要使 用方法 2 4 并行计算模型概述 在并行系统上求解问题，首先要写出求解问题的并行算法。并行算法是在并 行计算模型上设计出来的，而并行计算模型是从不同的并行系统体系结构模型中 抽象出来的。可以说并行计算模型是并行系统硬件和