algorithm - 平行二分

Question

考虑求平方根的二分法。每一步都依赖于前一步，所以在我看来，并行化是不可能的。我错了吗？

还考虑类似的算法，如二分查找。

编辑

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

Answer 1

这取决于您所说的并行化 的含义，以及并行化的粒度。例如，您可以使用指令级并行性(例如 SIMD)来计算一组输入值的平方根。

二分搜索更棘手，因为控制流与迭代次数相关，但您仍然可以想象并行执行多个二分搜索，只要您允许最大迭代次数 (log2 N).