多线程二分查找

Question

假设我有一个可计算的谓词P，将整数映射到布尔值。我知道P 0为真，并且我知道某个N使得P N为假。我还知道P n = false意味着P (n + 1)也为false [*]。我想找到最大的n，使得P n为真。

显然，我可以通过二分法找到解决方案。不幸的是，评估P很耗费时间（可能需要一小时左右）。我还有一个拥有许多内核的闪亮服务器。

如果评估P需要恒定的时间并且我有2个线程（比如），我可以看到如何进行搜索。我将区间[a，b]分成三个部分，并评估P（2a + b）/ 3和P（a + 2b）/ 3。一旦两个评估都完成，我就会知道要递归进入哪个三段。使用两个线程，我的搜索时间将减少三分之一。太好了！

但是，如果评估P需要极端变化的时间呢？在我的具体示例中，它可能需要10秒到一小时左右的时间。再次假设我有2个线程并按上述方式划分间隔。也许第一个线程（评估P（2a + b）/ 3）先完成。我该如何决定下一个运行在哪里？

我猜这与信息论或类似的东西有关，因为我正在尝试运行测试，给出当前知识的情况下会给我最多的信息。但是这似乎应该是其他人已经调查过的问题-有人可以指向论文或类似的东西吗？

[*] 在我关心的具体情况中，测试涉及运行SMT求解器，尝试找到一个约束问题的解X，并具有一个额外的约束条件形式为X≥n，其中n是上面的整数。

- Rupert Swarbrick

---

有没有关于给定子问题评估的运行时间的信息？ - Codor

更具体地说：运行时间与 n 没有"函数关系"，对吗？在许多情况下，P(n+1) 可能比 P(n) 花费更长的时间，但肯定有一些问题不是这种情况。如果运行时间基本上是"随机的"(即根本无法预测)，那么很可能很难找到任何比分割区间并尝试更系统的方法。然后，它将归结为传递给线程的"评估P任务"的顺序，并依赖于 https://en.wikipedia.org/wiki/Work_stealing 或类似技术... - Marco13

运行时间是n的函数，从这个意义上说它是确定性的。但它是一个我们事先不知道的复杂函数。我认为（但可能错了），根本问题是如果我已经有几个点正在区间内被评估，那么在哪里开始一个新线程：也许我应该选择部分评估点之间最大的间隔？还是其他什么？ - Rupert Swarbrick

我的问题的主要点是，随着n的增大，运行时间是否通常会增加。通过使用从P（0），P（N）和P（N / 2）开始的二分查找，可能可以快速推导出有关运行时间的大致估计（甚至可以猜测它是线性还是二次方）。这可能至少给出一个粗略的提示，关于一种可能有助于快速缩小到正确的n的策略。 - Marco13

哦，我明白了。在这种特殊情况下，SMT求解器似乎需要更长的时间来获取可满足的解（即小的n）。奇怪的是，随着接近截止点，运行时间似乎并没有增加太多：可能难度的增加被不强制选择的数量减少所抵消了？（不确定）。 - Rupert Swarbrick

Answer 1

如果您正在寻找一份论文参考资料，您可能会在CS.SE上获得更多的关注。在这里，我只能提供一些启发式方法。

每当一个线程完成时，您可以停止所有其他已知答案的线程（即，如果您得到了P(n)=T，则可以停止所有正在处理k<n的线程，如果P(n)=F，则可以停止所有正在处理k>n的线程）。因此，现在您有1个或多个线程需要启动。

从信息论的角度来看，将现有区间划分为最小化新区间的最大长度显然是最优的。

但是，由于您在评论中指出：

求解可满足的解的SMT求解器需要更长时间

开始使用大的n并缓慢降低可能更快（例如，如果您知道P(100)=F和P(1)=T，则在3个线程中测试95、90、80，而不是按照信息理论推荐的25、50、75）。

你还可以使用运行时间作为可能结果的指标。例如，在n=25,50,75开始3个线程。假设1分钟后你学到了P(75)=F，但另外两个仍在运行。然后你可以让n=25的线程休眠（将来根据需要唤醒或终止），并启动两个新线程分别为60和70。

- sds

Answer 2

如果关于P评估时间没有更多的知识，例如统计特性或与参数n的某些联系，那么最好的策略可能是使用首先完成的评估而不是等待其他已启动的评估。这是因为长时间的评估可能会比快速评估持续几百倍。少量的快速评估可以相当快地缩小搜索区间，因此根本不需要进行长时间的评估。

我会尝试二分搜索策略，从区间的一半开始启动更多的评估。例如，如果要检查区间[0, 100]，并且有8个线程，则启动n=[47, ..., 54]的评估。当第一个评估完成时，杀死不能得出结果的评估，暂停其他评估，并继续处理上一个区间的~一半。当区间略大于线程数（~1.5x）时，使用某些策略覆盖整个区间以进行评估，因为要找到结果，必须检查两个相邻的区间。暂停的评估数量不会超过2*num_threads。

- Ante