GPU‑beschleunigte Sortieralgorithmen erreichen bis zu 103‑fachen Speedup

Forscher haben die Ausführung von fünf klassischen Sortierverfahren auf einer modernen GPU mit CUDA untersucht und dabei im Vergleich zu sequenziellen CPU‑Implementierungen Speedups von bis zu 103‑fach erreicht.

Methodik

Die Studie implementierte Merge Sort, Quick Sort, Bubble Sort, Radix‑Top‑K‑Selection Sort und Slow Sort für die parallele Ausführung auf einer einzelnen GPU. Die Messungen umfassten Laufzeit und Speicherbedarf bei vier unterschiedlichen Datensätzen: zufällig generierte Werte, umgekehrt sortierte Reihen, bereits sortierte Reihen und nahezu sortierte Reihen.

Radix‑Sort

Beim Sortieren von 10 Millionen zufälligen Elementen benötigte die GPU‑Version 4,83 ms, während die sequenzielle CPU‑Variante 240,8 ms dauerte – ein Speedup von etwa 50‑fach.

Quick‑ und Merge‑Sort

Quick Sort verkürzte die Laufzeit von 1 461,97 ms auf 15,1 ms (≈ 97‑fach), und Merge Sort reduzierte 2 212,33 ms auf 21,4 ms (≈ 103‑fach).

Bubble‑Sort

Obwohl Bubble Sort eine Beschleunigung von rund 17‑fach (von 123 321,9 ms auf 7 377,8 ms) erzielte, blieb die absolute Laufzeit im Vergleich zu den anderen Algorithmen deutlich höher.

Slow‑Sort

Slow Sort zeigte eine moderate, aber konsistente Beschleunigung von etwa 18,6‑fach (74,07 ms → 3,99 ms).

Vergleich zu früheren Generationen

Frühere GPU‑Implementierungen lieferten Beschleunigungen zwischen dem 2‑ und 9‑fachen. Die aktuellen Ergebnisse übertreffen diese Werte deutlich und liegen im Bereich von 17‑bis über 100‑fach, vergleichbar mit den besten in jüngsten Fachpublikationen.

Bedeutung für die Praxis

Die Resultate belegen, dass einzelne GPUs erhebliche Leistungsgewinne für großskalige Sortieraufgaben ermöglichen, was insbesondere für datenintensive Anwendungen von Nutzen ist.

Ausblick

Weitere Optimierungen der Speicherzugriffe sowie die Skalierung auf mehrere GPUs könnten die Effizienz zusätzlich steigern.

Dieser Bericht basiert auf Informationen von PLOS ONE, lizenziert unter Creative Commons BY 4.0 (Open Access). Wissenschaftliche Inhalte, offen zugänglich.