An Efficient Implementation of Batcher′s Odd-Even Merge on a SIMD Hypercube

✍ Scribed by D. Nassimi; Y.D. Tsai

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 469 KB
• Volume: 19
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1993.1090

✦ Synopsis

We present an efficient (\theta(\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 (\Theta\left(\log ^{2} N\right)) 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.) A generalization of our technique has led to an efficient (O(\log N)) algorithm for a wider class of parallel computations, called (\pm 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. O 1993 Academic Press, Inc.