So I've got a decent head for what problems I work with are best one in serial, and which can be managed in parallel. But right now, I don't have much of an idea of what's best handled by CPU-based computation, and what should be offloaded to a GPU.

I know its a basic question, but much of my searching gets caught in people clearly advocating for one or the other without really justifying why, or somewhat vague rules of thumb. Looking for a more useful response here.

GPU hardware has two particular strengths: raw compute (FLOPs) and memory bandwidth.  Most difficult computational problems fall into one of these two categories.  For example, dense linear algebra (A * B = C or Solve[Ax = y] or Diagonalize[A], etc) falls somewhere on the compute/memory bandwidth spectrum depending on system size.  Fast Fourier transforms (FFT) also fit this mold with high aggregate bandwidth needs.  As do other transformations, grid/mesh-based algorithms, Monte Carlo, etc.  If you look at the NVIDIA SDK code examples, you can get a feel for the sorts of problems that are most commonly addressed.   

I think the more instructive answer is to the question `What kinds of problems are GPUs really bad at?'  Most problems that don't fall into this category can be made to run on the GPU, though some take more effort than others.

Problems that don't map well are generally too small or too unpredictable.  Very small problems lack the parallelism needed to use all the threads on the GPU and/or could fit into a low-level cache on the CPU, substantially boosting CPU performance.  Unpredictable problems have too many meaningful branches, which can prevent data from efficiently streaming from GPU memory to the cores or reduce parallelism by breaking the SIMD paradigm (see 'divergent warps').  Examples of these kinds of problems include:


Most graph algorithms (too unpredictable, especially in memory-space)
Sparse linear algebra (but this is bad on the CPU too)
Small signal processing problems (FFTs smaller than 1000 points, for example)
Search
Sort 

