<p>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.</p>

CC BY-SA 4.0
2020-01-28T17:45:56.057Z
I've seen the term associated with [polynomial homotopy continuation methods](https://en.wikipedia.org/wiki/Embarrassingly_parallel) (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.
Greenstick
CC BY-SA 4.0
2020-01-28T17:47:39.957Z
@Greenstick, there is no association.  That quote from Wikipedia is just a random example (and a rather confusing one, in my opinion).
D.W.
CC BY-SA 4.0
2020-01-28T17:48:32.197Z
Gotcha, thanks – I appreciate it.
Greenstick
CC BY-SA 4.0
2020-01-28T07:15:35.943Z
2020-01-28T07:15:35.943Z
D.W.
<p>I've been unable to find a good answer for this question: <strong>Formally, what makes a problem embarrassingly parallel?</strong> Intuitively, it would seem to me that an embarrassingly parallel problem is one where:</p>

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

<p>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?</p>

<p>Note: <em>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.</em></p>

CC BY-SA 4.0
2020-02-03T23:18:37.153Z
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.
Ryan Williams
CC BY-SA 4.0
2020-02-04T04:22:56.640Z
@RyanWilliams Maybe it could be captured through a constraint on [Amdahl's Law](https://en.wikipedia.org/wiki/Amdahl%27s_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.
Greenstick
<reference-request><fl.formal-languages><dc.parallel-comp>
Embarrassingly Parallel: Formal Definition & Citation
Greenstick
# Embarrassingly Parallel: Formal Definition & Citation

(Asked by: username_0 on 2020-01-27)

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.*

**Tags:** reference-request, fl.formal-languages, dc.parallel-comp

> **Comments:**
> **username_1**: 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.  
> **username_0**: @RyanWilliams Maybe it could be captured through a constraint on [Amdahl's Law](https://en.wikipedia.org/wiki/Amdahl%27s_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.  

---

## 1 answers

### Answer by username_2 on 2020-01-28. Score: 2 | Accepted answer

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.

> **Comments:**
> **username_0**: I've seen the term associated with [polynomial homotopy continuation methods](https://en.wikipedia.org/wiki/Embarrassingly_parallel) (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.  
> **username_2**: @username_0, there is no association.  That quote from Wikipedia is just a random example (and a rather confusing one, in my opinion).  
> **username_0**: Gotcha, thanks – I appreciate it.  

---

