Welcher parallele Sortieralgorithmus hat die beste durchschnittliche Fallleistung?

134

Das Sortieren dauert im seriellen Fall O (n log n). Wenn wir O (n) -Prozessoren haben, würden wir auf eine lineare Beschleunigung hoffen. O (log n) parallele Algorithmen existieren, aber sie haben eine sehr hohe Konstante. Sie sind auch nicht auf Standardhardware anwendbar, die nicht in der Nähe von O (n) -Prozessoren verfügt. Bei p-Prozessoren sollten vernünftige Algorithmen O (n / p log n) Zeit benötigen.

Im seriellen Fall weist die schnelle Sortierung im Durchschnitt die beste Laufzeitkomplexität auf. Ein paralleler Schnellsortieralgorithmus ist einfach zu implementieren (siehe hier und hier ). Es funktioniert jedoch nicht gut, da der allererste Schritt darin besteht, die gesamte Sammlung auf einem einzigen Kern zu partitionieren. Ich habe Informationen zu vielen parallelen Sortieralgorithmen gefunden, aber bisher habe ich nichts gesehen, was auf einen klaren Gewinner hindeutet.

Ich möchte Listen mit 1 bis 100 Millionen Elementen in einer JVM-Sprache sortieren, die auf 8 bis 32 Kernen ausgeführt wird.

Craig P. Motlin
quelle
@ Jon Alles wirklich. Dies sind meine Domänenobjekte, die alle unterschiedlich sind, aber alle Comparable implementieren.
Craig P. Motlin
1
Ich denke, Sie haben eine zu viele n / p in Ihrem "sollte nehmen"
Sparr
@ Sparr Ich glaube nicht. Ich unterscheide zwischen einigen Prozessoren und so vielen Prozessoren wie zu sortierenden Elementen.
Craig P. Motlin
@ CraigP.Motlin richtig, aber Sie scheinen das / p fälschlicherweise "verteilt" zu haben. Es sollte nur eine / p geben.
Sparr
@ Sparr Ah, das hat sich geändert, danke.
Craig P. Motlin

Antworten:

204

Der folgende Artikel (PDF-Download) ist eine vergleichende Studie zu parallelen Sortieralgorithmen auf verschiedenen Architekturen:

Parallele Sortieralgorithmen auf verschiedenen Architekturen

Laut dem Artikel, Samplesort scheint am besten Typen auf viele parallele Architektur.

Update, um Marks Altersbedenken auszuräumen:

Hier sind neuere Artikel, in denen etwas Neues vorgestellt wird (ab 2007, die übrigens immer noch mit der Beispielsorte verglichen werden):

Verbesserungen bei der Probensortierung
AA-Sortierung

Die Blutungskante (ca. 2010, einige erst ein paar Monate alt):

Paralleles Sortiermuster
Vielkernige GPU-basierte parallele Sortierung
Hybrid-CPU / GPU-Parallelsortierung
Randomisierter paralleler Sortieralgorithmus mit einer experimentellen Studie
Hoch skalierbare parallele Sortierung N-Elemente mit natürlicher Reihenfolge sortieren
: Ein neuer adaptiver Sortieransatz

Update für 2013: Hier ist der aktuelle Stand um Januar 2013. (Hinweis: Einige der Links beziehen sich auf Artikel bei Citeseer und erfordern eine kostenlose Registrierung):

Universitätsvorlesungen:
Parallele Partitionierung zum Auswählen und Sortieren
Parallele Sortieralgorithmen Vorlesung
Parallele Sortieralgorithmen Vorlesung 2
Parallele Sortieralgorithmen Vorlesung 3

Weitere Quellen und
Artikel : Ein neuartiger Sortieralgorithmus für Mehrkernarchitekturen basierend auf adaptiver bitonischer Sortierung
Hoch skalierbare parallele Sortierung 2
Paralleles Zusammenführen
parallel Zusammenführen von 2
parallelen Selbstsortiersystemen für Objekte
Leistungsvergleich von sequentiellen Schnellsortierungs- und parallelen Schnellsortieralgorithmen
Shared Memory, Message Passing und Hybrid Merge Sorts für Standalone- und Clustered-SMPs
Verschiedene parallele Algorithmen (Sorting et al.) Einschließlich Implementierungen

