<p>Imagine you are able to log execution of all processor instructions, which calculate new values, along with their operands. Then you get a huge acyclic graph. If that graph contains parallel branches, then the code can be split into parallel parts.</p>

<p>Sounds too obvious? It is.</p>

CC BY-SA 4.0
2018-09-09T09:55:29.583Z
2018-09-09T09:55:29.583Z
Alexei Kaigorodov
<p>I am new to the world of Parallel computing and that is why don't know exactly where I should look at or search to get the answer.</p>

<p>Is there any theorem or just general theory determining which code can be split into parts to run parallelly and then merge answers? Maybe some analysis algorithm exists that allows to tell whether the code is "splittable"? For example, like data-flow analysis which shows whether a chunk of code is used, or maybe to optimize the code, etc. I guess, I have an intuition that if the problem consists of calculating values of elements in an array that depend on the previous ones, then the problem cannot be divided as we don't know future values.</p>

<p>So, basically this is a reference request but I will appreciate more in-depth explanation of related things. Thanks in advance!</p>

CC BY-SA 4.0
2018-09-04T18:25:29.963Z
You might want to check out https://en.wikipedia.org/wiki/Embarrassingly_parallel and the references cited there.
Peter
<reference-request><dc.distributed-comp><parallel>
How to know if a problem is distributable?
Turkhan Badalov
# How to know if a problem is distributable?

(Asked by: username_0 on 2018-09-04)

I am new to the world of Parallel computing and that is why don't know exactly where I should look at or search to get the answer.

Is there any theorem or just general theory determining which code can be split into parts to run parallelly and then merge answers? Maybe some analysis algorithm exists that allows to tell whether the code is "splittable"? For example, like data-flow analysis which shows whether a chunk of code is used, or maybe to optimize the code, etc. I guess, I have an intuition that if the problem consists of calculating values of elements in an array that depend on the previous ones, then the problem cannot be divided as we don't know future values.

So, basically this is a reference request but I will appreciate more in-depth explanation of related things. Thanks in advance!

**Tags:** reference-request, dc.distributed-comp, parallel

> **Comments:**
> **username_1**: You might want to check out https://en.wikipedia.org/wiki/Embarrassingly_parallel and the references cited there.  

---

## 1 answers

### Answer by username_2 on 2018-09-09. Score: 0

Imagine you are able to log execution of all processor instructions, which calculate new values, along with their operands. Then you get a huge acyclic graph. If that graph contains parallel branches, then the code can be split into parallel parts.

Sounds too obvious? It is.


---

