CUDA: reduction or atomic operations?

algorithm matrix cuda reduction gpu-atomics
Marco A. picture Marco A. · May 7, 2011 · Viewed 9.1k times · Source

I'm writing a CUDA kernel which involves calculating the maximum value on a given matrix and I'm evaluating possibilities. The best way I could find is:

Forcing every thread to store a value in the shared memory and using a reduction algorithm after that to determine the maximum (pro: minimum divergence cons: shared memory is limited to 48Kb on 2.0 devices)

I couldn't use atomic operations because there are both a reading and a writing operation, so threads could not be synchronized by synchthreads.

Any other idea come into your mind?

Answer

peakxu picture peakxu · May 9, 2011

You may also want to use the reduction routines that comes w/ CUDA Thrust which is a part of CUDA 4.0 or available here.

The library is written by a pair of nVidia engineers and compares favorably with heavily hand optimized code. I believe there is also some auto-tuning of grid/block size going on.

You can interface with your own kernel easily by wrapping your raw device pointers.

This is strictly from a rapid integration point of view. For the theory, see tkerwin's answer.

Related questions

How do you rotate a two dimensional array?

Inspired by Raymond Chen's post, say you have a 4x4 two dimensional array, write a function that rotates it 90 degrees. Raymond links to a solution in pseudo code, but I'd like to see some real world stuff. [1][2][3][4] [5][6][7][8] [9][0][1][2] [3][4][5][6] Becomes: [3][9][5][1] [4][0][6][2] [5][1][7][3] [6][2][8][4] Update: Nick's …

Read More
Python Inverse of a Matrix

How do I get the inverse of a matrix in python? I've implemented it myself, but it's pure python, and I suspect there are faster modules out there to do it.

Read More
What is the fastest way to transpose a matrix in C++?

I have a matrix (relatively big) that I need to transpose. For example assume that my matrix is a b c d e f g h i j k l m n o p q r I want the result …

Read More