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