3
$\begingroup$

I've been unable to find a good answer for this question: Formally, what makes a problem embarrassingly parallel? Intuitively, it would seem to me that an embarrassingly parallel problem is one where:

  1. The full solution can be discretized.
  2. It is efficiently decomposable into subproblems that are similar in structure.
  3. Each subproblem is (more or less) independently soluble (i.e. without a large communication overhead required between the subproblems).
  4. The solutions of each subproblem are independent such that there is an efficient method that can reassemble them into the larger solution.

I realize there's some overlap in the bullets above, hence the question – how is 'embarrassingly parallel' or its synonymous technical term clearly defined? Is there a reference in the literature where this definition was first formalized?

Note: I'm not trained in TCS (as you may have guessed) and am aware that my descriptions above may not be entirely correct or in keeping with established formalisms and terminology.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Interesting question. As a first stab, I would say "embarrassingly parallel" is a property of a particular serial algorithm, not a problem, and roughly would say that if the algorithm takes t time then using k processors the algorithm can be implemented in O(t/k) time. This certainly captures the "parallel" part but not necessarily the "embarrassing" part of it. $\endgroup$
    – Ryan Williams
    Commented Feb 3, 2020 at 23:18
  • $\begingroup$ @RyanWilliams Maybe it could be captured through a constraint on Amdahl's Law? First, given $S_{speedup} \le {1 \over{(1 - p) + p/s}}$, where $p$ is the proportion of the task to be parallelized and $s$ is the speed improvement for that proportion. Then, we say something like an embarrassingly parallel problem is one where $p \lesssim 1$. Note that I'm using $\lesssim$ here to convey 'less than and approximately equal to.' That said, this would be more of a practical definition and not quite the complexity theory one I had in mind. $\endgroup$
    – Greenstick
    Commented Feb 4, 2020 at 4:22

1 Answer 1

Reset to default
2
$\begingroup$

There is no formal answer for that question, as the notion of "embarrassingly parallel" is not a formal one; it is an informal and imprecise notion. I understand it to basically mean that if you do the trivial and obvious thing to parallelize (whatever that may be), it works, and there's no need for sophisticated solutions.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I've seen the term associated with polynomial homotopy continuation methods (see Etymology section). I realize this may be a separate question, but is there a relationship between the terms? In my first reading I read the term as being similar to (or perhaps the formalism for) 'embarrassingly parallel,' but perhaps what is meant in the quote is that polynomial homotopy continuation methods are an instance of an embarrassingly parallel problem? There does seem to be a relation, but I don't have the expertise to make it precise. $\endgroup$
    – Greenstick
    Commented Jan 28, 2020 at 17:45
  • 2
    $\begingroup$ @Greenstick, there is no association. That quote from Wikipedia is just a random example (and a rather confusing one, in my opinion). $\endgroup$
    – D.W.
    Commented Jan 28, 2020 at 17:47
  • $\begingroup$ Gotcha, thanks – I appreciate it. $\endgroup$
    – Greenstick
    Commented Jan 28, 2020 at 17:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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