（通信与信息系统专业论文）对不同环境下集群系统作业提交方法的研究与改进.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除了特 别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的研究成 果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明并表示了谢 意。 作者签名：整盛日期：墨翌2 ：参、j 2 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即 学校有权保留送交 论文的复印件，允许论文被查阅和借阅：学校可以公布论文的全部或部分内容，可以 采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此规定。 作者签名：导师签名： 对不同环境下集群系统作业提交方法的研究与改进 摘要 近年来，集群技术成为国际上并行及分布式计算领域非常活跃的研究课题。 其中，很多并行技术都在集群系统上得到了实现。 肿i ( m e s s a g ep a s s i n gi n t e r f a c e ) 是一种消息传递编程模型，在大规模集 群型并行机和网格平台中被广泛使用，同时它也是一个标准库的规范，其设计目 标是高效率和可移植性。m p i 已经成为最流行的用于并行编程的消息传递标准， 有多种不同的m p i 实现，m p i c l t 是其中应用得最广泛的一种可移植的实现。 提高集群通信的效率和减少通信时间对集群系统的整体性能至关重要。本文 首先测试了基于s 肝( s y m m e t r i cm u l t i p r o c e s s o r ) 结点的集群并行计算机上 m p i c h 通信性能，包括点对点和集群通信，分析了其通信性能和执行效率。 在m p i 并行计算系统中，从两方面可以实现通信性能的优化。一个是w p i 并行计算程序的通信模式，另一个是m p i c h 的作业提交方法。 在集群并行机系统中，通信时间取决于许多因素，如结点数、网络带宽、拓 扑结构、还有软件算法等。到目前为止关于程序层面上的通信模式被研究得很多， 以期达到提高通信效率的目的，相当多的论文也都围绕此展开，所以通信模式的 定义也逐渐成熟起来。但是由于以往计算机规模比较小，系统内部所需要的通信 时间特别是作业提交过程所花费的时间往往为人们所忽略，随着系统规模的不断 扩大，这部分对整体性能的影响也在不断扩大，因此减少系统开销对提高整个并 行计算机的效率已变得非常重要，对此本文将进行重点讨论。 本文通过分析当前m p i c h 的作业提交方法，提出了一系列改进算法，以期达 到减少通信时间，优化通信性能的目的。并在由1 6 个结点所组成的s m p 集群系 统中进行了性能测试。 以上讨论都是只针对同构网络而言的，对于异构的集群式网络，情况可能有 所不同，各结点不同的通信性能会影响到整个集群通信性能的优化，在同构网络 中最优的算法此时不一定最优。针对这种情况，本文还研究了象c o w ( c l u s t e ro f w o r k s t a t i o n ) 集群式系统这样的异构网络，针对不同的异构情况提出了进一步 改进的作业提交算法，并且在模拟的环境中得到了验证。 复旦大学硕士学位论文 4 对不同环境下集群系统作业提交方法的研究与改进 关键词：肝i c i i ，s 肝，c o w ，集群，作业提交，通信性能 复旦大学硕士学位论文5 对不同环境下集群系统作业提交方法的研究与改进 a b s t r a c t r e c e n t l y c l u s t e rb e c o m e sa na c t i v ei n t e r n a t i o n a lr e s e a r c ht o p i ci n p a r a l l e la n dd i s t r i b u t e dc o m p u t a t i o nf i e l d s a n dm a n yp a r a l l e lt e c h n i q u e s h a v eb e e na c h i e v e do nt h ec l u s t e rs y s t e m m p ii sam e s s a g ep a s s i n gp r o g r a m m i n gm o d e l t h em o s tu n i v e r s a l p r o g r a m m i n gm o d ef o rl a r g es c a l ec l u s t e r sa n dg r i dc o m p u t i n gp l a t f o r m s ， a n da l s oi sas p e c i f i c a t i o nf o ras t a n d a r dl i b r a r y i t sd e s i g np u r p o s e i sh i g he f f i c i e n c ya n dp o r t a b i l i t y m p ih a sb e c o m et h em o s tp o p u l a r m e s s a g ep a s s i n gs t a n d a r df o rp a r a ll e lp r o g r a t m i n g t h e r ea r es e v e r a lm p i i m p l e m e n t a t i o n sa m o n gw h i c hm p i c hi st h em o s tp o p u l a ro n e f i r s t ，t h i s p a p e rd i s c u s s e sa n dt e s t st h ep e r f o r m a n c eo fm p i c ho v e rs 忡n o d e s i n c l u d i n gp o i n t t o - p o i n ta n dc o l l e c t i v ec o m m u n i c a t i o n ，a n da l s oa n a l y z e s t h ep e r f o r m a n c ea n de f f i c i e n c y t h e r ea r et w o w a y st oa c h i e v eo p t i m i z a t i o no fc o m m u n i c a t i o n c a p a b i l i t i e si n 船ip a r e l l e lc o m p u t i n gs y s t e m o n ei sc o m m u n i c a t i o nm a d e o fm p ip a r e l l e lp r o g r a m ，a n o t h e ri sm p i c hj o bs u b m i s s i o n i nm p i ， c o m m u n i c a t i o nm o d ec a nb ed i v i d e di n t op o i n t 。t o 。p o i n tm o d ea n dc o l l e c t i v e m o d e i nc l u s t e r ，t h em o s tc o m m o nm o d e l so fp o i n t t o - p o i n tm o d ea r el o g p m o d ea n dl o g g pm o d e l o g pi ss u i t e dt os h o r tm e s s a g ea n dl o g g pi ss u i t e d t ol o n go n e t h ec o l l e c t i v ec o m m u n i c a t i o ni n c l u d e sb r o a d c a s t ，o n e - t o a l l ， g a t h e r ，a l l t o - a l la n ds oo i l a c h i e v i n ge f f i c i e n c yo fc o l l e c t i v ec o m m u n i c a t i o no p e r a t i o n sa n d d e c r e a s i n gc o n n u n i c a t i o nt i m ea r eb o t ho fp a r a m o u n ti m p o r t a n c ef o rt h e o v e r a l lp e r f o r m a n c eo f c o l l e c t i v es y s t e m i nc o l l e c t i v es y s t e m s ， c o m m u n i c a t i o nt i m ed e p e n d so nm a n yf a c t o r ss u c ha st h en u m b e ro fn o d e s ， t h eb a n d w i d t h ，t h et o p o l o g y ，a n da l s ot h es o f t w a r ea l g o r i t h m s of a r ， c o m m u n i c a t i o nm o d e su p o nt h ep r o g r a m m i n gl e v e la r ew e l ls t u d i e d ，i no r d e r t oe n h a n c ec o m m u n i c a t i o he f f i c i e n c y h o w e v e r ，t h ec o m m u n i c a t i o nt i m ei n 复旦大学硕士学位论文 6 对不同环境下集群系统作业提交方法的研究与改进 t h em p i c hs y s t e m , e s p e c i a l l yt h et i m ej o bs u b m i s s i o ns p e n d s ，i so f t e n n e g l e c t e d t h i sp a p e ra n a l y z e st h ec u r r e n tm p ij o bs u b m i s s i o nm e t h o d ，a n d p r e s e n t ss o m en e wm e t h o d st oa c h i e v et h et a r g e to fr e d u c i n gc o m m u n i c a t i o n t i m ea n do p t i m i z i n gc o m m u n i c a t i o np e r f o r m a n c e a n dt h e nt e s tt h e mi na s m pc l u s t e rm a d eo f1 6n o d e s b u tf o r t h eh e t e r o g e n e o u sc l u s t e ro fw o r k s t a t i o n ，t h i n g sa r es o m e w h a t d i f f e r e n t d i f f e r e n tc o m m u n i c a t i o nc a p a b i l i t i eo fw o r k s t a t i o n sw i l l a f f e c tt h eo p t i m i z a t i o no ft h ew h o l ec l u s t e r t h eb e s ta l g o r i t h mi n h o m o g e n e o u sc l u s t e rm a yn o tb et h eb e s to n ea tt h i st i m e a i m i n ga ti t ， t h i sp a p e rp r e s e n t so t h e rj o bs u b m i s s i o na l g o r i t h m sf o rt h eh e t e r o g e n e o u s c l u s t e r sl i k ec o wc l u s t e r i no u rs i m u l a t e dc i r c u m s t a n c e s ，t h er e s u l t d e m o n s t r a t et h a tt h e r ei ss i g n i f i c a n tp o t e n t i a lf o ro u ra p p r o a c h e st ob e a p p l i e dt o w a r d sj o bs u b m i s s i o n k e yw o r d s ：m p i c h ，s m p ，c o w ，c l u s t e r ，j o bs u b m i s s i o n ，c o m m u n i c a t i o n p e r f o r m a n c e 复旦大学硕士学位论文 7 对不同环境下集群系统作业提交方法的研究与改进 第一章绪论 1 1 集群式系统 集群式计算机系统在并行计算领域正受到越来越大的关注和欢迎，因为其 相对于昂贵的专用并行计算机来说是一种既经济又实惠的选择。它具有性价比 高、可靠性高、可扩展性好、使用方便、应用领域广等特点。简单的说，集群 ( c l u s t e r ) 就是一组通过网络互连的计算机，它们作为一个整体向用户提供计算 资源。这些单个的计算机系统就是集群的结点( n o d e ) 。一个理想的集群是，用户 从来不会意识到集群系统底层的结点，在他她们看来，集群就是一个系统，而非 多个计算机系统。并且集群系统的管理员可以比较方便地增加和删改集群系统的 结点。在基于共享内存的s m p 并行机与分布式内存的并行计算机集群等硬件环境 下可以求解一大类复杂的科学与工程计算问题，并行计算编程技术的进步也使 得并行计算已经开始渗透并普及到各个领域和方面。一个并行处理系统主要由并 行平台( 操作系统和硬件) 与并行编程和求解应用问题的算法构成。 c l u s t e r 集群技术可定义为：一组相互独立的服务器在网络中表现为单一的 系统，并以单一系统的模式加以管理。 对于集群系统的主要优点，可简单总结如下； 1 高可扩展性：对于大多数应用程序，集群系统的性能随着c p u 个数的增 加而增加，有些程序几乎可以达到线性增加。 2 高可用性：集群中的一个结点失效，它的任务可以传递给其他结点。可 以有效防止单点失效。 3 高性能；可有效突破其他类型并行计算机处理器规模的限制，提高并行 计算机的总体性能。 4 高性价比；可以采用廉价的符合工业标准的硬件构造高性能系统。 集群式系统一般可以分成两类，致力于提供高度可靠服务的高可用( h i g h a v a i l a b i l i t y ) 集群，简称眦集群，以及致力于提供单个计算机所不能提供的强 大计算能力的高性能计算( h i g hp e r f o r m a n c ec o m p u t i n g ) 集群，简称h p c 集群。 其中h a 集群注重在它的高可用性和高可靠性上面，一般企业级的用户才使用这 复旦大学硕士学位论文 8 对不同环境下集群系统作业提交方法的研究与改进 种集群。这种集群一般采用的是容错技术和均衡负载技术。而h p c 集群就是采用 集群技术来实现高性能计算，主要包括大规模科学问题，像天气预报、地形分析 和生物制药等以及存储和处理海量数据，像数据挖掘、图象处理和基因测序等等。 相比较于h a 集群，盱c 集群运行m p i 、p v m 等并行程序时，要求更高的计算速度 和更低的通信延时，其性能主要取决于结点的规模、各结点的c p u 处理速度、内 存大小以及通信子系统的处理速度等。 1 2 并行编程模型 目前两种最重要的并行编程模型是数据并行和消息传递，两者的比较可见表 1 1 。数据并行编程模型的编程级别较高，编程相对简单，但仅适用于数据并行 问题，对于非数据并行类的问题一般难以取得较高的效率。而消息传递编程模型 的编程级别相对较低，可以有更广泛的应用范围。消息传递即各个并行执行的部 分之间通过传递消息来交换信息，协调步伐以及控制执行。灵活性和控制手段多 样化是消息传递并行程序能够提供高的执行效率的重要原因。消息传递是相对于 进程间通信方式而言的，并且与具体的并行机存储模式无关，任何支持进程间通 信的并行机均可支持消息传递并行程序设计。因此，目前大量的并行程序设计是 消息传递并行编程模式的。 对比内容数据并行消息传递 程序级别高 低 适用的并行机类型 s i 佃s p 姗s i 如m i 如s p 肋m p 锄 执行效率依赖于编译器高 地址空间单一 多个 存储类型共享内存分布式或共享内存 通信的实现编译器负责程序员负责 问题类数据并行类问题数据并行、任务并行 目前状况缺乏高效的编译器支持使用广泛 表1 1 数据并行和消息传递并行编程模型 最初设计的通信系统由于出自不同的厂商，它们之间的差异较大，虽然大 复旦大学硕士学位论文 9 对不同环境下集群系统作业提交方法的研究与改进 都采用消息传递并行编程模型，但对消息传递实现的途径却各不相同，从而给提 高应用程序及其系统的可移植性和可维护性造成了许多困难。因此，旨在希望定 义一种核心库函数的语法、语义，能够统一现存的各种消息传递系统的描述，满 足用户需求以及便于厂商高效率地实现。这就导致了消息传递接d m p i 标准的产 生。 1 3并行语言 并行程序通过并行语言来表达，并行语言主要有三种产生方式： ( 1 ) 设计全新的并行语言：优点是可以完全摆脱串行语言的束缚，从语言 成分上直接支持并行，同时可以使并行程序的书写更方便自然、相应的并行程序 也更容易在并行机上实现。但是，由于并行计算至今并没有一个统一的标准，还 没有任何一种并行语言能成为被普遍接受的标准。设计全新的并行语言难度大， 工作量也很大，客观上造成了一定的困难。 ( 2 ) 扩展原来的串行语言的语法成分，使它支持并行特征：一个很好的例 子就是标注，即将对串行语言的并行扩充作为原来串行程序的注释。相对于设计 全新的并行语言，对串行语言进行并行扩充的方法实现难度有所降低，但却需要 重新开发编译器，以支持扩充的并行部分。 ( 3 ) 不改变串行语言，仅为串行语言提供可调用的并行库：这是一种对原 来的串行程序设计改动最小的并行化方法。采用这种方法，原来的串行编译器也 能够使用，不需要任何修改，编程者只需要在原来的串行程序中加入对并行库的 调用，就可以实现并行程序的设计。本文讨论的m p i 并行程序设计就属于这种方 式。 1 4课题背景 m p i 是由m p i 论坛组织开发的适用于基于分布内存的并行计算机系统的一种 消息传递编程模型，同时它也是一个标准库的规范，其设计目标是高效率和可移 植性。它已经成为最流行的用于并行编程的消息传递标准，成为事实上的并行处 理标准。肝i 几乎被所有并行计算环境( s 咿、m p p 、集群系统等) 和流行的多进程 操作系统( u n i x 、l i n u x 、w i n d o w s ) 所支持，基于它开发的应用程序具有最佳的 复旦大学硕士学位论文 1 0 对不同环境下集群系统作业提交方法的研究与改进 可移植性、功能强大、效率高等多种优点。m p i 有多种实现，包括咿i c h 、l a m - m p i 和胛i g m 等。 m p i c h 是一种m p i 可移植的实现，其设计目标是高性能和可移植性，通常应 用在基于l i n e x 平台的集群机上。每当m p i 推出新的版本，就会有相应的肝i c h 的 实现版本。在m p i c h 中限定编程接口为m p i ，而对目标机器体系结构却不加以限制， 将高性能作为目标。 1 5 作者的工作 由于在当前集群系统中，应用的最多的并行编程模型是m p i ，而m p i c h 又是 m p i 中应用的最为广泛的一种可移植的实现，因此本文选择以m p i c h 为研究对象 来研究集群系统的作业提交方法问题。 并行计算性能的提高，大致体现在两个方面。一是计算的精确性和稳定性， 二是计算所需的时间多少。其中总时间分为计算处理时间和内部通信时间。通信 时间取决于许多因素，如结点数、网络带宽、拓扑结构、还有软件算法等。而作 业提交过程所需的时间往往是并行计算内部通信中不可忽略的一部分。 用户在一个结点上开始执行i 咿i c h 程序时，m p i c h 会在系统开始并行运算之 前将这一作业的副本提交给其他所有结点，这一过程包括各结点的启动时间和结 点间的通信时间。从根结点开始发送作业到各个结点都接收到作业并开始运行的 总时间即为作业提交时间。当集群系统的结点数较少时，作业提交时间相对于并 行计算所需时间来说可以忽略不计。但在大型并行计算中，往往有成百上千个甚 至上万个结点，程序也相当复杂，这时如采用m p i c h 标准中的提交作业方法将会 花费大量的通信时间，从而影响通信性能。 通过优化m p i c h 作业提交方式，可以显著降低花费在作业提交上的通信时 间，进而提高系统的通信性能。本文分析了在当前版本的m p i c h 中所使用的作业 提交方法，即由根结点依次将作业提交给其它所有结点所存在的缺陷。当参与运 行的结点数较少时，这种方法对整体性能的影响不是太大，但随着结点数的增加， 其对系统的通信性能影响将越来越明显。基于此，我们提出了二叉树法和二倍扩 散法等一系列可以作为作业提交方式的算法，并在由1 6 个结点所组成的s m p 集 群系统中一一进行了测试和分析。比较后我们发现，二倍扩散法是最优化的作业 复旦大学硕士学位论文 1 1 对不同环境下集群系统作业提交方法的研究与改进 提交算法。但是，以上的分析都是基于同构网络所进行的，即参与通信的各结点 本身都具有相同的通信性能。如果在一个异构的集群网络中，即参与通信的各结 点处理器性能互不相同或者网络的带宽不尽相同时，情况会更加复杂一些，此时 二倍扩散法并不一定是最优的作业提交方法。对于各结点处理器速度互不相同的 情况，我们在二倍扩散法的基础上进行改进，对各结点的启动速度进行排序，采 用了一种叫排序二倍扩散法，可以达到比未排序的二倍扩散法更高的通信性能。 但二倍扩散法并非是最优的算法，于是我们给出了最优法，它可以达到更好的理 论性能。但它的缺点是系统开销大，算法复杂度高。与此类似的，我们随后也针 对网络带宽不同的异构网络提出了最优法，以期达到最短的通信延时。 1 6 内容组织 本文主要研究在同构网络和异构网络中，集群系统的m p i c h 作业提交方式的 优化，以提高系统的通信性能，减少通信延时。 本文的后续部分结构如下： 第二章对集群系统加以概述并分类。 第三章主要介绍了m p i 与m p i c h 的相关背景信息，包括各种m p i 的通信模式 和基本调用接口。 第四章是对m p i 通信性能的分析，包括点对点通信和集合通信。其中还进行 了测试与分析。 第五章中详细研究了同构网络中m p i c h 的作业提交方法，并提出了新的一系 列的算法来改进目前的作业提交方法。 在第六章中，对异构网络中的作业提交方法进行了研究，给出了最优法的算 法，同时为了降低算法的复杂度，进一步提出了一种新的次优化方法：排序二倍 扩散法，从而能够在异构网络中进一步提高系统的通信性能。 在第七章里对同构网络和异构网络中提出的各种算法进行了测试与比较，并 对测试结果进行分析。 最后，对整篇论文进行了简单的总结并对未来的工作明确了方向，作了进一 步的展望。 复旦大学硕士学位论文 对不同环境下集群系统作业提交方法的研究与改进 第二章集群系统概述 2 i 并行计算机 由于高科技领域对计算机性能提出了越来越高的要求，自从1 9 7 2 年第一台 并行计算机i l l i a c 问世以来，并行计算机的发展非常迅速。同时随着超大规 模集成电路和微处理机技术的逐渐成熟，可扩展的并行机目前已经成为并行计算 机的发展主流。 为什么要采用并行计算? 这是因为：( 1 ) 它可以加快速度，即在更短的时间 内解决相同的问题或在相同的时间内解决更多更复杂的问题，特别是对一些新出 现的巨大挑战问题，不使用并行计算是根本无法解决的；( 2 ) 节省投入，并行计 算可以以较低的投入完成串行计算的任务；( 3 ) 物理极限的约束，光速是不可逾 越的速度极限，设备和材料也不可能做得无限小，只有通过并行才能够不断提高 速度。总之，并行计算机就是能在同一时刻同时执行多条指令( 或处理多个数据) 的计算机。 一个并行处理系统主要由并行平台( 操作系统和硬件) 与并行编程和求解应 用问题的算法构成。并行编程又包括并行语言和其他工具、源程序、编译程序( 包 括预处理器、汇编程序和连接程序) 、自然并行代码等运行时间支持和其他库。 所有这些操作系统实用程序、程序设计语言、编译器以及运行时间库等环境工具 构成了并行编程环境。 2 1 1 并行计算机的分类 根据一个并行计算机能够同时执行的指令与处理的数据的多少，可以把并行 计算机分为s i m d ( 单指令多数据并行计算机) ，m i m d ( 多指令多数据并行计算机) 以及s p m d ( 单程序多数据并行计算机) 和m p m d ( 多程序多数据并行计算机) 。 s i 4 d 计算机同时使用相同的指令对不同的数据进行操作，如向量计算机和 阵列计算机都属此类。由于系统在同一控制器的控制下进行工作，各计算部件使 用相同的指令，就限制了这类系统的应用范围。而m i m d 计算机同时有多条指令 对不同的数据进行操作。s p j 4 d 并行计算机是由多个地位相同的计算机或处理器 复旦大学硕士学位论文 对不同环境下集群系统作业提交方法的研究与改进 组成的，而m p m d 并行计算机内计算机或处理器的地位是不同的，根据分工的不 同，他们擅长完成的工作也不尽相同。显然，后两种的划分粒度要比前两种大得 多。 另一种常用的分类方法根据组织结构将大型并行机系统分为六大类：单指令 多数据流机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 ) ：并行向量处理机p v p ( p a r a l l e lv e c t o rp r o c e s s o r ) ；对称多处理机s m p ( s y m m e t r i cm u l t i p l e p r o c e s s o r s ) ；大规模并行处理机m p p ( m a s s i v e l yp a r a l l e l p r o c e s s o r ) ； 工作站集群c o w ( c l u s t e ro fw o r k s t a t i o n ) 和分布共享存储d s m ( d i s t r i b u t e d s h a r e dm e m o r y ) 多处理机。s i m d 计算机多为专用，其余的5 种均属于多指令多 数据流m i m d 计算机。目前绝大多数并行机均用商品硬件构成，而p v p 计算机的 部件很多都是定制的。 在当前的并行机中，集群系统较为常见。它是由同构或异构型串行或并行计 算机通过快速局域网或广域网相互松散连接而成。 2 1 2 并行计算机的发展 目前有三种基本的并行计算机存储方式，即共享内存、分布式内存和分布式 共享内存。 采用共享内存的并行计算机，各个处理单元通过对共享内存的访问来交换信 息，协调各处理器对并行任务的处理。它的编程实现相对要简单一些，但是共享 内存往往成为性能，特别是扩展性的重要瓶颈。 采用分布式内存的并行计算机，每个处理单元都拥有自己独立的局部存储 器。各个处理器之间通过消息传递来交换信息，以协调和控制各个处理器的执行。 因此，分布式内存的并行计算机有很好的扩张性和很高的通信性能，它的应用也 相当广泛。但它有个缺点，就是为并行程序设计的消息传递语句较为复杂。 另外一种类型，即分布式共享内存并行计算机，目前的集群计算大多采用这 种形式的结构。这种结构通过提高一个局部结点内的计算能力，不仅提高了整个 系统的计算能力，而且可以提高系统的模块性和扩展性，有利于快速构造大型的 计算系统。 最初的多计算机系统多属于大规模并行计算机( m p p ) ，这类系统结点一般是 复旦大学硕士学位论文 1 4 对不同环境下集群系统作业提交方法的研究与改进 高性能专用处理部件，每个结点并不独立构成一个计算机。m p p 的代表机型有 c r a y 的t 3 d t 3 e 、t h i n k i n gm a c h i n e 的c m - 2 c m - 5 和i n t e l 的p a r a g o nx p s 等。 在早期，m p p 在超级计算机市场上取得了很大的成功，但由于采用了专用部件， 整个系统的成本较高，同时也很难有一个统一的标准。随着多计算机规模的不断 扩大，计算机系统的成本及性能价格比成为了在设计计算机系统时不得不考虑的 一个重要因素。因为批量生产可以降低成本，使用商品化的部件作为结点的集群 系统可以有效地提高系统的性价比，所以集群系统逐渐成为设计超级计算机和超 级服务器的一种主流的结构。在软件结构上，将共享内存的编程模型应用于分布 式内存的计算机上，以降低集群计算机的编程难度，这方面典型的工作就是 i n t e l 的c l u s t e ro p e n m p 。其核心思想是在编译器层面上来实现一个分布式共享 内存系统，来替代以前的在操作系统层面的分布式共享系统，使整个计算机的使 用更加灵活。 2 2 集群系统结构 集群( c l u s t e r ) 技术可定义为：一组相互独立的服务器在网络中表现为单 一的系统，并以单一系统的模式加以管理。集群有结点和互连网络两大部分组成。 结点问的连接可采用商品化的网络( 如以太网) 或其它高速网络( 如m y r i n e t 等) 。 2 2 1 集群系统的结点 对于结点来说，除了满足由交互用户单独地使用每个结点外，所有的集群 系统结点必须能一起工作，如同一个单一集成的计算资源。集群中每个结点是一 台完整的计算机，它有自己的处理器、内存、磁盘和i o 适配器，并且具有一个 标准的操作系统。根据功能不同，我们可以把集群系统中的结点划分为六种类型： 用户结点、管理结点、控制结点、安装结点、存储结点和计算结点。 1 ) 用户结点 用户结点是外部世界访问集群系统的网关，是外部访问集群系统强大计算或 存储能力的唯一入口，它是整个系统的关键点。用户登陆到此结点上编译并运行 作业。 2 ) 管理结点 复旦大学硕士学位论文 对不同环境下集群系统作业提交方法的研究与改进 管理结点是集群系统各种管理措旌的控制结点，也是网络的控制点，它监控 集群系统中各个结点和网络的运行状况，并处理集群中所有计算机的日志和报警 信息。 3 ) 控制结点 控制结点为计算结点提供基本的网络服务，如d n s 和n i s 等。同时，它也负责 调度计算结点上的作业，运行如p b s 等的作业调度程序。 4 ) 安装结点 安装结点提供安装集群系统的各种软件，包括操作系统、各种管理软件和应 用以及各种运行库。 5 ) 存储结点 存储结点就是提供存储共享的结点，是集群系统的数据存储器和数据服务 器。只有保证每台执行任务的结点都能够访问同样的数据，才能使任务可以并行 执行。存储结点就是一个通过网络共享( n f s ) 或其它方式来确保数据访问的同 步。 6 ) 计算结点 大部分集群系统中的结点都属于这个类型。计算结点是整个集群系统的计 算核心。它的功能就是执行计算。 2 2 2 集群系统的网络 在并行计算机中，为了获得高效的网络通信能力，可以从上层的软件与下层 的硬件两方面着手寻找解决办法。除了上层软件对算法的优化外，最大限度地挖 掘原始网络带宽，寻找更高速更便捷的物理层网络同样具有重要的意义。在大规 模并行计算系统中，处理器之间或计算结点之间的快速互联网络的重要程度并不 亚于处理器本身。在早期的大型计算系统中，处理器之间的通信一直被所采用的 互联网络( 通常是以太网) 延时大、带宽不足等因素所牵制；如今，m y r i n e t 、 q s n e t 、s c i 以及i n f i n i b a n d 等多种专用高速互联网络的成功应用，使得这种状况 发生很大改观的同时，也使得高性能计算系统内部互联网络的选择成了一门学 问。 高性能计算系统的互联方式有很多种，最初的机群系统是基于l a n 技术的， 复旦大学硕士学位论文 1 6 对不同环境下集群系统作业提交方法的研究与改进 也就是以最普通的以太网( e t h e r n e t ) 作为数据交换媒介。其优势在于可以方便 地增加计算结点到集群系统中，但是其缺点也很多，传输速度较慢，复杂的协议 造成非常高的延时，并且限制了扩展性。各种各样的专用高速互联网络应运而生， 最为典型的有m y r i n e t 、q s n e t ，以及最近几年兴起的i n f i n i b a n d ，它们为集群系 统提供了构建高带宽、低延时数据交换环境的可行条件。 以下是几种当今最重要的集群系统互连网络。 1 ) e t h e r n e t 以太网是当今现有局域网采用的最通用的通信协议标准，其核心思想是使用 共享的公共传输信道。该标准定义了在局域网( l a n ) 中采用的电缆类型和信号 处理方法。以太网在互联设备之间以1 0 l o o m b p s 的速率传送信息包，双绞线电缆 1 0b a s et 以太网由于其低成本、高可靠性以及l o m b p s 的速率而成为应用最为广 泛的以太网技术。以太网使用了载波侦听冲突检测( c s 姒c d ) 技术，遵循 i e e e 8 0 2 3 标准。自从1 9 8 2 年以太网协议被i e e e 采纳成为标准以后，已经历了2 0 年的风风雨雨。在这2 0 年中，以太网技术作为局域网链路层标准战胜了令牌总线、 令牌环、w a n g n e t 、2 5 ma t m 等技术，成为局域网事实标准。以太网技术当前在局 域网范围市场占有率超过9 0 。以太网接入采用异步工作方式，很适于处理i p 突发数据流，技术已有重要变化和突破( l a n 交换、星形布线、大容量m a c 地址存 储以及管理性等) 。与传统的以太网相比，除了名字以外，仅剩的特征只有帧结 构和简单性仍然保留，其余基本特征已有根本性变化。 这里的以太网包含两种类型的网络：千兆以太网和万兆以太网。 千兆以太网和高速网络相比，在性能上有着一定的差距，但它的性价比最便 宜，同时又采用标准的通讯协议，能很好的与其它设备互联，具有很好的可使用 性和可管理性。千兆以太网在对性能要求相对较低的集群系统中得到了广泛的应 用。 千兆以太网是建立在标准的以太网基础之上的一种带宽扩容解决方案。它和 标准以太网以及快速以太网技术一样，都使用以太网所规定的技术规范，如 c s 姒c d 协议、以太网帧、全双工、流量控制以及i e e e 8 0 2 3 标准中所定义的 管理对象等。同时，千兆以太网本身作为以太网络的一部分，也支持流量管理技 术，通过i e e e 8 0 2 i p 第二层优先级、第三层优先级的o o s ( 服务质量) 编码位、 复旦大学硕士学位论文 1 7 对不同环境下集群系统作业提交方法的研究与改进 特别服务和资源预留协议( r s v p ) 这些技术规范，使它的服务质量得到了保证， 同时千兆以太网还利用i e e e s 0 2 lq v l a n 支持、第四层过滤、千兆位的第三层 交换。 采用千兆以太网的好处在于：千兆位以太网将提供1 0 倍于快速以太网的性 能并与现有的1 0 1 0 0 以太网标准兼容。 万兆以太网是目前市场上最快的以太网技术，具有极低延时( 不到5 0 0 纳秒) 。 万兆以太网使用i e e e8 0 2 3 以太网介质访问控制协议( m a c ) 、i e e e8 0 2 3 以太网 帧格式以及i e e e8 0 2 3 最小和最大帧尺寸。正如1 0 0 0 b a s e x 年l l l o o o b a s e - t ( 千兆 以太网) 都属于以太网一样，从速度和连接距离上来说，万兆以太网是以太网技 术自然发展中的一个阶段。但是，因为它是一种只适用于全双工模式，并且只能 使用光纤技术，所以它不需要带有冲突检测的载波侦听多路访问协议( c s l i a c d ) 。 除此之外，万兆以太网与原来的以太网模型完全相同。 2 ) m y r i n e t m y r i n e t 是一种采用全互联纵横制交换机连接各网络适配器的高速互联技 术，它提供比e t h e r n e t 更高的带宽和更低的延时。它是m y r i c o m 公司提供的一种 基于切入式包交换的千兆位网络，m y r i n e t 是目前集群系统中应用最为广泛、技 术最成熟、高性价比的一种高速网络。m y r i c o m 公司从1 9 9 4 年就开始销售第一代 m y r i n e t 产品，当时只是作为以太网络的第二选择来实现机群系统中的结点互联， 除了i o o m b s 的高带宽外，它的主要优势是小数据量延时只有1 0 1 5 微秒，这与 当时c o n v e x 、i b m 、s g i 等公司在并行系统中使用的专有网络形成鲜明对比。此 后随着软硬件的不断升级，m y r i n e t 更是成为了集群制造者的第一选择，直到今 天这种优势依然存在。 m y r i n e t 网络具有2 5 g b s 的单向连接速度，其最新推出的m y r i - l o g 提供更高 的带宽和更低的延时。同时，新的m y r i n e t 也完全实现了与以太网的互操作性。 m y r i n e t 使用全双工链路，可以通过胖树的联接方式来扩展互联的规模，并 且可以使用远程内存存取( r e m o t ed i r e c tm e m o r ya c c e s s ，r d m a ) 对其他主适 配器卡( 称为l a n a i ) 的远程内存进行读写操作。最新一代的m y r i n e t 使用了光 纤作为信号传输线。 复旦大学硕士学位论文 对不同环境下集群系统作业提交方法的研究与改进 3 ) i n f i n i b a n d i n f i n i b a n d 网络虽然诞生的时问不长，但以其高性能特别是高带宽( 高达 3 0 6 b p s ) ，在h p c 领域得到较多的应用。同咐r i n e t 一样采用胖树结构和全双工链 路，目前它提供1 x ( 2 5 6 b s ) 、4 x ( 1 0 g b s ) 、1 2 x ( 3 0 g b s ) 三种网络连接速度， 这三种链路都是全双工的，可以同时双向传输数据。在整个体系结构上，i n f i n i b a n d 的初始设计在拓扑结构上类似光纤通道，将通过i n f i n i b a n d 中间交换机，利用嵌 入式目标通道适配器( t c a ) 把服务器内的主机通道适配器( h c a ) 与其他设备连 接起来。i n f i n i b a n d 标准定义了一套用于系统通信的多种设备，包括通道适配器、 交换机和路由器。 i n f i n i b a n d 架构由可编程交换机连接通道适配器( c h a n n e la d a p t e r s ，c a ) 组成。c a 能够被安置在服务器中( 主通道适配器，h o s tc h a n n e la d a p e r s ，h c a ) ， 或者是转换到存储设备和以太网的u o 转换器中( 目标通道适配器，t a r g e t c h a n n e la d a p t e r ，t c a ) 。基于i n f i n i b a n d 的远程内存存取( r e m o t ed i r e c tm e m o r y a c c e s s ，r d 姒) 功能，消息可以从一个h c a t c a 传递到另一个h c a t c a ，也就是 说，允许从一个h c a t c a 读写另一个h c a t c a 的内存。 i n f i n i b a n d 协议是一种分层结构。首先是物理层，它允许多路连接直接获得 3 0 g b p s 的连接速度。链路层和传输层是其体系结构中最重要的方面。链路层可提 供i n f i n i b a n d 架构q o s 功能的支持。传输层的功能包括了几个关键的方面，如数 据包分送、通道复用、基本的传输服务。i n f i n i b a n d 网络层则提供了包从一个子 网到另一个子网的路由能力。源和目的节点的每个路由包有一个全局路由头和一 个1 2 8 位i p v 6 地址。网络层也嵌入了一个标准的全局6 4 位标识，这个标识在所有 的予网中都是惟一的。通过这些标识值之间错综复杂的交换，允许数据跨越多个 子网传输。最后的一层就是数据传输层，负责数据包的实际传送。 利用i n f i n i b a n d 实现集群的好处在于低时延、高性能。群集一般采用以太网， 如果是高性能计算机，内部也通常采用h i p p i 或m y r i n e t 网络，后两者的竞争力表 现在可靠性、可用性上现在i n f i n i b a n d 在这方面同样有出色表现。i n f i n i b a n d 网可大量扩充i o 控制器( 大多数都位于服务器外部) ，消除了单点故障。它在消 息传送协议之中还融入了差错管理功能，具有设备热增加能力。另外，i n f i n i b a n d 的可层叠交换技术把集群送到了一条更宽广的通路上，极大地突破了水平伸缩 复旦大学硕士学位论