# Which algorithms can not be parallelized?

Is there any algorithm which is very difficult to parallelize or the research is still active?

I wanted to know about any algorithm or any research field in parallel computing.

Anything, I searched for, has a 'parallel' implementation done. Just want to do some study on any unexplored parallel computing field.

• What exactly do you mean by "parallelize"? Arguably, every algorithm is parallelizable, just not always well. (It might be more interesting to find new algorithms, in any case.) – Raphael Jan 11 '14 at 10:28
• You got it right, my purpose is finding algorithms which are difficult to parallelize. Can you tell me more about what you mean by finding new algorithms? – Polynomial Proton Jan 11 '14 at 21:15
• You did not answer my question. How many processors do you allow (5, $p$, $n$, $\infty$)? What kind of speedup and/or efficiency are you after (any speedup, speedup linear in number of processors, poly-logarithmic total time)? – Raphael Jan 12 '14 at 11:38
• As of now, i'm looking out for algorithms which are difficult to parallelize i.e exploring the field and then decide accordingly after studying them. – Polynomial Proton Jan 12 '14 at 19:45
• – Ciro Santilli 新疆改造中心法轮功六四事件 May 5 at 9:53

this is basically an open research problem relating to the NC=?P question where NC is taken as the class of efficiently parallelizable algorithms.

in an influential/broadranging survey from Berkeley "the landscape of parallel computing", there are classes of algorithms or parallelism patterns separated into "dwarves". of the 1st 6 identified, it looks like $n$-body problems maybe relatively difficult to efficiently parallelize as the $n$ increases because there are $n^2$ interactions between all the $n$ points.

they added 6 others later in the paper and suggest that a last one called "FSMs" (p14) where the problem involves computing FSM like calculations (such as the $n$th state of the FSM) may be the opposite of "embarrassingly parallel" something they propose calling "embarrassingly sequential".

see also are there famous algorithms in sci. comp. that cant be parallelized, scicomp.se

• Brilliant, thanks for the links and explanation! – Polynomial Proton Jan 12 '14 at 19:50

This article gives a number of problems that are easy to solve sequentially but difficult to parallelise: http://en.wikipedia.org/wiki/P-complete

The circuit value problem ("given a Boolean circuit + its input, tell what it outputs") is a good starting point — easy to understand, easy to solve with sequential algorithms, and nobody knows if it can be parallelised efficiently.

• This assumes a complexity-theoretic definition of "parallelizable" which may or may not be of interest. – Raphael Jan 12 '14 at 11:37
• @Raphael: AFAIK, many classical P-complete problems are difficult to parallelise not only in theory but also in practice (even if you have a relatively small number of processors). – Jukka Suomela Jan 12 '14 at 11:59
• @JukkaSuomela There are also cases where complexity theory suggests hardness, but things work nicely in practice. Furthermore, positive results don't mean much in practice, either. – Raphael Jan 12 '14 at 13:36
• One might want to add that, from a complexity theoretic point of view, it is not at all clear whether "inherently unparallizable" problems do even exist, by the fact that it is not known whether $\mathsf{NC} = \mathsf{P}$, as vzn does in his answer – Cornelius Brand Jan 12 '14 at 19:05

From a practical-oriented perspective, you are asking about inherently-sequential algorithms. There are many candidates, such as hash-chaining, which is believed to be very difficult to parallelize. Hash-chaining is widely used in cryptography. For instance, the password-hashing scheme bcrypt was designed to try to make it difficult to speed up the hash through parallelization. Another example is repeated-squaring (again, in cryptography).

• I found a few papers who have parallelize hash chaining, but havent read it completely. I'll go through the same. Anyway, thanks for the input! – Polynomial Proton Jan 11 '14 at 21:21
• @TheUknown Links to those papers would be appreciated. – m33lky Sep 26 '14 at 23:48
• @m33lky Sorry, I do not have any of those papers with me now. This was way back in Jan and I finally continued my research on another topic. However, you can look up online on google scholar and I'm sure you will get many papers – Polynomial Proton Oct 2 '14 at 17:56
• On the practical perspective, it is also worth mentioning that if the algorithm is e.g. memory bound, then parallelization won't help much: stackoverflow.com/questions/868568/… – Ciro Santilli 新疆改造中心法轮功六四事件 May 5 at 9:52