multithreading - 是否有一些算法不支持高效的并行实现？

Question

这是我感兴趣的一个非常简单的研究问题。是否有一些算法示例，或者只是一些可以有效顺序实现但不支持高效并行化的代码？

Answer 1

当然有 - 许多算法由于其顺序性质而无法并行化。你在密码学方面有几个很好的例子。

很好的例子是密码 block 链接算法 (CBC)、传播密码 block 链接 (PCBC)、密码反馈和输出反馈。查看有关分组密码操作模式的维基百科页面；对于每种模式，右上角都有一个小框，表示加密和解密过程是否可并行:http://en.wikipedia.org/wiki/Block_cipher_mode_of_operation

一般来说，任何下一步依赖于上一步结果的算法都不能并行化，至少不能有效地并行化。您始终可以有多个线程处理它，但这不会有多大用处，您必须等待上一步完成才能继续，所以您永远不会真正拥有真正的并行性。

肯定还有其他几个例子，密码学只是其中之一，也是我能立即想到的。