Periodification scheme: Constructing sorting networks with constant period

Beitrag in einer Fachzeitschrift

Details zur Publikation

Autor(en): Kutylowski M, Lorys K, Oesterdiekhoff B, Wanka R
Zeitschrift: Journal of the Acm
Verlag: Association for Computing Machinery
Jahr der Veröffentlichung: 2000
Band: 47
Heftnummer: 5
Seitenbereich: 944-967
ISSN: 0004-5411
Sprache: Englisch


We consider comparator networks M that 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 'Us period, the sorting time of M is the total number of parallel steps that are necessary to sort in the worst case. Periodic sprting 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 O(n), where the depth was roughly 1/∈. We introduce a general method called periodiflcation scheme that converts automatically an arbitrary sorting network that sorts n items in time T(n) and that has layout area A(n) into a sorting network that has period 5, sorts (n · T(n)) items in time O(T(n) · log n), and has layout area O(A(n) ·T(n)). In particular, applying this scheme to Batcher's algorithms, we get practical period 5 comparator networks that sort in time O(log n). For theoretical interest, one may use the AKS network resulting in a period 5 comparator network with runtime 0(log n). © 2000 ACM.

FAU-Autoren / FAU-Herausgeber

Wanka, Rolf Prof. Dr.
Professur für Informatik (Effiziente Algorithmen und Kombinatorische Optimierung)


Kutylowski, M., Lorys, K., Oesterdiekhoff, B., & Wanka, R. (2000). Periodification scheme: Constructing sorting networks with constant period. Journal of the Acm, 47(5), 944-967.

Kutylowski, Miroslaw, et al. "Periodification scheme: Constructing sorting networks with constant period." Journal of the Acm 47.5 (2000): 944-967.


Zuletzt aktualisiert 2018-05-08 um 22:23