资源描述：
《并行计算中基于移动agent的负载均衡策略》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第36卷第3期郑州大学学报(理学版)Vol.36No.3
2004年9月JOURNALOFZHENGZHOUUNIVERSITYSep.2004并行计算中基于移动Agent的负载均衡策略王黎明, 赵中堂, 柴玉梅(郑州大学信息工程学院 郑州450052)摘要:针对并行程序设计的五种模式中主从模式的不足,提出了基于移动agent的负载均衡策略.该策略对移动agent获取的数据进行分析,合理地分配各个结点的处理数据量,明显地减少了程序的运行时间.关键词:并行算法;移动agent;k2mean算法;负载均衡策略中图分类号:T
2、P301.6 文章编号:1671-6841(2004)03-0005-040 引言在很多科学计算领域(如数据挖掘[1]、气象研究、天体研究)中,待处理的数据集非常大,而单处理器计算机的能力有限,于是利用多处理器系统并行处理就成为研究的热点.当多处理器系统为同构时,由于上述领域所要处理的海量数据集是固定的,在计算过程中不会产生新的数据,因此采用静态负载均衡策略可以解
决这些问题,即在计算的开始就把数据平均分配到各个并行任务中,再把各个任务调度到每个处理器上1由于进行并行处理的处理器性能会有所差别,
3、此时如果还采用平均分配的方法,势必出现负载失衡情况.由于[2～4],使得程序员常常对其产生依赖心理,而不去研究自己程当前的多处理器操作系统也具有负载均衡功能序的均衡策略.而操作系统的负载均衡策略,只是从系统资源的方面使得各个处理器的利用率最大,却看不到需要并行的任务的内部情况,也无法保证各个任务间的同步,造成各个任务间的负载失衡.本文分析了基于数据集分解的并行算法中的失衡现象,提出了负载均衡策略,该策略利用了移动agent的强大功能.实践表明,可以很好的提高算法的效率.1 主从模式中负载失衡现象的分析众所周知,关于并行系
4、统上程序设计的研究,软件界逐渐形成了五种设计模式[5],它们分别是分治模式、阶段并行模式、流水线模式、工作池模式、主从模式等.主从模式在处理大数据集方面效果比较好.我们研究
的就是这种模式下的负载失衡现象.我们主要是针对数据挖掘中的一个并行聚类算法-k2mean并行算法
来分析.在k2mean并行算法中,当主结点把数据集平均分配到各个从结点以后,自己就处于等待状态,等待所有从结点的结果.从结点收到分配给自己的数据后,开始处理.处理完毕后,把结果马上传送到主结点,自己处于等待状态,等待新的数据.当主结点收到所有从结点的处理
5、结果时,进行集成,得出总的结果.这是一
个计算过程.k2mean并行算法,需要若干个这样的过程,因此需要控制这个计算过程重复的执行.我们分析一下算法的时间复杂度.第一,主结点向各个从结点分配数据集的时间t1;第二,各个从结点的计算时间t2,由于主结点需要等待所有的从结点完成任务,所以我们要考虑其中最长的时间;第三,主结点进行集成的时间t3.问题出现在时间t2上面,由于从结点之间的性能差异,对于相同大小的数据集,它们同时完成处理是不可能的,所以在平均分配数据集的情况下[6],各个从结点之间势必出现负载失衡.量化一下,如果从
6、结点A的综合处理速度是从结点B的80%,则对于处理相同数据集结点A的处理时间将会是B的1.25 收稿日期:20031225基金项目:河南省自然科学基金资助项目,编号0111060800.作者简介:王黎明(1963—),男,副教授,博士研究生,主要从事分布式人工智能等研究;E2mail:wlmcym@zzu.edu.cn1 6郑州大学学报(理学版)第36卷倍1也就是说如果结点B要处理4h的话,结点A就要处理5h,等待时间将会是1h.在数据挖掘中,这么长的处理时间是有可能存在的.针对上面的不足,我们提出一种负载均衡的策略,利
7、用移动agent来提高整个程序的处理速度.2 移动Agent的设计移动agent(MobileAgent,简称MA)是一类特殊的agent,它除了具有智能agent最基本的特性如反应行、自治性、导向目标性和针对环境性外,还具有移动性,即它可以在网络上从一台主机自主地移动到另一台主机,代表用户完成指定的任务.MA计算模式能有效地降低分布式计算中的网络负载,提高通信效率,支持断连操作,支持异步自主交互,可动态适应网络环境,具有安全性和容错能力.MA的这些优点,决定了其广泛的应用前景,如电子商务、个人数字助理、安全代理、分布式
8、信息查询、网络管理、信息监测与通报、工业控制、信息与软件发布、并行计算、多角色智力游戏等领域.我们设计的MA应该具有信息检测和并行计算两方面的功能,由多个agent组成,它们各司其职.给出它的模型如图1.在数据池agent中装入数据,通过发指令指挥agent移动到指定处理器结点.消息侦听agent时刻监视自身的情况,
