Best problems that are prone to parallelization?

What are some problems that are prone to parallelization? When I think about this, the first thing that comes to my mind is matrix multiplication, which yields to faster calculations, meaning you can get speed ups easily. Any other examples like this?

• Dynamic programming, depending on the structure of the DP table.
– Rasto S.
Apr 20 '13 at 10:54
• This question is ill-posed. Almost any problem can be solved in parallel very well: just execute the brute-force search in parallel. So what are you really asking?
– Raphael
Apr 26 '13 at 9:50
• that is true esp for "embarrassingly parallel" and some other "natural" problems, but not true in general. some problems do not seem to break down under "divide and conquer", possibly inherently so. the question turns out to be very similar to (open?) complexity class separations. its an active area of research.
– vzn
Apr 26 '13 at 15:24
• @vzn Can you give an example for a problem that can not be solved by parallel brute-force search?
– Raphael
Apr 29 '13 at 10:33
• "example problem that can not be solved by parallel brute-force search?" my understanding, amdahls law seems to show that such problems exist but proving they exist formally is probably as hard as open/difficult complexity class separations
– vzn
Apr 29 '13 at 15:53

Tasks that are easily parallelizable are sometimes called embarassingly parallel. Straightforward examples are computing fractals like Julia or Mandelbrot sets (since all points are independent of each other) or brute-force searches.

this is actually a somewhat subtle/open question to prove that some particular problems are efficiently or not efficiently parallelizable. see also NC class. The class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. also NC$\stackrel{?}{=}$P is open. wikipedia states:

Just as the class P can be thought of as the tractable problems (Cobham's thesis), so NC can be thought of as the problems that can be efficiently solved on a parallel computer.

• Arguably, NC is not a good definition of "efficiently parallelisable".
– Raphael
Apr 26 '13 at 9:50
• ?? ref(s)? its a textbook definition of the class.
– vzn
Apr 26 '13 at 15:23
• @vzn: unfortunately, by definition NC also includes lots of problems which are not efficiently parallelizable. The most infamous example is parallel binary search. The trouble is that this problem has polylogarithmic time complexity even for $p$ = 1. Any sequential algorithm requiring at most logarithmic time in the worst case is in NC regardless of its parallel feasibility! Apr 26 '13 at 15:51
• @vzn Not everything ever defined makes sense in all circumstances. See e.g. A complexity theory of efficient parallel algorithms by Kruskal et al. As one point of concern, NC does not consider efficiency at all.
– Raphael
Apr 29 '13 at 10:31