I am looking for examples of general purpose algorithms (meaning non-graphics related) that have been proven to run an order of magnitude faster on a GPU than on a CPU. I will use these examples to think creatively about other algorithms that I could implement on a GPU.
A few things immediately come to mind:
A specialized Bitcoin client was written to use the GPU to perform the cryptographic hashes. The GPU client generally performs more than 10x better than the SMP CPU client on a typical 4-core system. Bitcoin depends on the computation of large numbers of unrelated cryptographic hashes, which can be computed in parallel.
The Folding@Home project offers a GPU client for their molecular dynamics simulations. These computations are performed on the individual bonds between atoms in various environments and conditions. The math is relatively simple, but must be computed billions of times for each bond to simulate mere nanoseconds of activity.
The popular "toy" example used by proponents of GPU computing is the n-body problem.
What these things have in common is that they are embarrassingly parallel. That is, the problem can be decomposed into a small number of discrete computations that are performed many times over a large data set. That is the kind of computation that the GPU is good at.
Complex computations that are dependent on the results of previous computations are not well-suited to the GPU.
Mining Bitcoins using a GPU has become very popular.
...peer-to-peer, electronic cash system. Bitcoin creation and transfer is based on an open source cryptographic protocol and is not managed by any central authority. Each bitcoin is subdivided down to eight decimal places, forming 100 million smaller units called satoshis. Bitcoins can be transferred through a computer or smartphone without an intermediate financial institution.
The processing of bitcoin transactions is secured by servers called Bitcoin miners. These servers communicate over an internet-based network and confirm transactions by adding them to a ledger which is updated and archived periodically. In addition to archiving transactions each new ledger update creates some newly-minted bitcoins...
Another application is in financial markets for real-time trading using models such as Black-Scholes.
...A key requirement for utilizing options is calculating their fair value. Finding ways of efficiently solving this pricing problem has been an active field of research for more than thirty years, and it continues to be a focus of modern financial engineering. As more computation has been applied to finance-related problems, finding efficient ways to implement these algorithms on modern architectures has become more important.
This chapter describes how options can be priced efficiently using the GPU. We perform our evaluations using two different pricing models: the Black-Scholes model and lattice models. Both of these approaches map well to the GPU, and both are substantially faster on the GPU than on modern CPUs. Although both also have straightforward mappings to the GPU, implementing lattice models requires additional work because of interdependencies in the calculations...
Conway's Game of Life is a good academic example.
...The universe of the Game of Life is an infinite two-dimensional orthogonal grid of square cells, each of which is in one of two possible states, alive or dead. Every cell interacts with its eight neighbours, which are the cells that are horizontally, vertically, or diagonally adjacent. At each step in time, the following transitions occur:
- Any live cell with fewer than two live neighbours dies, as if caused by under-population.
- Any live cell with two or three live neighbours lives on to the next generation.
- Any live cell with more than three live neighbours dies, as if by overcrowding.
- Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
The initial pattern constitutes the seed of the system. The first generation is created by applying the above rules simultaneously to every cell in the seed—births and deaths occur simultaneously, and the discrete moment at which this happens is sometimes called a tick (in other words, each generation is a pure function of the preceding one). The rules continue to be applied repeatedly to create further generations...
Problems that require a lot of math that can be done in concurrently. Where I used to work we wanted to play with GPU's to add/subtract/multiply 2 matrixes to work out genetic corrleation. The first time I heard of GPU's was that they were being used by a finacial software house to do some of their modelling (monte carlo and so forth). The would be usefull in code breaking.
GPU's probably wont help much with your more regular programming problems where a couple of CPU cores are enough because most regular programs only need to run a few concurrent process. (migh be different with memory/disk that is very much faster than we currently have)
Maybe I'm being very Math/Science/Engineering compute specific but one that comes to mind is the FFT algorithm.
I've seen this FFT benchmark thrown around before, and although it is a few years old I think it was well done for what it is: http://www.sharcnet.ca/~merz/CUDA_benchFFT