Periodic Merging Networks

We consider the problem of merging two sorted sequences on constant degree networks performing compare—exchange operations only. The classical solution to this problem is given by the networks based on Batcher's Odd—Even Merge and Bitonic Merge running in log(2n ) time. Due to the obvious log n lower bound for the runtime, this is time-optimal.

We present a new family of merging networks working in a completely different way than the previously known algorithms. They have a novel property of being periodic: this means that for some (small) constant k , each processing unit of the network performs the same operations at steps t and t+k (as long as t+k does not exceed the runtime). The only operations executed are compare—exchange operations, just like in the case of Batcher's networks. The architecture of the networks is very simple and easy to lay out.

We show that even for period 3 there is a network in our family merging two n -element sorted sequences in time O(log n ). Since each network of period 2 requires \(\Theta(n)\) steps to merge such sequences, 3 is the smallest period for which we may achieve a fast runtime.

In order to improve constants standing in front of log n we increment the period and tune the construction using additional techniques. We achieve the runtime 9 . . . log_3 n \(\approx\) 5.7 . . . log n for a network of period 4, and 2.25 . . . ((k+3)/(k-1+log 3))log n \(\approx\) 2.25 . . . log n for a network of period k+3 , for \(k\geq 1\) .

Due to the periodic design, our networks have small area complexity. For instance, if each processing unit requires O(1) area and a comparator uses a single wire of width O(1) connecting the processing elements, then our networks require \(\Theta((n/\log n)^2)\) area. This compares well with Batcher's networks that require area \(\Theta(n^2)\) .

Authors and Affiliations

1. Heinz Nixdorf Institute and Department of Mathematics and Computer Science, University of Paderborn, D-33095 Paderborn, Germany mirekk@uni-paderborn.de brigitte@uni-paderborn.de, , , , , , DE

   M. Kutylowski & B. Oesterdiekhoff

2. Department of Computer Science, University of Trier, D-54286 Trier, Germany lorys@TI.Uni-Trier.DE, , , , , , DE

   K. Lorys

Received February 1997, and in revised form September 1997, and in final form February 1998.

Reprints and permissions