Bachelor Thesis BCLR-2020-58

BibliographyFischer, Alexander: Experimental study of the AKS sorting network.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis No. 58 (2020).
33 pages, english.
Abstract

Sorting networks are usually bound at a depth of O(log^2 n), since a perfect halver is of at least depth O(log n). However, the AKS Sorting Network, by Ajtai, Komlos and Szemeredi, can sort data with depth O(log n) by using so-called ε-halvers, which are of constant depth. Such ε-halvers are allowed to have some errors and will eventually be corrected by sending elements to a level above. In this thesis, a CPU and CUDA version are implemented following a paper by Vasek Chvatal and the original paper by Ajtai et al. Experiments are run on these versions to observe and improve parameters.

Full text and
other links
Volltext
Department(s)University of Stuttgart, Institute of Formal Methods in Computer Science, Theoretical Computer Science
Superviser(s)Diekert, Prof. Volker; Weiß, Armin
Entry dateJanuary 18, 2021
   Publ. Computer Science