Parellellize使用CUDA的氣泡排序

Question

我被賦予了一項任務，並行化Bubble Sort並使用CUDA實現它。 我不明白泡沫排序可能會如何並行化。我認爲它本身就是連續的。因爲它會比較兩個連續的元素，並在條件分支之後交換它們。 想法，任何人？

Answer 1

說實話，我很難想出一種並行化泡沫排序的方法。我最初想到了一種可以平鋪的混合排序，對每個拼貼進行冒泡排序，然後合併（如果可以使其工作，可能還會提高性能）。但是，我瀏覽了「並行氣泡排序」，發現this page。如果向下滾動，你會發現下面的並行冒泡排序算法：

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 

您可以運行在CPU中的for循環和再使用內核爲每個do in parallel S的。這對於大型數組似乎很有效，但對於小型數組可能會造成太多的開銷。如果您正在編寫CUDA實現，則會假定大數組。由於這些內核中的交換與相鄰的元素對交換，因此您應該可以相應地進行平鋪。我搜索了通用的，非gpu特定的並行氣泡排序，這是我能找到的唯一一個。

我確實發現了一個（非常輕微）helpful visualization here，可以在下面看到。我很樂意在評論中進一步討論這個問題。

編輯：我發現氣泡的另一個平行版本的排序稱爲Cocktail Shaker Sort。下面是僞代碼：

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 

它看起來像這樣也有兩個for循環比較相鄰元素氣泡。這些算法看起來有點像類似的對立面，因爲第一算法（我現在已經學會叫odd-even sort ）假定已排序並讓for循環指定false，而雞尾酒調諧器排序有條件地檢查每個循環中的排序順序。

本帖子中包含的代碼odd-even sort似乎只是運行while循環足夠多的時間來保證排序，在wikipedia僞代碼檢查。一個潛在的第一遍可能是實現這個帖子的算法，然後用這個檢查進行優化，雖然CUDA實際上可能會降低檢查速度。

無論排序會緩慢。這裏有一個related SO question fyi，但沒有太多的幫助。他們同意它對小陣列無效，並且真的強調它的失敗。

您是否正在尋找特定的CUDA代碼或者是否夠用？您似乎希望對可能的選項進行概述並瞭解CUDA實現。