Access Restriction

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(<n})•$ log $\textit{n}),$ and has layout area $\textit{O(A(n)})$ • $\textit{T(n})).$ In particular, applying this scheme to Batcher's algorithms, we get practical period 5 comparator networks that sort in time $\textit{O}(log3\textit{n}).$ For theoretical interest, one may use the AKS netork resulting in a period 5 comparator network with runtime $\textit{O}(log2\textit{n}).$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2000-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 47
Issue Number 5
Page Count 24
Starting Page 944
Ending Page 967

Open content in new tab

   Open content in new tab
Source: ACM Digital Library