Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 1991 | Published
Book Section - Chapter Open

Tight Bounds for On-line Tree Embedding

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 embedding. In particular, we study tradeoffs between performance (load–balance) and communication overhead (message congest ion). 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.

Additional Information

©1991 SIAM. The authors thank Jin-Yi Cai for helpful discussions. Sandeep Bhatt was supported at Caltech by DARPA Order Number 6202, monitored by ONR under contract N00014-87-K-0745. Sandeep Bhatt, David Greenberg and Pangfeng Liu were supported at Yale in part by Air Force grant AFOSR-89-0382, NSF grant CCR-88-07426, and NSF/DARPA grant CCR-89-08285. Tom Leighton was supported at MIT by Air Force grant AFOSR-89-0271, Army contract DAAL-03-86-K-0171, and DARPA contracts N0001489-J-1988 and N0001487-K-825.

Attached Files

Published - p344-bhatt.pdf

Files

p344-bhatt.pdf
Files (719.8 kB)
Name Size Download all
md5:f96ae21f3a57f8535bc176d9f8b58f57
719.8 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
October 18, 2023