TY - JOUR
T1 - Tight bounds for on-line tree embeddings
AU - Bhatt, Sandeep
AU - Greenberg, David
AU - Leighton, Tom
AU - Liu, Pangfeng
PY - 1999
Y1 - 1999
N2 - Tree-structured computations are relatively easy to process in parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. However, to achieve good performance the on-line mapping algorithm must maintain load balance, i.e., 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 trade-offs between computation overhead (load imbalance) 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. We prove that the advantage of randomization is limited. Optimal bounds are achieved for several networks, including multidimensional grids and butterflies.
AB - Tree-structured computations are relatively easy to process in parallel. As leaf processes are recursively spawned they can be assigned to independent processors in a multicomputer network. However, to achieve good performance the on-line mapping algorithm must maintain load balance, i.e., 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 trade-offs between computation overhead (load imbalance) 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. We prove that the advantage of randomization is limited. Optimal bounds are achieved for several networks, including multidimensional grids and butterflies.
UR - http://www.scopus.com/inward/record.url?scp=0033299656&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0033299656&partnerID=8YFLogxK
U2 - 10.1137/S0097539796308710
DO - 10.1137/S0097539796308710
M3 - Article
AN - SCOPUS:0033299656
SN - 0097-5397
VL - 29
SP - 474
EP - 491
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 2
ER -