Any load-balancing regimen for evolving tree computations on circulant graphs is asymptotically optimal

Beitrag bei einer Tagung


Details zur Publikation

Autor(en): Wanka R
Verlag: Springer Verlag
Jahr der Veröffentlichung: 2002
Tagungsband: Proc. 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG)
Seitenbereich: 413-420
ISBN: 9783540003311
Sprache: Englisch


Abstract


We analyze evolving tree computations on circulant (rings with "regular" chords) and related graphs. In an evolving α-ary tree computation, a complete tree grows level by level, i. e., every leaf generates α 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. Gao/Rosenberg [2] introduced evolving computations and investigated the growth of complete binary trees on rings of processors. They showed that the so-called ks-regimen behaves optimally in the course of long computations. In this paper, we generalize evolving computations to trees of arbitrary degree 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 for certain inputs 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. © Springer-Verlag Berlin Heidelberg 2002.



FAU-Autoren / FAU-Herausgeber

Wanka, Rolf Prof. Dr.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)


Zitierweisen

APA:
Wanka, R. (2002). Any load-balancing regimen for evolving tree computations on circulant graphs is asymptotically optimal. In Proc. 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG) (pp. 413-420). Cesky Krumlov: Springer Verlag.

MLA:
Wanka, Rolf. "Any load-balancing regimen for evolving tree computations on circulant graphs is asymptotically optimal." Proceedings of the 28th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Cesky Krumlov Springer Verlag, 2002. 413-420.

BibTeX: 

Zuletzt aktualisiert 2018-18-10 um 20:40