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.