<p>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 <a href="http://en.wikipedia.org/wiki/Hype_cycle" rel="nofollow noreferrer">Gartner hype curve</a>. </p>

<p>a possibly helpful paradigm for understanding the GPU role in parallel computing is the Berkeley framework of 7 "dwarves" &amp; 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.</p>

<p>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.</p>

<ul>
<li><p><a href="https://scicomp.stackexchange.com/questions/943/what-kinds-of-problems-lend-themselves-well-to-gpu-computing">what kind of problems lend themselves well to gpu computing?</a> scicomp.se</p></li>
<li><p><a href="http://geomblog.blogspot.com/2013/05/on-gpu-algorithms.html" rel="nofollow noreferrer">on GPU algorithms (wrt TCS community)</a> Suresh Venkatasubramanian (tcs.se mod) &amp; commentary by other researchers</p></li>
<li><p><a href="http://www.cs.virginia.edu/kim/docs/ispass11.pdf" rel="nofollow noreferrer">Where is the Data? Why You Cannot Debate CPU vs. GPU Performance Without the Answer</a> Gregg / Hazel</p></li>
<li><p><a href="https://www.princeton.edu/~dlustig/dlustig_HPCA13.pdf" rel="nofollow noreferrer">Reducing GPU Offload Latency via Fine-Grained CPU-GPU Synchronization</a> Lustig/ Martonosi</p></li>
<li><p><a href="https://stackoverflow.com/questions/6500905/techniques-to-reduce-cpu-to-gpu-data-transfer-latency">techniques to reduce cpu to gpu data transfer latency</a> stackoverflow</p></li>
<li><p><a href="http://www.cs.virginia.edu/~mwb7w/cuda_support/memory_transfer_overhead.html" rel="nofollow noreferrer">CUDA memory transfer overhead</a></p></li>
<li><p><a href="http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html" rel="nofollow noreferrer">The Landscape of Parallel Computing Research: A View from Berkeley</a></p></li>
</ul>

CC BY-SA 3.0
2014-12-15T03:48:44.517Z
addendum. GPUs seem to hold a lot of promise in the area of deep learning based on very recent research by [Ng](http://www.wired.com/2013/06/andrew_ng/) eg [Deep learning with COTS HPC systems](http://cs.stanford.edu/people/ang/?portfolio=deep-learning-with-cots-hpc-systems) / Coates et al. also [CUDA](http://en.wikipedia.org/wiki/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).
vzn
CC BY-SA 3.0
2014-12-13T16:56:51.643Z
2014-12-13T16:56:51.643Z
2017-05-23T12:40:09.333Z
vzn
<p>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.</p>

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

<p>Is it because that is too difficult to do or not very interesting?</p>

CC BY-SA 3.0
2014-12-12T16:10:57.920Z
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](http://geomblog.blogspot.com/2013/05/on-gpu-algorithms.html)
vzn
CC BY-SA 3.0
2014-12-13T19:20:36.590Z
interesting read, coincidentally I was reading the blog post suresh is quoting the other day and was wondering the same thing.
ksm001
<machine-models><analysis-of-algorithms>
What is the state of the art research in analysing algorithms on GPU architectures?
ksm001
# What is the state of the art research in analysing algorithms on GPU architectures?

(Asked by: username_0 on 2014-12-12)

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?

**Tags:** machine-models, analysis-of-algorithms

> **Comments:**
> **username_1**: 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](http://geomblog.blogspot.com/2013/05/on-gpu-algorithms.html)  
> **username_0**: interesting read, coincidentally I was reading the blog post suresh is quoting the other day and was wondering the same thing.  

---

## 1 answers

### Answer by username_1 on 2014-12-13. Score: 2 | Accepted answer

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](http://en.wikipedia.org/wiki/Hype_cycle).

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.

* [what kind of problems lend themselves well to gpu computing?](https://scicomp.stackexchange.com/questions/943/what-kinds-of-problems-lend-themselves-well-to-gpu-computing) scicomp.se
* [on GPU algorithms (wrt TCS community)](http://geomblog.blogspot.com/2013/05/on-gpu-algorithms.html) Suresh Venkatasubramanian (tcs.se mod) & commentary by other researchers
* [Where is the Data? Why You Cannot Debate CPU vs. GPU Performance Without the Answer](http://www.cs.virginia.edu/kim/docs/ispass11.pdf) Gregg / Hazel
* [Reducing GPU Offload Latency via Fine-Grained CPU-GPU Synchronization](https://www.princeton.edu/~dlustig/dlustig_HPCA13.pdf) Lustig/ Martonosi
* [techniques to reduce cpu to gpu data transfer latency](https://stackoverflow.com/questions/6500905/techniques-to-reduce-cpu-to-gpu-data-transfer-latency) stackoverflow
* [CUDA memory transfer overhead](http://www.cs.virginia.edu/~mwb7w/cuda_support/memory_transfer_overhead.html)
* [The Landscape of Parallel Computing Research: A View from Berkeley](http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.html)

> **Comments:**
> **username_1**: addendum. GPUs seem to hold a lot of promise in the area of deep learning based on very recent research by [Ng](http://www.wired.com/2013/06/andrew_ng/) eg [Deep learning with COTS HPC systems](http://cs.stanford.edu/people/ang/?portfolio=deep-learning-with-cots-hpc-systems) / Coates et al. also [CUDA](http://en.wikipedia.org/wiki/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).  

---

