Implementation of a vectorized Quicksort using AVX-512 intrinsics

Jahrzehntelang wurden Verbesserungen der Rechengeschwindigkeit erreicht, indem die Taktfrequenz der CPU erhoht wurde. Im Laufe der letzten Jahre wurde dieser Mechanismus durch physikalische Einflusse gebremst. Daher mussen moderne Single-Thread-Anwendungen starker CPU-Funktionen ausnutzen, um von den Fortschritten neuer Prozessorgenerationen zu profitieren. Eine dieser Funktionen ist die Vektorverarbeitung, um mehrere Datenelemente gleichzeitig zu verarbeiten. Diese Arbeit untersucht die Verwendung von AVX-512-Befehlen zur Sortierung von primitiven Typen der Lange 32 bit. Die Nutzung von Vektorinstruktionen fur die Sortierung ist eine Herausforderung, da Sortieralgorithmen erst vektorisierungsfreundlich umgestaltet werden mussen. Glucklicherweise hat Mark Blacher einen effizienten vektorisierten Sortieralgorithmus auf Basis von Sortiernetzwerken und einem nichtquadratischen Quicksort entwickelt. In dieser Arbeit wird Blachers AVX2-basierte vektorisierte Implementierung auf den moderneren AVX-512-Befehlssatz portiert. Im Geschwindigkeitsvergleich schlagt Blachers AVX2-Version die in dieser Arbeit entwickelte AVX-512-Implementierung. Diese ist jedoch in der Lage, den bisherigen AVX-512-Sortieralgorithmus von Bramas zu ubertreffen.