ALCOMFT-TR-02-45
|
|
Rolf Wanka
Any Load-Balancing Regimen for Evolving TreeComputations on CirculantGraphs is Asymptotically Optimal
Paderborn.
Work package 2.
May 2002.
Abstract: We analyze evolving tree computations on circulant (rings with chords)
and related graphs.
In an evolving alpha-ary
tree computation, a complete tree grows level by level,
i. e., every leaf generates alpha new nodes that become the new leaves.
The load balancing task is to spread the new nodes on a network
of processors in the moment they were created in such a way that the
accumulated number
of nodes per processor, i. e., its load,
is as close as possible to the average
number of nodes per processor.
As a single processor can hold many leaves, it has to handle many
new tokens.
Gao/Rosenberg [L.-X. Gao and A. L. Rosenberg.
Toward efficient scheduling of evolving computations on rings of
processors.
Journal of Parallel and Distributed Computing, 38:92-100,
1996] introduced evolving computations
and investigated the growth of complete binary trees on %length n-
rings of processors.
They showed that the so-called \textscks-regimen
where one new node generated by a leaf
remains at the processor where it has been created
and the other one is transmitted to the right neighboring processor behaves
optimally in the course of long computations.
In this paper, we generalize evolving computations to arbitrary trees
and we generalize the regimen notion.
We show that any regimen behaves optimally.
For this purpose, we model the actual load distribution, the
generation process, and the distribution regimen by formal
infinite polynomials. Then we show that evaluating these polynomials
at certain points leads to the analysis of these regimens on circulant
and related graphs.
It is shown that any regimen leads to a close to optimal
load distribution.
Postscript file: ALCOMFT-TR-02-45.ps.gz (51 kb).
System maintainer Gerth Stølting Brodal <gerth@cs.au.dk>