Layout of the Batcher bitonic sorter

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

    Research output: Contribution to conferencePaper

    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 - 1998
    EventProceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA - Puerto Vallarta, Mexico
    Duration: Jun 28 1998Jul 2 1998

    Conference

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

    ASJC Scopus subject areas

    • 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

    Even, S., Muthukrishnan, S., Paterson, M. S., & Sahinalp, S. C. (1998). Layout of the Batcher bitonic sorter. 172-181. Paper presented at Proceedings of the 1998 10th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA, Puerto Vallarta, Mexico, .