Prescan, Prefix Sum Algorithm

Accelerated Computing CUDA CUDA Programming and Performance
1

I’m trying to understand on how does the Prefix Sum works on Cuda…

What does this mean?

for (int d = n>>1; d > 0; d >>= 1)

Thanks

2

is just the right shift operator–look up two’s complement representation of integers if you’re confused.

3

Ok, I’ve read what you meant by two’s complement representation…

e.g.

1100

(negative) 2^2 (1) + 2^1 (0) + 2^0 (0) = -4

But I still don’t get on what it mean by being “shifted”? How does it shifted? Any examples…?

Also, what is the difference between >> and >>= ?

Thanks

4

is right shift.

For example, if d is 30, the binary representation of that is 11110. Right shifting by 1 (30 >> 1) gives a binary representation of 1111 (equivalent to 15). Note that this is the same as dividing the number by 2.

= is right shift and assign (so if d is 30, then d >>= 1 leaves d with a value of 15).

5

Thanks a lot!!