Lower Bounds for Dynamic Tree Embedding in Bipartite Networks |
| |
| Authors: | Keqin Li Yi Pan Hong Shen Gilbert H. Young Si Qing Zheng |
| |
| Affiliation: | aDepartment of Mathematics and Computer Science, State University of New York, New Paltz, New York, 12561-2499, f1;bDepartment of Computer Science, University of Dayton, Dayton, Ohio, 45469-2160, f2;cSchool of Computing and Information Technology, Griffith University, Nathan, QLD 4111, Australiaf3;dDepartment of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong, f4;eDepartment of Computer Science, Louisiana State University, Baton Rouge, Louisiana, 70803-4020, f5 |
| |
| Abstract: | 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. |
| |
| Keywords: | bipartite network dynamic tree embedding lower bound performance ratio randomized tree |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
