Parellellize Blasensortierung mit CUDA

Question

Ich hatte eine Aufgabe, Bubble Sort zu parallelisieren und mit CUDA zu implementieren. Ich sehe nicht, wie Blasensortierung möglicherweise parallelisiert werden könnte. Ich denke, es ist in sich sequenziell. Da werden zwei aufeinanderfolgende Elemente verglichen und nach einer bedingten Verzweigung ausgetauscht. Gedanken, irgendjemand?

Answer 1

Um ganz ehrlich zu sein, hatte ich Probleme, über eine Möglichkeit zu Parallelisieren Bubble-Sort als auch denken. Ich dachte zuerst an eine hybride Sortierung, bei der man die Kacheln kacheln, bubble sortieren und dann verschmelzen konnte (wahrscheinlich würde es die Performance noch verbessern, wenn man es zum Laufen bringen könnte). Ich habe jedoch nach "Parallel Bubble Sort" gesucht und this page gefunden. Wenn Sie nach unten scrollen werden Sie den folgenden parallel Blase Sortieralgorithmus finden:

For k = 0 to n-2 
If k is even then 
    for i = 0 to (n/2)-1 do in parallel 
     If A[2i] > A[2i+1] then 
      Exchange A[2i] ↔ A[2i+1] 
Else 
    for i = 0 to (n/2)-2 do in parallel 
     If A[2i+1] > A[2i+2] then 
      Exchange A[2i+1] ↔ A[2i+2] 
Next k 

Sie könnten die for-Schleife in der CPU laufen und dann einen Kernel für jede der do in parallel s verwenden. Dies scheint für große Arrays effizient zu sein, könnte jedoch bei kleinen Arrays zu viel Overhead sein. Wenn Sie eine CUDA-Implementierung schreiben, werden große Arrays vorausgesetzt. Da die Swaps in diesen Kernen mit benachbarten Elementpaaren verbunden sind, sollten Sie in der Lage sein, entsprechend zu kacheln. Ich habe nach generischen, nicht-GPU-spezifischen parallelen Blasensorten gesucht und dies war die einzige, die ich finden konnte.

Ich fand eine (sehr leicht) helpful visualization here, die unten zu sehen ist. Ich würde gerne mehr darüber in den Kommentaren diskutieren.

EDIT: ich eine andere parallele Version der Blase gefunden Art Cocktail Shaker Sort genannt. Hier ist der Pseudo-Code:

procedure cocktailShakerSort(A : list of sortable items) defined as: 
    do 
    swapped := false 
    for each i in 0 to length(A) - 2 do: 
     if A[ i ] > A[ i + 1 ] then // test whether the two elements are in the wrong order 
     swap(A[ i ], A[ i + 1 ]) // let the two elements change places 
     swapped := true 
     end if 
    end for 
    if not swapped then 
     // we can exit the outer loop here if no swaps occurred. 
     break do-while loop 
    end if 
    swapped := false 
    for each i in length(A) - 2 to 0 do: 
     if A[ i ] > A[ i + 1 ] then 
     swap(A[ i ], A[ i + 1 ]) 
     swapped := true 
     end if 
    end for 
    while swapped // if no elements have been swapped, then the list is sorted 
end procedure 

Es sieht wie folgt aus auch zwei for-Schleifen Vergleich benachbarter Elemente sprudelnde .. Diese Algorithmen aussehen wie eine Art ähnlich Gegensätze, da der erste Algorithmus (was ich jetzt gelernt odd-even sort genannt wird) nimmt sortierte an und lässt die for-Schleifen falsch spezifizieren, während die Cocktail-Shaker-Sortierung bedingt in jeder Schleife sortiert prüft.

Der Code in diesem Beitrag für die odd-even sort scheint einfach die while-Schleife zu laufen genug, um sortierte zu garantieren, wo der Wikipedia Pseudocode überprüft. Ein möglicher First-Pass könnte darin bestehen, den Algorithmus dieses Posts zu implementieren und dann mit der Überprüfung zu optimieren, obwohl die Überprüfung mit CUDA tatsächlich langsamer sein kann.

Unabhängig von der Art wird langsam sein. Hier ist ein related SO question fyi, aber es gibt nicht viel Hilfe. Sie sind sich einig, dass es für kleine Arrays nicht effektiv ist, und betonen wirklich sein Versagen.

Suchen Sie einen bestimmten CUDA-Code oder war das genug? Es scheint, als wollten Sie einen Überblick über mögliche Optionen und verstehen die CUDA-Implementierung.