TI Load balancing and Poisson equation in a graph 

LT 90-009 

YR 1990 

AU J.E. Boillat 

AV ftp iam.unibe.ch:TechReports1990iam-90-009.ps.Z 

AB We present a fully distributed dynamic load balancing
algorithm for parallel MIMD architectures.  The algorithm can be
described as a system of identical parallel processes, each
running on a processor of an arbitrary interconnected network of
processors.  We show that the algorithm can be interpreted as a
Poisson (heath) equation in a graph. This equation is analized
using Markov chain techniques and is proved to converge in
polynomial time resulting in a global load balance.  We also
discuss some important parallel architectures and interconnection
schemes such as linear processor arrays, tori, hypercubes, etc.
Finally we present two applications where the algorithm has been
successfully embedded (process mapping and molecular dynamic
simulation).