TY - JOUR
T1 - Lower Bounds for Dynamic Tree Embedding in Bipartite Networks
AU - Li, Keqin
AU - Pan, Yi
AU - Shen, Hong
AU - Young, Gilbert H.
AU - Zheng, Si Qing
N1 - Funding Information:
Keqin Li was supported by National Aeronautics and Space Administration and the Research Foundation of State University of New York through the NASA University Joint Venture in Space Science Program under Grant NAG8-1313 (1996-99), and the 1996 NASA ASEE Summer Faculty Fellowship Program. Part of the work was done while he was visiting NASA Goddard Space Flight Center, Green-belt, Maryland, during the summer of 1996. Yi Pan was supported by the National Science Foundation under Grants CCR-9211621 and CCR-9503882, the Air Force Avionics Laboratory, Wright Laboratory, Dayton, Ohio, under Grant F33615-C-2218, and an Ohio Board of Regents Investment Fund Competition Grant. Hong Shen was supported by the Australian Research Council under its Large Research Grant (1996-98) A849602031. Gilbert Young was supported by CUHK Grant 220501290. Si Qing Zheng was supported by the National Science Foundation under Grant ECS-9626215, and Louisiana Grant LEQSF (1996-99)-RD-A-16. Thanks are also due to Cai-Pei Cao and Yizheng Zhou, two graduate students in SUNY at New Paltz, for observing the lower bounds from their simulation studies of dynamic tree embedding in hypercubes and meshes.
PY - 1998/9/15
Y1 - 1998/9/15
N2 - There are many parallel computations that are tree structured. The structure of a tree is usually unpredictable at compiler-time; the tree grows gradually during the course of a computation. The dynamic tree embedding problem is to distribute the processes of a parallel computation over processors in a parallel computer such that processors perform roughly the same amount of computation, and that communicating processes are assigned to processors that are close to each other. In this paper, we establish lower bounds for the performance ratio of dynamic tree embedding in bipartite static networks, including numerous important networks such asn-dimensional meshes,n-dimensional tori,k-aryn-cubes, cube-connected cycles, and butterflies. Our lower bounds are obtained from both tree and network properties and are applicable to a general class of dynamic tree embedding algorithms.
AB - There are many parallel computations that are tree structured. The structure of a tree is usually unpredictable at compiler-time; the tree grows gradually during the course of a computation. The dynamic tree embedding problem is to distribute the processes of a parallel computation over processors in a parallel computer such that processors perform roughly the same amount of computation, and that communicating processes are assigned to processors that are close to each other. In this paper, we establish lower bounds for the performance ratio of dynamic tree embedding in bipartite static networks, including numerous important networks such asn-dimensional meshes,n-dimensional tori,k-aryn-cubes, cube-connected cycles, and butterflies. Our lower bounds are obtained from both tree and network properties and are applicable to a general class of dynamic tree embedding algorithms.
KW - Bipartite network; dynamic tree embedding; lower bound; performance ratio; randomized tree
UR - http://www.scopus.com/inward/record.url?scp=0040635061&partnerID=8YFLogxK
U2 - 10.1006/jpdc.1998.1475
DO - 10.1006/jpdc.1998.1475
M3 - Article
AN - SCOPUS:0040635061
SN - 0743-7315
VL - 53
SP - 119
EP - 143
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 2
ER -