Constructing sorting networks with constant period
Miroslaw Kutylowski, Krzysztof Lorys,
Brigitte Oesterdiekhoff, Rolf Wanka
We consider comparator networks M which are used repeatedly: while the
output produced by M is not sorted, it is fed again into M. Sorting
algorithms working in this way are called periodic. The number of
parallel steps performed during a single run of M is called its period,
the sorting time of M is the total number of parallel steps that are
necessary to sort in the worst case. Periodic sorting networks have the
advantage that they need little hardware (control logic, wiring, area)
and that they are adaptive. We are interested in using comparator
networks with constant period, since they are very easy to implement by
VLSI circuits. This paper presents the following new results.
We introduce a general method called the periodification scheme that
converts automatically an arbitrary sorting network that sorts n items
in time T(n) and that has layout area A into a sorting network that has
period 5, sorts Theta(n T(n)) items in time O(T(n) log n), and has
layout area O(A T(n)). In particular, applying this scheme to Batcher's
algorithms, we get practical period 5 comparator networks that sort in
time O(log^3 n). For theoretical interest, one may use the AKS network
resulting in a period 5 comparator network with runtime O(log^2 n).
Developing the techniques necessary to show the main result, we
construct a network with period 3 that sorts n items in time O(sqrt(n)
log n), and that has the layout of a two-dimensional mesh.