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

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

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

  第18卷 第11期

   1997年11月小型微型计算机系统MINI-MICROSYSTEMSVol.18No.11Nov.1997

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

何炎祥 罗先林 吴 思 彭堂玉 祝向幸

(武汉大学计算机科学与技术学院 武汉430072)*

摘 要 本文先分析了基于图论的分配算法,整数规划方法和试探法等几种典型的分布式任务分配算法的基本思想、特点,不足和算法复杂度,以及可进一步改进之处,然后给出了一种试探法的改进算法,并简单讨论了其特点和性能,最后指出了分布式任务分配的发展方向。

关键词 通信开销,执行开销,负载平衡,合一,试探法

在分布式系统中非同居模块间的数据传递产生处理机间的通信,这种机间通信可能使得增加处理机数目反而会引起系统吞吐量的降低,即产生“饱和效应”。为降低饱和效应,人们倾向于把模块分配到尽可能少的处理机上,但这又导致系统负载不平衡,从而降低了系统的吞吐量。显然,这是任务分配中相互冲突的两个方面,不同的任务分配算法试图用不同的策略来平衡这两个方面。

传统的分布式任务分配算法大致可分为三类:基于图论的分配算法,整数规划方法和试探法。这三类算法并非互斥的,一类算法中往往可以借鉴其它方法中的某些技术。下面,我们先对这三类典型算法进行分析和比较,然后给出一种试探法的改进算法。

在讨论中,我们假定提交的任务已分解成一组模块并使模块间的通信量尽可能小。还假定分配模式为:一任务被分解成m个模块T={t1,t2,…,tm},系统中有n个可利用的处理机P={p1,p2,…,pn}。任务分配的目的就是将这m个模块分配到n个处理机上,使预期的性能目标函数值最小。

1 对三种典型算法的分析

1.1 基于图论的分配算法

基本思想是给定矩阵Cmxm表示模块间的通信开销:

C={ci,j 1≤i≤m&1≤j≤m&ci,j为ti与tj间的通信量}

给定矩阵Qmxn表示模块的执行开销:

Q={qi,j 1≤i≤m&1≤j≤n&qi,j为ti在pj上的执行开销}

将模块t1,t2,…,tm作为图中结点,若两模块间有数据传递,则相应结点间有一条无向边,1996-04-26收稿 *软件工程国家重点实验室开放基金部分资助。何炎祥,教授,研究方向:分布式OS与分布信息处理,,,

第1页

你可能喜欢

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

热门文档

相关文档

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