Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/113237
Title: A partially asynchronous and iterative algorithm for distributed load balancing
Authors: Song, J. 
Keywords: Distributed load balancing
Hypercubes
Load imbalance
Load sharing
Partial asynchronism
Issue Date: Jun-1994
Citation: Song, J. (1994-06). A partially asynchronous and iterative algorithm for distributed load balancing. Parallel Computing 20 (6) : 853-868. ScholarBank@NUS Repository.
Abstract: Defining task as independent entities with identical execution time and the workload of a processor as the number of tasks, load balancing is to distribute tasks among processors of a network so that the resulting workload of every processor will be as close to the average over all the workloads as possible. We propose in this paper a partially asynchronous and iterative algorithm for distributed load balancing, show its properties, and report its simulation results. The algorithm converges geometrically as assured by a theorem for balancing continuous workload. We prove that the algorithm can achieve the maximum load imbalance of no more than ⌈ d 2⌉ tasks, where d is the diameter of a network. Our simulation not only validated the properties but also showed that the algorithm could produce much smaller load imbalances for hypercubes. The obtained imbalances for hypercubes of order up to ten were no more than two tasks and 56% of the sample runs produced only one task difference, as opposed to the theoretical maximum of six tasks. © 1994.
Source Title: Parallel Computing
URI: http://scholarbank.nus.edu.sg/handle/10635/113237
ISSN: 01678191
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

33
checked on Oct 19, 2018

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.