Skip to content

Instantly share code, notes, and snippets.

@kose-y
Created August 7, 2020 01:48
Show Gist options
  • Save kose-y/fb2b223faf064a7615cd987aed1835a3 to your computer and use it in GitHub Desktop.
Save kose-y/fb2b223faf064a7615cd987aed1835a3 to your computer and use it in GitHub Desktop.
CUDA merge sort with Julia
using CUDA
function gpu_bottomUpMerge!(source, dest, first, middle, last)
i = first
j = middle
for k = first:last
if i < middle && (j > last || source[i] < source[j])
dest[k] = source[i]
i += 1
else
dest[k] = source[j]
j += 1
end
end
end
function gpu_mergesort!(source, dest, size, width, slices)
idx = (blockIdx().x - 1) * blockDim().x + threadIdx().x
first = width * (idx - 1) * slices + 1
for slice = 1:slices
if first > size
break
end
middle = min(first + (width >> 1), size)
last = min(first + width - 1, size)
gpu_bottomUpMerge!(source, dest, first, middle, last)
first += width
end
end
function mergesort!(data; verbose=false)
size = length(data)
data_swap = similar(data)
A = data
B = data_swap
nThreads = 512
width = 2
while width < (size << 1)
slices = size ÷ (nThreads * width) + 1
if verbose
println("mergesort - width: $width, slices: $slices, nThreads: $nThreads")
end
@cuda threads=nThreads gpu_mergesort!(A, B, size, width, slices)
A, B = B, A
width <<= 1
end
return A
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment