Can this GPU code snippet be redone without nested loops?

Hello, I have two matrices: matrix1 is a logical array of 1s and 0s (1000 x 800) matrix2 is a different logical array (2000 x 800)

I am essentially taking the first row of matrix 1 and calculating the row summation of common elements / total number of elements. Both of these arrays are gpuArrays. What I finding out:

for j=gpuArray.colon(1,x)
for k=gpuArray.colon(1,y)
   output(j,k)=sum(matrix1(j,:) & matrix2(k,:)) / sum(matrix1(j,:) | matrix2(k,:))
end
end

Runs very fast for small values of x and y, but once x,y is large is takes exponentially longer to run on the GPU

I am investigating the use of repmat here but I am not sure how to implement. Any ideas here? Or if there is another option for to get rid of the nested for loops?

Thanks

Answer 1

[Joss Knight]

The GPU isn't going to work well with your nested loops. This looks like a classic case for bsxfun:

matrix1 = permute(matrix1, [1 3 2]);
matrix2 = permute(matrix2, [3 1 2]);
output = sum( bsxfun(@and, matrix1, matrix2), 3 ) ./ ...
         sum( bsxfun(@or, matrix1, matrix2), 3);

I can't promise it will run faster than on your CPU though, if you have a lot of cores.

[Amr Ragab]

So what is it about the permute function that through reordering the array and the bsxfun that makes this so fast?

[Jill Reese]

Amr, the original code was processing fewer elements at once. When Joss mentioned that "The GPU isn't going to work well with your nested loops.", he was referring to the fact that the GPU wasn't being provided enough work to keep it busy.

[Joss Knight]

Yes, with the loop the GPU is being asked to do thousands of very small computations in series - entirely the opposite of what it's good at. Instead we created 1000x2000x800 arrays containing all possible and and or combinations (using bsxfun) and then summed along the 3rd dimension to reduce down to the 1000x2000 matrix you were after.

Answer 2

[Sean de Wolski]

Is output preallocated?

Before the loops:

output = gpuArray.zeros(x,y);

This should speed it up dramatically.

[Amr Ragab]

Oh yes - I did that, it improved it a little but still pretty slow. About 500 rows takes 60 seconds (NVIDIA TITAN 6GB)

[Sean de Wolski]

Do matrix1 and matrix2 already live on the gpu, i.e. are they gpuArrays?

[Amr Ragab]

Yes they live on the gpu as gpuArrays. Its all transferred over before this code snippet