Bal*_*laK 1 sorting algorithm cuda
我得到了一个任务,并行化冒泡排序并使用CUDA实现它.我不知道冒泡排序怎么可能并行化.我认为它本身就是顺序的.因为,它比较了两个连续的元素,并在条件分支之后交换它们.思绪,有人吗?
说实话,我也很难想出一种并行化冒泡排序的方法.我最初想到的是混合排序,你可以平铺,冒泡排序每个拼贴,然后合并(如果你能使它工作,可能仍会提高性能).但是,我浏览了"Parallel Bubble Sort",并找到了这个页面.如果向下滚动,您将找到以下并行冒泡排序算法:
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
Run Code Online (Sandbox Code Playgroud)
您可以在CPU中运行for循环,然后为每个do in parallel
s 使用内核.这对于大型数组似乎很有效,但对于小型数组而言可能过多.如果您正在编写CUDA实现,则假定使用大型数组.由于这些内核中的交换具有相邻的元素对,因此您应该能够相应地进行切片.我搜索了泛型,非gpu特定的并行气泡排序,这是我能找到的唯一一个.
我确实在这里找到了一个(非常轻微)有用的可视化,可以在下面看到.我想在评论中更多地讨论这个问题.
编辑:我发现另一个名为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
Run Code Online (Sandbox Code Playgroud)
看起来这也有两个for循环比较相邻的元素起泡 ..这些算法看起来有点像相似的对立面,因为第一个算法(我现在学到的叫做奇偶排序)假定排序并让for循环指定false,而鸡尾酒调酒器排序有条件地检查在每个循环中排序.
这篇文章中包含的代码odd-even sort
似乎只是运行while循环足以保证排序,维基百科伪代码检查.潜在的第一遍可能是实现这篇文章的算法,然后用检查进行优化,尽管使用CUDA检查实际上可能会更慢.
无论那种排序都会很慢.这是一个相关的SO问题,但没有太多帮助.他们认为它对小阵列无效,并且真正强调它的失败.
您在寻找特定的CUDA代码还是这样?您似乎想要了解可能的选项并了解CUDA实现.