algorithm - 使用 CUDA 并行冒泡排序

Question

我接到了一项任务，要并行化冒泡排序并使用 CUDA 实现它。
我看不出如何并行化冒泡排序。我认为它本质上是顺序的。因为，它比较两个连续的元素并在条件分支后交换它们。
有想法吗？

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 循环 bubbly.. 这些算法看起来有点像相似的对立面，因为第一个算法(我现在学习的是 odd-even sort )假定排序并让 for 循环指定 false，而 cocktail shaker 排序有条件地检查每个循环中的排序。

这篇文章中包含的用于奇偶排序 的代码似乎只是运行 while 循环足够的时间来保证排序，维基百科伪代码检查的地方。潜在的第一步可能是实现这篇文章的算法，然后使用检查进行优化，尽管使用 CUDA 检查实际上可能更慢。

无论如何排序都会很慢。这是一个 related SO question仅供引用，但没有太多帮助。他们同意它对小型阵列无效，并且非常强调它的失败。

您是在寻找特定的 CUDA 代码还是这就足够了？您似乎想要了解可能的选项并了解 CUDA 实现。