本质上不可能并行化的算法

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

您还可以查看无法通过并行化加速的此线程算法