TY - GEN

T1 - Efficient parallel divide-and-conquer for a class of interconnection topologies

AU - Wu, I-Chen

PY - 1991/1/1

Y1 - 1991/1/1

N2 - In this paper, we propose an efficient scheduling algorithm for expanding any divide-and-conquer (D&C) computation tree on k-dimensional mesh, hypcrcube, and perfect shuffle networks with p processors. Assume that it takes in time steps to expand one node of the tree and tc time steps to transmit one datum or convey one node. For any D&C computation tree with N nodes, height h, and degree d (maximal number of children of any node), our algorithm requires at most (formula presented) time steps, where φ is O(log2 p) on a hypercube or perfect shuffle network and is (formula presented) on a (formula presented) mesh network, where (formula presented) This algorithm is general in the sense that it does not know the values of N, h, and d, and the shape of the computation tree as well, a priori. Most importantly, we can easily obtain a linear speedup by nearly a factor of p, especially when (formula presented).

AB - In this paper, we propose an efficient scheduling algorithm for expanding any divide-and-conquer (D&C) computation tree on k-dimensional mesh, hypcrcube, and perfect shuffle networks with p processors. Assume that it takes in time steps to expand one node of the tree and tc time steps to transmit one datum or convey one node. For any D&C computation tree with N nodes, height h, and degree d (maximal number of children of any node), our algorithm requires at most (formula presented) time steps, where φ is O(log2 p) on a hypercube or perfect shuffle network and is (formula presented) on a (formula presented) mesh network, where (formula presented) This algorithm is general in the sense that it does not know the values of N, h, and d, and the shape of the computation tree as well, a priori. Most importantly, we can easily obtain a linear speedup by nearly a factor of p, especially when (formula presented).

UR - http://www.scopus.com/inward/record.url?scp=84974731441&partnerID=8YFLogxK

U2 - 10.1007/3-540-54945-5_67

DO - 10.1007/3-540-54945-5_67

M3 - Conference contribution

AN - SCOPUS:84974731441

SN - 9783540549451

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 229

EP - 240

BT - ISA 1991 Algorithms - 2nd International Symposium on Algorithms, Proceedings

A2 - Lee, R.C.T.

A2 - Hsu, Wen-Lian

PB - Springer Verlag

Y2 - 16 December 1991 through 18 December 1991

ER -