3

For instance, algorithms such as LZ77 might require previous results in order to proceed but it is still possible to execute them in parallel, at least to some extent (e.g. http://www.cs.cmu.edu/~jshun/dcc2013-final.pdf).

Are there any specific, real-world algorithms which have to be executed only sequentially?

5
  • 3
    Do you mean absolutely cannot be parallelised, or cannot be parellelised and show performance improvement? Sep 12, 2013 at 20:43
  • 1
    If you mean cannot be sped up, see this thread: scicomp.stackexchange.com/questions/1391/…. Also have a look at: quora.com/Computer-Science/…
    – sara
    Sep 12, 2013 at 20:48
  • @JohnCarter Aren't they the same? Any algorithm can be parallelized, just by running the same code concurrently.. then it is successfully parallelized, just with zero performance improvement. Wow, that was pedantic.
    – Thomas
    Sep 12, 2013 at 21:08
  • @Thomas That's what I'm wondering. If its just a matter of zero improvement, then the answer is yes -- one can point to lots of examples that won't provide speed up when parallelised. If its the alternative, then it's far more theoretical. Sep 12, 2013 at 21:14
  • @John I assumed that not showing any improvement is the same as not possible to parallelise.
    – AlexSee
    Sep 13, 2013 at 19:13

1 Answer 1

7

Wikipedia:

Some problems have no parallel algorithms, and are called inherently serial problems.

Examples:

http://en.wikipedia.org/wiki/Three-body_problem

http://en.wikipedia.org/wiki/Newton%27s_method

You can also have a look at this thread algorithms that cannot be sped up by parallelisation

1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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