并行二分

Question

考虑求平方根的二分法。每个步骤都取决于前面的步骤，所以在我看来，不可能并行化它。我说错了吗？

还考虑类似的算法，如二进制搜索。

编辑

我的问题不是二分法，但它很相似。我有一个单调函数f(mu)，我需要找到f(mu)<alpha所在的mu。一个核心需要2分钟来计算f(mu)，而我需要非常高的精度。我们有一个大约100个核心的农场。我的第一个注意是只使用一个核心，然后通过一个动态步骤扫描f的所有值，这取决于我离alpha有多近。现在我想使用整个农场，但我唯一的想法是在等距点上计算100个f值。

Answer 1

这取决于您所说的并行化是什么意思，以及在什么粒度上。例如，您可以使用指令级并行(例如SIMD)为一组输入值查找平方根。

二进制搜索更棘手，因为控制流与数据有关，迭代次数也是如此，但只要允许最大迭代次数(log2 N)，仍然可以并行执行许多二进制搜索。

Answer 2

即使这些算法可以并行化(我不确定它们是否能并行)，这样做也没有什么意义。

一般来说，尝试并行化已经具有次线性时间界的算法(即T< O(n))几乎没有意义。这些算法已经太快了，所以额外的硬件几乎没有什么影响。

此外，并非所有具有数据依赖关系的算法都不能并行化(一般情况下)。例如，在某些情况下，可以建立管道，使不同的功能单元并行工作，并在它们之间按顺序输入数据。特别是图像处理算法，常常能够适应这样的安排。

没有这种数据依赖关系(因此不需要在处理器之间进行通信)的问题被称为“令人尴尬的并行”。这些问题代表了可以并行化的所有问题空间的一小部分。

Answer 3

许多算法都有几个步骤，每一步都依赖于以前的步骤，有些算法可以将步骤改为并行，有些算法不可能并行，我认为BinarySearch是第二类，您没有错，但是可以将二进制搜索与多搜索并行。