6
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Apr 26 '13 at 8:06

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ Dynamic programming, depending on the structure of the DP table. $\endgroup$ – Rasto S. Apr 20 '13 at 10:54
  • $\begingroup$ 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? $\endgroup$ – Raphael Apr 26 '13 at 9:50
  • $\begingroup$ 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. $\endgroup$ – vzn Apr 26 '13 at 15:24
  • $\begingroup$ @vzn Can you give an example for a problem that can not be solved by parallel brute-force search? $\endgroup$ – Raphael Apr 29 '13 at 10:33
  • $\begingroup$ "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 $\endgroup$ – vzn Apr 29 '13 at 15:53
8
$\begingroup$

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.

You can find many other examples on the wikipedia page.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Arguably, NC is not a good definition of "efficiently parallelisable". $\endgroup$ – Raphael Apr 26 '13 at 9:50
  • $\begingroup$ ?? ref(s)? its a textbook definition of the class. $\endgroup$ – vzn Apr 26 '13 at 15:23
  • 2
    $\begingroup$ @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! $\endgroup$ – Massimo Cafaro Apr 26 '13 at 15:51
  • $\begingroup$ @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. $\endgroup$ – Raphael Apr 29 '13 at 10:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.