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

David Nassimi, Yuh Dong Tsai

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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 [11]. This class includes odd-even merge and many other algorithms. In this paper, we briefly discuss the main ideas of this paradigm.

Original languageEnglish (US)
Pages (from-to)58-63
Number of pages6
JournalJournal of Parallel and Distributed Computing
Volume19
Issue number1
DOIs
StatePublished - Sep 1993

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'An efficient implementation of batcher′s odd-even merge on a SIMD hypercube'. Together they form a unique fingerprint.

Cite this