（计算机应用技术专业论文）基于移动agent的网络并行计算技术研究与应用.pdf

南京航空航天大学硕十学位论文 摘要 随着人们对计算速度要求的不断提高，传统的单机计算已经无法满足应用要求。 近年来，随着廉价高性能个人计算机和工作站以及高速网络技术的发展，基于网络 的并行计算研究已经成为当前并行计算领域研究与应用的热点。但是，并行计算平 台如p v m 、m p i 在稳定性、可扩充性等问题上没有得到很好的解决。 移动a g e n t 具有自治性、反应性、移动性等特点，它为并行计算提供了一种新 的计算模式，并弥补了一些并行软件平台的不足，具有良好的移植性、可扩展性、 灵活性。 为了提高和改善并行计算性能，本文将移动a g e n t 与并行计算相结合，提出一 种基于移动a g e n t 的网络并行计算模型。本文分析了并行计算技术的现状与发展趋 势，并分析了机群系统在并行计算中的应用，以及移动a g e n t 的技术特性。在综合 分析移动a g e n t 技术和并行计算技术的基础上，提出了基于移动a g e n t 的网络并行 计算模型a b p c 。本文对a b p c 相关模块进行了详细的论述，并对设计a b p c 模型过程中可能遇到的问题进行了专门探讨。文章结合航空公司运行经济分析与航 班优化系统的建设，对a b p c 模型的应用及其实现效果进行了阐述、分析和评估， 并对a b p c 模型提出了进一步改善的建议。 关键词：移动a g e n t ；并行计算；a b p c ；移动a g e n t 平台：m p i ；p v m 机群系 统 基丁移动a g e n t 的网络并行计算技术研究与应用 a b s t r a c t w i t ht h ei n c r e a s i n gd e m a n df o rc o m p u t i n gs p e e d ，t h et r a d i t i o n a ls i n g l ec o m p u t i n gc a n n ol o n g e rm e e to u rn e e d s t h a n k st ot h ed e v e l o p m e n to ft h e c h e a ph i 曲p e r f o r m a n c e c o m p u t e r s ，w o r k s t a t i o n sa n dh i g hp e r f o r m a n c en e t w o r kt e c h n o l o g y , p a r a l l e lc o m p u t i n g b a s e do nn e t w o r kh a sb e c o m et h ef o c u so fc u r r e n tp a r a l l e lc o m p u t i n gr e s e a r c h p a r a l l e l c o m p u t i n gp l a t f o r m s s u c ha sp v m ，m p is t i l ln e e dt ob ei m p r o v e di nt e r m so f s t a b i l i t ya n d e x p a n s i b i l i t y m o b i l ea g e n tf e a t u r e sa u t o n o m y ，r e a c t i v i t ya n dm o b i l i t y i tp r o v i d e san e wc o m p u t i n g m o d e lf o rp a r a l l e lc o m p u t i n g ，a n db a s i c a l l ym a k e su pf o rs o m es h o r t c o m i n g so fp a r a l l e l c o m p u t i n gp l a t f o r m s i t i sc h a r a c t e r i z e dw i t ht r a n s p l a n t a t i o n ，e x p a n s i b i l i t ya n d f l e x i b i l i t y i no r d e rt oi m p r o v et h ep e r f o r m a n c eo f p a r a l l e lc o m p u t i n g ，t h ep a p e rp r e s e n t sap a r a l l e l c o m p u t i n gm o d u l eb a s e do nm o b i l ea g e n tb yc o m b i n i n gm o b i l ea g e n tw i t hp a r a l l e l c o m p u t i n g i t f i r s t a n a l y z e s t h ec u r r e n ts i t u a t i o na n d d e v e l o p m e n t t r e n do f p a r a l l e l c o m p u t i n gt e c h n o l o g y a sw e l la st e c h n i c a lf e a t u r e so f a g e n t o n t h eb a s i so f c o m p r e h e n s i v ea n a l y s i so fm o b i l ea g e n ta n dp a r a l l e lc o m p u t i n gt e c h n o l o g y , t h et h e s i s p r o p o s e sap a r a l l e lc o m p u t i n gm o d u l eb a s e do na g e n t 一a b p c t h i st h e s i sa l s og i v e s a t h o r o u g hi n t r o d u c t i o no ft h er e l e v a n tm o d u l e ，s u c ha sc o m m u n i c a t i o nm o d u l e ，t r a n s f o r m m o d u l ea n dd a t aa c c e s sm o d u l e i tt a k e si n t oc o n s i d e r a t i o no fp o t e n t i a l p r o b l e m si n d e s i g n i n g t h em o d u l ea n de x p l o r e d p o s s i b l es o l u t i o n s f i n a l l y , b yd r a w i n gu p o n t h e c o n s t r u c t i o no ff o p m a x ，t h et h e s i se l a b o r a t e s ，a n a l y z e sa n da s s e s s e st h ea p p l i c a t i o na n d e f f e c to f a b p ca n dm a k e ss o m es u g g e s t i o n sf o rf u n h e ri m p r o v e m e n t k e yw o r d s ：m o b i l ea g e n t ；p a r a l l e lc o m p u t i n g ；a g l e t s ；m o b i l ea g e n tp l a t f o r m ；m p i ； p v m ：n e “v o r ko fw o r k s t a t j o n s i i 承诺书 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究 工作所取得的成果。尽我所知，除文中已经注明引用的内容外，本学位论文的 研究成果不包含任何他人享有著作权的内容。对本论文所涉及的研究工作做出 贡献的其他个人和集体，均已在文中以明确方式标明。 本人授权南京航空航天大学可以有权保留送交论文的复印件，允许论文被 查阅和借阅，可以将学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其他复制手段保存论文。 ( 保密的学位论文在解密后适用本承诺书) 作者签名： 日期： 委趣 笸：2 ：塑 南京航空航天大学硕十学位论文 第一章绪论 基于网络的并行计算是指通过高速信息网络，充分利用网上资源来实现大型问题 求解的合作计算过程。近年来，由于廉价的高性能个人机和工作站以及高速网络技术 的发展，基于网络的并行计算的研究成为当前并行计算领域中最具活力的研究方向之 一。网络并行计算以其成本低，结构灵活可靠，给用户提供了一种以较少代价来实现 高性能并行计算的有效途径。基于移动a g e n t 技术的网络并行计算提供了一种新的计 算模式，它弥补了一些并行计算软件平台的不足，具有良好的移植性、可扩展性、灵 活性。 1 1 并行计算技术发展现状与趋势 从计算机诞生之日起，人们就开始努力提高计算机的运行速度，并且已经取得非 常显著的成绩。然而这种努力不久就因趋于物理器件的极限而终止。人们在研制新一 代计算机的一个共同特点就是采用并行技术。增加同一时间间隔内操作数量的技术即 所谓并行处理技术；为并行处理所设计的计算机统称之为并行计算机；在并行计算机 上求解问题称之为并行计算；在并行计算机上实现求解问题的算法可称之为并行算 法。 11 1 并行计算技术发展现状 并行处理，是一门综合性的计算机学科，它包括硬件技术，也包括算法、语言、 程序设计等软件方面的问题，当然，还包括各种理论上的探讨。严格地说，并行性有 两种含义：一是同时性，亦即并行性，指两个或多个事件在同一时间发生；二是并发 性，指两个或多个事件在同一时间间隔内发生。 当前，并行计算发展的基本状况是 1 l 】： ( 1 ) 并行计算软件的发展远远落后于并行计算体系结构的发展。 ( 2 ) 并行计算算法的应用远远落后于并行计算技术的发展。 ( 3 ) 大规模并行处理系统已不再是主要研究领域。 ( 4 ) 由高速网联成的各种类型的、规模可伸缩计算机机群，将进一步促使并行计算 应用有较大的发展。 ( 5 ) 计算系统的规模可伸缩性和可编程性已成为并行计算系统进一步发展的一对主 要矛盾。 基丁移动a g e n t 的网络并行计算技术研究与应用 我国的并行和分布计算技术研究，自6 0 年代末开始至今，按照国防科大周兴铭 院士的观点已经历了三个阶段。第一阶段，自6 0 年代末至7 0 年代末，主要从事大型 机中的并行处理技术研究；第二阶段，白7 0 年代末至9 0 年代初，主要从事向量机和 并行处理器系统研究：第三阶段，自8 0 年代末至今，主要从事m p p ( m a s s i v e l y p a r a l l e l p r o c e s s 0 0 系统及工作站机群系统研究。 我国目前在分布与并行计算方面的重点研究领域为：( 1 ) 开放式分布与并行计 算模型、算法与体系结构。( 2 ) 开放式集群计算、网格计算。( 3 ) 移动计算与自主网 技术。( 4 ) 分布式人工智能与多代理技术。( 5 ) 分布式可视化技术。 1 1 2 并行计算技术的发展趋势 近年来，机群已在很多领域得到广泛的应用，并成为并行计算研究的热点。机群， 又称为n o w ( n e t w o r k o fw o r k s t a t i o n s ) 【1 】，是指一些通过网络连接在一起的、独立的 计算机构成的具有单一系统映像的高可用、高性能、高可扩展性的计算机集群系统。 机群系统成本低廉、构造简单、使用方便，并有良好的可扩展性，性价比远高于大型 的专用计算机系统。 机群系统利用高速通用网络将一组高性能工作站或p c 机按某种结构连接起来， 在并行程序设计以及可视化人机交互集成开发环境支持下，统一调度，协调处理，实 现高效并行处理。从结构和结点间的通信方式来看，它属于分布存储系统。机群系统 中的主机和网络可以是同构的，也可以是异构的。 机群系统之所以能够从技术理论到实际应用，主要原因是它与传统的并行计算系 统相比有以下几个明显的特点： ( 1 ) 系统开发周期短。由于机群系统大多采用商用工作站和通用l a n 网络，节省了 大量的研制时间。 ( 2 ) 系统价格低。构成机群的工作站或p c 机是批量生产的，因而售价较低。 ( 3 ) 用户投资风险小。机群系统不仅是一个并行处理系统，它的每个结点同时也是 一台独立的工作站，即使整个系统对某些应用问题并行效率不高，它的结点仍然可以 作为单个工作站使用。 ( 4 ) 系统扩展性好。机群系统大多使用通用网络，系统扩展容易。 ( 5 ) 节约系统资源。出于机群系统的结构比较灵活，可以将不同体系结构，不同性 能的工作站连在一起，这样就可以充分利用现有设备。 1 ( 6 ) 用户编程方便。机群系统中，程序的并行化还是在用户熟悉的编程环境c 、c + + 或f o r t r a n 下实现的。 总之，随着网络技术的发展和对机群系统研究的深入，特别是高效通信机制的丌 2 南京航空航天大学硕_ _ = 学位论文 发，机群系统的通信性能将会接近专用的互联网络，并行编程环境和工具会更加完善， 有望在机群系统上解决粒度更细的应用问题，使并行处理系统的应用领域更加广泛。 1 1 3 网络并行计算系统的前景 基于机群的并行计算系统即网络并行计算系统在并行计算能力、内存以及磁盘的 利用上都有着巨大的潜力和很好的前景。 1 1 3 1 并行计算能力 网络并行计算系统比其他任何并行计算系统都更容易构筑，可以利用现有的计算 机网络化的成果，更好地发挥联网计算机的优势。同时，网络并行计算系统可以对新 的网络和新的处理器能尽快的加以利用，减少了用户的投资风险。 网络并行计算系统还可以充分利用现有大量商用软件的成果，具有很好的兼容 性，从而方便用户利用各种已有的工具进行编程和调试。网络并行计算系统可以在需 要时根据问题的规模扩展系统的规模，以提高系统速度，这一点是多数并行计算机所 不具备的。相应的，网络并行计算系统也可以在一部分成员机出错的情况下将其排除 出系统，并仍保持自身地正常运行，即所谓的容错性好。但对于并行机，只要有一个 成员节点出错就只好重新启动系统。网络并行计算系统的性能虽然还赶不上并行计算 机，但正在接近后者，相对来说，及其廉价的成本保证了它的高性能价格比。 1 1 3 2 巨大网络内存的利用 存储器芯片技术的发展，使得桌面系统计算机都具有极大的存储能力。通过网络， 使一些空闲的内存可以为整个网络并行计算系统做出两个方面的贡献：分别为虚拟存 储器和磁盘缓冲。而虚拟存储器与磁盘缓冲技术的运用正是大数量并行计算成功运行 的技术保证。 1 2 课题背景及研究内容 航班是航空公司的主营业务和生产方式，对航空公司的整体效益有着决定性影 响。合理、科学的编排航班有利于充分利用航空公司资源，提高航空公司经济效益。 一个航班计划的产生牵涉到航空公司的方方面面，是一个十分复杂的任务集合。目前， 有的航空公司甚至还在用手工来编排航班，既难以对航班计划做出快速准确的调整， 更难以准确地对航班计划的执行进行查询统计，这种方式已经不能满足现代航空运输 的需要。针对这个问题，我们开发了“航空公司运行经济分析与航班优化系统” ( f o p m a x ) ，旨在通过提供的多种图形化工具合理配置航空公司航班资源，使航班效 基于移动a g e n t 的网络并行计算技术研究与应用 益最大化。 在f o p m a x 系统的实际开发中我们遇到了一个比较大的问题，航班优化的基础 数据量特别大，而该系统又必须要计算大量的这些基础性数据，需要花费大量的计算 时间，系统实时性受到挑战。为解决航空公司业务复杂、数据量大等问题，我们在航 空公司i n t r a n e t 环境下结合a g e n t 技术构建并行计算应用系统，以便高效地利用资源 来提高系统运行速度，提高企业经济效益。最终达到构建更为高效、快速、稳定、安 全的企业并行计算环境的目的。 本文研究的重点是并行计算领域中的基于网络的并行计算技术，该技术充分利用 现有l a n 网络的资源来提高并行计算的性能指标。本文首先研究了并行计算技术及 现有的基于网络的并行计算环境，并研究了移动a g e n t 技术，最后提出了一种基于移 动a g e n t 的网络并行计算模型一一a b p c 。通过“航空公司运行经济分析与航班优化 系统”将本课题应用于实践，以a b p c 模型为基础对航班计划及性能优化管理系统进 行了设计和整合。 4 南京航空航天人学硕士学位论文 第二章并行计算技术研究 随着信息时代的到来，需要处理的信息量开始越来越庞大，需要解决的问题也越 来越复杂。通过提高单个处理器的运算速度和采用传统的串行计算技术己难以胜任。 因此，要有功能强大的新的计算机系统和计算技术来支援。并行计算机及并行计算应 运而生。 2 1 p c 机群系统的并行计算 近年来，人们对使用一组价格便宜、功能强大的工作站或高档p c 机组成一个并 行计算机产生了浓厚的兴趣。现代p c 机的性能不断大幅度提高，价格大幅度下降， 其性能价格比已优于工作站。特别是在我国，很少单位拥有多台工作站，而拥有多台 p c 机的单位已经十分普遍。另一个事实是，全世界熟悉p c 机的人数远大于熟悉工 作站的人数。因此，开发p c 机群上的并行计算环境是十分有意义的。 2 1 1p c 机群技术分析3 所谓p c 机群技术是指将多台p c 机通过高速局域网相互连接起来，配备一定的 并行支撑软件，形成一个松散耦合的并行计算环境，协同地并行求解同一个问题。它 们可以利用本局域网内的p c 机资源，动态地构造并行虚拟机，能提供几百亿或几千 亿次的计算性能。例如，多台p c 机通过快速以太网( 1 0 0 m b s 、相互连接，以l i n u x 操作系统为平台，配备p v m 或m p i 消息传递并行程序设计软件支撑环境，就可以构 成个p c 机群系统。 机群系统有如下一些特征：( 1 1 使用方便。机群中每个单独的节点都是传统的平 台，用户可以在他们熟悉的成熟环境下开发和运行他们的应用程序。传统的平台提供 了在工作站上运行的功能很强的程序设计环境工具，并且有成千上万种现成的为串行 执行所开发的应用程序可供使用，这些软件可以不加修改地在机群上运行。因而可以 把机群看作是一个比单个工作站吞吐量大得多、响应时间短得多的、可供多个串行用 户作业使用的巨大的工作站。f 2 1 可靠性好。机群中有多个存储器、处理机和磁盘部 件，有一个部件出现故障，其它部件仍能使用，从而保证机群能继续工作。机群中每 个节点都有自己的操作系统，一个操作系统崩溃了，其它节点仍能工作。这一点显然 比s m p 好。s m p 的存储器如有故障，就会使整个系统不能工作。s m p 只有一套操作 系统驻留在共享存储器中，操作系统崩溃，整个系统就不能工作。f 3 1 可缩放性好。 5 基于移动a g e n t 的网络并行计算技术研究与应用 机群的计算能力能随节点的增加而增加。机群中处理机、存储器、磁盘、甚至输入输 出设备都可增减。由于节点间是松耦合的，机群的节点数有可能增加到几百个，而 s m p 只能增减处理机，处理机数最多也只能有几十个，因为s m p 是紧耦合的，存储 器会成为瓶颈。f 4 、性能价格比好。机群的节点和互连网络等都用已商品化的计算机 产品做成，能大批量生产，使成本降低。因而机群的性能价格比好。国外资料表明， 在相同的性能峰值情况下，机群的价格比传统的p v p 和m p p 可以低1 到2 个数量级。 现有的机群计算环境主要是针对工作站网络。由于p c 机相对工作站价格便宜， 通用性强，因此迫切需要在p c 机群上研制并行计算环境。由于工作站机群运行的操 作系统比较单一，主要是u x i x 或类u n i x 操作系统，例如s u n o s 、a l t r i x 、a i x 等，但p c 机上可以运行的操作系统多种多样，如d o s 、s c o u n i x 、l i n u x 、x e n i x 、 w i n d o w s 等，这些操作系统之间差别很大；另外，p c 机中兼容机品种较多，因此开 发p c 机群计算环境不能简单地把工作站机群软件移植到p c 机群上。此外，工作站 操作系统相对p c 机操作系统功能十分强大，提供了比较丰富的系统调用，特别是网 络功能为用户提供了良好的程序设计接口，p c 机上的操作系统提供的功能相比还不 十分完善，因此研制p c 机群上的并行计算环境还需要解决很多问题。 2 1 2 机群并行系统负载平衡技术 在并行计算中，一个大的任务往往由许多子任务组成。所谓负载，是指被分配到 各个处理节点上并行执行的子任务。负载在并行系统的各处理节点上分布的均衡程度 称为负载平衡度 1 3 】。 从应用的角度看，任何并行环境要提高并行应用的有效性，负载平衡策略是必不 可少的。机群系统平台上的并行计算，因其异构性、特殊的网络结构和节点性能的动 态变化( 由于交互用户的介入，后台进程的运行等) ，使得负载平衡问题显得尤其重 要，因而其异构性及实际应用则变得更为复杂。当整个系统任务较多时，各节点上的 负载可能产生不均衡现象，从而会降低整个系统的利用率。负载不平衡问题解决得好 坏，直接影响到整个并行计算的性能，因此负载平衡度是影响机群并行效率的重要因 素。 在机群并行系统中，负载平衡要解决的问题主要有： ( 1 ) 系统资源使用不均。以c p u 资源为例，在并行计算中常常会出现某个节点的 c p u 处于十分繁忙的状态，而另一些节点却非常空闲。并行程序运行时系统资源状 况在动态改变，程序员很难做出准确的并行任务静态调度。因此，必须动态监视系统 的资源状况，做出准确的分配决策。 ( 2 ) 保证前台用户对工作站的优先使用权。机群并行系统是多用户系统，可能有多 6 南京航空航天人学硕士学位论文 个用户同时运作各自的作业，这时就要保证前台对工作站的优先使用权。对机群并行 系统来说，如何充分利用高度并行的系统资源，合理地安排和调度任务，充分运用各 节点的处理能力，缩短程序的响应时间，提高整个系统的吞吐率，是并行处理中必须 解决的问题，这就需要负载平衡技术的支持。负载平衡技术的核心就是调度算法，即 将各个子任务比较均衡地分布到不同的处理节点上并行计算，从而使各节点的利用率 达到最大。 一般有两种常用的负载平衡方法：静态负载平衡和动态负载平衡。在设计负载平 衡系统时应考虑到网络结构、并行机群构造( 同构或异构) 、系统利用状况( 用户数 量、系统的平均负载量、通信量等) ，以及系统的可靠性等因素。 静态负载平衡就是根据机群中各计算结点处理能力上的差异，将工作量相应地分 配到各计算结点上，处理能力强的计算结点分配更多的工作。这种负载平衡方式，仅 考虑了各计算结点处理能力上的差异，而并未考虑各计算结点上负载的波动情况，仅 当整个机群中的计算结点均单独用于该并行应用软件时才有效。当各计算结点还用于 日常的业务时，采用这种负载平衡方式并不能取得令人满意的效果。 动态负载平衡就是应用软件能在运行过程的各个阶段中，不断地根据运行时各计 算节点的负载情况，将工作量动态地分配到各个计算结点上，负载轻的计算结点分配 较多的工作。因为机群的工作通常是建立在不影响各计算结点原有工作的前提下，动 态负载平衡在机群并行系统中占据十分重要的位置。本文后面设计的a b p c 模型采用 的就是动态负载平衡的策略。 2 1 3 动态负载平衡策略 动态负载平衡的策略包括四个部分：转移策略，选择策略，定位策略和信息策略 1 v l 。 转移策略：用来决定一个节点是否处于合适的状态来参与任务转移。参与转移时， 要么是发送者或是接收者，如果节点负载超过t 1 ( 发送阀值) ，转移策略将该节点确 定为发送者；如果节点负载小于t 2 ( 接收阀值) ，转移策略将它确定为远程任务的接 收者( t i t 2 ) 。另一个转移策略是相关转移策略，例如，若一个节点的负载在全系 统中最低，则被确定为接收者。 选择策略：一旦转移策略确定了一个节点是发送者，选择策略就要从本地选择一 个任务来转移。如果选择策略不能发现一个合适的任务来转移，这个节点就不在被认 为是发送者，最简单的方法是选一个导致节点成为发送者的新近产生的任务，这种任 务转移开销比较小。选择策略需要考虑以下几个因素：转移的额外开销尽量小，被选 择的任务应该足够大，以值得花去额外开销。 7 基于移动a g e n t 的网络并行计算技术研究与应用 定位策略：定位策略的作用是为准备转移的负载选择合适的“转移伙伴”。在非 集中式算法中一个广泛采用的方法是轮转搜寻，即由一个节点询问其他每个节点以确 定是否可以共享负载。轮转搜寻可以采取串行和并行两种方式。在集中式算法中，一 个指定的节点作为协调者来定位、收集系统信息，发送者从协调者处获得系统信息来 选择接受者。在非集中式算法中定位接收节点有下述三种方案： ( 1 ) 随机：是最简单的定位策略，因为不需要使用远程状态信息。任务被随机地选 择发送到一个节点，而不必彼此交换信息。但这样会带来一些问题，特别是当全系统 的负载比较平均时，随机定位策略可能使所有节点都忙于转移任务而没有时间去执行 他们。为此，必须限制轮询次数。 ( 2 ) 阀值：为避免没有必要的转移，首先要查看转移到某个节点上是否会造成该节 点负载超过某个阀值。如果没有，就将任务转移到该节点；否则，再去查看其他节点。 为了减少额外开销，必须限制轮询次数。 ( 3 ) 最短：最短定位策略不仅能决定哪些节点可以接收任务，还能决定哪些节点接 收任务更好些。与前两种定位策略一样，它也要轮询，但确定选择具有最短任务队列 的节点作为转移对象。 信息策略：信息策略决定系统中其他节点的状态信息如何收集、从哪里收集、收 集哪些信息等。有三种类型的信息策略。 ( 1 ) 要求驱动策略：在非集中式策略中，一个节点只有在成为发送者或接收者时才 能收集其他节点的信息。 ( 2 ) 周期策略：定期地收集信息，可用于集中式算法，也可用于非集中式算法中。 ( 3 ) 状态改变驱动策略：在自身状态改变到一定程度时，节点向外发布它的状态信 息。从排队论看，当任务到达的速度快于系统处理的速度时，会造成不稳定性：从算 法看，当某引进参数或策略设置不恰当时，会使任务频繁转移而造成系统“抖动”。 22 基于机群的并行程序设计环境 目前通用的网络并行计算环境可分为两种：基于消息传递的计算环境和基于共享 内存的计算环境。 基于消息传递的并行计算环境主要有p v m ，m p i ，e x p r e s s ，l i n d a ，p 4 等，它们 之间的信息交换主要是通过数据包的发送和接收。当并行任务中的一个成员进程告诉 另一个进程某些消息时，它便将这些信息打包发送给对方，而对方则对应的进行接收 操作。这样对方就有了一个该信息的副本。 基于共享内存的并行计算环境包括t r e a d m a r k s 、q u a r k s 、c v m 以及j l a j i a 等。 这些系统中，并行应用的成员进程之间的信息共享是通过共享地址空间实现的。 8 南京航空航天大学硕士学位论文 2 2 1 基于消息的并行计算环境 所谓基于消息传递的并行程序设计，是指用户必须通过显示地发送和接受消息来 实现处理机间的数据交换。此时，每个并行进程均有自己独立的地址空间，循环之间 的访问不能直接进行，必须通过显示的消息传递来实现。因此，并行开销比较大，主 要适合于大粒度的并行计算。 由于消息传递的程序设计要求用户很好地分解问题，组织不同进程间的数据交 换，并行计算粒度大，特别适合于大规模可扩展并行算法。当处理机台数较多时，只 有消息传递才能充分发挥并行机的潜在性能。因此，消息传递是当前并行计算领域的 一个非常重要的并行程序设计方式。 消息主要有两类 1 8 1 ，一种是普通的消息，即数据块，并行进程间通过它来进行数 据交换；一种是活跃消息，一它是一种特殊的消息，该消息在接收端激活一个指定函数 的执行。 消息传递库的主要功能有f 1 8 】： ( 1 ) 点到点通信机制消息的传送只涉及一个发送者和一个接受者，发送者通常要指 定要发送的消息、消息的接收者和消息的类型，而接收者通常要指定要接收的消息、 消息的发生者和消息的类型。 ( 2 ) 全局通信机制在并行计算中，存在一些通信需要所有并行进程参加，称之为全 局操作。常见的全局操作主要包含全局同步操作、全局广播操作、归约计算、并行前 缀计算、连接与分布操作、全局移位操作等。 ( 3 ) 并行控制与任务组机制。 ( 4 ) 处理机拓扑机制。 ( 5 ) 并行i o 机制。 消息传递方式是广泛应用于多类并行机的一种模式，特别是那些分柿存储并行 机。下面分别来介绍两种常用的消息传递并行计算环境m p i 和p v m 。 2 2 2 并行虚拟机p v m p v m 是并行虚拟机( p a r a l l e l v i r t u a lm a c h i n e ) 的简称，p v m 计划是1 9 8 9 年夏天在 美国橡树岭国家实验室开始的。p v m 计划的目标是产生一种可将某一网络上的计算 机连接起来从而建立并行虚拟计算机的软件，促使这样的一组计算机能够被协同使 用，以进行并发或并行计算。 p v m 是一个分布式计算平台，建立在以u n i x 为操作系统、基于t c p i p 协议、 异构的网络环境中。p v m 是一套软件工具及程序库的集合，它提供了一个可以让用 户在其中利用现有硬件有效而简单地开发并行程序的统一模型，它将一组多机种网络 9 基于移动a g e n t 的网络并行计算技术研究与应用 化的计算机系统看作是单个并行虚拟机，对用户而言，其面对的就是一台资源丰富、 功能强大的并行计算机。 p v m 系统经过过去若干年的发展，在各种规范方面已逐渐成为一种适用于分布 式和并行处理的可行性技术。p v m 系统由两大部分组成。系统的第一部分是一个称 为p v m d3 的守护程序，有时缩写为p v m d ，它驻留在构成虚拟机的所有计算机上。 守护程序是在后台执行的一种程序，在需要时随时准备完成一个操作。它通常是在开 始时启动的一种无人值守的被挂起的进程，它等待某种事件发生，自动地被激活，执 行作业，然后终止或将自身挂起，等待下一事件。f 邮件程序就是守护程序的一个例 子，它在后台运行，处理计算机上的所有输入和输出电子邮件。1 当用户指定了构成 并行虚拟机的节点后，启动p v m ，就会在相应的节点上各自启动一个p v m d3 进程， 它们之间可以互相通信，共同管理各并行任务的执行和通信，从而构成了一个并行虚 拟机。并行任务之间的通信实际上是通过各p v md3 进程来实现的，因此每个p v m d3 进程都起着不可估量的作用。由于p v m d3 是在后台运行的，因此它对于虚拟机 中的机器完成其它工作毫无影响。用户可在任意主机上从一个u n i x 提示开始执行 p v m 应用，多用户可以配置重叠的虚拟机，并且每个用户可以同时执行若干个p v m 应用。 系统的第二部分是个p v m 接口例行程序库。它包含各种功能完备的原语，这 些原语主要用于协调应用任务。该程序库包括那些用于消息传递、创建进程、协调任 务以及修改虚拟机等用户可调用例行程序。p v m 可在体系结构互不兼容的计算机网 络上透明地处理所有消息路径选择、数据转换及任务调度等。p v m 计算模型是基于 由若干个任务组成的应用，所有任务通过这个标准接口例行程序库来访问p v m 资源。 p v m 具有以下主要特点【2 0 l ：( 1 ) p v m 是一个可以运行在异构的硬件环境的编程 环境；( 2 ) p v m 许多函数的语义很自由；( 3 ) p v m 的消息传递语义比较简单。 简言之，p v m 具有通用性强、系统规模小、使用方便等优点，已能在国际上所 有的并行计算机上运行。 2 2 3 消息传递界面m p l m p i 是一个新的消息传递标准，是由m p i 委员会在1 9 9 2 年至1 9 9 4 年举行的一 系列会议上逐渐产生的。m p i 能用于大多数并行计算机、计算机群和异构网络环境， 能达到较高的数据传输效率，同时还具备了公共软件包和厂家专用软件包的优点。除 此之外，由于m p i 建立在多种可靠的消息传递库的基础之上，所以能博采众长，扬 长避短，使m p i 的功能更加丰富和完善。 m p i 的设计目标包括：( 1 ) 可移植性和易用性；( 2 ) 有效的通信；( 3 ) 适合异构 l o 南京航空航天大学硕士学位论文 环境；( 4 ) 可靠性。 简言之，m p i 的目标是开发一个广泛使用的写消息传递程序的标准，所以该环境 必须是一个可使用的，可移植的，有效的，灵活的消息传递标准。 m p i 的特点f 12 】如下：( 1 ) m p i 有完备的异步通信：使得s e n d ，r e c e i v e 能与计算 重叠；( 2 ) m p l 是被正式的详细说明的，它已经成为一个标准，对m p i 的所有实现 必须是建立在已有的含有该确定语言的标准之上；( 3 ) m p i 是完全可移植的，只须要 重新编译便可运行在各种实现上；( 4 ) 可以很有效的在m p p 上或c l u s t e r 上用m p i 编程，m p i 的虚拟拓扑反映了应用程序所申请的一组结点的通信模式，在m p p 上实 现的m p i 便可以利用这种信息来优化处理器间的通信路径。 m p i 能采用的通信协议比较丰富，有的协议还不需要调用操作系统提供的通信功 能，因此效率较高。另外，m p i 程序的执行不需要任何守护进程，其各个并行任务之 间的信息传递是直接进行的，因此m p i 比p v m 的通信效率高。 2 3 并行算法设计 并行算法设计就是将一个任务分解为多个可同时执行的子任务，这些子任务分别 运行在不同的处理器上，通过相互之间的数据交换完成同一个任务。 23 1 并行计算模型 并行计算模型为并行算法和并行计算机系统结构的设计和分析提供具有指导意 义的理论界面和模型，是并行计算研究的重要领域。在并行计算模型的研究中，人们 主要从如下两方面寻求合适的参数以及它们对性能的影响程度，并通过性能公式加以 表达，据此来分析、评价算法。( 1 ) 处理器的计算能力和特性。主要是并行机的硬件 并行度、计算的同步性、异步性、同构性、异构性以及并行的层次等。( 2 ) 计算所需 数据的实际供数方式和能力。主要是存储层次，如访问、通信、i o 等特性。 一般而言，并行计算模型可分为专用并行结构和通用并行结构，所谓专用并行结 构是专门为有效解决一类特定问题而设计的一种并行结构，如一类求解排序和选择问 题的比较器网络。所谓通用并行结构是为解决广泛应用问题而设计的一种并行结构， 通常可分为s i m d 和m i m d 两大类。他们可分别再细分为不同互连结构的s i m d 和 m i m d 计算模型，和共享存储的s i m d 和m i m d 计算模型。 1 不同互连结构的s i m d 模型 不同互连网络连接的s i m d 机器，有两种常用的组态：处理器一处理器组态和处 理器一存储器组态。前者适合于处理器和存储器数目相等的场合；后者当存储器数目 多于处理器数目时尤为合适。但从算法设计角度看，两者并无本质区别。 1 1 基于移动a g e n t 的网络并行计算技术研究与应用 2 共享存储的s i m d 模型 共享存储器模型( s i m d - - s m ) 是指所有的处理器之间采用读，写一个公共的共 享存储器而相互通信。理想的情况是：当共享存储器的容量充分大时，在任何时刻， 任何一个处理器均可通过共享存储器的某一单元而与任何其他的处理器相互交换数 据。这时，共享存储器相当于一个全连接的交叉开关。 3 共享存储m i m d 模型 该模型就是前面所介绍的多处理机系统。其中，各处理器之间以共享公共存储器 中的全局变量通信。在m i m d - - s m 模型上所发展的算法，如异步并行算法，其运行 时间主要是求解问题的计算时间。在m i m d - - s m 模型中可以使用较多的处理器。 4 通信链接的m i m d 模型( m i m d - - c l ) 该模型各处理器之间用通信网络以信息方式交换数据。在该模型上发展的算法如 分布式算法，其运行时间主要是由通信开销所决定。在实际使用这种模型时，处理器 的数目通常比问题的规模要小。网络并行计算采用的基本上就是这种模型。 2 3 2 并行算法的一般概念 算法是解题方法的精确播述，他是一组有穷的规则，这些规则规定了解决某一特 定类型问题的一系列运算。所谓并行算法可以解释为：适合于在各种并行计算机上求 解问题和处理数据的算法。下面给出与并行计算相关的一些概念 2 1 】。 2 3 2 并行算法 是一些可同时执行的诸进程之集合，这些进程互相作用和协调动作从而达到对给 定问题的求解。 并行算法可从不同的角度加以分类：数值计算和非数值计算的：同步的、异步的 和分布式的，s i m d 机器上的和m i m d 机器上的等等。 23 2 2 数值计算 主要研究相关问题计算、矩阵与多项式运算、线性与非线性方程组求解、矩阵特 征值问题计算、非线性方程求根、微分方程数值解，离散变换、最优化问题计算和大 整数分解等基本数学问题的并行算法研究，并将其应用于各领域科学与工程计算和大 型数据处理中。基本上是属于数值分析的范畴。 2 3 2 3 非数值计算 是指基于关系运算的一类诸如排序、选择、搜索、匹配以及图论等方面的计算问 题。基本上届于符号处理的范畴。如字符、数字、图形或别的一些记号。 1 2 南京航空航天大学硕十学位论文 于是研究数值和非数值计算问题的并行算法分别称为数值计算的并行算法和非 数值计算的并行算法。 2 3 2 4 同步算法 所谓同步并行算法是指算法的诸进程集合中，某些进程中的若干操作要等待另一 些进程中的某些操作执行之后才能执行的算法。由于进程的执行要依赖于信息交换和 数据输入，因此，导致全部进程需要同步在一个给定时钟上，以等待较慢进程。 一般而言，运行在s i m d 机器模型上的并行算法称为同步并行算法 2 3 2 5 异步算法 所谓异步并行算法是指进程集合中的所有进程间无需等待，进程间的信息交换或 通过动态地读公用存储器中更新的数据来实现，或随机地相互使用对方送来的信息。 这里的“动态地”与“随机地”是强调进程既不等待其他进程更新数据，也不等待传 送信息，因此，进程不会出现暂时的封锁，但对存储器的并行存取会发生冲突，使某 些进程在存取公用变量时有小的延迟。 一般而言，运行在m i m d s m 机器模型上的并行算法称为异步并行算法。 2 3 2 6 分布式算法 是指由通信链路连接的多个场点或节点协同完成某项计算任务的算法。一般而 言，运行在m i m d c l 机器模型上的算法称为分布式算法。 2 3 3 并行算法的评估 评估一个并行算法性能的好坏要从以l - z 个部分分析：( 1 ) 并行算法的成本；( 2 ) 加速比； ( 3 ) 并行算法的效。 2 3 3 1 并行算法的成本：c ( n ) 并行算法的成本c ( n ) 定义为并行算法的运行时间t ( n ) 与并行算法所霞的处理器数 目p ( n ) 的乘积，即c ( n ) = c ( n ) + p ( n ) 。 换句话说，成本等于求解一问题时总的执行步数。 如果求解一个问题的并行算法之成本，在数量级上等于最坏情况下串行求解此问 题所需的运行时间，则称这样的并行算法是成本最佳的。 2 3 3 2 加速比：s p ( n ) 令t 。( n ) 是求解一问题的最快的串行算法运行时间：t p ( n ) 是求解同一问题的并行算 1 3 基_ 丁二移动a g e n t 的网络并行计算技术研究与应用 法的运行时间，则加速比s p ( n ) 可定义为：s p ( n ) = t 。( n ) t p ( n ) a 可见，s 。( n ) 是度量算法并行性对运行时间的改进的程度。很清楚，s j ，( n ) 越大，并 行算法越好。理想情况下，s 。( n ) = p ( n ) ，但实际上是达不到的，因为在绝大多数情况 下，所求解的原始问题是不可能分解成1 3 个子任务，而每个运行在一个处理器上所需 时间为1 n 。同时并行计算机运行时还有额外的开销。事实上，因为任何并行算法都 能在同一串行计算机上模拟，因此，t 。( n ) p ( n ) 4 t p ( n ) ，从而1 s p ( n ) p ( n ) 。 2 3 3 3 并行算法的效率：e p ( n ) 有时候，一个并行算法虽然有好的加速，但处理器的利用率可能很低，特别是当 处理器的数目p ( n ) 不固定的情况下，s p ( n ) 不是一个最好的评价标准，为此提出并行算 法效率的概念。它可定义为加速比与处理器数目之比，即e ，( n ) = s ，( n ) p ( n ) 。 1 4 南京航空航天人学硕士学位论文 第三章移动a g e n t 技术研究 a g e n t 技术起源于人工智能，a g e n t 是指模拟人类行为与关系、具有一定智能并 能自主运行和提供相应服务的程序。随着网络技术的发展，可以让a g e n t 在网络中移 动并执行，完成某些功能，这就是移动a g e n t 的思想。 3 1 移动a g e n t 系统 2 0 世纪9 0 年代由g e n e r nm a g i c 公司在推出商业系统t e l e s c r i p t 时提出了移动 a g e n t 的概念，简单的说，移动a g e n t 是一个能在异构网络上自主地从一台主机迁移 到另一台主机，并可与其他a g e n t 或资源交互的程序。实际上它是a g e n t 技术与分布 式计算技术的结合。 3 ，1 ，1 移动a g e n t 概述 移