other · CaltechAUTHORS (California Institute of Technology) · 1991

Tight Bounds for On-line Tree Embedding

Bhatt, Sandeep, Greenberg, David, Leighton, Tom, Liu, Pangfeng

Cited by 0Open access

Abstract

Many tree–structured computations are inherently parallel.\nAs leaf processes are recursively spawned they can\nbe assigned to independent processors in a multicomputer\nnetwork. To maintain load balance, an on–line\nmapping algorithm must distribute processes equitably\namong processors. Additionally, the algorithm itself\nmust be distributed in nature, and process allocation\nmust be completed via message–passing with minimal\ncommunication overhead.\n\nThis paper investigates bounds on the performance\nof deterministic and randomized algorithms for on–line\ntree embedding. In particular, we study tradeoffs between\nperformance (load–balance) and communication\noverhead (message congest ion). We give a simple technique\nto derive lower bounds on the congestion that\nany on–line allocation algorithm must incur in order to\nguarantee load balance. This technique works for both\nrandomized and deterministic algorithms, although we\nfind that the performance of randomized on-line algorithms\nto be somewhat better than that of deterministic\nalgorithms. Optimal bounds are achieved for several\nnetworks including multi–dimensional grids and butterflies.

Cite this paper

APA 7

Bhatt, S., Greenberg, D., Leighton, T., & Liu, P. (1991). Tight Bounds for On-line Tree Embedding. CaltechAUTHORS (California Institute of Technology).

MLA 9

Bhatt, Sandeep, et al. “Tight Bounds for On-line Tree Embedding.” CaltechAUTHORS (California Institute of Technology), 1991.

Chicago

Bhatt, Sandeep, David Greenberg, Tom Leighton, and Pangfeng Liu. 1991. “Tight Bounds for On-line Tree Embedding.” CaltechAUTHORS (California Institute of Technology).

Harvard

Bhatt, S. et al. (1991) ‘Tight Bounds for On-line Tree Embedding’, CaltechAUTHORS (California Institute of Technology).

BibTeX

@misc{bhatt1991tight,
  title = {{Tight Bounds for On-line Tree Embedding}},
  author = {Bhatt, Sandeep and Greenberg, David and Leighton, Tom and Liu, Pangfeng},
  journal = {CaltechAUTHORS (California Institute of Technology)},
  year = {1991}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.