Gibt es Algorithmus zum Sortieren von Saiten für die GPU?

Question

Array, um zu sortieren, hat ungefähr eine Million Saiten, in denen jede Zeichenfolge eine Länge von bis zu einer Million Zeichen aufweisen kann.

Ich suche nach einer Umsetzung des Sortieralgorithmus für GPU.

Ich habe einen Datenblock mit einer Größe von ca. 1 MB und ich muss konstruieren Suffix Array .Jetzt können Sie sehen, wie es möglich ist, eine Million Saiten in einem wirklich geringen Speicherplatz zu haben.

Answer 1

Der Stand der Technik in der GPU-Sortierung ist nicht besonders ermutigend.

Zum Sortieren von 32-Bit-Ganzzahlen das folgende Papier von 2009 (mit 2 Autoren, die in NVIDIA sind) nur 23% auf die beste CUTA-Sortierung auf GTX280 im Vergleich zu der besten CPU-Sortierung auf einem 4-Core Yorkfield.

http://www.mgarland.org/files/papers/gpuort -IPDPS09.pdf

Dies verwendete eine Radix-Sortierung auf der GPU und sortieren Sie die Sorte auf der CPU. Sie brauchen eine Vergleichs-Sortierung, um ein Suffix-Array zu erstellen, so dass anstelle von GPU Radix sortiert, dass das Beste derjenigen in der Zeitung die GPU-Merge-Sorte sein würde, die etwa die Hälfte der Geschwindigkeit der GPU-Radix-Sortierung erreichte (mit 1 Million Tasten) - dh etwa 40% langsamer als die CPU-Merge-Sortierung.

Das Hinzufügen von Schlüsseln mit variabler Länge scheint wahrscheinlich Threads in einem Warp zu verursachen, wechselt die Synchronisierung auf einer GPU, sodass die Leistung auf der GPU mehr als CPU verringert wird.

Insgesamt, wenn Ihr Zweck ein effizientes System aufbauen soll, würde ich empfehlen, dass Sie eine CPU-Implementierung für dieses Problem verwenden, da er schneller und einfacher ist, um zu schreiben.

aber, wenn Ihr Zweck experimentieren soll oder nur um eine GPU zu erfahren, dann finden Sie die CUDA-Implementierung von Merge-Sortierung aus dem Papier in der Cuda SDK:

http://developer.download.nvidia .com / compute / cuda / sdk / website / data-parallel_algorithmen.html