Implementation of a vectorized Quicksort using AVX-512 intrinsics

Abstract

Jahrzehntelang wurden Verbesserungen der Rechengeschwindigkeit erreicht, indem die Taktfrequenz der CPU erhöht wurde. Im Laufe der letzten Jahre wurde dieser Mechanismus durch physikalische Einflüsse gebremst. Daher müssen moderne Single-Thread-Anwendungen stärker 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 Länge 32 bit. Die Nutzung von Vektorinstruktionen für die Sortierung ist eine Herausforderung, da Sortieralgorithmen erst vektorisierungsfreundlich umgestaltet werden müssen. Glücklicherweise 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 schlägt 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 übertreffen.