Tight bounds for on-line tree embeddings

Sandeep Bhatt, David Greenberg, Tom Leighton, Pangfeng Liu

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

22 Scopus citations

Abstract

Many tree-structured computations are inherently parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. To maintain load balance, an on-line mapping algorithm must distribute processes equitably among processors. Additionally, the algorithm itself must be distributed in nature, and process allocation must be completed via message-passing with minimal communication overhead. This paper investigates bounds on the performance of deterministic and randomized algorithms for on-line tree embeddings. In particular, we study tradeoffs between performance (load-balance) and communication overhead (message congestion). We give a simple technique to derive lower bounds on the congestion that any on-line allocation algorithm must incur in order to guarantee load balance. This technique works for both randomized and deterministic algorithms, although we find that the performance of randomized on-line algorithms to be somewhat better than that of deterministic algorithms. Optimal bounds are achieved for several networks including multi-dimensional grids and butterflies.

Original languageEnglish
Title of host publicationProceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Pages344-350
Number of pages7
StatePublished - 1 Mar 1991
Event2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991 - San Francisco, United States
Duration: 28 Jan 199130 Jan 1991

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Country/TerritoryUnited States
CitySan Francisco
Period28/01/9130/01/91

Fingerprint

Dive into the research topics of 'Tight bounds for on-line tree embeddings'. Together they form a unique fingerprint.

Cite this