Periodic merging networks
Miroslaw Kutylowski, Krzysztof Lorys, Brigitte Oesterdiekhoff
We consider the problem of merging two sorted sequences on constant
degree networks using comparators only. The classical solution to the
problem are 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 new merging networks that have a novel property of being
periodic: 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 the Batcher's
networks. The architecture of the networks is very simple, easy to be
laid out. The runtimes achieved are c log n, for a small constant c.