Notes on merging networks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

10 Scopus citations

Abstract

Several new results which contribute to the understanding of parallel merging networks are presented. First, a simple new explanation of the operation of Batcher's merging networks is offered. This view leads to the derivation of a modified version of Batcher's odd-even (m, n) network which has delay time [log(m + n)]. This is the same delay time as Batcher's bitonic (m, n) network, but it is achieved with substantially fewer comparators. Second, a correspondence is demonstrated between the number of comparators (and the delay time) for such networks and certain properties of binary number systems which have recently been extensively studied. Third, the (log(m + n)] delay time is shown to be optimal for a non-degenerate range of values of m and n.

Original languageEnglish (US)
Title of host publicationProceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982
PublisherAssociation for Computing Machinery
Pages296-302
Number of pages7
ISBN (Print)0897910702
DOIs
StatePublished - May 5 1982
Externally publishedYes
Event14th Annual ACM Symposium on Theory of Computing, STOC 1982 - San Francisco, United States
Duration: May 5 1982May 7 1982

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other14th Annual ACM Symposium on Theory of Computing, STOC 1982
CountryUnited States
CitySan Francisco
Period5/5/825/7/82

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Notes on merging networks'. Together they form a unique fingerprint.

  • Cite this

    Hong, Z., & Sedgewick, R. (1982). Notes on merging networks. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982 (pp. 296-302). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800070.802204