TY - GEN
T1 - Optimal implementation of general divide-and-conquer on the hypercube and related networks
AU - Mayr, Ernst W.
AU - Werchner, Ralph
N1 - Publisher Copyright:
© 1993, Springer Verlag. All rights reserved.
PY - 1993
Y1 - 1993
N2 - We show how to implement divide-and-conquer algorithms without undue overhead on a wide class of networks. We give an optimal generic divide-and-conquer implementation on hypercubes for the class of divide-andconquer algorithms for which the total size of the subproblems on any level of recursion does not exceed the original problem size. For this implementation, appropriately sized subcubes have to be allocated to the subproblems generated by the divide-step. We take care that these allocation steps do not cause unbalanced distribution of work, and that, asymptotically, they do not increase the running time. Variants of our generic algorithm also work for the butterfly network and, by a general simulation, for the class of hypercubic networks, including the shuflte-exchange and the cube-connected-cycles network. Our results can also be applied to optimally solve various types of routing problems.
AB - We show how to implement divide-and-conquer algorithms without undue overhead on a wide class of networks. We give an optimal generic divide-and-conquer implementation on hypercubes for the class of divide-andconquer algorithms for which the total size of the subproblems on any level of recursion does not exceed the original problem size. For this implementation, appropriately sized subcubes have to be allocated to the subproblems generated by the divide-step. We take care that these allocation steps do not cause unbalanced distribution of work, and that, asymptotically, they do not increase the running time. Variants of our generic algorithm also work for the butterfly network and, by a general simulation, for the class of hypercubic networks, including the shuflte-exchange and the cube-connected-cycles network. Our results can also be applied to optimally solve various types of routing problems.
KW - Algorithms and Data Structures
KW - Theory of Parallel and Distributed Computation
UR - http://www.scopus.com/inward/record.url?scp=85029522764&partnerID=8YFLogxK
U2 - 10.1007/3-540-56731-3_19
DO - 10.1007/3-540-56731-3_19
M3 - Conference contribution
AN - SCOPUS:85029522764
SN - 9783540567318
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 195
EP - 206
BT - Parallel Architectures and Their Efficient Use - First Heinz Nixdorf Symposium, Proceedings
A2 - Meyer auf der Heide, Friedhelm
A2 - Monien, Burkhard
A2 - Rosenberg, Arnold L.
PB - Springer Verlag
T2 - 1st Heinz Nixdorf Symposium on Parallel Architectures and Their Efficient Use, 1992
Y2 - 11 November 1992 through 13 November 1992
ER -