3 ms·
Some GPU based methods are faster when they rely on raw parallel processing power, even if it caused a huge amount of work to be discarded. These chips are well
by gmueckl 9y ago
Some GPU based methods are faster when they rely on raw parallel processing power, even if it caused a huge amount of work to be discarded. These chips are well suited for regular, embarassingly parallel, dumb work. This starts to drop sharply with increasing branching and the amount of unordered memory accesses, although GPUs get better and better at that. So it can be better right now to do the dumb thing instead of the smart thing.
I think that sorting on the GPU is a good example: a parallel quicksort is hard to implement and maps badly to GPU threads. A bitonic sort algorithm is likely to be much faster, although it is a very dumb algorithm.
- epberry 9y agoInteresting, I wasn't familiar with bitonic sorting.
- Coding_Cat 9y agoIn general, all algorithms seem to get pushed more and more towards "optimize for memory access" than actually optimizing for computations. GPUs are no exception. Personally, I wonder more what effect widespread HBM (with speeds realistically expressed in TB/s for future iterations) will have on the algorithms we design.
- gmueckl 9y agoWell, GPUs expose the memory hierarchy to the programmer and have atrocious latency when hitting global memory with unordered memory access patterns. Your only chance to make a GPU outperform a CPU is to design your algorithm completely around memory usage. The difference between doing it right and wrong can be several orders of magnitude. Even CPUs show huge performance gains when all the algorithm's data fits in the cache. This can easily be a factor 10 or more when you get it right.