GPU- und CPU / GPU-Hybridquellen und -Papiere:
Eine OpenCL-Methode für parallele Sortieralgorithmen für die GPU-Architektur
Datensortierung mithilfe von Grafikverarbeitungseinheiten
Effiziente Algorithmen für die Sortierung auf GPUs
Entwerfen effizienter Sortieralgorithmen für viele Kern-GPUs
Deterministische Stichprobensortierung für GPUs
Schnelle Sortierung vor Ort mit CUDA basierend auf bitonischer Sortierung
Schnelle parallele GPU-Sortierung mit einem Hybridalgorithmus
Schnelle parallele Sortieralgorithmen auf GPUs
Schnelle Sortierung auf CPUs und GPUs: Ein Fall für bandbreitenunabhängige SIMD-Sortierung
GPU-Beispielsortierung
GPU-ABiSort: Optimale parallele Sortierung auf Stream-Architekturen
GPUTeraSort: hoch Performance-Grafik-Co-Prozessor-Sortierung für die Verwaltung großer Datenbanken
Hochleistungsvergleichsbasierter
Sortieralgorithmus für Mehrkern-GPUs Parallele externe Sortierung für CUDA-fähige GPUs mit Lastausgleich und geringem Übertragungsaufwand
Sortierung auf GPUs für große Datensätze: Ein gründlicher Vergleich

Michael Goldshteyn
quelle
2
Es handelt sich um eine vergleichende Studie zu parallelen Sortieralgorithmen für verschiedene Architekturen, die 1996 aktuell waren. Seitdem hat sich beim parallelen Rechnen viel geändert.
High Performance Mark
1
Anscheinend haben Sie verpasst, was meiner Meinung nach das Beste von allem ist: Effiziente Implementierung der Sortierung in einer Multi-Core-SIMD-Architektur. Aus der Intel-Forschung, vorgestellt auf der VLDB 2008.
Alecco
1
Dies wäre einmal eine großartige Antwort gewesen. Jetzt sind die meisten Links defekt.
Tim Long
6

Ich habe sowohl mit einem Parallel Quicksort-Algorithmus als auch mit einem PSRS-Algorithmus gearbeitet, der Quicksort im Wesentlichen parallel zum Zusammenführen kombiniert.

Mit dem Parallel Quicksort-Algorithmus habe ich eine nahezu lineare Beschleunigung mit bis zu 4 Kernen (Dual Core mit Hyper-Threading) demonstriert, was angesichts der Einschränkungen des Algorithmus zu erwarten ist. Ein reiner paralleler Quicksort basiert auf einer gemeinsam genutzten Stapelressource, die zu Konflikten zwischen Threads führt und somit den Leistungsgewinn verringert. Der Vorteil dieses Algorithmus besteht darin, dass er "an Ort und Stelle" sortiert wird, wodurch der benötigte Speicherplatz reduziert wird. Möglicherweise möchten Sie dies berücksichtigen, wenn Sie wie angegeben über 100 Millionen Elemente sortieren.

Ich sehe, Sie möchten auf einem System mit 8-32 Kernen sortieren. Der PSRS-Algorithmus vermeidet Konflikte mit der gemeinsam genutzten Ressource und ermöglicht eine Beschleunigung bei einer höheren Anzahl von Prozessen. Ich habe den Algorithmus mit bis zu 4 Kernen wie oben demonstriert, aber experimentelle Ergebnisse anderer berichten von einer nahezu linearen Beschleunigung mit einer viel größeren Anzahl von Kernen, 32 und darüber hinaus. Der Nachteil des PSRS-Algorithmus besteht darin, dass er nicht vorhanden ist und erheblich mehr Speicher benötigt.

Wenn Sie interessiert sind, können Sie meinen Java-Code für jeden dieser Algorithmen verwenden oder lesen. Sie finden es auf github: https://github.com/broadbear/sort . Der Code ist als Ersatz für Java Collections.sort () gedacht. Wenn Sie nach der Möglichkeit suchen, eine parallele Sortierung in einer JVM durchzuführen, wie oben angegeben, kann Ihnen der Code in meinem Repo helfen. Die API ist vollständig generiert für Elemente, die Comparable implementieren oder Ihren eigenen Comparator implementieren.

Darf ich fragen, wonach Sie suchen, um so viele Elemente zu sortieren? Ich bin interessiert an möglichen Anwendungen für mein Sortierpaket.

Broadbear
quelle
Ich habe einen 8-Kern-Prozessor. :) Jetzt habe ich das Sortieren von mehr als 40 Millionen Elementen getestet. Ich sehe keine lineare Beschleunigung, aber ich sehe einen erheblichen Leistungsgewinn gegenüber dem Standard-Sortieralgorithmus für Java 8-Sammlungen, bei dem es sich angeblich um einen Timsort mit mehreren Threads handelt. Meine PSRS-Implementierung sortiert 40 Millionen Elemente in durchschnittlich 4985 ms, verglichen mit 19759 ms für den Standard-JDK-Sortieralgorithmus.
Broadbear