Reference no: EM133090134

Question: Rank Sort 

This algorithm finds the rank of each number in an array and places it in order in a second array. This isn't a good sequential algorithm (0(N2)), but there is plenty of parallelism as the iterations of the inner loop can be done independently:

function ranksort(a)
a = length(a)
b = similar(a)
for i in 1:n
idx =0
einbounds for J in 1:n
a[i] > a[J] && (idx += 1)
end
b(idx+1] = a[i]
end
return b
end

Your task is to parallelize this algorithm for CPU execution in two ways:

1. With Julia's CUDA Native programming model, replacing the inner loop with a call to a CUDA kernel. The function must include a parameter chunkSize, which is the munber of iterations assigned to each thread.

2. With Julia's CuArrays programming model, replacing the inner loop with Julia's broadcast/dot notation. To do this you'll need to write the comparison moults to a temporary array and then sum this array using the CUDA/Julia sum() function.

Test your functions for correctness and benchmark them on Mach2. Please note that the second function will give poor performance. See if you can optimize it but don't be disappointed if it's still slower than the CPU version. Test your first function with a few chunk sizes varying from 1 to 128 and for two arrays of different sizes with at least 218 floats. Don't forget to test for correctness! Compare the performance of both functions (in Maps, based on n2 + n array operations) with the performance of the sequential ranksort().

To pass in the assignment: Submit a .zip file of your source code and a single pdf document containing listings of your code and output from your testing, and submit it via D2L. Name your document LastNanefirstName A3.pdf (LastNtune and FirstName are of course substituted with your last and first name).