Dynamic load balancing by random matchings
Dynamic load balancing by random matchings
复制标题
DOI：
10.1006/jcss.1996.0075
复制
发表时间：
1996-12-01
影响因子：
1.1
通讯作者：
Muthukrishnan, S
中科院分区：
文献类型：
--
作者：
Ghosh, B;Muthukrishnan, S
在并行和分布式网络中，动态负载平衡和作业调度的基本问题涉及到在处理器之间移动负载。本文研究了同步电机负载运动的一种新模型。在我们的模型的每一步中，负载只能在一组匹配的通信链路上移动，但在每条链路上可以移动任意数量的负载。针对负载移动模型下的动态负载均衡问题，提出了一种高效的局部算法。我们的算法适用于可能发生链路故障的任意拓扑网络。算法的运行时间与底层图的特征结构有关。我们还给出了实验结果，分析了与我们的算法相关的负载均衡问题。(C)1996年学术出版社。
The fundamental problems in dynamic load balancing and job scheduling in parallel and distributed networks involve moving load between processors. In this paper we consider a new model for load movement in synchronous machines. In each step of our model, load can be moved across only a matching set of communication links but across each link any amount of load can be moved. We present an efficient local algorithm for the dynamic load balancing problem under our model of load movement. Our algorithm works on networks of arbitrary topology under possible failure of links. The running lime of our algorithm is related to the eigenstructure of the underlying graph. We also present experimental results analyzing issues in load balancing related to our algorithms. (C) 1996 Academic Press, Inc.