The Library
Dynamic diffusion load balancing
Tools
Tools
Tools
Berenbrink, Petra, Friedetzky, Thomas and Martin, R. (2004) Dynamic diffusion load balancing. University of Warwick. Department of Computer Science. (Department of Computer Science research report). (Unpublished)
|
PDF
WRAP_cs-rr-402.pdf - Other - Requires a PDF viewer. Download (235Kb) | Preview |
Abstract
We present the first analysis of a simple discrete diffusion scheme for dynamic load balancing. In each round (1-epsilon)n tasks are (arbitrarily) generated over a set of n processors, load is balanced amongst neighbours in some underlying graph, then a single task is deleted from each non-empty processor. We show that the system is stable, in that the total load remains bounded (as a function of n alone) over time. Our proof only requires that the underlying "communication" graph be connected, and holds even when epsilon = 0. We further show that the upper bound we obtain is asymptotically tight (up to a moderate multiplicative constant) by demonstrating a corresponding lower bound on the system load for the particular example of a linear array (or path). We also show some simple negative results (i.e., instability) for work-stealing based diffusion-type algorithms.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Data structures (Computer science), Software engineering | ||||
| Series Name: | Department of Computer Science research report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | July 2004 | ||||
| Dates: |
|
||||
| Number: | Number 402 | ||||
| Number of Pages: | 13 | ||||
| DOI: | CS-RR-402 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Access rights to Published version: | Restricted or Subscription Access | ||||
| Funder: | Natural Sciences and Engineering Research Council of Canada (NSERC), MITACS (Network), Engineering and Physical Sciences Research Council (EPSRC) | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
