TY - GEN

T1 - Notes on merging networks

AU - Hong, Zhu

AU - Sedgewick, Robert

N1 - Funding Information:
I Researchs upportedb y the NSF, Grant No. MCS80-17579
Publisher Copyright:
© 1982 ACM.
Copyright:
Copyright 2018 Elsevier B.V., All rights reserved.

PY - 1982/5/5

Y1 - 1982/5/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85009207886&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85009207886&partnerID=8YFLogxK

U2 - 10.1145/800070.802204

DO - 10.1145/800070.802204

M3 - Conference contribution

AN - SCOPUS:85009207886

SN - 0897910702

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 296

EP - 302

BT - Proceedings of the 14th Annual ACM Symposium on Theory of Computing, STOC 1982

PB - Association for Computing Machinery

T2 - 14th Annual ACM Symposium on Theory of Computing, STOC 1982

Y2 - 5 May 1982 through 7 May 1982

ER -