Lower Bounds for Dynamic Tree Embedding in Bipartite Networks

Keqin Li, Yi Pan, Hong Shen, Gilbert H. Young, Si Qing Zheng

研究成果: Article同行評審

12 引文 斯高帕斯(Scopus)


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.

頁(從 - 到)119-143
期刊Journal of Parallel and Distributed Computing
出版狀態Published - 15 9月 1998


深入研究「Lower Bounds for Dynamic Tree Embedding in Bipartite Networks」主題。共同形成了獨特的指紋。