Embarrassingly parallel

In parallel computing, an embarrassingly parallel workload (or embarrassingly parallel problem) is one for which little or no effort is required to separate the problem into a number of parallel tasks. This is often the case where there exists no dependency (or communication) between those parallel tasks.

Embarrassingly parallel problems tend to require little or no communication of results between tasks, and are thus different from distributed computing problems that require communication between tasks, especially communication of intermediate results. They are easy to perform on server farms which do not have any of the special infrastructure used in a true supercomputer cluster. They are thus well suited to large, internet based distributed platforms such as BOINC.

A common example of an embarrassingly parallel problem lies within graphics processing units (GPUs) for tasks such as 3D projection, where each pixel on the screen may be rendered independently.

Examples

Some examples of embarrassingly parallel problems include:

• Distributed relational database queries using distributed set processing
• Serving static files on a webserver.
• The Mandelbrot set and other fractal calculations, where each point can be calculated independently.
• Rendering of 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 for multiple queries (but not for individual large queries)
• Large scale face recognition that involves comparing thousands of input faces with similarly large number of faces.
• 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.
• Sieving step of the quadratic sieve and the number field sieve.
• Tree growth step of the random forest machine learning technique.

Implementations

• In R (programming language) - The snow (Simple Network of Workstations) package implements a simple mechanism for using a collection of workstations or a Beowulf cluster for embarrassingly parallel computations.

See also

• Amdahl's law - an embarrassingly parallel problem would have P almost or exactly equal to 1.
• MapReduce

External links

• Embarrassingly parallel, Parallel algorithms
• Embarrassingly Parallel Computations, Engineering a Beowulf-style Compute Cluster
• "Star-P: High Productivity Parallel Computing"