In broad terms, algorithms that run faster on the GPU are ones where you are doing the same type of instruction on many different data points.
An easy example to illustrate this is with matrix multiplication.
Suppose we are doing the matrix computation
$A \times B = C$
A simple CPU algorithm might look something like
//starting with C = 0
for (int i = 0; i < C_Width; i++)
{
for (int j = 0; j < C_Height; j++)
{
for (int k = 0; k < A_Width; k++)
{
for (int l = 0; l < B_Height; l++)
{
C[j, i] += A[j, k] * B[l, i];
}
}
}
}
The key thing to see here is that there are a lot of nested for loops and each step must be executed one after the other.
See a diagram of this
Notice that the calculation of each element of C does not depend on any of the other elements. So it does not matter what order the calculations are done in.
So on the GPU, these operations can be done concurrently.
A GPU kernel for calulating a matrix multiplication would look something like
__kernel void Multiply
(
__global float * A,
__global float * B,
__global float * C
)
{
const int x = get_global_id(0);
const int y = get_global_id(1);
for (int k = 0; k < A_Width; k++)
{
for (int l = 0; l < B_Height; l++)
{
C[x, y] += A[x, k] * B[l, y];
}
}
}
This kernel only has the two inner for loops. A program sending this job to the GPU will tell the GPU to execute this kernel for each data point in C. The GPU will do each of these instructions concurrently on many threads. Just like the old saying "Cheaper by the dozen" GPUs are designed to be faster doing the same thing lots of times.
There are however some algorithms which will slow the GPU down. Some are not well suited for the GPU.
If for example, there were data dependencies, ie: imagine the computation of each element of C depended on the previous elements. The programmer would have to put a barrier in the kernel to wait for each previous computation to finish. This would be a major slow down.
Also, algorithms which have a lot of branching logic ie:
__kernel Foo()
{
if (somecondition)
{
do something
}
else
{
do something completely different
}
}
tend to run slower on the GPU because the GPU is no longer doing the same thing in each thread.
This is a simplified explanation because there are many other factors to consider.
For example, sending data between the CPU and GPU is also time consuming. Sometimes it is worth doing a computation on the GPU even when its faster on the CPU, just to avoid the extra send time (And vice versa).
Also many modern CPUs support concurrency now as well with hyperthreaded multicore processors.
GPU's also seem to be not so good for recursion, see here which probably explains some of the problems with the QR algorithm. I believe that one has some recursive data dependencies.
