无法进行并行化的算法

Question

例如，像LZ77这样的算法可能需要先前的结果才能继续执行，但仍然可以在一定程度上并行执行（例如http://www.cs.cmu.edu/~jshun/dcc2013-final.pdf）。

是否有任何特定的现实世界算法必须仅按顺序执行？

- AlexSee

---

你的意思是绝对不能进行并行处理，还是可以进行并行处理但没有性能提升？ - John Carter

如果您的意思是无法加速，请参考此线程：http://scicomp.stackexchange.com/questions/1391/are-there-any-famous-problems-algorithms-in-scientific-computing-that-cannot-be。还可以看看这个网站：http://www.quora.com/Computer-Science/What-are-some-of-the-famous-algorithms-in-use-which-cannot-be-parallelized。 - sara

@JohnCarter 不是一样吗？任何算法都可以被并行化，只需同时运行相同的代码...然后它就成功地被并行化了，只不过没有性能提升。哇，这太学究了。 - Thomas

@Thomas 我也在想这个问题。如果只是零改进的问题，那么答案是肯定的——可以指出很多例子，在并行化时不会提供加速。如果是另一种情况，那么就更具有理论性了。 - John Carter

@John 我认为如果没有显示任何改进，那么就意味着无法并行化。 - AlexSee

Answer 1

维基百科：

有些问题没有并行算法，被称为本质上串行问题。

例如：

三体问题

牛顿迭代法

您还可以查看这个帖子无法通过并行化加速的算法

- sara

---

相关链接：https://cs.stackexchange.com/questions/19643/which-algorithms-can-not-be-parallelized - Ciro Santilli OurBigBook.com