What is the state of the art research in analysing algorithms on GPU architectures? 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?
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" &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.

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? scicomp.se
on GPU algorithms (wrt TCS community) Suresh Venkatasubramanian (tcs.se mod) &amp; commentary by other researchers
Where is the Data? Why You Cannot Debate CPU vs. GPU Performance Without the Answer Gregg / Hazel
Reducing GPU Offload Latency via Fine-Grained CPU-GPU Synchronization Lustig/ Martonosi
techniques to reduce cpu to gpu data transfer latency stackoverflow
CUDA memory transfer overhead
The Landscape of Parallel Computing Research: A View from Berkeley