I am implementing an algorithm on GPU. The scatter version of the algorithm uses atomic token extensively, distributing N^2*h*w values on N^4 output location where N ranges from 5-40. The conversion to gather algorithm was expected to speedup the solution as a result of removing atomic token. Anyone has some clarifications?
First off, today's GPUs have atomic operations implemented much more optimally than the ones 6+ years older - such as were used in the linked materials above. So it might be difficult to say how much you can rely on the specific results in there (but of course the general principles apply still).
In my experience, it doesn't quite matter how many values your kernel distributes, but rather in what kind of pattern is this happening. If the output pattern is predictably coherent, it should be as fast, and maybe even faster than a gather algorithm, depending on how much costlier would the algorithm re-formulation be.
On the other hand, if the write pattern is random, and worse, there can be collisions in that different threads will write into same memory banks, then you can expect much slower performance of the scatter version. But this of course still depends - if the computations are very arithmetically intensive, and then in the end you just output the results, that still can be fine.
I would recommend you to use various parameters and perhaps you may find both algorithms could work equally well.
probably it may work. you can go through:
http://www.cse.ust.hk/catalac/papers/scatter_sc07.pdf
Dear Ahmed Hassan Yousef
I sent you link.
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter32.html
http://hiperfit.dk/pdf/marco-eilers-thesis.pdf
Regards, Shafagat
First off, today's GPUs have atomic operations implemented much more optimally than the ones 6+ years older - such as were used in the linked materials above. So it might be difficult to say how much you can rely on the specific results in there (but of course the general principles apply still).
In my experience, it doesn't quite matter how many values your kernel distributes, but rather in what kind of pattern is this happening. If the output pattern is predictably coherent, it should be as fast, and maybe even faster than a gather algorithm, depending on how much costlier would the algorithm re-formulation be.
On the other hand, if the write pattern is random, and worse, there can be collisions in that different threads will write into same memory banks, then you can expect much slower performance of the scatter version. But this of course still depends - if the computations are very arithmetically intensive, and then in the end you just output the results, that still can be fine.
It seems odd that scatter requires atomic operations while gather doesn't. I'd say scatter and gather are rather complementary...
As said before, these 2 operations are closely related,but the overall performance depends on many factors:
1) are these operations immediately followed by a barrier?
2) pattern of distribution: it guarantees unique distribution (no collision or how the collisions are solved?) ? Even no-collision pattern can lead to false-sharing behaviour.
3) this operation is done by a) only one warp b) one thread block c) all threads?
4) what are typical values of w and h?
5) are items only stored or there is some operation (e.g., ADD) ?
6) what is sizeof(item) ?
7) how the conversion works? empty matrix+SCATTER+normal matrix addressing => all "writes" into temporal array, preproccessing(sorting), access to this temporal array?
For fast algorithms on the GPU you need so-called coalesced memory access. Threads should access neighboring values in memory. This is independent of scatter and gather.
In general, atomic operations will always slow down your algorithms. Any sort of synchronization slows down your algorithm. But, with atomic scatter operations you definitely loose parallel memory access on writes. The gather algorithm can only become faster than the scatter version if you can make use of parallel memory access. If, however, memory access is serialized because of bad patterns (as Oskar already mentioned), you cannot gain more performance. Usually, the gather algorithm will be faster. But finally, this depends on how much work can actually be done in parallel. (Since it seems that you don't really use the parallelism of the GPU, have you tried implementing the scatter algorithm on the CPU? This could actually be faster because of higher clock frequencies.)
It's worth noting that writes are often faster, in general, simply because they can be posted. That means that the pipeline can advance as soon as the write is delivered to a write buffer, even though it make take further time to propagate to its final location/state. Write buffers/queues are often not well-documented in any ISA, since they're not really programmer-visible.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms