Notes on merging networks (Prelimiary Version)

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.

REFERENCES

• 1: K. E. Batcher, "Sorting networks and their applications", AFIPS SJCC32 1968.
• 2: H. Delange, "Sur la fonction sommatoire de la fonction somme des chiffres", Enseignement Math. 21, (1975).
• 3: P. Flajolet and L. Ramshaw, "A note on Gray code and odd-even merge", SIAM J. on Computing9, 1 (1980).
• 4: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 5: H. S. Stone, "Parallel processing with the perfect shuffle", IEEE Trans. on ComputingC-20, 2 (1971).
• 6: Andrew Chi-Chih Yao , Foong Frances Yao, Lower Bounds on Merging Networks, Journal of the ACM (JACM), v.23 n.3, p.566-571, July 1976 [doi>10.1145/321958.321976]