ALCOMFT-TR-02-96

Robert Elsässer, Burkhard Monien and Robert Preis
Diffusion Schemes for Load Balancing on Heterogeneous Networks
Paderborn. Work package 2. May 2002.

Abstract: Several different diffusion schemes have previously been developed for load balancing on homogeneous processor networks. We generalize existing schemes, in order to deal with heterogeneous networks. The generalized schemes may operate efficiently on networks where every processor can have arbitrary computing power, i. e., the load will be balanced proportionally to these weights. The balancing flow that is calculated by the schemes for homogeneous networks is minimal with regard to the l₂-norm and we prove this to hold true for the generalized schemes, too. We demonstrate the usability of the generalized schemes by a number of experiments on several heterogeneous networks.

Postscript file: ALCOMFT-TR-02-96.ps.gz (124 kb).