What are canonical examples of parallel computation?

Question

I am writing a paper to test a new application that will demonstrate the benefits of parallelized computation (compared to the traditional serialized version of this application). I want to use the canonical examples for parallel computation in my paper.

My first example is the parallel computation of pi. I would ideally like an example where each iteration is very time consuming (because of the additional overhead associated with parallelizing); my first thought is a Bayesian simulation with MCMC and Gibbs sampling.

What other problems are typically discussed in this context? What are good examples of large embarassingly parallel problems?

Answer 1

One example I've used in the past of an embarrassingly parallel problem is visualizing the mandelbrot set. Each pixel can be computed independently.

Conway's Life is interesting as well, in that each value of the "next" board can be computed independently, but will depend on the relevant bits of the "current" board being done already.

Answer 2

Word counting seems to be the canonical example for MapReduce.

http://en.wikipedia.org/wiki/MapReduce#Example

Answer 3

just a few more -

• Multiplying matrices
• Inverting matrices
• FFT
• String matching
• Rendering 3d scenes (via scan line conversion or ray tracing)

Answer 4

My favorite example is monte carlo simulation.

Answer 5

Finding collisions in hash functions using Paul C. van Oorschot and Michael J. Weiner's method (PDF) comes up often in various cryptographic settings.

Answer 6

I would suggest that canonical examples of parallel computation and embarassingly parallel problems are, if not completely, then nearly, disjoint sets. To put it another way, people working in parallel computation aren't terribly excited about embarassingly parallel problems; we call them that because we'd be embarassed to be working on them.

I'd be looking, if I were you, at these (a not entirely original list):

• linear algebra on large dense matrices, both direct and iterative approaches;
• linear algebra on huge sparse matrices
• branch and bound approaches to linear programming (and related) problems;
• sequence matching for bioinformatics (outside my field, I may have mis-expressed this);
• continuos optimisation.

I expect there are many more.

EDIT: You may be interested in this list of problems which have been selected for benchmarking the next generation of European (academic) supercomputers. It will give you some idea of where that niche is heading.

Answer 7

Molecular dynamics simluations allow you to change the size of the problem until your computer resources are exhausted (i.e. 256 particles vs. 256,000,000 particles). Its truly a "canonical" example if you run the MD simulations under NVT conditions ;-)

Answer 8

You may want to have a look at Table of Contents of Parallel Programming in C with MPI and OpenMP

Answer 9

I used the Mandelbrot set demo to explain to my mom what parallel programming is about : http://www.ateji.com/px/demo.html

All the examples you mentions are mostly heavy data-parallel codes. You'll probably want to mention also task-oriented codes, such as servers responding to many requests in parallel, and data-flow or stream programming examples (MapReduce is a good representative of this class).