Multiple message broadcasting with generalized Fibonacci trees
Jehoshua Bruck, Robert Cypher, et al.
SPDP 1992
This paper presents a parallel sorting algorithm called Cubesort. Cubesort sorts N data items by performing a number of rounds, each of which partitions the N data items into groups of size S and sorts within the groups. For many values of N and S, Cubesort requires fewer such rounds than are required by any previously published algorithm. Cubesort can also be used to sort N data items on hypercube, shuffle-exchange, and cube-connected cycles computers with P processors in time O(N log2 N P log( N P)) over a wide range of the parameters N and P. In particular, when N = P1 + 1 k and k is a constant, Cubesort sorts on the above parallel computers in O(N log N P) time, thus obtaining an optimal processor-time product for comparison sorting. The application of Cubesort to general routing problems is also discussed. © 1992.
Jehoshua Bruck, Robert Cypher, et al.
SPDP 1992
Jehoshua Bruck, Robert Cypher, et al.
SIAM Journal on Computing
Robert Cypher, Smaragda Konstantinidou
SPAA 1993
Jehoshua Bruck, Robert Cypher, et al.
IEEE TC