Layout of the Batcher bitonic sorter

Sh Even, Shan Muthukrishnan, M. S. Paterson, S. C. Sahinalp

Research output: Contribution to conferencePaperpeer-review

7 Scopus citations

Abstract

The grid-area required by a sorting net for input vectors of length N is shown to be at least (N - 1)2/2. Of all sorting nets which use o(N2) comparators, the bitonic sorting net of Batcher has been known to have a layout of O(N2), but the hidden constant factor has not been investigated. A straightforward use of known techniques leads to a layout of grid-area 20.25N2. We present area-efficient layouts of the bitonic sorter. First, we describe a flip-bitonic sorting net - it is isomorphic to Batcher's bitonic sorter but leads naturally to a layout of grid-area less than 4N2. Second, we present a butterfly-based layout of the bitonic sorter with grid-area of 3N2 + O(N). The former does not use knock-knees while the latter relies on them and is more compact.

Original languageEnglish (US)
Pages172-181
Number of pages10
StatePublished - Jan 1 1998
Externally publishedYes
EventProceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA - Puerto Vallarta, Mexico
Duration: Jun 28 1998Jul 2 1998

Other

OtherProceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA
CityPuerto Vallarta, Mexico
Period6/28/987/2/98

All Science Journal Classification (ASJC) codes

  • Software
  • Safety, Risk, Reliability and Quality

Fingerprint Dive into the research topics of 'Layout of the Batcher bitonic sorter'. Together they form a unique fingerprint.

Cite this