Bachelorarbeit BCLR-2020-58

Fischer, Alexander: Experimental study of the AKS sorting network.
Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Bachelorarbeit Nr. 58 (2020).
33 Seiten, englisch.

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.

Volltext und
andere Links
Abteilung(en)Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
BetreuerDiekert, Prof. Volker; Weiß, Armin
Eingabedatum18. Januar 2021
   Publ. Informatik