（计算机软件与理论专业论文）并行算法中基于移动agent的数据集均衡策略的研究.pdf

摘要 v j 6 3 5 3 08 解决并行算法中的数据分配问题，目前采用的主要方法是在各个计算结点上 平均分配数据。如果并行系统是同构的，采用这种方法设计的算法具有很高的运 行效率。但是在异构系统下，由于各个计算结点的性能不同，平均分配数据集的 方法就有可能导致系统的负载失衡。 本文提出了在并行算法中使用的基于移动a g e n t 的数据集负载均衡策略：基于 移动a g e n t 综合处理速度的数据集均衡策略d b s m a v ( d a t a s e tb a l a n c i n gs t r a t e g y b a s e do nm o b i l e a g e n tv e l o c i t y ) 和基于移动a g e n t 调度的数据集均衡策略 d b s m a s ( d a t a s e tb a l a n c i n gs t r a t e g yb a s e d o nm o b i l e a g e n ts c h e d u l i n g ) 。目前对如 此细粒度的负载均衡问题所作的研究工作还很少，本文的工作借鉴了n a s a 所建 立的i p g ( i n f o r m a t i o n p o w e r g r i d ) 网格上面的粗粒度负载均衡算法p l u m ( p a r a l l e l l o a db a l a n c i n gf o ru n s t r u c t u r e dm e s h e s ) 、s b n ( s y m m e t r i cb r o a d c a s tn e t w o r k ) 、 m i n e x ( m i n i m a le x t r ao v e r h e a d ) ，也参考了接收者发起的分布式启发性算法，并 结合了移动a g e n t 的思想。 理论和实验证明，移动a g e n t 综合处理速度m a v ( m o b i l ea g e n tv e l o c i t y ) 在计 算结点的内存足够大时能够比较准确地反映计算结点的计算能力。d b s m a v 策略 按照各个计算结点的m a v 分配数据集，较好地克服了异构系统中平均分配数据集 造成的失衡。为了解决由于内存的影响而导致的负载失衡现象，我们提出了 d b s m a s 策略。d b s m a s 策略按照重负载优先调度和整体上减少系统执行时间的 原则，命令一部分移动a g e n t 携带数据集进行迁移，使系统重新达到了平衡状态。 实验证明，我们所研究的均衡策略，利用移动a g e n t 的移动性，很好地解决 了负载失衡问题，提高了程序的执行效率。较之于传统的算法，我们策略的特点 是优先保证提高程序的执行速度( 平衡负载的目的是为了提高并行算法的速度) ， 而不是优先保证系统的平衡。 【关键字】负载均衡，移动a g e n t ，调度策略，并行计算 a b s t r a c t t os o l v et h ep r o b l e mo f d i s t r i b u t i n g d a t ai n p a r a l l e la r i t h m e t i c ，t h em e t h o do f d i v i d i n gd a t a s e ti n t os e v e r a le q u a lp a r t sa n ds e n d i n ge v e r yp a r tt oas p e c i a lc o m p u t i n g n o d ew a sa d o p t e d i ft h es y s t e mw a sc o n s t r u c t e db yt h es a m e t y p eo fc o m p u t i n gn o d e s ， t h e nt h em e t h o dc a nw o r ke f f i c i e n t l y o nt h eo t h e rh a n d ，i tc a nm a k et h es y s t e m u n b a l a n c e d i nt h i st h e s i s ，t h ed a t a s e tb a l a n c i n gs t r a t e g yb a s e do nm o b i l ea g e n ti np a r a l l e l a r i t h m e t i cw a s p r o p o s e d t h em o b i l i t yo f m o b i l ea g e n te n a b l e dt h ep a r a l l e lc o m p u t i n g t ob et r u ea n dt h ed a t a s e tb a l a n c i n gt ob ee a s y t h es t r a t e g yc o n s i s t e do ft w op a r t d b s m a v ( d a t a s e tb a l a n c i n gs t r a t e g y b a s e do nm o b i l e a g e n tv e l o c i t y ) a n d d b s m a s ( d a t a s e tb a l a n c i n gs t r a t e g yb a s e do nm o b i l ea g e n ts c h e d u l i n g ) b yu s i n g p l u m ( p a r a l l e l l o a d b a l a n c i n g f o r u n s t r u c t u r e d m e s h e s ) ，s b n ( s y m m e t r i c b r o a d c a s t n e t w o r k ) ，m i n e x ( m i n i m a le x t r ao v e r h e a d ) ，t h et h i n k i n gi nm o b i l ea g e n tf o r r e f e r e n c e ，w ep r o p o s e d t h i ss t r a t e g y i tw a s p r o v e d t h a tm a y ( m o b i l e a g e n tv e l o c i t y ) c o u l dr e f l e c tt h ep e r f o r m a n c eo f t h ec o m p u t i n gn o d ew h e nt h em e m o r yo ft h en o d ew a sl a r g ee n o u 曲d b s m a vc o u l d b a l a n c et h es y s t e mw h e ni td i v i d e dt h ed a t a s e ta c c o r d i n gt om a v i no r d e rt or e s o l v et h e u n b a l a n c e dp r o b l e ml e db yt h em e m o r y , t h ed b s m a sw a sp r o p o s e d i nt h ed b s m a s s t r a t e g y , t h eo v e rl o a d f i r s t s c h e d u l i n gp r i n c i p l ew a sa p p l i e d w h e nt h ed b s m a s s t r a t e g yj u d g e dt h a ts c h e d u l i n gam o b i l ea g e n tc o u l dr e d u c et h e t o t a lt i m eo ft h e s y s t e m ，i ts c h e d u l e d t h em o b i l ea g e n tt om o v et oa n o t h e rn o d ew i t hi t sd a t a s e t b yt h i s w a y , t h eu n b a l a n c e ds y s t e m c a nb eb a l a n c e d i no u re x p e r i m e n t ，t h ed a t a s e tb a l a n c i n gs t r a t e g yb a s e do nm o b i l ea g e n ti n p a r a l l e la r i t h m e t i cs h o wh i g hp e r f o r m a n c e k e y w o r d s ：l o a d b a l a n c i n g ，p a r a l l e lc o m p u t i n g ，m o b i l ea g e n t 2 1 。1 研究背景 第一章绪论 随着人们对世界认识的不断深入，所获取的知识也在急剧膨胀，迫切需要计 算机参与到问题的处理过程中来。在科学计算中，由于处理的数据量通常以百兆、 千兆、甚至更大数量级计，使得单处理器系统的处理能力不能满足需求。人们寻 求利用多个处理器的计算能力来共同解决这个问题。 构建多处理器系统的形式有多种，如s m p 、m p p 、集群等 1 3 】【1 4 】，它们都能 够提供强大的计算能力。有专家通过对世界超级计算机( h p c ) t o p 5 0 0 的结构、 性能等进行分析，得出以下结论： ( i )超级计算机领域美国仍然占据主导地位，其次是欧洲和日本，如果不 考虑e s ( e a r t hs i m u l a t o r ) ，欧洲超级计算的计算能力略领先日本： ( 2 ) e s ( e a r t hs i m u l a t o r ) 是目前世界上运行速度最快的超级计算机，理 论上的峰值速度可以达到4 0 9 6 0g f l o p s ； ( 3 ) 摩尔定律继续生效： ( 4 ) 单处理器和s i m d 方式来构建高性能计算系统的方式己不复存在， s m p 方式也趋于消失； ( 5 ) m p p 仍然是h p c 结构的主流。集群( 尤其是s m p 集群) 将在不久的将 来取代m p p 结构的主流地位； ( 6 ) 超级计算机正在完成一个从科研工具和实验产品到产业应用的转变。 并行计算在许多计算机应用领域都产生了巨大的影响，使原来无法解决的应 用问题成为可能。 例如：天气预报。考虑3 0 0 0 * 3 0 0 0 平方公里的范围，垂直方向的考虑高度为 1 l 公里。将3 0 0 0 * 3 0 0 0 * 1 1 立方公里的区域分成o 1 + 0 1 。o 1 立方公里的小区域，则 将近有1 0 “个不同的小区域。另外还需考虑时间因素，将时间参数量化。假定考 虑4 8 小时天气预报。若每一小区域计算的操作指令为1 0 0 条，则整个范围一次计 算的指令为1 0 “* 1 0 0 = 1 0 ”，两天的计算次数将近1 0 0 次，因此，指令总数为1 0 5 条。用一台1 0 亿次秒( p i i i s 0 0 ) 计算，将大约需要2 8 0 小时。若我们用1 0 0 个1 0 亿次秒的处理器构成一台并行处理机，每个处理器计算的区域为1 0 3 个，不同的 处理器通过通信来传输参数，若个处理器的计算能力得到充分利用，则整个问题 的计算时间不超过3 小时。所以说，并行计算机可以解决原先不能解决的问题， 并可进行更准确的天气预报。 其它应用包括：卫星数据处理、石油数据处理( 连续优化问题) ，调度问题、 平面性问题及v l s i 设计( 离散优化问题) 美国h p c c 计划公布的重大挑战性应用： 磁记录技术：研究静磁和交互感应以降低高密度磁盘的噪音 新药设计：通过抑制人的免疫故障病毒蛋白酶的作用来研制治疗癌症与艾 滋病的药物 高速民航：用计算流体动力学来研制超音速喷气发动机 催化作用：仿生催化剂计算机建模，分析合成过成中的酶作用 燃料燃烧：通过化学动力学计算，揭示流体力学的作用，设计新型发动机 海洋建模：对海洋活动与大气流的热交换进行整体海洋模拟 臭氧耗损：研究控制臭氧损耗过程中的化学与动力学机制 数字解析：用计算机研究适时临床成像、计算层析术、磁共振成像 大气污染：对大气质量模型进行模拟研究，控制污染的传播，揭示其物理 与化学机理 蛋白质结构设计：对蛋白质组成的三维结构进行计算机模拟研究 图像理解：实时绘制图像或动态 密码破译：破译由长位数组成的密码，寻找该数的两个乘积因子 为了利用多处理器系统的能力，需要对海量数据进行划分，使每个处理器处 理其中一部分，多个处理器并行地求解。如何划分数据是一个值得研究的问题， 划分不当，会使一部分处理器“时刻处于忙于计算的状态”，一部分处理器t t 大部 分时间处于空闲的状态”，整个系统出现负载失衡，不能充分利用多处理器系统的 计算能力。对于同构系统，由于各个处理器的性能相同，所以平均分配数据集是 一个行之有效的方法。而对于异构系统，由于各个处理器的性能不尽相同，平均 分配数据集可能会导致负载失衡。我们在实验室的条件下研究并行k - m e a n 算法时， 发现了这一问题。如何解决异构系统下的负载均衡问题，是本文研究的重点。 1 2 负载均衡的研究现状 1 2 1 操作系统中的负载均衡策略 当有大批任务提交给操作系统时，其分配应该遵从下面准n t 2 1 】【2 6 】： ( 1 ) 分配给每个处理器的计算任务应均衡，以减少处理器由于等待其他处 理器完成计算任务而造成的空闲； ( 2 ) 不同处理器之间的交互应尽量最少，这样处理器可以用更多的时间去 完成有效的工作。 但是，这两个目标经常冲突。比如，最小化处理器间的交互可以用下述方法 达到：即将需要交互豹子任务分配到同一个处理器上。在极少数情况下，这种方 法对负载平衡影响不大，但更多的时候，它会带来系统的负载不均衡。同样地， 为了均衡负载，有时会把需要很多交互的任务分配给不同的处理器。为了解决冲 突，通常采用的一种策略是在任务分配中，先集中目标使负载尽量均衡，然后再 对任务分配进行调整，使得交互最小化。 通常，按照均衡的决策与系统的负载是否相关，并行系统的负载均衡策略可 以分为状态无关平衡( 静态平衡) 和状态相关平衡( 动态平衡) 两大类。 ( 1 ) 状态无关平衡。就是根据以往的经验或系统本身信息的收集，把外来的 任务分配给各个结点，或对某些结点上的任务迸行重新分配。例如，随机平衡， 把第i 个任务分配给第ir o o dn 个结点( n 为系统中的结点总数) ；概率平衡，按 照概率p 。( 由任务的平均到达速率和结点的运行速率确定) 把任务分配给第i 个结 点。由于这样的平衡决簧是与系统当前状态无关的，带有一定盲目性，因丽决策 的准确性很低。常用的静态平衡法还有图论法、枚举搜索法、排队法等。静态平 衡法，其效率取决于对系统本身以及交互的任务是否有充分的了解，如各任务的 执行代价和任务之间的通信代价，处理机的性能以及软硬件设置等。由于这些先 验知识常常是不可得的或不准确的，所以静态法的通用性差，效率低。 ( 2 ) 状态相关平衡。其决策取决于系统当前的状态，也就是说，系统可以根 据当前的负载分布情况，对各个结点上的负载进行动态的调整，使已经分配给重 载结点上的任务，通过通信设备迁移到轻载的结点上去，从而提高系统的资源利 用率，减少任务的平均响应时间。通常，动态平衡法应包含以下三个基本步骤 各个结点问信息的收集； 根据收集的负载信息进行决策： 实现任务在各结点之间的迁移。 这样的附加处理给系统增加了一定的开销。但是这种开销往往是值得的。目 前，大多数系统都采用动态平衡法。 并行操作系统上比较成熟的负载均衡系统有w i s c o n s i n - m a d i s o n 大学的 c o n d o r ，c a n a d ap l a t f o r m 公司的l s f 系统等。 这种操作系统上的负载均衡以任务( 或者说进程、线程) 为单位，不能深入 到任务内部了解其执行的状况，因此不能协调任务内部需要并行的模块之闻的快 慢，也不能解决软件内部的失衡问题。 1 2 2w e b 服务器上的负载均衡策略 w e b 服务器负载均衡是指将多台服务器设置为对称方式，每一台服务器都具 有等价的地位，共同承担网络的负载，通过负载均衡技术将客户的请求分配到多 个本地或者远地服务器中以避免造成单个服务器过载，并在单个服务器出现故障 时，通过自动故障切换从而提高系统的可靠性和高效性。下图为引入负载均衡的 w e b 服务器1 3 0 】。 图1 1 引入负载均衡的w e b 服务器 当前使用的负载均衡技术是采用两台或更多台w e b 服务器相互备份，这些不 同的服务器可以通过负载均衡机制连接起来，负载均衡组件根据某类算法将收到 的请求路由到不同的服务器进行处理。每台服务器通常只处理总体通信的一部分， 服务器的数量则根据需要来确定。 常见的算法有： d o m a i n ：按照域名最近的原则，指定最近的服务器响应； s e r v e r l o a d ：由服务器提供负载均衡算法，该方法需要在服务器端安装负载测 量引擎： r o u n d r o b i n ：根据记录表中的情况指定下一个响应服务的服务器。 具体实旖分以下几种情况： 纯软件方式的分布式负载均衡； 基于n a t ( n e t w o r k a d d r e s st r a n s l a t i o n ) 的负载均衡； 0 n e i p 技术的负载均衡： 基于d n s 技术的负载均衡： 通过路由器和缓存器实现负载均衡； 一揽子负载均衡系统 随着负载均衡、容错网络和功能更强大的硬件产品的出现，越来越多的w e b 站点能够达到极高的可用性。为这些高可用性w e b 站点“保驾护航”的是种类繁 多的分布式负载均衡软件和解决方案。与传统的本地负载均衡系统相比，新一代 的分布式负载均衡产品增加了许多新的容错和管理功能。如果与传统的负载均衡 方案一起使用，分布式负载均衡系统可以保证整个w e b 站点即使在出现某些故障 9 的情况下也能有很高的可用性。 w e b s e r v e r 上比较成熟的负载均衡算法和软件有r o u n d r o b i n 算法、i b m 公司 的n e t w o r kd i s p a t c h e r 等。 w e b 服务器的负载均衡是基于请求的，这些请求是孤立的，彼此之间不需要 交互。而在并行程序设计中，即使是最简单的基于数据划分的并行算法，也需要 各个并行模块之间的交互。因此，w e b 服务器的负载均衡算法只能为并行程序中 的负载均衡提供一个参考方案，而不能全盘照搬，我们必须研究自己的负载均衡。 1 2 3 并行程序中的负载均衡策略 既不能依靠操作系统来协调并行任务的快慢，也不能像w e b 服务器那样来均 衡并行程序中的负载，我们必须在并行程序中实施自己的负载均衡策略。 在基于内存共享的并行系统中 2 5 1 ，a r i z o n as t a t e 大学研制的c a l y p s o 是一 个开发程序中并行性的并行系统，它向用户提供了一个扩展c + + 编程语言c s l ( c a l y p s os o u r c el a n g u a g e ) ，支持d s m ( d i s t r i b u t e ds h a r e dm e m o r y ) ，编程模式， 相应地增加了并行操作原语：s h a r e d 、p a r b e g i n 、p a r e n d 和r o u t i n e 。运行过程中， 系统进行动态负载均衡，并具有容错能力。c a l y p s o 系统分离了逻辑并行性和物 理并行性，使用户无需考虑数据划分和任务分配。 在基于消息传递的并行系统中2 7 1 1 2 8 l ，目前的研究主要集中到同构系统。在各 个处理器性能相同的条件下，研究的重点就集中在任务分配上。在任务规模已知 的情况下，可以事先平均分配数据集到各个处理器上。而在任务规模随着程序执 行发生变化时，就需要采用动态的负载均衡算法。 在异构系统领域 2 9 ，由于各个处理器的性能存在差异，平均分配可能会产生 负载失衡：对于如何消除异构系统上的负载失衡状态，目前所作的研究还不多， 主要原因是异构的多处理器系统很少，之前没有这方面的需求。集群概念的出现， 必将使得异构多处理器系统应用广泛，因此做这方面的研究意义重大。 1 3 我的工作 本文深入研究了数据挖掘中的并行分类算法一并行k m e a n 算法，发现了严重 的负载失衡现象。并且进一步发现大多数异构系统上的并行算法都会存在这种现 象。经分析，这是由系统的异构性引起的。因此，解决异构系统上的数据集失衡 j 0 问题具有重要意义。 本文提出了并行算法中基于移动a g e n t 的数据集负载均衡策略：基于移动a g e n t 综合处理速度的数据集均衡策略d b s m a v 和基于移动a g e n t 调度的数据集均衡策 略d b s m a s 。目前对如此细粒度的负载均衡问题所作的研究工作还很少，本文借 鉴了n a s a 所建立的i p g ( i n f o r m a t i o np o w e r g r i d ) 网格上面的粗粒度负载均衡算 法p l u m 、s b n 、m i n e x 算法，也参考了接收者发起的分布式启发性算法，并结 合了移动a g e n t 的思想。 在d b s m a v 策略中，我们首先提出了m a v ( 移动a g e n t 综合处理速度) 的概 念。经过理论和实验的验证，m a v 能够比较准确地反映计算结点的综合处理能 力。d b s m a v 策略按照各个计算结点的m a v 分配数据集，较好地克服了大内存 系统的失衡问题。实验证明，按照d b s m a v 策略分配数据集比平均分配数据集能 够提高并行程序的执行效率。 如果小内存不能容纳分得的数据，则在计算过程中，需要进行内外存的缺页 调换，降低程序的处理速度。还有可能出现失衡现象。我们提出的d b s m a s 策略 在系统中出现空闲结点时，调度重负载结点上的a g e n t 到空闲结点上，使系统重新 达到平衡。经过模拟实验，d b s m a s 策略能够在减少并行程序执行速度的同时平 衡负载，其性能相对于传统的算法有很大提高。 1 4 论文结构 本文以后各章节安排如下：第二章介绍并行系统现状和并行软件设计中 的五种模式，为并行算法的编写打下基础：第三章分析异构并行系统中产生负载 失衡现象的原因，以便有针对性的提出解决的办法；第四章针对不考虑各个计算 结点的性能盲目分配而导致的负载失衡现象，提出d b s m a v 策略；第五章针对由 于内存的影响而使得d b s m a v 策略不能完全解决失衡问题时，提出d b s m a s 策 略来进行二次均衡：第六章总结了本文工作，并指出了今后的改进工作；第七章 致谢。 第二章并行系统综述 2 1 并行处理系统的现状 2 1 1 单处理器内的并行 单处理器内比较先进的并行技术有1 】：流水线技术、超级流水线技术( 主要利 用时间上面的重叠) 、向量机技术、超级向量机技术( 主要利用向量每次能够处理 较多的数据) 、超级流水线超级向量机技术。 2 1 2 多处理器并行系统 最早的多处理器机为s i m d 单指令流多数据流) 计算机，h j s i e g e l 提出其 模型如下： 图2 1s i m d 多处理机 s i m d 多处理机因其结构不灵活，功能狭窄；且无法利用高性价比的微处理器， 而必须设计专用处理器，所以没有得到广泛应用。 近年来，m i m d 作为通用多处理器系统结构的主要技术正在兴起 6 i f l 3 1 。它的优 点首先是灵活，既可作单用户机，面向解决单个的高性能应用，也可运行多任务 多道程序，或用于上述两种混合方式。其次，它还可利用高性价比的微处理器。 基于构建m i m d 多处理机的思想，具体形式有三种： 第一种，m p p ( 大规模并行处理机) 。如图2 2 ： 图2 2m p p ( 大规模并行处理机) 该系统最主要的特点是进行大规模并行处理。在m p p 系统中，用的是v l s i 硅片、砷化镓技术、高密度组装和光技术，采用可扩展技术、共享虚拟存储技术、 容许时延技术、多线程技术的系统结构。m p p 中，每个处理机都有自己的存储器， 属于分布存储方式，这种方式可以使系统容易扩充。但是由于每个处理机不能访 问非本地存储器，使得编程困难并且通信开销增加。虚拟共享存储，又称共享分 布存储器，可以改变这种状况。这是在基于分布存储器的多处理机上，实现物理 上分布但逻辑上共享的存储系统。其基本思想是：将物理上分散的各个处理机所 用的局部存储器，在逻辑上加以统一编址，形成一个虚拟地址空间来实现存储器 的共享。 典型的m p p 有i n t e lp a r a g o n 、c m 一5 、c r a yt 3 d 等。 第二种，s m p 。如图2 3 ： r _ 1l 阿画研 互联网络 一童堡堂! i! 厂= _ = ：= - 焉翮 图2 3s m p ( 共享存储多处理机) s m p 称为共享存储多处理机( s h a r e dm e m o r ym u l p t i p r o c e s s o r s ) ，也称为 对称性多处理机( s y m m e t r ym u l p t i p r o c e s s o r s ) 。共享存储系统拥有统一的寻 址空间，程序员不必参与数据分布和传输。早期的并行处理系统大多属于基 于总线的共享存储系统，它们的发展得益于两方面：一是微处理器令人难以 置信的高性价比，一是在基于微处理器的并行处理系统中广泛使c a s h ( 高 速缓冲存储器) 技术。这种基于总线的方式虽然简单，但各个处理器对总线 的竞争使用却阻碍了系统的扩展能力。 典型的s m p 系统有s g ic h a l l e n g e 和s u n s p a r c c e n t e r 。 第三种，集群( c l u s t e r ) 。如图2 4 ： 图2 4c l u s t e i 计算机集群 机群系统是利用高速通用网络将一组高性能工作站或高档p c 机，按照某种结 构连接起来，并在并行程序设计以及可视化人机交互集成开发环境支持下，统一 调度，协调处理，实现高效并行处理的系统。从结构和结点间的通信方式来看， 它属于分布式存储系统，主要利用消息传递方式实现各个主机之间的通信，由建 立在一般操作系统之上的并行编程环境完成系统的资源管理及相互协作，同时也 屏蔽工作站及网络的异构性。对程序员和用户来说，机群系统是一个整体的并行 系统。集群中的主机和网络可以是同构的，也可阻是异构的。目前已实现和正在 研究的集群系统大多采用现有商用工作站和通用l a n 网络，这样既可以缩短开发 周期又可以利用最新的微处理器技术。大多数集群系统的并行开发环壤也是建立 在般的u n i x 操作系统之上，尽量利用商用系统的研究成果，减少系统的开发与 维护费用。 典型的集群系统有：b e o w u l f , c o w ，m o s i x ，中国的曙光h p c 系列。 - 从以上介绍中，我们可以看出，9 0 年代，并行计算机系统发展很快，但应用 范围不广，主要应用于大型商业集团( 如各种订票系统、电信系统等) 或事关国 计民生的领域( 如地震预测、天气预报、天体运行等) ，高校的研究领域等。 1 4 2 2 并行软件系统 要想充分利用并行系统的性能，必须设计出有利于并行系统解释执行的并行 程序。对于可以明显划分为并行任务的程序( 如进行科学计算的f o r t r a n 程序) ， 可以利用编译程序把以前的串行程序编译成并行程序。对于其他方面的程序，现 在的编译系统还有所欠缺，需要在编制程序时指出。 下面我们对目前在分布存储多机系统和集群系统上广泛使用的几个并行程序 设计环境做一简单介绍1 1 7 1 1 1 9 i ： ( 1 ) p v m ( p a r a l l e l v i r t u a lm a c h i n e ) 由美国橡树岭国家实验室、t e n n e s s e e 大 学、e m o r y 大学以及e m u 等单位开发的。是一套并行计算工具软件，支持多种体 系结构的计算机，像工作站、并行机以及向量机等，这些机器用网络连接起来， 给用户提供一个功能强大的分布存储计算机系统。p v m 支持c 、c + + 和f o r t r a n 语 言。 ( 2 ) m p 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 委员会在 1 9 9 2 年1 1 月至1 9 9 4 年1 月举行的一系列会议上逐渐产生的。该委员会由来自约 4 0 个研究院所和几乎所有的m p p 销售商、以及世界范围内设计并行计算的大学和 政府实验室的成员组成。m p l 支持c 和f o r t r a n 两种语言，编程模型采用s p m d ， 它的编程模型要比p v m 容易。 ( 3 ) 美国p a r a s o f l 公司推出的e x p r e s s 系统；美国耶鲁大学与计算机协会共 同研制的用于实现并行程序设计的、与机器无关的程序环境l i m a ；清华大学计算 机系开发的高效可用的可视化集成开发环境i p c e 等。 ( 4 ) 各种移动a g e n t 系统f 3 1 】f 3 2 。移动a g e n t ( m o b i l e a g e n t 简称m a ，) 是一类 特殊的a g e n t ，它除了具有智能a g e n t 的最基本特性- 反应行、自治性、导向目标性 和针对环境性外，还具有移动性，即它可以在网络上从一台主机自主地移动到另 一台主机，代表用户完成指定的任务。目前已经开发出众多的m a 系统，其代表 性的系统有：g e n e r a lm a g i c 公司的t e l e s c r i p t ，i b m 公司的a g l e t ，m i t s u b i s h i 公司 的c o n c o r d i a ，d a r t m o u t h 学院的d a g e n t ，o b j e c t s p a c e 公司的v o y a g e r ，d e c ( c o m p a q ) 研究院的o b l i q ，c o m e l l 大学的t o c a m a ，s t u f f g a r t 大学的m o l e 等。 2 3 并行软件的五种设计模式 随着对并行软件设计研究的不断深入，软件界逐渐形成下面五种并行程序设 计模式【1 8 i ： 1 分治策略( 如图2 5 a ) 。把总任务分成几个规模相当的子任务，对其分别 处理并将处理结果集成起来。这种方案适用于以下情况：总任务可以明显 分为互不相关的子任务，子任务执行结果的集合就是总任务的结果。 2 阶段并行( 如图2 5 b ) 。总任务的各个子任务在一定阶段是并行执行，在 另一阶段却要互通信息，或是互斥共享资源，或是为了同步。这种模式下， 要努力分解总任务，了解任务的执行流程，才能知道何时并行处理，何时 互通信息。 3 流水线方式( 如图2 5 c ) 。这种方式下的功能模块在执行上有明显的先后 顺序，因此可以使各个模块在执行时间上进行重叠，来提高并行度。 4 工作池方式( 如图2 5 d ) 。这种模式下，工作池是一个性能较好的结点， 负责处理其他子结点的请求。工作池只负责为子结点分配任务，其本身不 执行其他任务，也不负责管理其他子结点的处理结果。 5 主从模式( 如图2 。5 e ) 。主结点可以参与计算工作，也可以不参与，它全 权管理任务的分发与结果的集成。这种形式只需主从结点之间进行通信， 形式简单，易与管理，并且具有很好的可扩展性。 替皋硷搞 ( a ) 分治簧喀( b ，阶段并行( c ) 藏术线方式( d ) 工作池方式( e ) 主从模式 图2 5 并行程序设计攫式 在数据挖掘研究领域中，处理的数据多，而执行的程序相对简单( 经常采用 把数据分配到各个结点上分别计算，最后进行结果集成的方法) 。数据挖掘算法 的这些特性，决定了其采用主从模式比较合适。 1 6 第三章异构系统中负载失衡现象的研究 3 1 异构并行系统中的负载失衡现象 我们主要针对目前数据挖掘中的一个并行聚类算法一k m e 柚并行算法来分析 并行算法中的数据集失衡现象。 3 1 1k m e a n 算法 k - m e a n 算法是数据挖掘中一个重要聚类算法。就是将数据对象划分成多个类 同一类对象之间具有较高的相似度，而不同类对象差别较大。如图所示： 圉3 ik - n e a n - 算祛翻示 k - m e a l l 算法用伪码表示如下： l ：m s e = l a r g e n u m b e r ； 2 ：s e l e c tki n i t i a lc l u s t e re e n t r o i d s m j k i ；l ： 3 ：d o 4 ：o i d m s e = m s e ； 5 ：m s e = o ： 6 ：f o r j _ 1 t o k 7 ： m j = 0 ；n j - 0 ； 8 ：e n d f o r 9 ：f o r i = l t o n 1 0 ： f o r j = l t o k 1 1 ： c o m p u t es q u a r e d e u c l i d e a nd i s t a n c ed 2 ( x i ，m j ) 1 2 ：e n d f o r 1 3 ：f i n dt h ec l o s e de e n t r a i dm i t ox i ； 1 4 ： m l = m l + x i ；n 产n i 十1 ； 1 5 ： m s e = m s e + d 2 隘，m i ) ； 1 6 ：e n d f o r 1 7 ：f o r j - 1t o k 1 8 ： n j = m a x ( n i ，1 ) ；m j _ m j n 1 ，； 1 9 ：e n d f o r ； 2 0 ： w h i l e ( m s e o i d m s e ) ； 3 1 2 k - m e a n 并行算法 k - m e a n 并行算法就是如何利用多处理器系统并行地实现k m e a n 聚类。并行 机制有以下优点： ( 1 ) 多台计算机所提供的内存空间总和能够容纳待处理数据集，不必进行数 据的缺页调换，所以能够提高速度； ( 2 ) n 台计算机同时对不同的数据进行计算，总的计算能力理论上是一台计 算机的n 倍，更能够提高速度。 已经存在的k - m e a n 并行算法是把数据平均分配到各个处理器结点上，各个处 理器并行计算，需要结果集成的时候，各个处理器相互交换信息，得出结果。目 前已经存在的一个k m e a n 并行算法可以用伪码表示如下【9 】： 1 ：p = m p l c o m m _ s i z e 0 ； 2 ：u = m p i _ c o m mr a n k 0 ； 3 ：m s e = l a r g e n u m b e r ； 4 ：i f ( u = 0 1 5 ：s e l e c tki n i t i a lc l u s t e re e n t r o i d s m j j ：l ； 6 ：e n d i f 7 ：m p i _ b c a s t ( m j k i ；1 o ) ； 8 ：d o 9 ： o i d m s e = m s e ； 1 0 ：m s e = 0 ： 1 1 ： f o r j = 1t o k 1 2 ： m j = 0 ；n j - o ； 1 3 ：e n d f o r 1 4 ：f o ri = t l ( n p ) + lt o ( u + 1 ) ( n p ) 1 5 ： f o r j = l t o k 1 6 ： c o m p u t es q u a r e d e u e f i d e a nd i s t a n c ed 2 ( x i ，m j ) 1 7 ：e n d f o r 1 8 ：f i n dt h ec l o s e dc e n t r o i dm lt ox j ； 1 9 ： m 尸m i 斗甄；n l _ n l + l ； 2 0 ：m s e = m s e + d 2 ( x j ，m i ) ； 2 1 ：e n d f o r 2 2 ： f o r j = l t o k 2 3 ： m p i _ a l l r e d u c e ( nj ，n j ，m p i _ s u m ) ； 2 4 ： m p i _ a l l r e d u c e ( m j m j ，m p i _ s u m ) ； 2 5 ： n j = m a x ( h i ，1 ) ；m j 2m gn j ，； 2 6 ： e n d f o r ； 2 7 ： m p l _ a l l r e d u c e ( m s e , m s e , m p i _ s u m ) ； 2 8 ： ) w h i l e ( m s e o i d m s e ) ； 3 1 3 异构系统下数据集分配的失衡问题 在同构系统中，k m e a n 并行聚类算法能够高效地工作；但是在异构系统中， 弊端就很容易暴露出来： ( 1 ) 从各个从结点内存的大小来分析。该算法的数据集是平均分配的( 从算 法中t 卸可以看出，其中n 为数据集的大小，p 为进程的数目，l 却为每个进程分 得的数据量) ，如果各个计算机所能容纳的数据量相同，平均分配不会出现大的问 1 9 题。假设异构计算机的内存大小不同，平均分配数据集可能使得最小的内存不能 容纳所分得的数据。上述算法没有考虑到这一点。如图3 2 所示： 图3 2各个结点内存不同导致的问题 ( 2 ) 从各个结点的计算时间来分析。经分析，算法的计算时间由以下三个部 分组成。第一，向各个处理器分配数据集的时间t l ( 上述程序中没有体现出来) ； 第二，各个处理器的计算时间t 2 ( 第9 行到第2 1 行) ，由于需要所有处理器都完 成任务后才能进行信息交换，所以我们考虑其中最长的时间；第三，信息交换后 进行整合的时间t 3 ( 第2 2 到第2 7 行) 。下图清楚的表明了三个阶段的情况： l 处理器1ll 处理器2 |l 1l 处理喜i it 1 ( 分配数据) 工 t lt 2 ( 并行计算 ， it 3 ( 结果集成) r 1 图3 3各个结点性能不同导致的问题 第二阶段的时间t 2 决定着算法总的运行时间。在异构系统中( 如集群) ，由于 处理器之间的性能差异，对于相同大小的数据集，它们几乎不可能同时完成计算 任务，所以在平均分配数据集的情况下，各个处理器之间势必造成等待。推而广 之，如果各个从结点的性能差异太大，等待时间就会很长。量化一下，如果从结 点a 的综合处理速度是从结点b 的8 0 ，则相同数据集下从结点a 的处理时间将 2 0 会是b 的1 2 5 倍，也就是说如果结点b 要处理4 小时的话，结点a 就要处理5 小 时，等待时间将会是1 小时。在数据挖掘中，这么长的处理时间在目前有可能存 在。 如上文所提，如果各个从结点完成任务的时间相差很大，就叫做系统中产生 了负载失衡现象。如果各个从结点完成任务的时间相差不大，可以认为系统中负 载均衡，系统资源的利用率就很高。 针对上面的不足( 尤其是第二条) ，必须设法调整各个处理器上的数据，使各 个处理器的运算时间t 2 基本相同。为此，我们首先研究了当前已经存在的各种负 载均衡算法，并结合移动a g e n t 的移动性，提出一种数据集均衡策略，克服负载 失衡问题，提高整个程序的处理速度。 3 2 几种典型的负载均衡算法 正如我们在第一章中谈到的，由于考虑的角度和应用的领域不同，我们不能 照抄其他领域中的已经存在的负载均衡算法。但是可以通过某些条件进行引申和 改变，又可以借鉴比较接近的负载均衡算法。在本章中，先介绍一下我们所参考 的两类负载均衡算法，它们都属于分布式操作系统中的算法，具有典型性。 3 2 1 算法简介 1 发送者发起的分布式启发性算法和接收者发起的分布式启发性算法1 1 8 j h ，醋簇薹 “等饕稿它 的负担太重 司谖便崩 发送者发起的分布式启发性算法和 长收者发起的分布式启发性算法 7 需要帮助 ( 1 ) e a g e r 等人提出了发送者发起的分布式启发性算法( 如图3 4 a ) 。在他们研究 2 1 的“最有效代价”算法中，当创建进程时，创建进程的机器将对一个随机选取的机 器发送询问，询问其负载是否低于阀值。如果是，将发送进程，否则将选取另一 台机器发送询问。这一过程并不会一直持续下去，如果在n 次询问内还没有找到 合适的机器，算法将停止，新进程将在创建它的机器上运行。 他们已经构造并研究了一个关于该算法的分析队列模型。利用这个模型，已 经确定该算法运行得很好并且在各种条件下，包括各种参数：不同的阀值、传输 代价、询问次数限制等，都运行的十分稳定。 然而应该注意到，在负载很重的情况下，所有的机器都会不停的毫无意义的 向其他机