多线程二分搜索

Question

假设我有一些可计算的谓词P，它将整数映射为bools。我知道P 0是真的，我也知道一些P N是假的。我也知道P n = false意味着P (n + 1) is false *。我想找出最大值n，这样P n是真的。

显然，我可以通过二分法找到这个问题的解决方案。不幸的是，评估P是昂贵的(可能需要一个小时左右)。我还有一个有许多核心的闪亮的服务器。

如果评估P需要恒定的时间，并且我有两个线程(例如)，我可以看到我将如何进行搜索。我将区间a，b划分为三个部分，并计算P (2a + b)/3和P (a + 2b)/3。一旦两个评估都完成了，我就会知道要将哪三个部分恢复到哪个部分。使用两个线程，我的搜索时间将减少三分之一。太棒了！

然而，如果评估P的时间变化很大呢？在我的具体例子中，它可能需要10秒到一个小时左右。再一次假设我有两个线程，并且像上面一样划分了间隔。也许第一个线程(评估P (2a+b)/3)首先完成。我该如何决定下一次在哪里运行呢？

我想有一些信息理论或类似的链接，因为我试图运行的测试，将给我提供最多的信息，鉴于我目前的知识。但这似乎应该是其他人调查过的一个问题--有人能给我指一下报纸或类似的文件吗？

*在我关心的具体情况下，测试涉及运行一个SMT求解器，试图找到一个约束问题的解X，该约束问题的形式为X≥n，其中n是上面的整数。

Answer 1

如果您正在寻找纸质参考，您可能会在CS.SE上获得更多的支持。在这里，我只能提供一些启发。

每当线程完成时，您就可以停止所有其他线程，这些线程的答案都是您现在知道的(也就是说，如果您得到了P(n)=T，您可以停止所有线程在k<n上工作，如果是P(n)=F，则可以停止所有线程在k>n上工作)。因此，您现在有一个或多个线程要启动。

从信息论POV出发，对现有区间进行划分，使新区间的最大长度最小，显然是最优的。

但是，既然您在评论中注意到：

SMT求解程序对于可满足的解要花费更长的时间。

从大型n开始并缓慢下降可能更快(例如，如果您知道P(100)=F和P(1)=T，测试95、90、80在3个线程中，而不是信息论建议的25、50、75 )。

您还可以使用运行时间来指示可能的结果。例如，在n=25,50,75启动你的3个线程。假设您在1分钟内学习了P(75)=F，但其他两个仍然在运行。然后，您可以让n=25线程进入睡眠状态(在将来必要时被唤醒或终止)，并为60和70启动两个新线程。

Answer 2

如果对P的评估时间没有更多的了解，比如统计性质，或者与参数n的某种联系，那么最好的策略是使用第一次完成的评估，而不是等待其他开始的评估。这是因为长期的评估可以持续几百倍于快速评估。很少有快速评估可以缩短搜索间隔相当快，所以长时间的评估将根本不需要。

我会尝试的策略，是二进制搜索，开始更多的评估间隔一半。例如，如果间隔0,100必须检查，并且有8个线程比开始计算n=47，.，54。当第一次评估结束时，终止无法得到结果的评估，暂停其他评估，然后继续进行前一间隔的一半。当间隔略大于线程数(~1.5x)时，使用某种策略覆盖整个间隔，因为要找到结果，必须检查两个邻居。只会有2*num_threads暂停的评估。