Please use this identifier to cite or link to this item:
|Title:||A partially asynchronous and iterative algorithm for distributed load balancing|
|Keywords:||Distributed load balancing|
|Source:||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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Feb 17, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.