Embarrassingly parallel

In the jargon of parallel computing, an embarrassingly parallel workload (or embarrassingly parallel problem) is one for which no particular effort is needed to segment the problem into a very large number of parallel tasks, and there is no essential dependency (or communication) between those parallel tasks. [http://www-unix.mcs.anl.gov/dbpp/text/node10.html Designing and Building Parallel Programs, by Ian Foster. Addison-Wesley (ISBN 9780201575941), 1995.] Section 1.4.4]

A very common usage of an embarrassingly parallel problem lies within graphics processing units (GPUs) for things like 3D projection since each pixel on the screen can be rendered independently from any other pixel.

Embarrassingly parallel problems are ideally suited to distributed computing over the Internet (e.g. SETI@home), and are also easy to perform on server farms which do not have any of the special infrastructure used in a true supercomputer cluster.

Embarrassingly parallel problems lie at one end of the spectrum of parallelization, the degree to which a computational problem can be readily divided amongst processors. At the other end of the spectrum are "disconcertingly serial" workloads.

Examples

Some examples of embarrassingly parallel problems include:
* The Mandelbrot set and other fractal calculations, where each point can be calculated independently.
* Distributed rendering of non-real-time computer graphics. In ray tracing, each pixel may be rendered independently. In computer animation, each frame may be rendered independently (see parallel rendering).
* Brute force searches in cryptography. A notable real-world example is distributed.net.
* BLAST searches in bioinformatics.
* Computer simulations comparing many independent scenarios, such as climate models.
* Genetic algorithms and other evolutionary computation metaheuristics.
* Ensemble calculations of Numerical weather prediction.
* Event simulation and reconstruction in particle physics.

See also

* Amdahl's law

References

* [http://www.cs.mu.oz.au/498/notes/node40.html ]
* [http://www.phy.duke.edu/~rgb/Beowulf/beowulf_book/beowulf_book/node30.html]