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 Θ(log2N) 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 ±2b-descend, on a SIMD hypercube . This class includes odd-even merge and many other algorithms. In this paper, we briefly discuss the main ideas of this paradigm.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Artificial Intelligence