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!


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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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