• DocumentCode
    301102
  • Title

    Minimizing communication of a recirculating bitonic sorting network

  • Author

    Lee, Jae-Dong ; Batcher, Kenneth E.

  • Author_Institution
    Dept. of Math. & Comput. Sci., Kent State Univ., OH, USA
  • Volume
    1
  • fYear
    1996
  • fDate
    12-16 Aug 1996
  • Firstpage
    251
  • Abstract
    This paper presents the construction of a new recirculating bitonic sorting network which reduces the O(Nlog2N) cost complexity of the original bitonic sorting network to O(NlogN) while preserving the well known time complexity of O(log2N). Network communication is reduced by one half by leaving the N/2 even-parity keys in the local memory of each comparator
  • Keywords
    communication complexity; multistage interconnection networks; parallel algorithms; parallel architectures; sorting; N/2 even-parity keys; O(Nlog2N) cost complexity; O(NlogN); comparator; local memory; network communication; recirculating bitonic sorting network; time complexity; Computer science; Corporate acquisitions; Costs; Electronic mail; Mathematics; Network topology; Parallel processing; Sorting; Switches; Time measurement;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Parallel Processing, 1996. Vol.3. Software., Proceedings of the 1996 International Conference on
  • Conference_Location
    Ithaca, NY
  • ISSN
    0190-3918
  • Print_ISBN
    0-8186-7623-X
  • Type

    conf

  • DOI
    10.1109/ICPP.1996.537166
  • Filename
    537166
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=301102