Fast and feasible periodic sorting networks of constant depth,
Miroslaw Kutylowski, Krzysztof Lorys,
Brigitte Oesterdiekhoff, Rolf Wanka
A periodic comparator network has depth (or period) k, if for every t>k,
the compare-exchange operations performed at step t are executed between
exactly the same registers as at step t-k.
We introduce a general method that converts an arbitrary comparator
network that sorts n items in time T(n) and that has layout area A into
a periodic sorting network of depth 5 that sorts Theta(n T(n)) items in
time O(T(n)log n) and has layout area O(A T(n)). This scheme applied to
the AKS network yields a depth 5 periodic comparator network that sorts
in time O(log^2 n). More practical networks with runtime O(log^3 n) can
be obtained from Batcher's networks. Developing the techniques for the
main result, we improve some previous results: Let us fix a din IN. Then
we can construct a network of depth 3 based on a d-dimensional mesh
sorting n items in time O(n^(1/d) log^(O(d) n)).