I have found many papers on sequential algorithms that have been implemented and tested on GPU architectures. Each of these papers usually as a result contains the amount of speedup that was achieved when using a specific GPU.

However I could not find a lot of papers on theoretically analysing algorithms, proving bounds etc when working in this new model.

Is it because that is too difficult to do or not very interesting?

  • $\begingroup$ there is some research. have been collecting a few links/ refs on this subj. gpus have generally not turned out to be a scalable alternative for many problems because theres a huge issue/ overhead of transferring data to and from the gpu. see eg suresh blog notes $\endgroup$
    – vzn
    Dec 12, 2014 at 16:10
  • $\begingroup$ interesting read, coincidentally I was reading the blog post suresh is quoting the other day and was wondering the same thing. $\endgroup$
    – ksm001
    Dec 13, 2014 at 19:20

1 Answer 1


research into GPU algorithms continues and it is well suited to some problems, but some of the initial excitement may be wearing off after lackluster results and difficulty of translating problems into GPU approaches. also in recent times there is some consternation over transfer overhead to/ from the GPU. from anecdotal/ background stories/ conversations shared by some physics researchers, some universities (eg specializing in supercomputing) spent significant money on GPU clusters which are not largely utilized (eg in physics simulations contexts?), but what factor that may be due to is not clear. a forthright appraisal might observe that historically GPU companies might have overhyped the potential somewhat akin to the Gartner hype curve.

a possibly helpful paradigm for understanding the GPU role in parallel computing is the Berkeley framework of 7 "dwarves" & there is some brief mention of GPU there. another recent success story, at one point GPUs for a time period/ window were heavily used in bitcoin mining, but they are now almost entirely eclipsed by custom ASIC solutions.

from the theoretical pov there may not be so much interest due to that they are to some degree "just a hardware implementation detail" and possibly at best leading to linear speedups (albeit for sizeable/ worthwhile constants) even with ingenious implementations.

  • $\begingroup$ addendum. GPUs seem to hold a lot of promise in the area of deep learning based on very recent research by Ng eg Deep learning with COTS HPC systems / Coates et al. also CUDA was initially thought to be the solution to many programmability problems and it does indeed help a lot (esp vs no programmability alternative) but it does not decrease sometimes major human-based programming overhead (automatic translation mostly unavailable). $\endgroup$
    – vzn
    Dec 15, 2014 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.