An efficient implementation of batcher′s odd-even merge on a SIMD hypercube

We present an efficient Θ(log N) implementation of Batcher′s odd-even merge on a SIMD hypercube. (The hypercube model assumes that all communications are restricted to one fixed dimension at a time.) The best previously known implementation of odd-even merge on a SIMD hypercube requires Θ(log²N) time. The performance of our odd-even merge implementation is comparable to that of bitonic merge. (If the input sequences are both in ascending order and the architecture provides half-duplex communication, then our algorithm runs faster than bitonic merge by a factor of 4/3.) A generalization of our technique has led to an efficient O(log N) algorithm for a wider class of parallel computations, called ±2^b-descend, on a SIMD hypercube [11]. This class includes odd-even merge and many other algorithms. In this paper, we briefly discuss the main ideas of this paradigm.