TY - GEN
T1 - Tight bounds for on-line tree embeddings
AU - Bhatt, Sandeep
AU - Greenberg, David
AU - Leighton, Tom
AU - Liu, Pangfeng
N1 - Publisher Copyright:
© 1991 Association for Computing Machinery. All rights reserved.
PY - 1991/3/1
Y1 - 1991/3/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84957550967&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84957550967&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:84957550967
SN - 0897913760
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 344
EP - 350
BT - Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
T2 - 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 1991
Y2 - 28 January 1991 through 30 January 1991
ER -