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

just a few more -

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