Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question

closed as too broad by GlenH7, MichaelT, Bart van Ingen Schenau, mattnz, jwenting May 28 at 10:06

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

    
String concatenation, sleep sort –  Job May 15 '13 at 18:31
add comment

6 Answers

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

share|improve this answer
add comment

Video and audio transcoding is a great example. It's the conversion from one file format to another. An example is MPEG-2 to H.264.

Note video transcoding is not related to 3D graphics. You cannot encode a video using a vertex and pixel shader.

share|improve this answer
    
The OP is asking for non-graphics related examples. –  kiamlaluno Dec 27 '11 at 20:07
6  
@kiamlaluno Transcoding a video isn't related to graphics, and audio transcoding most certinly isn't. It's the conversion from one file format to another. An example is MPEG-2 to H.264. It doesn't require the display of graphics to perform. –  Thomas Owens Dec 27 '11 at 20:14
2  
@kiamlaluno: Video transcoding is not related to 3D graphics. You cannot encode a video using a vertex and pixel shader. –  DeadMG Dec 28 '11 at 3:13
add comment

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

share|improve this answer
add comment

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:

  1. Any live cell with fewer than two live neighbours dies, as if caused by under-population.
  2. Any live cell with two or three live neighbours lives on to the next generation.
  3. Any live cell with more than three live neighbours dies, as if by overcrowding.
  4. 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...

share|improve this answer
add comment

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)

share|improve this answer
add comment

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.

share|improve this answer
    
Multiple BOINC clients have GPU support. SETI@Home is another. –  Brian Knoblauch Dec 27 '11 at 20:13
    
Indeed. There are many such projects, but I didn't want to make this a comprehensive list of projects - just to point out what they have in common. –  greyfade Dec 27 '11 at 23:34
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.