Pipelined Parallel Prefix Computations, and Sorting on a Pipelined Hypercube

This paper brings together a number of previously known techniques in order to obtain practical and efficient “pipelined” implementations of the prefix operation for the complete binary tree, hypercube, and shuffle-exchange families of networks. In each case, we provide a scheme for performing k prefix operations in O(k + lg p) time on p processors. The same bounds are shown to apply to the “data distribution” operation of Ullman (Computational Aspects of VLSI, Computer Science Press, Rockville, MD, 1984). The data distribution primitive leads to a simplified implementation of the optimal merging algorithm of Varman and Doshi (Tech. Rep. TR-8802, Rice University, Department of Electrical and Computer Engineering, Feb. 1988), which runs on a pipelined model of the hypercube. Finally, a pipelined version of the multi-way merge sort of Nassimi and Sahni (JACM29 (1982), 642-667), running on the pipelined hypercube model, is described. Given p processors and n < p lg p values to be sorted, the running time of the pipelined algorithm is O(lg²p/lg((p lg p)/n)).