Prefix Computation and Sorting in Dual-Cube
Yamin Li, Shietung Peng, Wanming Chu · 2008
In this paper, we describe two algorithmic techniques for the design of efficient algorithms in dual-cube. The first uses cluster structure of dual-cube, and the second uses recursive structure of the dual-cube. We propose efficient algorithms for parallel prefix computation and sorting in dual-cube based on the two techniques, respectively. For a dual-cube Dnwith 22n-1nodes and n links per node, the communication and computation times of the algorithm for parallel prefix computation are at most 2n+1 and 4n-2, respectively; and those of the algorithm for sorting are at most 6n2and 2n2, respectively.