（计算机软件与理论专业论文）基于中间件的企业集群系统结构设计.pdf

摘要 摘要 随着各种网络应用和企业信息化系统的普及并持续增长，数据集中和应用集 成迫切需要可管理、易伸缩、高性价比的数据共享解决方案。集群系统正是满足 这样要求的一个具备强大处理、存储能力的计算机群。然而现有集群研究多立足 于高性能计算的要求，对企业信息系统的支持尚有诸多不足，表现在单一- 一系统欧 像和可管理性、可升级可扩展性、数据的完整性和一致性支持等方面。 针对上述情况，在通用集群体系结构基础上，根据企业应用集成环境对集群 系统的具体需求，本文从并行化分解、进程迁移、负载均衡、高速通信、容错技 术、单一系统映像等方面出发，提出了基于中间件的企业集群系统( m e c s ) 方案， 主要进行了如下几方面的工作： ( 1 ) 针对服务功能的可再分性及非平衡性，提出分层模块化的集群中间件结构 设计；通过体系结构提供对调度器、服务器池、存储网络各个层次组件的配嚣灵 活性，尤其是可伸缩的的共享存储子系统，可满足多样化的应用规模和需求； ( 2 ) 在分析集群系统的各种任务调度策略利弊的基础上，以复合负载向量作为 负载均衡控制的动态反馈，提出了一种基于时间特性的加权最小连接数调度算法 可有效降低调度器和通信连接的开销； ( 3 ) 针对数据关联和数据依赖的复杂性，从多方位多层次探讨了保障数据完整 一一致的相关技术，分析了分布式环境下的封锁和隔离、复制与更新等机制。 最后，对该系统原型进行了模型化评估，具体测试了多种情况下的响应时间。 测试数据表明该框架具有良好的扩展性、可达到较好的负载均衡性、满足数据的 完整性和一致性要求，实现了预期目标。 关键字：集群，数据完整性，数据一致性，负载均衡，单一系统映像 a b s t r a c t a b s t r a c t w i t ht h ec o n t i n u o u sd e v e l o p m e n to fa l lk i n d so fn e t w o r ka p p l i c a t i o n sa n d e n t e r p r i s ei n f o r m a t i o ns y s t e m s ，d a t as h a r i n ga n di n t e g r a t i o nw o u l db ei nu r g e n tn e e d 。 d a t ac e n t r a l i z i n ga n de n t e r p r i s ea p p l i c a t i o ni m e g r a f i o n ( e a i ) w i l lb eo fg r e a tb e n e f i tt o a l le n t e r p r i s e ，w h i c hn e e das o l u t i o nw i t hh i 曲s c a l a b l ec a p a b i l i t ya n dt h c i l i t yi n m a n a g e m e n t ，w h i c hw o u l dp r o v i d eap o w e r f u lc o m p u t i n ga n ds t o r i n gc a p a b i l i t y h o w e v e r , m o s tc u r r e n tc l u s t e r sa r eb u i l to nh i g hp e r f o r m a n c ec o m p u t i n g ，w h i c h h a ss o m ed e f i c i e n c yo fs u p p o r t i n ge n t e r p r i s ei n f o r m a t i o ns y s t e m t h cd a t ai n t e g r i t ya n d c o n s i s t e n c yc o u l d n tc o m p l e t e l yg u a r a n t e e t os o l v et h e s ep r o b l e m s ，t h i st h e s i sa n a l y z e st h ep i v o t a lt e c h n o l o g yo nc o m m o n c l u s t e ra r c h i t e c t u r e ，w h i c hi n c l u d e sp a r a l l e lc o m p u t i n ga n dc o m m u n i c a t i o n ，p r o c e s s m i g r a t i o n ，l o a db a l a n c i n ga n df a u l tt o l e r a n t a c c o r d i n gt ot h ea c t u a ld e m a n do ft h ee a i e n v i r o n m e n t ，ac l u s t e ra r c h i t e c t u r eb a s e do nm i d d l e w a r ef o re n t e r p r i s ec o m p u t i n g ( m e c s ) i sd e s i g n e d s t e mf r o mt h es e r v i c e ss e p a r a b i l i t ya n dn o n b a l a n c i n g ，t h eh i e r a r c h ym o d e li s i n t r o d u c e d b ym e c st op r o v i d e t h ef l e x i b l e c o n f i g u r a t i o n a n d m a n a g e m e n t c h a r a c t e r i s t i cb e s i d e sh i g hp e r f o r m a n c e a f t e ra n a l y z i n gt h ec l u s t e rl o a d - b a l a n c i n ga l g o r i t t u n ，t h i s 曲e s i sp r e s e n t sa n a l g o r i t h mb a s e do nd y n a m i cf e e d b a c k ，w h i c hr e g a r d st h er e s i d u a lt a s kq u e u e si nc h j a st h ei n d e xo fn o d e sc o m p u t i n gr e s o u r c e t a k i n gt h ew e i g h t e dp a r a m e t e ri n t ot h el e a s t c o n n e c t i o nn u m b e rs c h e d u l i n g ，t h i sa l g o r i t h mc a na c c u r a t e l yp r e d i c tt h en o d e sl o a d s t a t u si nt h en e a rf u t u r e e v e n t u a l l y , am o d e le v a l u a t i o na n ds i m u l a t i o na r eu s e dt ot e s tm e c s i tm a i r i l y f o c u s e so nt h ed a t ar e l e v a n c ym a dd e p e n d e n c y t h ee x p e r i m e n tp r o v e st h a tt h ea p p r o a c h j sv a l i da n dp r a c t i c a l k e y w o r d ：c l u s t e ll o a db a l a n c i n g ，d a t ai n t e g r a l i t y , d a t ac o n s i s t e n c y , s s i i i 图表清单 图表清单 图2 一l 、m i m d 计算机的分类 图2 2 、p r a m 模型。 图2 3 、b s p 模型 图2 - 4 、计算机系统规模与互连性能 图2 - 5 、多级存储器层次结构 图2 - 6 、i s c s i 结构原理 图3 - 1 、集群典型体系结构 图3 - 2 、进程迁移的层级 图3 3 、负载均衡的层次化结构 图3 4 、五层沙漏模型与g l o b u s 基础结构 图4 1 、d b m s 主要组件 图4 2 、事务状态转换图 图4 3 、两阶段提交过程 图4 - 4 、数据仓库系统体系结构 图5 1 、m e c s 系统体系结构示意图 图5 - 2 、m e c s 请求队列状态转换图 图5 - 3 、m e c s 服务器池状态转换图 图5 - 4 、m e c s 系统内部逻辑组成 图5 5 、面向连接协议的典型过程 图5 - 6 、调度模块逻辑流程 图5 7 、通信模块逻辑流程 图6 1 、调度仿真模型的处理流程 图6 - 2 、调度事件模型的时间序列过程 图6 。3 、无相关性模型的加速比与请求数关系图 图6 - 4 、无相关性模型的效率与请求数关系图 图6 - 5 、不同数据相关性下的加速比一节点数关系图 图6 - 6 、不同数据相关性下的效率一节点数关系图 v 一9加m殂筋蕊如的椰铊铊鳃船弱郇舛陀陀豫眇 图表清单 表2 1 、不同可用性级别的分类及容错能力表 表2 2 、存储器典型参数 表4 1 、多粒度加锁的锁相容性矩阵( 4 = 兼容，= 不兼容) 表4 2 、d b m s 静态完整性约束 表6 1 、w i n d o w s 平台可用时钟源 表6 2 、无相关性的模型测试数据 v i 1 3 1 9 4 4 4 6 7 4 7 5 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明 确的说明并表示谢意。 签名：a ；查i 日期：泐彭年月莎日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：盔查鳖导师签名：盘。聋 日期：o 。饵月易日 第1 章引言 第1 章引言 信息技术的发展极大推动和加速了工业现代化进程，特别是关系数据库技术 的成熟所衍生的大量企业应用系统，促进了各种i n t e r n e t 和i n t r a n e t 应用的层出不 穷【l j 。在此过程中，一方面是数据信息和用户访问量的急剧膨胀，而另一方面却是 单机存储和处理能力的有限提高。面对这种矛盾所可能导致的危机，出现了多种 解决方案，其中将服务器扩展为服务集群的解决途径尤其值得关注 2 1 。 本文拟在集群技术基础上，通过优化体系结构和调度算法提高系统吞吐率、 性能加速比和可扩展性，通过引入存储区域网络解决数据存储容量和访问瓶颈问 题，通过锁、事务与复制更新等机制解决数据共享与完整性问题。在此基础上， 还进一步讨论了数据仓库构建过程中所面临的数据完整与有效性问题。 1 t 问题与背景 信息技术在电子计算机出现以来，呈现出一种前所未有的递增发展加速度【3 】。 早期计算机技术起源于军事应用和科学计算对大量、重复运算的高时效性要 求，借助高速电子器件协调完成计算任务。随着材质、工艺、器件的进步，并伴 随着相应软件控制技术的进步，愈来愈低的信息系统最终拥有成本和愈来愈明朗 的投入产出率，吸引着愈发壮大的信息产业队伍。 源于企业对数据采集、加工、存储、统计分析的迫切需求，在数据处理的发 展过程中，数据处理技术得以快速成长。尤其是关系数据库理论和关系数据库产 品的成熟，伴随着在海量存储技术基础上的数据分析与演算成为现实，信息技术 在数据事务处理领域取得长足进步。各种企业纷纷实现了各自的财务、物资计划 与库存、电子文档等无纸化管理系统。 通信与网络技术的迅速发展，极大地促进了计算机技术的普及：企业内部信 息系统都己逐渐从单机版进化到局域网版；尤其在互联网络出现以后，浏览器技 术的成熟，如p d m 、e r p 、o a 等各种系统都得到了广泛而深入的应用。 i n t e m e t 应用等i t 技术的发展使传统业务发生着深刻的变化。几乎所有的企业 为支持企业信息化工程、w e b 和电子商务领域的创新，都在竞相采用新技术，使 得信息总量呈爆炸式增长，企业数据的总量每三年就增加四倍。互联网络的信息 电子科技大学硕士学位论文 内容几乎无所不包，涉及政治、经济、文化、体育、艺术、宗教等各个方面，已 成为科学研究、商业活动和共享信息资源的重要手段。 上述状况使得企业对数据的依赖程度不断增加，使原来就必须处理大量业务 信息的计算机系统负担更大，对计算资源的可扩展性以及负载共享提出了更高的 要求；同时，企业要成功运作，就必须高效而可靠的保护、访问、存储和管理这 些信息，并且必须保证数据信息3 6 5 * 2 4 小时高可用性 4 1 ：更重要的是，需要将这 些零乱分散的、细粒度的数据，深度加工为可供决策的规律知识。 这种发展趋势使得整合企业数据资源、进行数据集中势在必行，理想状况是 所有信息资源都融合在一个单一数据库系统中，同时保持所有操作处理请求的快 速响应。此即企业信息化应用迅猛发展所必然衍生出的企业应用集成( e n t e r p r i s e a p p l i c a t i o ni n t e g r a t i o n ，e a i ) 问题。 尽管影响e a i 成败的问题很多，如软件的设计、开发与实施，企业管理与业 务流程问题等，但不可避免地，是否成功解决数据相关性与数据一致问题是相当 重要的。此外，当e a i 成熟起来之后，大量用户著发访问所产生的性能问题也不 容忽视。更进一步，企业信息系统的最终价值在于其能够为企业发展提供足够详 细和精确的决策数据支持，此即数据仓库；而在构建过程中的各种清理、合并、 加工等技术，都务须考虑数据的完整、一致和有效。 1 2 国内外研究现状及发展趋势 在解决上述问题所相关的技术中，需兼顾效率和灵活性，重点关注主机与集 群的计算与通信技术、分布式文件系统与数据库的存储技术等，具体讨论如下。 集群系统是将一组机群通过网络互联，或利用现存网络计算资源，以形成超 级计算能力。按照对具体需求的不同发展思路和侧重点，而有高可用性计算集群 h a 、负载均衡集群l b 、超级计算集群h p c 之分【5 1 。主要系统或软件有b e o w u l f , p l a n9 、m o s i x 、o p e n m o s i x 、l i n u xv i r t u a ls e r v e r ，t u r b o l i n u xc l u s t e rs e r v e r 等。 负载均衡作为集群的典型特征，是通过实时地分析数据包，掌握网络中的数 据流量状况，合理分配任务请求。其实现机制和负载均衡策略有多种，分别可以 基于数据包的目的m a c 地址选择不同链路、基于i p 地址将数据分流到多个节点、 基于访问流量和请求内容的第四、乃至第七层交换控制。具体实现如使用已久的 d n s 、b e r k e l e ym a g i c r o u t e r 、i b me n e t w o r k ，以及基于l v s 的众多系统【6 j 。 集群需要高性能通信子系统支持，目前存在以系统总线、i 0 总线、交叉开关 第1 章引言 等多种方式的互连通信。特别是在工作站集群中，一般采用h i p p i 、光纤通道及 f d d i 、m y d n e t 、s c i 、a t m 、e t h e m e t 等商用网络进行节点互连口j 。由于连接距离 对通信带宽的巨大影响，导致了1 u 刀片服务器、集中机柜专用机群、高密度阵列 柜专用机群等组装方式的发展。然而集群终归是多节点松耦合系统，节点间连接 复杂、连接线路长，带来较大的通信延迟，以及可靠性、时钟扭斜和串道等问题； 并且集群一般使用标准通信协议下的商品化网络，其开销比较大。这方面曙光系 列集群服务器通过开发高速通信协议b c l 3 ，兼具高层和底层协议多方面的优点。 系统可用性研究一直是国内外研究的一个热点问题。在可用性理论方面，提 出了动态故障树分析法、可靠图法、m a r k o v 模型分析法、p e t r i 网模型分析法等分 析方法和模型【8 】，都试图解决系统可用性的理论分析，并解释可用系统结构。在计 算机系统体系结构方面，关注于软硬件架构的错误失效恢复机制，如j i mg r a y 提 出的t r o u b l e f r e es y s t e m s 概念，b u t l e rl a m p s o n 关于系统的可用与自适应设计理 念，j o h n i - i e n n e s s y 对于可用性、可维护性、可扩展性的关注，i b m 的a u t o n o m i c c o m p u t i n g 计划，r e c o v e r y o r i e n t e dc o m p u t i n g 项目等。 商用高可用性集群系统首先基于u n i x 在8 0 年代末实现，随后，i b m 在a i x 平台上设计了可以支持3 2 个r s 6 0 0 0 或s p 节点的h a c m p 、m i c r o s o f t 源自 w o l f p a c k 的m s c s 目前可支持4 个w i n d o w s 节点、v e r i t a s 的v c s 可支持3 2 个异构节点群集、还有r o s eh a 、l e g a t on e t w o r k e r 和c o - s t a n d b y s e r v e r 、以及 w e s t e m m i c r os a v w a r e h a ，以及国内中科院计算所的c n i c h a 等。近年l i n u x 平 台的高可用性集群系统发展迅速，如t u r b o l i n u xt u r b o c l u s t e r 、r e dh a tp i r a n h a 等。 对于存储技术，要求高带宽、大容量的一致访问。如共享虚拟存储系统，是 在消息传递的硬件上通过软件的方法实现共享存储的编程界面，其中基于s m p 的 有：s h a s t a 、c a s h m e r e 一2 、s o f c f l a s h 、h i r l s m p 、s i r o c o o 、t r e a d m a r k s 以及j i a j i a 等1 9 】。，非均匀存储器存取结构作为分布式共享存储结构中的一种并行模型，是由若 干通过高速专网连接起来的独立节点构成的系统，可使系统的计算能力、内外存 容量、图形性能及联网能力独立地扩展，具有多功能性、模块化、灵活性等特点。 基于对数据管理、对象管理和知识管理的需求，在传统数据库基础上产生出 多种新型数据库系统技术。除保持对其它系统开放、支持数据库语言标准、支持 标准网络协议、有良好的可移植性、可连接性、可扩展性和互操作性等特征外， 新型数据库支持多种数据模型，并和诸多新技术相结合，广泛应用于多个领域。 如分布式数据库、并行数据库、多媒体数据库、模糊数据库、面向对象数据库等。 源于多维分析、数据挖掘和知识发现技术的深入研究，各种数据覆盖范围的数据 电子科技大学硕士学位论文 叠库得到愈来愈多的部署，数据集成中的各种问题亟待解决。 i3 新解决方案着眼点 j 。述问题的根源，来自计算机发展与食业信息化过程的不同步所致；即业务 数据飞速累积、单机计算能力有限提高、存储速度发展缓慢，更加之软件、安全 等方面开销成倍增长，这随之而来的问题便是信息系统的访问迟滞、资源利用低 效、峰值超负荷运转而易于宕机。企业计算所面临的主要问题是业务数据的海量 存储及其组织、主要业务支撑系统的咖靠畅通访问、业务数据的分析决策支持等。 解决之道是提供一个响应快速而町靠、易于扩充与管理、并能保证数据完整 致的集群数据库系统。相关的支撑技术包括聚合，协同计算、分布式存储、高速 高带宽高效率的通信网络、高效的数据挖掘系统、构建符合企业切身需求的经营 分析系统等。 对于计算、存储及其控制的方式，有集中和分布几种选择。在性能效率、可 管理性、可扩展性等指标的可接受性之问，可选择集中控制、分布计算、分椎存 储。即基于统一而可靠的调度器、采用存储区域嘲络( 规模较小时采用共享r a i d 磁盘阵列) 的服务器池集群。对于数据的组织管理，可将所需数量的一定服务器 配置成数据库集群，如o r a c l er a c ，以同时增强可靠性和处理性能。 1 4 内容组织 本文组织为三个部分七个章节： 第一部分在讨论企业信息集成实际需求的基础上，将解决企业信息系统的访 问性能、可用性、数据完整性作为主要目标。 第二部描述了解决该问题所相关的技术和方案；第二幸概要介绍了计算技术 的发展方向，综合分析了企业计算的高性能、高可用支撑技术，以及通信和存储 技术等；第三章则重点归纳总结了集群计算中的关键技术：第四章探讨了数据库 对保证数据完整有效和一致的相关技术机制。 第三部分作为本文主体，是在前述基础上对适应企业计算的集群系统作r 一 个切步的设计构想：第五章就主要阐述了相关的技术细节和为达到设计目标采取 的策略；第六章则是对这个原型系统的模型化测试，并作了初步评估；最后还提 出完善这种计算集群的进步研究方向。 完善这种计算集群的进步研究乃向。 第2 章基础支撑技术 2 1 计算模式演变 第2 章基础支撑技术 随着信息技术发展和信息化的普及，对系统计算能力和可靠性的要求不断攀 高。在计算机发展早期，囿于技术实现和成本，计算、控制、存储等功能均集中 在主机上，哑终端仅仅实现用户的键盘输入操纵、和屏幕输出回显等交互功能。 到8 0 年代，随着i c 技术进步和大型主机技术向下转移，微机能力迅速发展， 加之源于远程终端的通信网络技术的成熟，人们逐渐让服务器放权，把越来越多 的工作交给工作站去做，服务器只提供必需的文件、打印、邮件、数据库等服务， 由此大幅减少服务器的集中处理开销，使得客户端朋弪务器组网计算模式盛极一时。 随着应用系统的日益增多，以及频繁的软硬件升级，c s 体系结构【1 0 1 在诸如版 本更新、配置、安全等方面的管理和维护、町靠性、成本等方面上的缺点就凸现 出来，加之w w w 和浏览器技术的快速发展，在这种情况下以瘦客户机、n c 为 指导思想的浏览器服务器就应运而生，并在系统的开发部署数量、技术更新换 代、性能与效益的实际表现等方面取得极大成功。 同时基于自主性、多用途等需求，p c 已经变得愈来愈普及、计算性能也今非 昔比；同时得益于互联网的迅猛发展，非机密的绝大多数计算机均已入网。于是， 计算资源的广域分布、不断增长的对资源共享的需求、网络技术的发展成熟，在 分布式计算基础上催生了网格技术的产生。简要而言，这种计算模式利用互联网 把分散在不同地理位置的计算机节点组织成一个虚拟的超级计算机，使之具有强 大的数据协同处理能力、充分利用节点闲置处理能力、以相对低廉的价格可靠提 供相当质量的超级计算服务等优势。限于协议和体系结构的开放性标准化、性能、 q o s 、通信开销等方面的障碍，真正意义上的网格计算如g l o b u s 者尚寥寥无几【”】。 综上可见，从早期的主机系统、小型机系统、p c 机到现在的多元化系统，计 算模式的发展呈现出以主机一终端、c s 和b s 、分布式和网格系统为代表的集中控 制集中处理、集中控制分散处理、分散控制分散处理三种趋势。 理论研究和实际应用的历史经验表明，控制的集中可以保证更高的系统可用 性和性能发挥，而处理的分散则更容易获得更低的成本和结构扩展性。 如i b mzs e r i e s 主机产品中，通过耦合器( c o u p l i n g f a c i l i t y ) 和定时器( t i m e r ) 电子科技大学硕士学位论文 鼓术实现并行多处理系统( p a r a l l e ls y s p l e x ) 之间的资源共享和控制同步1 2 1 ，将传 统的活动一备份模式升级为负载共享的可调度系统，从而提供强大的计算能力和吞 j 上量，并拥有很强的容错与恢复能力。 2 。2 高性能计算 随着计算机应用的普及，各个应用部门对计算机的依赖性越来越大，并且对 训算枫的性能也提出了越来越高的要求。在诸如生物科学、能源、军事、工程设 训和自动化、预测模型的构造和模拟、基础理论研究等领域中提出了诸如计算规 模和计算精度等具有极高挑战性的要求。 超级计算机体系结构的发展，正是源于对计算速度、吞吐率、可靠性、可管 理性的追求，据其特点归纳主要有计算密集型、数据：密集型、网络密集型和综合 型三种应用需求类型。当前高性能计算的基本思想和技术路线均是将一组机群通 过网络互联，或利用现存网络计算资源，形成超级计算能力。在这种意义上，集 群计算、工作站网络、可伸缩计算、元计算、全球计算、网格计算，都可以统称 为基于网络的高性能计算。世界上最快的计算机将是i n t e r n e t 或是由网络连接起来 的计算机群，超级计算机t o p5 0 0 历年排名顺序已经极其明了地反映出这个趋势。 按照高性能计算的不同发展思路和侧重点，主要有以下类别 13 】： 1 1 超级计算集群( h i g hp e r f o r m a n c ec o m p u t i n g ) ：在s m p 架构及进程并行调 度机制基础上通过改进扩展性而来，具有响应大量计算的性能。如t u r b o l i n u x e n f u s i o n 、s c o r e 、m o s i x 等。 2 ) 高可用性计算集群( h i g ha v a i l a b i l i t yc l u s t e r ) ：提供软硬件故障失效的接 替和切换机制，最大限度地减少服务中断时间，包括计划停机和意外故障当机的 恢复时间，并且对一种服务而言不一定具有负载均衡功能。适用于面向关键任务 的不停机应用。这类集群有t u r b o l i n u xt u r b o h a 、h e a r t b e a t 、k i m b e r l i t e 等。 3 1 负载均衡集群( l o a db a l a n c i n gc l u s t e r ) ：在多节点之间按照一定的算法策 略分发网络或计算处理负载。负载均衡建立在现有网络结构之上，在接到访问请 求时，检查接受请求较少而不繁忙的服务器，并把请求转到这些服务器上。其目 的是提供和节点个数成正比的负载能力，以一种廉价有效的方法来扩展服务器带 宽，增加吞吐量，提高数据处理能力，同时又可以避免单点故障。这种集群适于 提供大访问量的w e b 服务。负载均衡集群往往也具有一定的高可用性和可扩展性。 t u r b o l i n u xc l u s t e rs e r v e r 、l i n u xv i r t u a ls e r v e r 都属于负载均衡集群。 第2 章基础支撑技术 2 2 1 计算机体系结构 从e n i a c 的出现到现在，计算机技术突飞猛进地发展，先后经历了以器件更 新为标志的从电子管、晶体管、中小规模集成电路到大规模和超大规模集成电路 四代系统的演变过程。电子器件制造技术的进步和计算机体系结构的发展极大地 推动了计算机性能地提高。目前，器件的性能虽然仍在高速的发展，但仍难以满 足计算的需求。研究并行可扩展的计算机体系结构成为提高计算机系统性能的_ 个重要途径。 并行计算机即是由多个处理单元组成的计算机系统，这些处理单元通过相互 通信和协作以快速、高效地求解大型复杂问题。其产生和发展如下图所示，结构 模型基本上沿着阵列机、并行向量多处理机系统( p v p ) 、共享存储的多处理机系 统( 以对称多处理机s m p 为代表) 、分布存储的大规模并行处理系统( m p p ) 、分 布共享存储多处理机( d s m ) 、以及集群系统等这样个历程方向发展，其主要代 表分别有i l l i a ci v 、c r a y y m p 一9 0 、s g ic h a l l e n g e 、i n t e lp a r a g o n 、s t a n f o r dd a s h 、 b e r k e l e yn o w 等等u 4 j 。 根据指令流和数据流的不同，通常可将计算机系统分为四大类：单指令流单 数据流系统( s i s d ) 、单指令流多数据流系统( s i m d ) 、多指令流单数据流系统 ( m i s d ) 、多指令流多数据流系统( m i m d ) 。m i m d 指多个处理机之间各自执行 不同的指令流，并分别作用于不同的数据流上；根据其处理单元间通信方式的不 同，有m u l t i p r o c e s s o r s ( 通过公用存储器中的共享变量实现) 、和m u l t i c o m p u t e r s ( 使用消息传递的方式实现) 之分。 m u l f i p r o c e s s o r s 为耦合程度较高的、共享存储的多处理机系统，多个处理机通 过总线、开关阵列或者多级网络等方式共享一个公共的存储器，分散在各个处理 器中的应用程序的各部分之间可以方便地通过共享存储变量来交换数据，并实现 各种同步和互斥操作。其访存模型有u m a ，n u m a ，c o m a ，c c - n u m a ，n o r m a 等五种。这类系统由于受到存储器带宽的限制，可扩展性一般较差，难以构建超 大规模和超高性能的计算系统。 m u l t i c o m p u t e r s 为耦合程度较低的、分布存储的多计算机系统，每个处理结点 通常都包括处理器、存储器和网络接口等部件，可视为一个完整的计算机，各个 处理结点之间则通过一个高速互连网络连接在一起，通过互连网络以消息传递的 方式实现间接访问。这类系统是实现作业、任务和指令各个级别全面并行的理想 结构，是当今并行处理系统的主流。在此基础上进而派生出以网格计算环境为代 表的高性能计算技术。 电子科技大学硕士学位论文 存多机系统中按其结点机的通用化程度，又有大规模并行处理机( m a s s i v e l y p a r a l l e lp r o c e s s i n g 简称m p p ) 和机群( c l u s t e r ) 两种类型。m p p 主要特征有：处 理结点采用商用微处理器；系统中有物理上的分布式存储器：采用高通信带宽和 低延迟、专门设计和定制的互连网络；能扩放至成百上千各处理器；它是一种异 步的m i m d 机器，通常运行一个操作系统的微核，程序系由多个进程组成，每个 都有私有地址空间，进程间采用传递消息相互作用。相比之下，集群系统的结点 机通常采用现成的商用微机、工作站和s m p ，是一个具有处理器、内存、硬盘以 及网络接口等部件的完整计算机系统，可以独立地工作。 22 2 处理器技术 图2 - 1 、m i m d 计算机的分类 微处理器是现代计算机系统核心和引擎，它不仅提供计算机系统所需的处理 能力，而且能够管理缓存、内存和互联子系统、支持整个系统实现多处理器弗行 计算。现代计算机最大的特点就是并行型，充分发挥处理器内部的并行性是现代 处理器的主要目标。现代处理器按照可编程性、编译器设计、芯片设计、能耗等 有关指令集方面的差别，通常可分为复杂指令集( c i s c ) 、精简指令集( r i s c ) 及显式并行指令集( e p i c ) 三类。除了字长和主频技术外，为提高单机性能，有 关支持并行、提高效率的常用体系结构新技术的有超标量技术、v 1 l w 、流水、 c a c h e 、同时多线程、向量i r a m 技术、单芯片多处理器技术、超线程技术等。 2 2 3 并行计算 并行计算的发展是基于人们在两个方面的认识，一是单机的性能由于物理限 第2 章基础支撑技术 制、： 艺水平和制造成本等因素限制，不可能满足大规模科学与工程问题的计算 需求，而并行计算机是实现高性能计算、解决挑战性计算问题的唯一途径；二是 同时性和并行性是物质世界的一种普遍属性，具有实际物理背景的计算问题在许 多情况下都可以划分为能够并行计算的多个子任务。 相关性分析( d e p e n d e n c y a n a l y s i s ) 作为研究计算程序中所有语句间依赖关系 的。种理论，是并行算法的基础。顺序代码段中一般有如下的四种相关 15 】：流 相关( f l o w d e p e n d e n t ) 、反相关( a n t i d e p e n d e n t ) 、输出相关 ( o u t p u t d e p e n d e n t ) 、控制相关( c o n t r 0 1 d e p e n d e n t ) 。 针对具体应用问题，可以利用它们内部所固有的并行性，设计并行算法，即 将其分解为相互独立、但彼此又有一定联系的若干子问题，分别交给各台处理机， 而所有处理机按并行算法共同完成应用问题的求解。因此基于并行算法，可以利 用并行机求解大规模现实问题，有效提高计算机系统计算速度和处理能力，以满 足各个应用部门的需求。 2 2 3 1 并行计算模型 计算模型作为软硬件问的一种桥梁，用以设计分析算法，以及编译和硬件实 现高级语言。在串行计算时，冯诺依曼机就是一个理想的串行计算模型。并行 计算模型是并行计算的低层实现与高层抽象的界面，需要相当的抽象度与通用性。 传统并行计算模型，如从共享存储的s i m d 抽象而来的同步p r a m 模型、从 共享存储的m u l t i p r o c e s s o r s 抽象而来的异步p r a m 模型、从分布存储的 m u l t i c o m p u t e r s 抽象而来的s p 和l o g p 模型等【1 6 1 ，均不适用于基于l a n 的c o w 结构，或者基于w a n 的格点结构。新一代面向c o w 的、基于l o g g p 和b a r r i e r 同步的非独占异构计算模型n h b l a x ，已经趋于成熟。 1 ) p r a m 模型( p a r a l l e lr a n d o m a c c e s sm a c h i n e ) 并行随机存取机器模型中，假定存在着一个容量无限大的共享存储器；有多 个功能相同的处理器，且均具有简单的算术运算和逻辑判断功能；任何时刻各处 理器均可以通过共享内存交换数据。 s h a r e dm e m o r y 图2 - 2 、p r a m 模型 电子科技大学硕士学位论文 p r a m 模型使用简单，特别适合于并行算法的表达、分析和比较；且处理器 问通信、存储管理和进程同步等细节均隐含于模型中；使用该模型易于设计算法， 舅稍加修改即可运行于不同的处理机。在目前算法界被普遍接受和广泛使用。 但p r a m 模型作为一个同步模型，单一存储器的假定忽略了存取竞争和有限 带宽，对并行任务的增大不加限制。针对这些问题，通过共享存储的m u l f i p r o c e s s o r s 珂、境抽象，衍生出异步p r a m 模型，可初步解决访问冲突和异步模拟。 2 ) b s p 模型( b u l ks y n c h r o n o u sp a r a l l e l ) 轻量同步模型也称为块同步模型，它采用三个定量的参数p ，g ，l 描述的分 布存储的多计算机模型。p 是处理器和存储器模块，简称处理器；g 是处理器间点 对点消息传递的选路器；l 则是执行以时间间隔l 为周期的路障同步器。 c o m m t m i c a t i o nn e t w 。r k 图2 3 、b s p 模型 b s p 模型由n 个p m 对组成，借助网络进行互连。计算通过全局同步由一系 列周期为l 的超级步所组成。在各个超级步中，各处理器p 均执行局部计算，并 通过选路器g 接收和发送消息。然后作一全局检查，确定该超级步是否已由所有 处理器完成。若是，则进入下一步；否则下一个l 周期分配给未完成的超级步。 b s p 模型采用路障方式实现粗粒度同步，提供了执行紧耦合同步式算法的有 效方式。且为p r a m 模型所设计的算法，均可在每个b s p 处理器上模拟实现。 3 1 1 0 9 p 模型 l o g p 模型是种分布存储的，点到点通信的多处理机模型。其通信网络自一 组参数来描述，其中延时l 表示网络中消息从源到目的地所遭到的延迟；额外开 销0 是指发送或者接收一条消息所需的额外开销；时间间隔g 是指处理器可以连 续进行消息发送或者接收的最小时间间隔；l 和g 一起反映网络的容量；处理器p 表示处理器存储器模块数。 i o g p 模型充分揭示了分布存储并行机的性能的主要瓶颈，用l 、0 、g 三个参 数刻画了通信网络的特性，但却隐藏了网络的拓扑结构、选路算法和通信协议。 4 1 c 3 模型( c o m p u t a t i o n ，c o m m u n i c a t i o n ，c o n g e s t i o n ) c 3 模型是一个与体系结构无关的粗粒度并行计算模型，与b s p 模型和l o g p 模型相似，旨在反映计算复杂度、通信模式和通信期间潜在的拥挤诸因素对粗粒 第2 章基础支撑技术 度喇络算法的影响，考虑了网络链路拥挤和处理器拥挤对并行算法的影响。 2 2 3 2 并行程序设计模型及语言 除数据并行程序设计模式外，目前广泛使用共享存储程序设计模式和消息传 递程序设计模式，各自均适用于一定的硬件体系结构。前者能够直接对应共享存 储的体系结构，如s m p 系统、n u m a 系统；后者可以直接对应分布式存储体系结 构，如机群系统、m p p 。发展趋势是新的跨平台、构件化的并行模型。 1 ) 数据并行程序设计模式是s i m d 的自然模型，通过将相同操作同时作用于 不同数据，而提高问题求解速度。作为一种细粒度的并行，数据并行语言用单线 程控制配合用户定义的数据和计算在处理器上的分布注释，由程序员在一一个全局 的地址空间中简单地给出有关并行的指示，而性能效果则在很大程度上依赖于能 否确定一个好的数据分布。 2 ) 共享存储程序设计模式适合于p v p 、s m p 、n u m a 等共享存储的计算机系 统，各处理器驻留进程通过读写公共存储器中的共享变量相互通信。数据驻留在 单一共享的地址空间中，无需显式分配数据，而工作负载可以是显式或隐式的。 共享存储的程序设计与数据并行相似之处在于它有一个单一的全局地址空间，弓 消息传递程序设计的相似之处在于它是多线程的和异步的。 3 ) 消息传递并行程序设计模式属于s p m d 或m p m d 编程模型，是m p p 和机 群系统采用的主要编程方式，也适合于s m p 、n u m a 等共享内存的并行计算机。 在此模式中，并行应用由一组进程组成，每个进程的代码是本地的，只能访问私 有数据，进程之间由用户通过显式的发送和接收消息实现数据共享和进程同步。 即需要程序员显式分配每个进程要处理的负荷和所需数据，显式同步程序，保障 进程间的数据划分和顺畅通信。其优点是用户可以对并行性的开发数据分布和通 信实现完全控制，并具有良好的跨平台性和可移植性。 基于消息传递的并行编程语言中最流行的是并行虚拟机( p a r a l l e lv i r t u a l m a c h i n e ，p v m ) 和消息传递接口( m e s s a g ep r o c e s si n t e r f a c e ，m p i ) 。p v m 是 种基于局域网的并行计算环境，能够将异构的u n i x 计算机通过异构网络连接成 个易于管理、编程、扩展的虚拟并行计算系统，为其上运行的应用程序提供分布 式并行计算环境。m p i 是一种基于消息传递模式的并行编程接口标准，旨在提高 并行程序的可移植性和易用性，所有并行计算机制造商都已提供m p l 支持。m p i 比p v m 具有更佳的功能、性能、适应面、扩展性等，但不支持进程的动态管理 1 7 。 电子科技大学硕士学位论文 22 4 并行化分解 依据求解问题的基本运算对象、子问题间的依赖关系、以及基本任务的粒度， 在数据划分前提下，可有如下并行化分解方法： 1 ) 任务分解：多任务并发执行，适用于不同参数的大量工况计算。 2 ) 区域分解：分解被执行的数据，适用于大规模多节点分块并行计算。 3 ) 功能分解：分解被执行的计算，在分治基础上将复杂问题分解成若干简单 予问题，再