patternModerate
Which algorithms can not be parallelized?
Viewed 0 times
canparallelizedalgorithmswhichnot
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#19643, answer score: 13
Revisions (0)
No revisions yet.