(计算机软件与理论专业论文)基于均值机群动态负载平衡系统的设计与实现.pdf_第1页
(计算机软件与理论专业论文)基于均值机群动态负载平衡系统的设计与实现.pdf_第2页
(计算机软件与理论专业论文)基于均值机群动态负载平衡系统的设计与实现.pdf_第3页
(计算机软件与理论专业论文)基于均值机群动态负载平衡系统的设计与实现.pdf_第4页
(计算机软件与理论专业论文)基于均值机群动态负载平衡系统的设计与实现.pdf_第5页
已阅读5页,还剩88页未读 继续免费阅读

(计算机软件与理论专业论文)基于均值机群动态负载平衡系统的设计与实现.pdf.pdf 免费下载

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

北京交通大学硕十学位论文 5 8 6 2 1 9 摘要 计算机和网 络技术的 发展使得机群系统成为并行计算的主流 趋势, 而负 载平衡技术是影响机群并行性能的主要因素。 负载平衡技术的核心, 是将各 个任务比 较均衡的分布到不同的处理结点上并行执行, 从而提高系统资源的 利用率。 本文正是从这种需求出发, 设计并实现了基于均值的机群动态负载 平衡系统。 本文的研究重点是规则的数据并行程序的动态负载平衡问题, 它属于中 粗粒度的作业级应用, 特点是只存在父子任务之间的通信, 该类问题是实现 高性能计算的基础,具有深远的应用价值。 本文所做的主要工作和贡献: i 、详细介绍了机群系统的体系结构、分类以及所研究的主要领域,说 明了负载平衡问题在机群系统中所占的重要地位,对负载平衡问题从产生、 发 展到目 前的 研究现状 进行了阐 述, 并 对一些具有代表性的机群负载平衡系 统的 设计进行了 深入的 研究和 分析。 z 、从动态负载平衡技术的基本组成要素出发,本文分析比较 了一些现 存系统所采用的策略,从结构, 调度时机的选取,以及系统参数的设计等角 度对其进行了改进。 3 、 在对上述基本组成要素分析的基础上,本文对负载平衡系统的设计 进行了扩展。首先, 构造了防颠簸函数, 一方面解决负载平衡问题中可能会 出现的颠簸现象,另一方面作为负载平衡集合的选取标准。 然后, 本文还设 计了适用于异构机群的基于均值的调度算法。 另外, 本文还对传统的任务提 交 和分配方式进行了改 进, 从而实现了 单个或 者成组任务的 提交和分配, 减 少了通信次数。 4 、 本文通过消息传递机制的 运用, 还实现了 结点机的动态加入、 退出, 任 务的动态提交、 分配, 各结 点机之间的任务负载平衡信息的传递等功能。 5 、最后, 本文通过多次 试验 工作, 将该 系统与 其它负 载平衡系统从不 同 的 角 度 得 出 的 实 验 结 果 进 行 分 析 和 比 较 , 并 提 出 了 进 少 的 研 究 工 作 。 关键词: 相群索统消 r 传递 负载平衡 任务调度 接收者驱动 颠簸 均值 北京交通大学硕士学位论文 abs t r ac t wit h t h e r a p i d d e v e l o p m e n t o f c o m p u t e r a n d n e t w o r k t e c h n o l o g i e s , c l u s t e r o f w o r k s t a t i o n ( c o w) i s n o w b e c o m i n g t h e m a i n t r e n d o f p a r a l l e l c o m p u t i n g h o w e v e r , t h e t e c h n o l o g y o f l o a d b a l a n c i n g i s o n e o f t h e mo s t i m p o rt a n t f a c t o r s w h i c h g r e a t l y c o n t r i b u t e t o t h e p e r f o r m a n c e o f c o w. i n o r d e r t o i m p r o v e t h e u t i l i t y o f c o w , t h e c o r e o f l o a d b a l a n c i n g i s t o a l lo c a t e t h e w o r k l o a d s a m o n g a l l t h e p r o c e s s o r s b y s c h e d u l i n g p o l i c i e s . f r o m t h e p o i n t o f v i e w , t h e a rt i c l e d e s i g n s a n d r e a l i z e s a s y s t e m 一 mv - b d l b s ( me a n v a l u e - b a s e d d y n a mi c l o a d b a l a n c i n g s y s t e m). t h e r e s e a r c h p u t s e m p h a s i s o n r e g u l a r d a t a p a r a l l e l i s m p r o g r a m s d y n a mi c l o a d b a l a n c i n g i s s u e . n o t o n l y i t s c h a r a c t e r i s t i c w i t h m e d i u m o r c o a r s e g r a n u l a r i t y j o b a p p l i c a t i o n b u t a l s o i t h a s i n t e r c o m m u n i c a t i o n s b e t w e e n p a r e n t s a n d c h i l d r e n t a s k . s u c h k i n d o f i s s u e i s t h e b a s e o f r e a l i z i n g h i g h - p e r f o r m a n c e c o m p u t i n g w i t h f a r - r e a c h in g p r a c t i c a l v a l u e s . t h e c o n t r i b u t i o n s o f t h i s d i s s e rt a t i o n a r e a s f o l l o ws : i 、 f i r s t l y , t h e a rt i c l e i n t r o d u c e s t h e a r c h i t e c t u r e , c l a s s i f y a n d m a in r e s e a r c h f i e l d s o f c o w. i t a l s o a n a l y s e s t h e i mp o rt a n c e o f l o a d b a l a n c i n g i n c o w. a f t e r t h a t , t h e i s s u e fr o m t h e a p p e a r a n c e a n d d e v e l o p m e n t t o s t a t u s q u o o f l o a d b a l a n c i n g is s h o w n . s o m e r e p r e s e n t a t i v e s y s t e m s h a v e a l s o b e e n i n v e s t i g a t e d a n d a n a l y z e d . 2 . t o b e g i n w i t h t h e b a s i c e l e m e n t s w h i c h c o n s i s t o f d y n a m i c l o a d b a l a n c i n g t e c h n o l o g y , t h e a rt i c l e n o t o n l y a n a l y z e s t h e s t r a t e g i e s t h a t t h e s y s t e m s e x i s t i n g a d o p t , b u t a l s o i m p r o v e t h e m a t t h e a s p e c t s o f s t r u c t u r e,s c h e d u l e t i me , p a r a me t e r s o f s y s t e m a n d s o o n . 3 . t h e a rt i c l e e x p a n d s t h e d e s i g n b a s e d o n t h e a b o v e e l e m e n t s . f i r s t l y , m a k e a n a n t i - t u r b u l e n c e f u n c t i o n , w h i c h c a n d e a l w i t h t h e t u r b u l e n c e p h e n o m e n o n i n t h e p r o c e s s o f l o a d b a l a n c i n g . b e s i d e s t h i s , it i s u s e d a s t h e c r i t e r i o n o f c h o o s i n g t h e e l e m e n t s o f t h e l o a d b a l a n c i n g s e t . s e c o n d l y , a s c h e d u l e s t r a t e g y b a s e d o n m e a n v a l u e i s d e s i g n e d a n d a p p l i e d t o h e t e r o g e n e o u s c o w f u r t h e r m o r e , t h e 北京交通大学硕士学位论文 a rt i c le i m p r o v e s t h e t r a d i t i o n a l m e t h o d o f t a s k s u b mi s s i o n a n d a s s i g n m e n t . t h e r e f o r e , t h e t a s k s c a n b e s u b mi tt e d a n d a s s i g n e d b y s i n g l e o r g r o u p r e d u c i n g t h e c o mmu n i c a t i o n t i me . 4 , t h r o u g h t h e a p p l i c a t i o n o f t h e m e s s a g e t r a n s f e r r i n g m e c h a n i s m , t h e n e w s y s t e m m a k e s s o me f u n c t io n s p o s s i b l e , f o r e x a mp l e , t h e d y n a m i c e n t e r i n g o r e x i t i n g o f n o d e , t h e d y n a m i c s u b m i tt i n g o r ass i g n i n g o f t a s k , t h e t r a n s m i s s i o n o f l o a d b a l a n c i n g me s s a g e s a mo n g n o d e s . 5 , t h e a r t i c l e ma k e s c o mp a r e s a n d a n a l y s e s b e t w e e n t h e n e w s y s t e m a n d t h e o t h e r s f r o m s e v e r a l d i ff e r e n t a n g l e s . i t i s a l s o p u t f o r w a r d t h e f u r t h e r s t u d y f i e l d i n co w k e y w o r d s : c l u s t e r o f w o r k s t a t i o n s , me s s a g e t r a n s f e r r i n g , l o a d b a l a n c i n g , s c h e d u l e , r e c e i v e r - i n i t i a t e d , t u r b u l e n c e , m e a n v a l u e 北京交通大学硕士学位论文 第一章 概 述 1 .1 背景与研究动机 那 .1 . 1 并行计算的产生与发展 十年前,一提起并行计算,很多人都会联想到那是大型机所能做的 1 f o 然 而 , 十 年 来, 这 一 切发 生 了 巨 大的 变 化。 以p v m , m p t , p 4 , e x p r e s s , l i n d a 及g l u n i x 等为代表的网 络并行计算环境由 于构造简单、成本低 廉、 编程和实现方便等众多优点而受到并行处理研究与应用人员的青睐, 人们在 这 些 平 台 上 卜 发 了 大 量 的 应 用 , 形 成 了 可 供 继 承 和 扩 展 的 丰 富 的 应 用 程 序 库。而且,这一趋势还将以更大和更深的程度延续下去、 、 、 、 、 、 计算机技术、 尤其是用于低端桌面系统的计算机技术和网络技术的快速 发 展 演绎着这一切. 十年来, 个人机的处理性能以 超出莫尔定律的 速度飘升, 工作站和服务器的性能价格比每年的增长的速度高达 8 0 %, 而大型机和超级 计算机的性能价格比每年的增长率仅为 2 0 % - - 3 0 %,远远落后于工作站和服 务 器, 更落后于个人机。 这种变化, 使得个人机与 工作站、 甚至工作 站与 服 务 器的功能差别变得越来越小, 个 人机已 经可以 部分或 者全部的 替代原 先只 有工作站或服务器才能完成的工作;同时, 大型机和超级计算机之间的差别 也 正在缩小。 个人机、 工作站、 服务器等低、 中 端计算机领域之所以 有如此 迅速的发展, 根本原因就在于其良好的性能价格比满足了用户的需求、 增强 了用户的购买能力, 实现了技术更新与市场扩大之间的良性循环; 而大型机 和超级计算机由于没有足够的用户需求, 或者由于其昂贵的价格使得用户望 而却步,以及技术突破本身方面的困难等原因而导致其性能提高缓慢。 十年 来, 计算机网络以 前所未有的 速度向 前发展, 使整个信息产业的核 心都转移到了以网络为中心的计算时代。 网络的飞速发展使我们充分享受了 它所带给我们的高效、 方便与快捷, 使相同地域的不同计算机和不同地域的 工作组之间可以相互协作, 以解决一台或者少量计算机不能解决的问题。 十 年来, 在局域网或者广域网范围内, 结点间的通信速度有了质的飞跃, 不但 北京交通大学硕士学位论文 使多 个结点的协同计算成为可能, 而且 促进了 一大批单机应用程序向 多机、 网 络化方向的 转变, 使多个结点的协同计算和求解在某些方面成为一 种必 然。 计算 机和网络技术的发展使一 种新型的并 行计算模式一网 络并行计算, 成为可能和现实。 所谓网络并行计算, 就是指充分利用网络上的计算机资源, 通过高速网络, 实现大规模并行计算。 除了少量的像地质、 气象、 航天飞行、 流体力学等领域的计算机用户, 很多用户其实并不经常需要超级计算, 即使 用有超级计算机或者大型机, 其使用率也较低。因此,由于其较差的性能价 格比和较低的利用率, 除非万不得已, 用户不愿意或者没必要购买这类大型 和超级计算机。 一旦有超级计算需要, 可以通过网络将多个计算机组合起来 使其在一个适当的网络软件平台的管理与控制下, 充分发挥各自优势, 合作 起来完成超级计算功能。 我们称这种网络并行计算所依赖的环境为网络并行 计 算环境。 由 于高速网 络的 高带宽和低延迟性能 国 际上己 经有越来越多的 研究单 位采用这种网络并行计算模式来 解决 他们的大型并 行计算问 题, 如美 国成功破译的 r s a 1 2 9密码就是在因特网上利用 1 6 0 0多台计算机在这种网 络并行计算模式下合作完成的。由于其所需要的计算资源成本低廉、 构造容 易、 性能价格比高等优点, 网 络并行计算已 经成为并行计算领域一个极具发 展前景的重要分支, 尤其适合于我国这样既需要并行计算, 又缺乏足够经费 支持和条 件的国家。 当前主要的网 络并行计算环境有p v m, m p i , g l u n ix , e x p r e s s , l i n d a 等, 它们在世界范围内 均有着广泛的 应用, 取得了 显著的成 效。 1 .1 .2机群的产生与发展 机 群n o w ( n e t w o r k o f w o r k s t a t i o n ) 正是在并行计算迅猛发展的背景下 产 生和发展起来的。 最先提出n o w概念和从事n o w研究的是美国加州大 学b e r k e r l e y 分校的n o w研究小组。 他们把机群定义为: “ 由多个独立的计 算机通过高速网络和特定的 网络操作系统 ( 如g l u n i x 等) 连接而成的一个 可用来进行大规模并 行处理 和负 载平衡的网 络并 行环境” 。 利用价 格低廉的 多个计算机和特定网 络操作系统构成的机 群, 即 可进行大规模并行处理, 每 个计算 机又可独立的为用户提供服务, 具有较高的性能价格比, 且 通过适当 北京交通大学硕士学位论文 的 任务 调度和负载平衡机制可以 大大提高整个机群的 工作效 率. 因此, 对于 机群的研究和开发, 成了近年来分布式处理和并行计算领域的一个最大的热 点 之一。 b e r k e r l e y 大学n o w研究小组和g l u n i x 研究 小组的 研究和实验结 果相继表明, n o w 的性能非常令人满意, 前者在 d i s k - t o - d i s k排序中名列前 茅, 后者在指纹映像、 并行编译等方面都显示了较强的性能, 两者都已经成 功的扩展到了包含 1 0 0 个结点的n o w 中。 扒.1 .3机群负载平衡的意义 a n d e r s o n 丁 【 在文献中 指出 在一个n o w环境中,大部分结点 在大部分 时间内 都处于低利用率状态。 加州大学b e r k e l e y n o w研究小 组的研究结果 表明: 即使在每天下午最繁忙的时候, 平均也有近 6 0 %的结点处于空闲可利 用状态。 尽管不同系统对于 “ 空闲可利用状态”的定义不同, 但有一点是肯 定的,即这些结点上的负载较轻, 还可以承受更多的任务。如果我们把 “ 空 闲可利用状态” 定义为结点开机但不运行应用程序 ( 只占少量计算资源的一 些常驻d a e mo n 进程除外) , 用户连键盘、鼠标都不动一下, 表 1 - 1 列出了某 实 验室3 个月内 关于空闲 可利用结点的统计结 果 z 1 . 日 期起始时间结束时间 开机总结 点数 空闲可利用结 点数 星期一至星期五 0 : 0 07: 4 02 3 . 42 2 . 9 5 星期一至星期五 8 : 3 01 1 : 3 03 7 乃11 7 . 1 5 星期一至星期五 1 2: 1 51 4: 0 52 6 . 3 8 2 4 . 2 6 星期一至星期五 1 4: 5 01 7: 0 0 3 6 .431 8 . 8 7 星期一至星期五 1 8 : 3 0 2 3: 0 0 2 8 . 5 52 3 . 2 6 星期一至星期五 0: 0 02 4: 0 01 6 . 7 91 4 . 4 2 表 1 - 1 从上表中 可以 看出,即使 在星期一 至星期五上午,下午最繁忙的时候, 仍然有不少的结点处于空闲可利用状态。 机群中 这些空闲可 利用结点, 如果不加以 合理的利 用,其c p u等计算 资源就白白的浪费了。而实际上, 在一个局域网或者广域网内, 在高速网络 和适当的任务调度和负载平衡机制的管理与控制下, 我们可以 充分利用这些 北京交通大学硕士学位论文 空 闲 可 利用结点 来执行大规 模并行 计算和结点间 负载平衡。 这种为了 充分利用高度并行的系统资 源, 提高 整个系 统的吞吐 率, 而 采 用 的策 略称之为负载 平衡技术。 负载平衡技 术的 核心是调度算法, 即将各 个 任务比较均衡的分布到不同的处理结点上执行, 从而使各结点的利用率达到 最大。 这种基于机群的任务调度和负载平衡机制, 由于其极强的应用背景和极 为 广阔 的发展前景,己 经成为并行领域一个十分重要的发 展方向 3 j 1 .2论文组织及贡献 如.2 . 1 论文组织 第一章概述了 并行计算和机群技术的产生和发 展, 以 及机群中 任务调度 和负载平衡的意义。 第二章详细介绍机群系统的体系结构、 分类、 发展优势以及机群系统的 主 要研究 领域。 第三章详细讨论了负载平衡的产生原因 和定义、 负载平衡的 意义所在, 负载平衡的分类, 并详细介绍了静态负载平衡和动态负载平衡, 并且将两者 加以比 较。 第四章介绍了现存的一些负载平衡系统, 分析其存在的不足, 提出基于 均 值的 机 群 动 态 负 载 平 衡 系 统m v - b d l b s ( m e a n v a lu e - b a s e d d y n a m ic l o a d b a l a n c i n g s y s t e m) 的设计方案。 第五章详细阐述了基于均值的机群动态负载平衡系统的设计和实现。 第六章通过与现存系统的比较实验,对其总结并展望进一步的工作。 扒.2 .2论文主要贡献 本文的主要工作包括以下几个方面: 首先, 对并行计算以 及机群系统的产生和发展 进行了介 绍, 分析了 机群 系 统的 体系结构, 分类以 及得以 迅速发 展的 优势所在, 并且对机群系 统研究 的主要领域进行了剖析。 北京交通大学硕士学位论文 进而, 详细介绍了机群系统中负载平衡问题的产生发展和分类, 重点讲 述了静态负载平衡和动态负载平衡技术, 并且广泛而深入的研究了一些具有 代 表 性的 机群负载平衡技术, 分析 这些系统的 设计思想、 实现技术, 借鉴其 先进之处,总结其不足。 最后, 对网络通信技术进行了研究, 并且对并行性能的评价指标进行了 探讨。 本文的主要工作和贡献: 1 、 深入 研究动态负载平衡技术的基本组成 要素, 分析 现存系统所采用 的 策略, 进行了 总结 和改进, 结构上 选用全 局集中 控制方式, 实 现简单, 掌 握负载信息全面, 减少通信开销。 在调度时机选取上采用接收者驱动的方式, 由空闲结点发出调度请求, 避免了周期性的信息查询,减少通信时间。 系统 参 数设计成静态和动态信息相结合的方式, 在初始阶段, 搜集各个结点的 静 态信息,根据这些信息,进行任务的初始分配; 在任务执行阶段, 综合各个 结 点的动态信息, 动态的 分配任务, 保证更准确有效。 z 、 在基本组成要素的基础上 进行扩展, 构造防颠簸函 数: 一方面解决 负载平衡问题中可能会出 现的颠簸现象, 另一 方面作为负 载平衡集合的选取 标准, 区别于现存系统中点对点或者是全局参与的集合选取方式。 设计了基 于均值的调度算法, 从同构机群引出均值的思想, 并将其应用到异构机群的 情况。 3 、 本文还对传统的任务提交 和分 配方式进行了改 进, 任务不是单独提 交的,也不是一经分配到子节点上就执行,而是,可以一次提交多个任务, 系统分配任务时也可以将多个任务一次分配给某一个节点, 实现了单个或者 成组任务的提交和分配,减少了通信次数。 4 、 本系统通过消息传递机制,在统一的消息结构中, 定义了不同的消 息类型和接 口函数, 从而实现了结点机的动态加入、 退出, 任务的动态提交、 分配, 各结点机之间的任务负载平衡等信息的传递以及各结点机信息的采集 等功能。 最后,本文将该系统与其他负载平衡系统从不同的角度进行了多次试 验,并 对实 验结 果进行分析和比 较,并提出 进一步的 研究 工作。 北京交通大学硕士学位论文 第二章 机群系统 2 . 1 机群的体系结构 2 .1 .1机群基本体系结构 机群系统是互相连接的多个独立计算机的集合, 这些计算机可以是单机 或多处理器系统 ( p c ,工作站或 s m p ) ,每个结点都有自己的存储器,1 / 0 设 备和操作系统。 机 群对用户和应用来讲是一 个单一的 系统, 这 样的系 统可 以提供低价高效 的高性能环境来提供快速 可靠 的服 务,其一般结构 如下图 2 - 1 - 1 . 并 行应 用 c nm m sm 干 w et s y!c om et 4 w 篇 .- . 17 c or m s iw 抽 . t . a二e衬份 t 玩t 几. 七s .7 1 9 yt 如t n v 比.1 护日n nt o . 止 . 甘即 n et nma m e 叫 图2 - 1 一 i 以下是机群计算机的一些重要部件: 4多个高性能计算机 ( p c 、工作站或s mp ) 令优秀的操作系统 ( 分层或 基于微内 核) 4高性能网 络/ 开关 ( 如千兆位以 太网或m y r i n e t ) 4网络接口卡 ( n i c ) 夺快速通信协议和服务 ( 如活动消息和快速消息) 0机群中间件 ( 单一 映像系 统s s i 和系统可 用性基 础) 北京交通大学硕士学位论文 第二章机群系统 2 1 机群的体系结构 2 1 i 机群基本体系结构 机群系统是互相连接的多个独立计算机的集合,这些计算机可以是单机 或多处理器系统( p c ,工作站或s m p ) ,每个结点都有自己的存储器,i 0 设备和操作系统。机群对用户和应用来讲是一个单一的系统,这样的系统可 以提供低价高效的高性能环境来提供快速可靠的服务,其一般结构 如下图2 1 1 。 苗重呈 图2 1 1 以下是机群计算机的一些重要部件: 夺多个高性能计算机( p c 、工作站或s m p ) 夺优秀的操作系统( 分层或基于微内核) 夺 高性能网络开关( 如千兆位以太网或m y r i n e t ) 夺网络接口卡( n i c ) 夺快速通信协议和服务( 如活动消息和快速消息) 夺机群中间件( 单一映像系统s s i 和系统可用性基础) 6 北京交通大学硕士学位论文 一硬件( 如d i g i t a l ( d e c ) 陕j 存通道、硬件d s m 和s m p 技术) 一操作系统内核或粘合层( 如s o l a r i sm c 和g l u n i x ) 一应用程序和子系统 一应用程序( 如系统管理工具和电子表格) 一实时系统( 如软件d s m 和并行文件系统) 一资源管理和调度软件( 如l s f ( d 载分配器1 和c o d i n e ( 分布网 络环境中的计算) ) 夺 并行编程环境和工具( 如编译器、p v m ( 并行虚拟机) 和m p i ( 消息 传递接口1 夺应用程序 一串行 一并行或分布式 2 1 2 与其它体系结构的比较 机群、s m p 、m p p 以及分布式系统是4 个重叠的体系结构概念。分布 式系统一个很好的例子就是l a n 。如下图2 1 2 所示: 单一系统快俊 图2 1 2 l a n 中的一个结点可以是一台p c 、一台工作站或者一台s m p 服务器。 结点复杂性是指硬件和软件能力。机群结点要比m p p 结点复杂,因为前者 北京交通大学硕士学位论文 有一个磁盘且有一个完整的操作系统,而后者可能没有磁盘且只使用操作系 统的一个微核。 s m p 服务器比机群结点更为复杂,因为它有较多的外围设备,如终端、 打印机、外部的磁盘阵列以及磁带等。在机群的结点中,可能只有部分的上 述外围设备。我们设想机群范围在未来将继续扩展,因而会与m p p 和s m p 有更多的重叠。 水平轴表示在不同抽象层次上的s s i 程度:其范围包括一个单一应用层 次、子系统、运行时间系统、操作系统内核以及硬件层次。换句话说,s s i 是一个相对概念,取决于用户所见到的s s i 边界。s m p 总是在所有的层次 上提供s s i ,m m p 仅在某些应用和系统层次上支持s s i ,而机群能提供的 s s i 程度低于s m p 。但与m p p 提供的不相上下。 机群或m p p 能用作单资源,而一个分布式系统常产生多系统映像,因 为在网络范畴内的单个计算机具有自治性。目前m p p 和分布系统的最大规 模可有几千个结点。大多数机群规模为几十个结点,仅有少数机群的规模超 过百个。 m p p 结点通常运行一个微核,而其它系统结构中的结点则使用完整的 操作系统。在分布式系统中的操作系统通常是异构的,而其它系统结构则倾 向于使用同构操作系统。在m p p 或机群中的结点间通信通常使用消息传递, 而在分布式系统常使用服务器中的共享文件。s m p 中的处理器则通过共享 存储器进行通信。只有s m p 维持单地址空间。仅当d s m 由硬件支持时m p p 才有单地址空间。 对所有处理器,s m p 有单一运行队列。机群和m p p 中使用多运行队列, 各运行队列相互合作以平衡负载。分布式系统中的多队列,大多是独立的。 分布式系统常跨越多个机构,因此需要结点间安全措施,这一点m p p 和机 群是不需要的。 北京交通大学硕士学位论文 2 .2机群系统的 分类 根据几个不同的属性对机群进行分类,如下图2 - 2 所示: 属性属性值属性值 应用 目标 高性能机群 高可用性机群 组装方式紧密松散 控制方式集中分散 同构性同构异构 安全性 隐蔽暴露 实例独用型机群企业型机群 建筑机群的方式专用机群非专用机群 图 2 - 2 按应用目标可分为面向科学计算的高性能机群( h i g h p e r f o r m a n c e c lu s te r )和面 向 关 键 任 务 应 用 的 高 可 用 性 机 群 ( h ig h a v a i la b i lity c lu s te r) . 按组装方式, 机群的各个结点可以紧密或松散的组合在一起。 在紧密机 群中, 结点被较接近的 组装在一个或几个同 处一室内的 机架中。 结点 不 与外围设备相连。 在松散机群中, 结点仍与各自 的外围设备相 连, 它们 可以在不同的房间内, 不同的建筑物中, 甚至在地理上相隔遥远的场所。 按 控制方式, 一个机群可以 采用集中 控制或管理与非 集中 控制或管理两 种方 式。 在集中控 制方式下, 所有结点为 一个中央 操作 者所有, 并由 其 进行控制、管理和支配。在非集中控制方式下,结点有各自的属主。 按处 理机的配置, 可分 为同 构型机群 ( 所有结点拥有相同的处理机结构 和相同的 操作系统 ) 和异构型 机群( 所有结点采用不同的工作平台 )o 按组成机群的处理机类型可分为p c机群、 工作站机群和 s nip( 对称多 处理器)机群。 从安全性角度考虑, 机群内各结点的通信连接方式可以为暴露式或隐藏 式两种。 在暴露式机群中, 结点间的通信线路暴露与外部世界, 机群之 外的机器也可以访问通信线路和机群内的结点。 隐藏式机群中, 机群内 通信与外部世界相屏蔽。 从实例分析, 机群也可以 分成两类: 独用型和企业型。 独 用型机 群具 有 一下特点: a . 一般安装在一个中 央计算机房的桌 边机架上: b 一 般由相 北京交通大学硕士学位论文 同类型的结点同构的组装在一起; c由一个类似主机的单一管理员组统 一管理;d 一般来说通过一个前段系统进行访问。企业型机群具有如下 特点: a . 机群结点一般是一个完整的s m p 、工作 站或 p c , 它们连接 着 所有必须的外围设备;b . 结点在地理位置上是分布的,不必处于同一个 房间内或同一建筑物内;c . 结点可以有多个属主,机群管理者对结点的 管理权限是有限的, 因为结点的所有者可以在任何时刻关机。 所有者的 局部作业比企业 ( 机群)的作业优先级高;d . 机群通常用异构计算机结 点构成,结点之间一般通过低成本的e t h e r n e t 互连。 8 . 另 外还可以 按处理机操作系 统可分为 l i n u x机群( 如 b e o w u l o 、 s o l a r i s 机群( 如 b e r k e l e y n o w ) , n t机群( 如 h p v m ) , a i x 机群( 如 i b m s p 2 ) 、 数字v ms ( 虚拟存储机) 机群、 h p - u x机群、 微软 w o l f g a c k 机群 等。 9 , 按处理机的 位置和数量可分为 组机群 ( 结点 数量2 - 9 9 , 通过s a n s 系统 级网 络如m 州n e t , 机群事实上装入一个机箱中或存在一个范围 之内) 、 部门机群 ( 结点数量 几十或几百) 、企业机群 ( 结点数量 几百) 。 1 0 .按构筑机群的 方式可分为 专用机群和非专用机群。 2 .3机群系统发展的优势 机群系统之所以能够从技术可能发展到实际应用主要是它与传统的并 行 处理系统相比有以 下几个明显的特点13 1 . 1 . 系统开发周期短。由于机群系统大多采用商用工作站和通用 l a n 网络, 使结点主机及系统管理相对容易, 可靠性高。 开发的重点 在 通信和并行编程环境上,一般不用重新研制计算结点,也不用重新 设计操作系统和编译系统, 这就节省了 大量的 研制时间。 2 . 用户投资风险小。 用户在购置传统巨型机或 mp p系统时很不放心, 担心使用效率不高, 系统性能发挥 不好, 从而浪费大量资金。 而机 群系统不仅是一个并行处理系统, 它的每 个结点同时也是一台 独立 的工作站, 即 使整个系统对某些应用问 题并行效率不高, 它的结点 仍然可以 作为单个工作站使用。 3 . 系统价格低。由于生产批量小,传统巨型机或 mp p的价格都比较 北京交通大学硕士学位论文 昂贵,往往要几百万到上千万美元。工作站或高档 p c机由于是批 量生产出来的,因而售价较低。由近十台或几十台工作站组成的机 群系统可以满足多数应用的要求,而价格却比较低。 节约系 统资源。由 于机群系统的结构比 较灵 活, 可以将不同体系 结 构、不同性能的工作站连在一起,这样可以充分利用现有设备。 单 从使用效率上 看, 机群系 统的 资源利用率也比 单机系统要高的多。 u c b e r k e le y 计 算机系1 0 0 多台工 作站的 使用情况调查 表明, 一般 单机系统的使用率不到 1 0 %,而机群系统中的资源利用率可达到 8 0 % 左右。 另一方面, 即使用户设备 更新, 原有的 一些 性能 较低或 型号较旧的机器在机群系统中仍可发挥作用。 系统扩展性好。 从规模上说, 机群系统大多使用通用网络,系 统扩 展容易;从性能上说,对大多数中、 粗粒度的并行应用都有较高的 效率。 清华大学计算机系研制的可 扩展机群系统上测试的 结果表明 8 台工作站 的加速 比可以达到 5 . 8 3 - 7 .9 ,并行处理 的效率为 7 2 . 8 8 %- -9 9 %. 用户编程方便。 机群系统中, 程序的并行化只是在原有的c , c + + 或 f o r t r a n串行程序中,插入相应的通信原语。用户使用的仍然是 熟悉的编程环境, 不用适应新的环境, 这样就可以继承原有软件财 富,对串行程序做并不很多的修改。 2 .4机群系统研究的主要领域 妇. 4 . 1负载平衡和调度策略问 题 在机群系统中, 一个大的任务往往由多个子任务组成。 这些子任务被分 配到各个处理结点上并行执行, 称之为负载。对于有异构处理结点构成的机 群系统而言, 由于各结点的处理能力不同,相同的负载在其上运行的时间和 资源占有 率都不同。 因此, 准确的负 载定义应是绝对的负载量与结点处理能 力的比值。当整个系统任务较多时,分配给各结点的负载可能并不均衡, 整 个系统的利用率就会降低。 因此, 有效的将各个子任务均衡的分布到不同的 处理结点 进行并 行计算, 使各结点的 利用率达到最大。 北京交通大学硕士学位论文 从 任务 分配决策的时 机讲,负载平衡技术可分为静态和动态两类方法 闭 。 静态 方法是 在编译时针对 用户程序中的 各种信息以 及机群系统本身的状 况对用户程序中的并行任务做出静态分配决策, 程序运行时将任务分配到相 应结点。 动态方法是通过分析机群系统的实时负载信息, 动态的将任务在各 处理机之间进行分配和调整,以消除系统中负载分布的不均匀性。 2 . 4 . 2通信问 题 众所周知, 通信技术是提高机群系统性能的关键, 对系统的并行加速性 能、并行计算效率、 可扩展性以及系统的应用范围有十分重要的影响。提高 通 信速 度, 减少 通信开 销, 使系 统的时间资 源主要用于计算是机群系统中 研 究的 重要课题, 提供低延迟、 高带宽的 通信支持几乎 是所有研究中的 机群系 统的 共同目 标,另外对机群系统中 可靠多播/ 广播通信的研究也相当 重要, 因为多播/ 广播是并行计算中实现 c o l l e c t i v e 操作的基础,提高多播/ 广播 通信效率对改善整个机群系统的性能的意义很大。 卯. 4 . 3并行化问题 目 前 广大 应用部门用c . c + + 和f o r t r a n 等语言编制了大量的应用程序, 这些 应用程序, 如果不用修改, 通过并行编译系统就能自 动生成能在并行系 统 上运行的并 行代码, 当 然是最理想的。 但是要自 动识别串 行程序中的并行 性, 并不是一个容易的事。对有些问题,串行程序的结构是清楚的.可以手 工 得对串行程序作少量的 修改, 从而实现并行化。 综合起来, 并行化问题 在 机群系统上有这么几条途径: 预编译 技术、 并行函数类库方 法和并行 化编 译 技术。 预编译技术是在传统语言 编译器之前设计一个预编译器, 通过预编译, 将扩展语言的并行成分用传统语言加以 实现,再通 过传统串行编译器编 译, 生成可并行执行的代码。 并 行函 数类库方法无需改变传统语言和编译器, 只 是为程 序员 提供井行程序开发所需的函数 库或类库, 在编译生成可 执行代码 时再 将其 链接进来, 生成并行代码。 并行化编译技术在机群系统中 主要是针 对应用程 序的中、粗粒度的并行性,与 传统的向 量化方法有很大不同。 北京交通大学硕士学位论文 芍 2 . 4 . 4并行调试技术 并行程序的调试要比串行程序的调试复杂得多, 主要面临的是并行程序 的不确定性, 通信以及复杂的全局状态等问题。 对于基于消息传递机制的机 群系统而言,并行程序中会出现消息死锁、 消息乱序等错误,调试时必须费 力的在通信语句前后设立断点, 从而确定通信的内容, 对于有大量通信和复 杂 通信模式的应用程序来说, 做起来就更为困 难。目 前, 常 用的并行 调试技 术 主要有记 录与重放、 动态分析和可视化三种5 2 .4 . 5并行程序设计环境 广义的说, 并 行程序设计环 境应包括硬件平台、 操作系统和并行程序语 言、 编译、 编程、 调 试及性能分析工 具等, 狭义的 并行程序设计环境则仅指 系统核心之上的工具软件部分。 在这里主要讨论后者的情况,目前在分布存 储多机系统 及机群系统上用的最广 泛的 是 p v m ( p a r a l l e l v i r t u a l m a c h i n e ) 和m p i ( m e s s a g e p a s s i n g i n t e r f a c e ) . p v m 的开发最早开始于 1 9 8 9 年春天, 它的 开发队 伍包括美国 橡树岭国 家实 验室 ( o r n l ) , t e n n e s s e e 大学、 e m o r y 大学以 及c m u 等单位。 p v m 是一 套并 行计算工具软 件, 支持多种体系结构的计算 机, 能够在大多数流行工 作 站系 统、 m p p 系统和向 量机上运行, 这些 机器通过网 络连起来, 给用户提 供 一个 功能 强大的 分布存储 计算 机系统。 p v m 支持c . c + + 和f o r t r a n 语言, 由 于p v m 是免费的,因此使用范围非常广泛。 m p i 是一个新的消息传递标准, 由m p i 讨论组 在 1 9 9 2 年至1 9 9 4 年 举行 的一系列会议上逐渐产生。m p i 能用于大多数 m p p 系统和工作站机群系统, 并达到较高的并行效率。m p i 定义统一的编程接口,将通信部分独立出来, 由 具体的系统来实现, 这样它既具 备了公 共软件包的通用性, 又 具有厂家专 用软件包的高效性. 除了 上述的 两种并 行程序设 计环境, 基于消息 传递机 制且适合 机群系统 的并行 程序设计环境还有美国a r g o n n e 国 家实验室开发的p 4 , y a l e 大学开 发的l i n d a 以及p a r a s o f t 公司开发的e x p r e s s , 这些并行程序设计环境都 各具 特点, 但是他们没有p v m 和m p i 用的 广泛。 北京交通大学硕士学位论文 笋 .4 .6故障恢复与容错 随着机群系统逐渐推广, 人们对可靠性、 可用性的要求逐渐提高, 而许 多并行应用程序的运行时间比较长, 且需要在多个结点上同时运行, 这样一 旦某个结点出现故障, 往往导致整个机群系统失败, 最终结果是应用程序必 须重新执行,导致了大量时间的浪费。 为了避免这

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论