CUDAを使用したParellellizeバブルソート

Question

Bubble Sortを並列化してCUDAを使用して実装する割り当てが与えられました。 バブルソートを並列化する方法がわかりません。私はその本質的に逐次的だと思う。以来、2つの連続した要素を比較し、条件分岐の後にそれらを入れ替えます。 思考、誰ですか？

Answer 1

まったく正直言って、バブルソートを並列化する方法については考えがありませんでした。私は最初に、タイルを並べ替えることができ、それぞれのタイルを並べ替えてからマージするハイブリッドソートを考えました（おそらく、それを動作させることができればパフォーマンスは向上するでしょう）。しかし、私は "Parallel Bubble Sort"を閲覧し、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秒ごとにカーネルを使用することができます。これは大規模な配列では効率的ですが、小さな配列ではオーバーヘッドが大きくなる可能性があります。 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ループの隣接する要素を比較する2を持っているよう快活に見えます私は今、学んだ最初のアルゴリズムは（odd-even sortと呼ばれているので。これらのアルゴリズムは、一種の同様の正反対のように見えます）はソートを仮定し、for-loopsはfalseを指定し、cocktail shakerは条件付きでソートされたソートをソートします。

odd-even sortのこの記事に含まれるコードは、whileループを実行してソートされていることを保証しているようですが、ウィキペディアの擬似コードがチェックします。潜在的な初回通過は、このポストのアルゴリズムを実装し、チェックで最適化することができますが、実際にはCUDAではチェックが遅くなる場合があります。

これに関係なく、並べ替えは遅くなります。ここにはrelated SO question fyiがありますが、多くの助けはありません。彼らは、小さな配列に対しては効果的ではなく、本当にその失敗を強調していることに同意します。

特定のCUDAコードをお探しですか、それとも十分でしたか？可能なオプションの概要を知りたいし、CUDAの実装を理解しているようです。