๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Analysis of nearest neighbor load balancing algorithms for random loads

โœ Scribed by Peter Sanders

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
280 KB
Volume
25
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

โœฆ Synopsis

Nearest neighbor load balancing algorithms, like diusion, are popular due to their simplicity, ยฏexibility, and robustness. We show that they are also asymptotically very ecient when a random rather than a worst case initial load distribution is considered. We show that diusion needs Hlog n 2ad balancing time on a d-dimensional mesh network with n d processors. Furthermore, some but not all of the algorithms known to perform better than diffusion in the worst case also perform better for random loads. We also present new results on worst case performance regarding the maximum load deviation.

๐Ÿ“œ SIMILAR VOLUMES

Efficient schemes for nearest neighbor l
Efficient schemes for nearest neighbor load balancing
โœ Ralf Diekmann; Andreas Frommer; Burkhard Monien ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 282 KB

We design a general mathematical framework to analyze the properties of nearest neighbor balancing algorithms of the diusion type. Within this framework we develop a new Optimal Polynomial Scheme (OPS) which we show to terminate within a ยฎnite number m of steps, where m only depends on the graph and