### Periodification scheme: constructing sorting networks with constant periodPeriodification scheme: constructing sorting networks with constant period

Access Restriction
Subscribed

 Author kutyowski, Mirosaw ♦ Lory, Krzysztof ♦ Oesterdiekhoff, Brigitte ♦ Wanka, Rolf Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2000 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Comparator network Abstract We consider comparator networks $\textit{M}$ that are used repeatedly: while the output produced by $\textit{M}$ is not sorted, it is fed again into $\textit{M}.$ Sorting algorithms working in this way are called $\textit{periodic}.$ The number of parallel steps performed during a single run of $\textit{M}$ is called its $\textit{period},$ the sorting $\textit{time}$ of $\textit{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 comparator networks of a constant period, due to their potential applications in hardware design. Previously, very little was known on such networks. The fastest solutions required time $\textit{O(n}ε)$ where the depth was roughly 1/ε. We introduce a general method called periodification scheme that converts automatically an arbitrary sorting network that sorts $\textit{n}$ items in time $\textit{T(n})$ and that has layout area $\textit{A(n})$ into a sorting network that has period 5, sorts $***(\textit{n}$ • $\textit{T}(\textit{n})$ items in time \$\textit{O(T(

#### Open content in new tab

Source: ACM Digital Library