（通信与信息系统专业论文）分布式网络并行系统在舰载指控系统中的应用研究.pdf

哈尔滨工程大学硕士学位论文 摘要 分布式系统比单机系统具有更高的性能和可靠性，并且随着互联网的普 及和某些应用本身所具有的分布式特性，使其应用日益广泛。但是，对于网 络分布式系统来说，当系统的任务量过重时，单机处理速度的瓶颈、网络拥 塞和延迟、负载分布的不均衡，使分布式系统达不到预期的性能要求，因此 进一步提高分布式系统的性能是一个急待解决的问题。 本文结合了分布式系统和并行系统的优点，将单机结点的分布式系统改 造为网络并行计算结点的分布式系统 要组成部分水面舰载指控系统中 并首次应用于海军综合电子系统的重 由于网络并行计算结点的处理速度高 r ，尊机结点，从而提高了整个分布式系统的处理速度。同时，本文还深入分 析了基于网络的并行计算系统程序设计方法，对本课题所研究的舰载指控系 统原有的分布式体系结构按照并行化的思想进行了优化；提出了一种适合目 前海军舰载指控系统作战要求的分布式网络并行体系结构；讨论了这种体系 结构的可行性和性能优势。另外，本文根据前面提出的分布式网络并行舰载 指控系统体系结构的特点，通过研究目前各种并行系统负载平衡算法，提出 种适合于这种网络并行分布式体系结构的负载平衡解决方案，即基于优先 级的任务请求动态负载平衡，使系统的稳定性和可靠性得到了一定的提高。 本文所提出的分布式网络并行体系结构和适应于这种体系结构的负载平 衡方法在舰载指控系统仿真平台上做了仿真试验，证明这种方法的应用使舰 载指控系统在性能上比原有的分布式系统有所提高，从而验证了本文所提出 的方法具有一定的实用价值。 关键字：分布式系统：网络并行计算环境；负载平衡；高性能：分布式网络 并行系统 哈尔滨工程大学硕士学位论文 a b s t r a c t d i s t r i b u t e ds y s t e mh a sh i g h e rp e r f o r m a n c ea n dr e l i a b i l i t yt h a nt h es i n g l e c o m p u t e rs y s t e m ，a n dh a sb e e n i n gu s e dw i d e ra n dw i d e rw i t ht h ea l l p e r v a d i n go f i n t e r n e ta n dd i s t r i b u t e dc h a r a c t e r i s t i c so fs o m ea p p l i c a t i o n s b u tf o r t h e d i s t r i b u t e ds y s t e m ，w h e nt h es y s t e mi so v e r l o a d e d ，t h ed i s t r i b u t e ds y s t e mc a nn o t m e e tt h ep e r f o r m a n c er e q u i r e m e n t sa n t i c i p a t e db e c a u s eo ft h eb o t t l e n e c ko ft h e s p e e do fm o n o l i t h i cp r o c e s s o r ，n e t w o r kc o n g e s t i o na n dd e l a ya n du n b a l a n c e d p a r t i t i o no fl o a d ，c o n s e q u e n t l yt oi m p r o v et h ep e r f o r m a n c eo ft h ed i s t r i b u t e d s y s t e mu l t e r i o r l yi sa ni m p e r a t i v ep r o b l e m t h i st h e s i sc o m b i n e st h em e r i t so fd i s t r i b u t e ds y s t e ma n dt h o s eo fp a r a l l e l s y s t e m ，a n dt h em o n o l i t h i cp r o c e s s o rc o n j u n c t i o nd i s t r i b u t e ds y s t e mi sc h a n g e d i n t on e t w o r k e dp a r a l l e lc o m p u t i n gc o n j u n c t i o nd i s t r i b u t e ds y s t e m ，w h i c hi s a p p l i e di ni m p o r t a n tc o m p o n e n to fn a v yi n t e g r a t e de l e c t r o n i cs y s t e mf o rt h ef i r s t t i m e - - s u r f a c ev e s s e lc o m m a n da n dc o n t r o ls y s t e m o na c c o u n to ft h eh a n d l i n g s p e e d o fn e t w o r k e dp a r a l l e l c o m p u t i n gc o n j u n c t i o ni sh i g h e rt h a n t h a to f m o n o l i t h i cp r o c e s s o rc o n j u n c t i o n ，s ot h eh a n d l i n gs p e e do fw h o l ed i s t r i b u t e d s y s t e mi si m p r o v e d a tt h es a m et i m e ，t h i st h e s i sh a sa n a l y z e dt h ep r o g r a m m i n g m e t h o do fp a r a l l e lc o m p u t i n gs y s t e mb a s e do nn e t w o r ka n do p t i m i z e dt h eo r i g i n a l d i s t r i b u t e da r c h i t e c t u r eo fs u r f a c ev e s s e lc o m m a n da n dc o n t r o ls y s t e mw h i c hi s s t u d i e di nt h i st h e s i sa c c o r d i n gt op a r a l l e l i s m ，a n dp r o v i d e dad i s t r i b u t e dn e t w o r k p a r a l l e la r c h i t e c t u r ew h i c hi sa d a p tt oo p e r a t i o n a lr e q u i r e m e n t so fa c t u a ln a v y s u r f a c ev e s s e lc o m m a n da n dc o n t r o ls y s t e m ，a n dd i s c u s s e dt h ef e a s i b i l i t ya n d p e r f o f i n a n c ep r e d o m i n a n c eo ft h i sk i n do fa r c h i t e c t u r e i na d d i t i o n ，t h i st h e s i s p r o v i d e s ak i n d o fl o a db a l a n c er e s o l u t i o ns c h e m ew h i c hi sa d a p tt ot h e n e t w o r k e dp a r a l l e ld i s t r i b u t e da r c h i t e c t u r ea c c o r d i n gt ot h ec h a r a c t e r i s t i c so ft h e a r c h i t e c t u r eo fd i s t r i b u t e dn e t w o r k e dp a r a l l e ls u r f a c ev e s s e lc o m m a n da n dc o n t r 0 1 s y s t e ma n ds t u d y i n ga c t u a la l lk i n d so fp a r a l l e ls y s t e ml o a db a l a n c ea l g o r i t h m s ， t h a ti st od e m a n dd y n a m i cl o a db a l a n c eo nt h eb a s i so f p r i o rm i s s i o na n dt om a k e 哈尔滨工程大学硕士学位论文 t h es t a b i l i t ya n dr e l i a b i l i t yo f t h es y s t e mt ob ei m p r o v e d t h ed i s t r i b u t e dn e t w o r k e dp a r a l l e la r c h i t e c t u r ea n dl o a db a l a n c er e s o l u t i o n s c h e m ew h i c hi sa d a p tt ot h i sk i n do fa r c h i t e c t u r eh a v eb e e ns i m u l a t e do nt h e s u r f a c ev e s s e lc o m m a n da n dc o n t r o ls y s t e m a r t i f i c i a l p l a t f o r m ，a n d t h e e x p e r i m e n ts h o w st h a t t h ep e r f o r m a n c eo ft h es u r f a c ev e s s e lc o m m a n da n d c o n t r o ls y s t e mi sh i g h e rt h a nt h a to f t h eo r i g i n a ld i s t r i b u t e ds y s t e mb ym a k i n gu s e o ft h i sk i n do fm e t h o da n dp r o v e st h a tt h em e t h o dd i s c u s s e di nt h i st h e s i sh a s s o m ep r a c t i c a lv a l u e k e yw o r d s ：d i s t r i b u t e ds y s t e m ；n e t w o r k e dp 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 ；l o a d b a l a n c e ；h i g h - p e r f o r m a n c e ；d i s t r i b u t e dn e t w o r k e dp a r a l l e ls y s t e m 堕叠堡兰堡盔堂丝塞生堂垡丝塞 第1 章绪论 1 1 本课题的研究背景 人类社会步入信息时代，计算机性能的不断提高和通信技术的迅速发展， 推动了分布式系统的广泛应用，同时也对分布式系统的性能提出了更高的要 求。分布式系统是指不具有共享内存的多个c p u 组成一个系统，共同完成一 个任务，用户注意不到多c p u 的存在，系统好像是运行在一台计算机上。分 们式系统应该比单机系统具有更高的性能和可靠性，但是在实际的应用中， 由于网络拥塞和负载分布的不平衡，往往使分布式系统达不到预期的性能指 标，因此，迸一步提高分布式系统的性能，对于发展我国的国民经济、强化 军事装备等方面，起着重要的作用。 存近半个世纪内，海军水面舰艇军队的指挥控制、高速机动、远程攻击、 精确打击和超常规毁伤能力的发展发生了深刻的变化，武器的射程、速度、 杀伤j j f l l 精度几乎达到了极限。随着信息技术的发展，信息战能力开始成为 决定交战双方实力的一种重要的作战能力，舰艇作战指挥控制系统是海军综 合电子信息系统的重要组成部分，是一种物理上松耦合、逻辑上紧耦合的全 分布式系统，这种全分布式的体系结构具有机动灵活、可靠性高、处理速度 快等优点，但是，随着现代海军作战要求的不断提高，这种分布式的体系结 构也产生了以下一些问题： ( 1 ) 由于分布式舰载指控系统单机处理速度的限制，只能通过降低目标指 示精度换取必要的处理速度，使建立的航迹不稳、不连续，甚至于无法提取 j 击目标。 ( 2 ) 系统在遇到多目标、多通道，既有空中、水面、又有水下目标时，处 理能力尚有不足，工作不够稳定。 ( 3 ) 舰艇指控系统在解决动态负载平衡方面，普遍没有做太多的考虑。 i j 门j l 饯场态势的随机性，使分布式的舰艇指控系统负载分布很不平衡，无法 进行动态的调节，影响了分布式舰载指控系统的响应速度。 l 蚓此，提高分布式舰载指控系统的性能，是现代战争需要迫切解决的问 哈尔滨工程大学研究生学位论文 题。本文以海军综合电子信息系统为背景，以提高分布式舰载指控系统的性 能为主要目的，研制了一种网络并行分布式舰载指控系统，它的主要思想是 用并行化体系结构取代分布式系统中的单机体系结构，并提出了相应的负载 平衡解决方案，即基于优先级的任务请求动态负载平衡方案，其首要目的就 是使指控系统的性能较目前原有的分布式指控系统有所提高，同时使舰载指 控系统的抗破坏、抗失效能力得到一定的提高，提高战场上的攻击力和生命 力。 1 2 并行处理技术与分布式系统的性能 以高性能计算为平台的大规模并行计算在国内外受到高度的重视，它在 科学研究、工程技术以及军事等方面的应用，已经取得了巨大的成就。从更 广泛的意义上来讲，“计算”，已经和“理论”与“实验”并列，被普遍认 为足人类自然的三大支柱之一。这种计算，主要是指应用于科学与工程的、 以岛划：能计算机为平台的大规模并行计算。它己发展成为一门新的学科 人规模科学与工程计算。大规模并行计算已成为研究科学与工程技术问题的 一种崭新的手段和方式，采用这种手段和方式进行的科学与工程技术问题的 研究，被称为“计算科学与工程”( c o m p u t a t i o n a ls c i e n c ea n de n g i n e e r i n g ) 并行计算系统通过大量数据的并行化，在解决大规模科学计算和紧耦合 问题上，体现出了巨大的优势，它的设计充分考虑了消息的传输时延和并行 算法的使用，因而其主要优点是计算速度快：而分布式系统则应用于解决多 个不相关的问题或多用户环境，通过多任务的并发控制，提高系统的处理速 度。松耦合的分布式系统的主要优势是系统的可靠性高、可扩展性好，但是 传输时延较大，数据的传输速率较低，而且当某项任务的计算量大时，单机 h 算的瓶颈将影响到分布式系统的性能。 本文所开发的分布式网络并行系统，是将并行计算机系统与分布式系统 结合在一起，在多任务的处理级上采用通常的分布式系统，在数据的计算级 j ：采用紧耦合的并行计算机系统，补充了分布式系统与并行系统各自的缺陷， 并充分考虑了多任务情况下的负载平衡，提出了一种适合这种体系结构和性 能要求的基于优先级的任务请求动态负载平衡解决方案，并首次在舰载指控 系统仿真平台上取得了应用，在很大程度上提高了分布式系统的性能。 喧玺鎏三堡盔堂婴窒生堂焦堡塞 1 3 并行计算机体系结构的发展 并行计算机体系结构的发展经历了几个阶段，第一种是向量机，以c r a v y m pc 9 0 、n e cs x 3 和f u j i t s u 为代表，主要用于大型科学计算与工程设计， 在求解有关向量和线形代数操作的数值计算问题时表现出良好的特性，但只 局限于单指令序列的向量处理：另一种是基于共享内存的多处理机系统，以 s e q u e n ts - 8 1 、b b nt c 一2 0 0 0 和s u ns p a r c c e n t e r2 0 0 0 为代表，它具有物理 上的共享内存，所有处理器面对的都是单一的、全局共享的地址空间，每个 处理器都可以对共享存储空间的任意地址进行存取，是目前技术较为成熟的 一种并行处理系统，通常处理器之间通过总线或交叉开关进行连接。第三种 是分布式存储多计算机系统，以i n t e l p a r a g o n 、t h i n k i n g m a c h i n e c m 5 、c r a y t 3 d 等为代表，每个处理器与自己的局部存储器组成一个处理单元，各个处 理单元之间通过互联网络连接起来，以消息传递( m e s s a g e p a s s i n g ) 方式实 现处理器之间的通信，它的弱点是造价昂贵，应用软件难以真正发挥其威力， 工程设计周期也相对较长，因此没有得到广泛的应用。 随着并行计算技术在各个领域的渗透和普及，以及高速网络产品的陆续 问j 牡和不断成熟，一种新的并行计算系统一一网络并行计算( n e t w o r k e d p a r a l e l lc o m p u t i n g ，n p c ) 系统应运而生。网络并行计算系统利用计算机网 络以某种拓扑结构连接各个节点的p c 机和工作站。采用消息传递的方式进 行节点机间的通信，充分利用各节点的资源，统一调度、协调处理，以实现 高效并行处理。并行计算的硬件支持也从原来的只有国家或大公司才能负担 的专用硬件超级计算机发展到现在一个小的实验室就可以组建的“个人超级 计算机”，它是种非均匀存储访问的m i m d 型的分布式存储的并行计算机， 物理上具有松耦合特性，通常由普通网络如以太网、f d d i 、或a t m 进行连 接，并且能够运行任何为专用并行计算机设计的任何软件或并行算法。这种 网络并行计算机系统也称为计算机群或工作站网络即c o w s 或 n o w s ( c l u s t e r so rn e t w o r k so f w o r k s t a t i o n s ) 。 网络并行计算系统主要由三部分组成：节点机、互联网络以及提供网络 行仃计算环境的支撑软件。各个节点机既可以是同构的，也可以是异构的， 既可以是普通的p c 机，也可以是工作站、s m p ( 对称处理机) 服务器等。 瓦联网络可以是通常使用的局域网，也可以是新出现的高速网络或者专门设 哈尔滨工程大学研究生学位论文 汁的高速互联网络系统。网络并行计算系统的支撑软件主要由节点机的操作 系统、网络通信协议、通信原语以及并行程序设计环境与并行工具包组成。 在网络并行计算机系统中，最为常用的操作系统是u n i x 和w i n d o w s n t 等， 网络通信协议负责实现节点机之间通过互联网络的数据通信服务，既可以使 用标准的t c p o p 协议，也可以使用经过简化的特殊协议；通信原语是提供给 用户编程调用的基本函数库：并行程序设计环境与并行工具包则为用户提供 了方便、友好的使用接口。 本文所应用的就是这种网络并行计算系统，它相对于其他的各种并行计 算机体系结构具有以下特点： 1 ) 具有很好的性能价格比，用户的投资风险很小。另外，网络并行计算 系统可以帮助用户充分利用现有的计算设备，从而保护用户的现有投 资。 2 ) 程序的编写简便。用户利用并行程序设计环境，在c 或f o r t r a n 语言 的基础上，加入消息传递库函数调用，即可实现并行程序，无需使用 新的并行语言重新编写程序。 3 ) 采用松散耦合式结构，具有出色的扩展性。只要有带宽、低延迟的互 联网络支持，便可以通过增加节点机的数目来提高实际应用系统中的 加速比。 4 ) 系统结构灵活。适合用户将不同体系结构、不同性能的节点机连接在 一起，构成异构型系统。这样，一方面可以充分发挥已有系统的作用。 同时，这种异构型系统能够避免单一体系结构适应面窄的弱点，可以 更全面地满足各种高速复杂计算的需求。 5 ) 网络并行计算系统可以包括专用的并行处理机系统，将它们作为整个 网络并行计算系统的若干节点，进行异构并行计算( h e t e r o g e n e o u s p a r a l l e lc o m p u t i n g ) 。 网络并行计算系统代表着并行处理领域的新方向，并有可能主导以后并 行计算技术的发展。本文将这种网络并行计算系统作为分布式系统的一个独 萨节点，将单机节点上复杂的数值计算进行并行化处理，应用合理的并行程 序设计技术，开发了水面舰艇指挥控制系统的仿真平台，是这一领域上该技 术的首次应用，同时提出了一种动态负载平衡解决方案，使分布式舰载指控 系统的性能获得了一定的提高。 4 堕玺堡三堡丕堂婴塑笙堂垡堡窒 1 4 并行程序设计的特点与并行算法的发展 并行程序设计方法不同于顺序程序设计方法，主要在于对问题采取何种 看法：顺序程序设计方法把事物的变化发展看成是单线程的，任何两种事物 之间必然存在因果关系，从而把一系列统一事物看成是不可分割的整体。后 来的结构程序设计特别是对象式程序设计把一个复杂的事物分解成多个简单 的事物，或者把一个系统看成是由多个相互联系的实体构成的。应该说，这 罩在对事物的认识上取得了突破性的进展，但也是从事物的静态结构上来看 的，并未从行为上来分解。从行为上来看，它们仍然被认为或者是一致的， 或者是先后相继的，相互之间不存在有并发干扰现象，更不存在可同时发生 的相互作用的行为。 并行程序设计方法的一个最基本的观点，就是把一个事物的行为看成是 多个事物互相作用的结果。这是一个观念上的根本转变，根据这个观点，并 行程序设计方法的核心内容就是并行划分与算法映射。其理论基础是并行计 算模型。并行计算模型决定了并行语义，并行语义决定了可并行执行的准则， 从而决定了并行划分的原则。 由于并行程序设计相对于顺序程序设计具有以上一些特点，因此，也有 + 些特殊的困难。 ( 1 ) 并行程序设计和顺序程序设计的一个根本不同之处就是要把问题看成 是由多个可并行求解的子问题组成，并行分解是并行程序设计的第一步，而 要进行并行分解并不容易，需要经过复杂的计算与分析，这就使并行程序设 汁显得更加困难。 ( 2 ) 一般来说，不管什么程序都有改变程序行为的手段，可称之为交互作 用。并行程序除了具有顺序程序、并发程序的交互作用以外，还有动态调度 与映射机制等等都会影响程序的行为，并行程序的交互作用途径很多，除了 存存储单元内容的修改以外，进程执行的时间( 时序与定时) 、空间( 处理 机分配、站点分配) 、控制流( 改变执行路径) 、执行速度以及相互关系的 改变都可能会引起程序行为的改变。总之，影响并行程序行为的因素很多， l n 】且部分因素之间也有互相影响，情况比较复杂，单凭程序员的直觉与经验 是难以保证可靠性的，必须要有一种理论和并行计算模型来指导。 ( 3 】关于算法结构与系统结构适配性问题，也是并行程序设计的一个重要 哈尔滨工程大学研究生学位论文 问题。不但关系着程序执行的性能问题，甚至关系到程序能否在所指定的系 统上执行的问题。算法映射就是为了解决这类问题。 ( 4 ) 关于进程调度问题，它本来属于操作系统的问题，但当前有些语言， 需要用户来负责，这也增加了程序员开发程序的难度。 ( 5 ) 关于自治合作，这是并行程序可靠性的一个重要问题，一般只考虑同 步约束使之顺序化，实际上这个问题的一般提法应是进程之间的合作协议。 这是并行程序设计的首要问题，也是非常困难的问题。 ( 6 ) 并行程序设计的可靠性问题要比顺序程序的可靠性问题的内涵丰富得 多复杂得多。例如，并行程序的安全性，除部分正确性以外，还有死锁问题， 并行程序的活跃性，不限定是停机问题，而是一般的可达到性问题。在并行 程序中，所谓安全性，是指不应当出现的状态，在任何时候都不会出现：所 旧活跃性问题，是指应当出现的状态终究会出现。在并行设计理论中，除安 全性、活跃性问题以外，还有公平性的问题，这更是顺序程序所没有的。 随着并行机技术的发展，必然引起数值计算方法和非数值计算方法的“并 行化”。并行算法是数值算法和非数值算法的集合，所谓并行算法研究，就 是针对实际的数值与非数值计算问题，挖掘和开发其内在并行性，并结合并 行系统软硬件特性，设计有效的计算方法，在并行计算机上实现高效计算， 以充分发挥并行结构的处理效率，不断开拓并行计算机的应用领域，以满足 大规模科学与工程计算问题的迫切要求，满足大规模数据处理和人工智能方 面的深度和广度并行处理的要求，适应计算机体系结构的发展方向，并促进 新的并行系统结构出现，推动计算机事业的发展。 对并行算法的研究，可以追溯到6 0 年代初期，它与并行计算机的研制是 同时进行的。并行计算机系统的研制与应用推动了并行算法的研究和发展； 同时，有效的并行算法研究又给并行计算机系统的发展予以有力的支持。并 行汁算技术己广泛应用于海洋建模、图像分析、医疗药品试验、物理、化学、 基因工程等多个领域，而且这种应用已经不仅仅局限于科学与工程计算领域， 并行计算技术的研究不但具有广阔的前景，而且日益紧迫，国内外一些并行 计算机厂家与用户已深切地感到，在并行机上进行科学计算急需一套强有力 的并行算法的支持，因此，大力开展并行处理和并行算法研究、充分挖掘计 算机体系结构和计算问题本身的内在并行性，己成为当今世界上一个崭新的 研究课题，开展并行处理和并行算法的研究具有十分广泛而深远的现实意义。 哈尔滨工程大学研究生学位论文 j 。以洗，并行算法与并行计算机硬件、软件三者并重，缺一不可，共同构成 了并行计算技术。 总而言之，并行计算与传统的计算概念是根本不同的，必须从最基础的 理论开始，创建一个新的计算理论体系。从总体上看，并行技术在几十年中 已经取得了很多重要进展，但很多方面还处于完善和探索阶段，并行处理技 术作为计算机科学的一个重要方向，其应用前景将是非常广阔的，它的发展 还需要大量科研工作者的共同努力，来促进并行技术的进一步普及化，实用 化。 1 5 本论文的主要工作 本文以海军综合电子信息系统中水面舰艇指控系统的研制为背景，提出 j 7 用嬉j 二嘲络的并行计算体系结构改造目前的分布式舰载指控系统的方案， 将分布式系统中的单机计算节点改造为前面讨论的并行计算机体系结构的第 四种方式网络并行计算机系统，并提出了相应于这种分布式网络并行系 统的负载平衡解决方案，即基于优先级的任务请求动态负载平衡解决方案， 是这项技术在舰载指控系统中的首次应用，在提高系统的性能和可靠性问题 ：取得了一定的进展。本文还在此基础上研究了基于网络的分布式并行计算 系统的并行处理技术，以及构造消息传递模型的并行处理软件的方法，并且 在舰载指控系统仿真平台上进行了实现。 第二章介绍了分布式系统与并行计算系统的基本理论。分析构成并行计 算平台的几种体系结构，指出基于网络的并行计算系统的优点，并介绍了在 其上| i 进行并行程序设计的消息传递模型。 本文在第三章提出了一种新的体系结构模型分布式网络并行系统体 系结构，将这一体系结构模型应用于舰载指控系统中，对原有的分布式舰载 指控系统进行了改造，并给出了分布式舰载指控系统的并行化程序设计方法。 这一体系结构是作者在深入研究了并行系统和分布式系统的基础之上，为了 满足那些功能上分布、性能和可靠性高，同时可扩展性和伸缩性好的系统要 求而提出的。同时，介绍了并行程序设计的基本方法，提出了并行舰载指控 系统体系结构模型。 第四章描述了本文所提出的适合分布式网络并行系统体系结构的舰载指 哈尔滨工程大学研究生学位论文 控系统负载平衡解决方案，在分析了静态负载平衡和动态负载平衡的基础上， 提出一种适合复杂的分布式网络并行舰载指控系统负载平衡要求的基于优先 级的任务请求动态负载平衡解决方案。 第五章介绍了分布式网络并行舰载指控系统仿真平台的建立和仿真结果 分析，对本文提出的体系结构的性能做了总体测评。由于仿真系统与真实的 舰载指控系统还存在着很大的差别，实际的舰载指控系统能否具有采用此体 系结构的软硬件设施，还有待于进一步的实践，而且因为有些试验数据无法 取得，因此只能在一定程度上完成本系统的仿真过程，但是，从试验的数据 上看，系统体系结构的设计是基本可行的。 哈尔滨工程大学研究生学位论文 第2 章分布式系统与并行计算系统的基本理论 2 一分布式系统的基本概念 随着计算机网络的出现，分布式系统的应用成为可能，分布式系统为用 户提供了尽可能多的计算机处理能力和数据的透明访问，同时实现高性能和 高可靠性的目标。 2 1 1 分布式系统的定义 对于分布式系统，通常使用以下定义：一个分布式系统是一个对用户看 起来象一个普通系统，然而运行在一系列自治处理单元( p e ) 上的系统，每 个处理单元有各自的物理存储器空间并且消息的传输延迟不能忽略不计，在 这些处理单元间有紧密的合作，系统必须支持任意数量的进程和处理单元的 动态扩展。 2 1 2 分布式计算标准 为了达到不同硬件和软件平台上建立的分布式系统的互操作性，用户需 要一个标准的分布式计算环境，在这个环境里，所有的系统和资源都可用。 d c e ( 分布式计算环境) 是开放系统基金会开发的分布式计算技术的工 业标准集，它提供保护和控制对数据访问的安全服务、易于寻找分布式资源 的名字服务以及高度可伸缩的模型，用于组织极为分散的用户、服务和数据。 d c e 可在所有主要的计算平台上运行，并设计成支持异构型硬件和软件环境 下的分布式应用。一些其他的标准，如c o r b a ( 公共对象请求代理) ，使 用面向对象模型实现分布式系统中的透明请求服务：微软的分布式组件对象 模型( c o m d c o m ) 提供了在w i n d o u w s 平台和某些实时操作系统如v x w o r k s 卜的分布式应用。目前所建立的分布式系统，大多是应用以上标准，在操作 系统与应用程序层加入一个中间层，通常称为中间件，进行分布式系统的通 信与管理。 哈尔滨工程大学研究生学位论文 本文建立的分布式网络并行系统，其分布式部分应用微软的c o m d c o m 技术，建立了一个专用于通信管理的网络通信中间件，为软件的二次开发提 供了通信接口。 2 1 3 分布式系统设计的几个关键性问题 在分布式系统的设计中，要考虑几个关键的问题： ( 1 ) 透明性：系统的透明性是分布式系统设计中最关键的问题，即如何 实现单系统映像。透明度可分为两个级别： 第一，对用户隐藏系统的分布性。就终端的命令发布和结果显示而言， u j _ 以将分布式系统建成象一个单处理机系统一样。 第二，在系统的低层中实现系统对程序也是透明。即系统的调用接口设 汁成使多处理机的存在对编程人员来说是不可见的。 透明性适用于分布式系统的多个方面，包括位置透明：用户不知道资源 位于何处；迁移透明：资源可以不改名的随意移动；复制透明：用户不知道 有多少个拷贝存在：并发透明：多个用户可以自动的共享资源；并行透明： 系统活动可以在用户没有感觉的情况下并行发生。 ( 2 ) 灵活性：设计过程中始终保持很大的灵活性，避免大量的设计返工。 ( 3 ) 可靠性：包括三个不同的方面： 町用性：系统可用时间的比例。设计时，要提供必要的冗余，即给关 键的硬件和软件提供备份，以便其中之一毁坏时可以用备份的部件来进行替 换。 安全性：必须保护文件和其他资源不被非法用户使用。在单处理机系 统中，用户通过口令进行登录，同时被确认。此后，系统知道该用户是谁， 也能够检查它的每一个访问是否合法。在分布式系统中，当一条消息到达服 务器向其发送请求时，服务器没有一个简单的方法来判断该指令是哪个用户 发的。 容错性：假设一个服务器出了故障，然后很快再启动，系统应具有关 键数据和任务的恢复能力。分布式系统能设计成可以屏蔽错误，也就是对用 户隐藏错误。 ( 4 ) 可伸缩性：系统的容量和结构应该是可伸缩的。 堕堡堡三塑盔堂堡塞圭堂焦堡壅 2 2 并行计算系统的基本理论 计算机自从诞生之日起，就面临着应用领域对其性能提高的迫切要求， 而且这种要求正在日益增强。正是源于这种对高性能的要求，人们早在计算 机发展的初期，就认识到了并行处理的重要性，而且在计算机发展过程中也 随试陶在系统的各个层次上开发并行性。近年来，高科技领域对计算机性 能提出了越来越高的要求，而物理上的极限和工程实现上的约束使单机速度 很难满足应用要求，并行机结构引起了普遍兴趣。大规模、超大规模集成电 路，特别是微处理器技术的逐渐成熟为并行计算机结构提供了技术上和物质 卜的基础，使并行机系统成为可能。事实上并行机正在取代高性能单处理机 系统而成为下一代超高速计算机系统的代表机型。目前大部分超级计算机和 小型计算机都已经采用了并行体系结构。美国国防部尖端研究规划署( a p p a ) 曾十1 9 8 2 年初在纽约召开了一次巨型机和并行体系结构的专家会议，得出的 结沦是：提高目前计算机系统性能的唯一方法是选择“大量的并行化”。 采用并行汁算的原因可以总结出以下三点：( 1 ) 可以加快速度，即在更 l l 的时| 1 ：1 j 内解决相同的问题或在相同的时间内解决更多更复杂的问题，特别 是对+ 些新出现的巨大挑战问题，不使用并行计算是根本无法解决的；( 2 ) 岢省投入，并行计算可以以较低的投入完成串行计算的任务；( 3 ) 物理极限 的约束。 2 2 1 并行计算系统的分类 并行计+ 算系统是指能够在同一时间内执行多条指令( 或处理多条指令) 的计算机系统，是并行计算的物理载体。通过对并行计算机的不同分类方式 的酏明，可以对并行计算机有一个总体上的了解，帮助编程人员设计出更高 效的并行程序。 ( 1 ) 按照指令与数据进行分类 根据一个并行计算机能够同时执行的指令与处理的数据的多少，可以把 并行计算机分为s i m d ( s i n g 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 ，单指令多数据并行计 蜉机) 和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 ，多指令多数据并行计算 机) 两种。 s i m d 计算机同时用相同的指令对不同的数据进行操作。比如数组赋值运 哈尔滨工程大学研究生学位论文 算 a = a + 1 ( 2 - 1 ) 在s i m d 并行机上可以用加法指令同时对数组a 的所有元素实现加1 。 即数组( 或向量) 运算特别适合在s i m d 并行计算机上执行，s i m d 并行机 可以对这种运算形式提供赢接地支持和高效的实现。 m i m d 计算机同时有多条指令对不同的数据进行操作，比如算术表达式 爿= b + c + d e + f + g ( 2 2 ) 可以转换为 a = ( b + c ) + ( 1 9 一e ) + ( f + g ) r 2 3 、 如果加法( b + c ) 、减法( d e ) 和乘法( f t g ) 有相应的直接执行部件， 则这三种不同的计算可以同时进行。 虽然人们至今还在使用s i m d 和m i m d 这种表达方法，但是，随着新的 j 1 ：行计算机组织方式的产生，按同时执行的程序和数掘的不同，人们又提出 了s p m d ( s i n g l e p r o g r a mm u l t i p l e d a t a ，单程序多数据并行计算机) 和 m p m d ( m u l t i p l e p r o g r a mm u l t i p l e 地t a ，多程序多数据并行计算机) 的概 念。这种划分方式所依据的执行单位不是指令而是程序，显然其划分粒度( 划 分对象的大小程度) 要大得多。 ( 2 ) 按存储方式分类 从物理划分上，共享内存和分布式内存是两种基本的并行计算机存储方 式。除此之外，分布式共享内存也成为一种越来越重要的并行计算机存储方 式。 对于共享内存的并行计算机，各个处理单元通过对共享内存的访问来交 换信息，协调各处理器对并行任务的处理。这种共享内存的编程实现起来相 刈简单，但共享内存往往成为性能特别是扩展性的重要瓶颈。 共享内存并行计算机是专门设计的计算机系统，其体系结构模型如图2 一l 所示，多个不具有局部存储器的处理单元连到多个存储器模块，使得每个处 理器能以共享存储器配置的形式访问任意存储器模块。共享存储器的多处理 机系统使用单地址空阳j ，在整个主存储器系统中的每一个单元有一个唯一的 地址，用此地址每个处理器就可以访问该单元。 堕堑堡三堡盔堂婴窒圭堂垒堡壅 型代表不具有局部存储的处理单元 图2 1 共享内存并行计算机模型 共享内存并行计算机模型对于程序员来说是很有吸引力的，因为它方便 了对数据的共享；但是用硬件来达到所有处理器对所有存储器的快速访问是 很困难的。因此大多数大型的实际的共享存储器系统都具有某种形式的层次 或分御式存储器结构，以使处理器能以更快的速度访问物理上相近的处理单 ，。 对r 分布式内存的并行计算机，各个处理单元都拥有自己独立的局部存 储器。出于不存在公共可用的存储单元，因此各个处理器之间通过消息传递 来交换信息，以协调和控制各个处理器的执行。分布式内存并行计算机是消 息传递并行编程模型所面对的并行计算机的存储方式，其体系结构如图2 - 2 所示。 吲代表具有局部存储的处理单元 世j 图2 。2 分布式内存并行计算机模型 通信对分布式存储并行计算机的性能有重要的影响，复杂的消息传递语 句的编写成为在这种并行计算机上进行并行程序设计的难点所在，但是，对 于这种类型的并行计算机，由于它有很好的扩展性和很高的性能，因此，它 的应用非常广泛。 另一种并行计算机模型是分布式共享内存的并行计算机，它结合了共享 内存和分布式内存并行计算机的特点，这种并行计算机的体系结构模型如图 2 3 所示。 堕叠蒌三焦盔堂堕壅圭堂重堡塞 f 一刊斟 一 互联网络 j 譬代表共享存储的局部处理单元 j 一一r “ ；r 、 j 一j 图2 3分布式共享内存并行计算机模型 在这种并行处理机中局部节点共享存储可以是共享内存，也可以是分 布式内存。对于节点是分布式内存的情况来说，它的实现方法比较复杂，当 个处理器要访问的单元不在本地存储器中时，必须使用消息传递方法将数 据从处理器送到该单元或是将该单元传递到处理器，这种传递必须以某种自 动的方式进行，以隐藏存储器是分布的这一事实。这种思想被称为共享虚拟 存储器，它给用户的感觉是共享存储器，尽管事实上它是分布式的。这样， 每个局部节点的计算能力得到了提高，因此称为“超节点”。当然，远程访 问将导致更大的延迟，而且地起本地访问来，此延迟常常是相当大的。必须 使川某种形式的查找表来在分布式存储器中定位实际的单元。 2 2 2 并行编程模型 目前两种最重要的并行编程模型是数据并行和消息传递。数据并行模型 的编程级别比较高，编程相对简单，但它仅适用于数据并行问题：消息传递 编程模型的编程级别相对较低，但消息传递编程模型可已有广泛的应用范围。 ( 1 ) 数据并行编程模型 数据并行即将相同的操作同时作用于不同的数据，因此适合在s i m d 及 s p m d 并行计算机上运行。它是一种较高层次的编程模型，提供给编程者一 个全局的地址空间。一般这种形式的语言本身就提供并行执行的语义，因此 对于编程者来说，只需要简单地指明执行什么样的并行操作和并行操作对象， 就实现了数据并行的编程。因此，数据并行的表达式是相对简单和简洁的， 它不需要编程者关心并行计算机是如何对该操作进行并行执行的。 数据并行模型虽然可以解决一大类科学与工程计算问题，但是对于非数 据并行类的问题，如果通过数据并行的方式来解决，一般难以取得较高的效 哈尔滨工程大学研究生学位论文 率。数据并行不易表达甚至难以表达其他形式的并行特征。 ( 2 ) 消息传递编程模型 消息传递即将各个并行执行的部分之间通过传递消息来交换信息、协调 步伐、控制执行。消息传递一般是面向分布式内存的，但是它也可以适用于 共享内存的并行机。消息传递编程模型为编程者提供了更灵活的控制手段和 发达并行的方法，一些用数据并行方法很难表达的并行算法，都可以用消息 传递模型来实现。灵活性和控制手段的多样化，是消息传递并行程序能提供 高的执行效率的重要原因。 消息传递模型一方面为编程者提供了灵活性，另一方面，它也将各个并 行执行部分之间复杂的信息交换和协调、控制的任务交给了编程者，这在一 定程度上增加了编程者的负担，虽然如此，消息传递的基本通信模式是简单 和清楚的，因此，目前大量的并行程序设计仍然是消息传递并行编程模式。 2 2 3 网络并行计算系统的组成与优点 基于网络的异构并行计算机是一种分布式内存并行计算机结构，通过互 联网络连接多台完整的计算机，每台计算机具有自己的处理器和本地主存储 器，其它处理器不可访问该本地的主存储器，这种存储访问控制方式称为非 对称存储访问，如图2 - 4 所示。在多计算机系统中，主存储器分布在多台计 算机中，每台计算机都有自己的地址空间，每个处理器只能访问自己的本地 丰存储器中的单元。系统中的互联网络是供处理器间传递消息用的，这些消 息可能含有其它处理器进行计算时所需的数据。 幽2 - 4 基于网络的并行计算机 哈尔滨工程大学研究生学位论文 它与专门设计的多处理机系统相比“具有以下优点： 1 、用较低成本的工作站和p c 机实现具有很高性能的并行系统。 2 、系统可很容易地进行升级、扩充，引入最新的处理器。 3 、可使用已有的软件或对之加以修改。 2 2