parallel-processing - 本質的に並列化できないアルゴリズム

Question

たとえば、LZ77 などのアルゴリズムでは、続行するために以前の結果が必要になる場合がありますが、少なくともある程度は並行して実行することは可能です (例: http://www.cs.cmu.edu/~jshun/dcc2013- final.pdf )。

シーケンシャルにのみ実行する必要がある特定の現実世界のアルゴリズムはありますか?

Answer 1

ウィキペディア:

一部の問題には並列アルゴリズムがなく、本質的に直列問題と呼ばれます。

例:

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

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

並列化によって高速化できないこのスレッドアルゴリズムもご覧ください。