文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 对三种典型分布式任务分配算法的分析
侵权投诉

对三种典型分布式任务分配算法的分析

并行与分布式计算动态负载均衡策略

               小型微型计算机系统               1997年2

边上的权wi,j=ci,j;处理机p1,p2,…,pn也作为图中结点,若qi,k≠∞,则在ti与pk间有一

条边,定义该边上的权为wi,k=∑qi,j-ci,k。于是,可将该图视为一个网络,并定n-1j≠kn-1

义n度割集为将网络中各个结点分割成n个不相交的子集,使得每个子集中有且仅有一个处理机结点。可以证明,每个切口的开销正好是执行开销和通信开销之和,因此,在图上执行MaxFlow/MinCut算法,就可得到任务的最优分配方案。在现阶段,仅有多项式复杂度n=2的MaxFlow/MinCut算法,因此,基于图论的分配算法仅限于在处理机数目小于3的环境中使用,因而局限性较大。

Lo在[1]中提出了一种改进算法。该算法分为迭代、汇总和贪心三个阶段。在第一阶段的每一轮迭代中,依次考虑每个结点p1,p2,…,pn,把pj和-pj=P-{pj}作为两个独立的结点,并将所有到P-{pj}的边用一个到-pj的边代替,该边上的权为所有到P-{pj}的边上的权之和。利用MaxFlow/MinCut算法,可得到分配给pj的模块的一个子集。删去在此轮迭代中已分配给pj的那些模块结点,并定义未删除的模块tj与处理机pk间的权为

qi,k[1]=qi,j+-t为已分配给p的某个处理机的模块jk∑ci,j

若所有的模块结点已分配完,或在最后一轮迭代中没有模块分配给某个处理机,则迭代阶段结束。Lo证明了迭代的终止性及若此时模块分配完则将获得最优解。

在汇总阶段,首先计算一个优化的n度割集的下界

L=∑min(q

t∈T′jki,k)+minc(pj,pr)j≠r

其中,c(pj,pr)为任意选择的处理机间最小切口的开销,T′为所有第一阶段中没有分配的模块的集合。然后,检查将剩余模块指派到某个处理机上是否更合适,若是,则算法结束,也得到一个最优解。否则进入贪心阶段。将相互通信开销大的模块汇集成簇,同一簇中的模块分配到同一个处理机上,这样得到的结果是次最优的。

这个改进算法解决了基本算法在处理机数目上的限制。为使此算法更能反映真实情况,Lo还考虑了每个处理机上可利用资源的限制和同居模块间的通信开销,并引入了冲突开销的因素。此外,Lo提出了一种限制各处理机上模块数的方法,其基本思想是:若m>2n,则先进行合一,并保证合一后的簇中模块数目不超过[B/2](B为一处理机上最大允许的模块数)。重复这种合一过程,直至模块簇数目m′≤2n,然后再用适当算法将m′个模块簇按最小执行开销分配到n个处理机上。

这个改进算法利用了试探法中对模块进行合一的思想,并直接利用了现有的网络算法,因此实现较简单,但算法开销大,因为MaxFlow/MinCut算法的时间复杂度为O(a2log2+a/nb),其中a,b分别为边数和结点数。每次迭代中,每获得分配给一个处理机的模块子集的复杂度为O(mlog2m)(设系统为全互连的),这样,每次迭代的开销为O(nmlog2m),而最坏迭代次数为m。因此,最坏情况下的复杂度为O(nmlog2m)。此外,该算法没有明确反映实时性和存储方面的限制,没有提供保护模块优先关系的机制,也不能衡量排队延迟对吞吐量的影响。

1.2 整数规划方法

基本思想是仍用前面定义的Q矩阵表示执行开销,但用Vm×m表示模块间的通信开销:vit544

上一页第2页

你可能喜欢

  • 分配问题
  • 任务调度算法
  • 分布式计算技术
  • 分布式系统
  • 领导能力

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email