多线程平分搜索
Multi-threaded bisection search
假设我有一些可计算的谓词 P，它将整数映射到布尔值。我知道 P 0 是真的，我知道一些 N 使得 P N 是假的。我也知道 P n = false 意味着 P (n + 1) is false [*]。我想找到最大 n 使得 P n 为真。
很明显，我可以通过二分法找到解决这个问题的方法。不幸的是，评估 P 是昂贵的（可能需要一个小时左右）。我也有一个闪亮的多核服务器。
如果评估 P 花费固定时间并且我有 2 个线程（比方说），我可以看到我将如何进行搜索。我将区间 [a, b] 分成三个部分并评估 P (2a + b)/3 和 P (a + 2b)/3。一旦两个评估都完成，我就会知道要递归到三个部分中的哪一个。使用两个线程，我的搜索时间将减少三分之一。太棒了！
但是，如果评估 P 的时间变化很大怎么办？在我的具体示例中，可能需要 10 秒到一个小时左右。再次假设我有 2 个线程并按上述方式划分了间隔。也许第一个线程（评估 P (2a+b)/3）首先完成。我如何决定 运行 下一个在哪里？
我想有一些 link 信息论或类似的东西，因为我正在尝试 运行 测试，根据我目前的知识，它会给我最多的信息。但这似乎应该是其他人调查过的问题 - 谁能指出我的论文或类似内容？
[*] 在我关心的具体案例中，测试涉及 运行ning 一个 SMT 求解器，它试图找到一个约束问题的解 X，该约束问题具有 X ≥ n 形式的一个额外约束，其中n是上面的整数。
如果您正在寻找论文参考，您可能会在 CS.SE 上获得更多关注。在这里我只能提供一些启发。
每当一个线程结束时，您可以停止所有其他您现在知道其答案的线程（即，如果您得到 P(n)=T，您可以停止所有正在处理 k<n 的线程，如果 P(n)=F，您可以停止在 k>n) 上工作的所有线程。因此，您现在有 1 个或多个要启动的线程。
从信息论的POV来看，划分现有区间以最小化新区间的最大长度显然是最优的。
但是，由于您在评论中指出：
the SMT solver takes much longer for satisfiable solutions
从 大 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 启动两个新线程。
如果没有更多关于 P 评估时间的知识，例如统计属性或与参数 n 的某种联系，那么最好的策略可能是使用先完成的评估而不是等待其他开始的评估。这是因为持久的评估可以比快速评估持续数百倍。很少有快速评估可以非常快速地缩短搜索间隔，因此根本不需要持续很长时间的评估。
我会尝试二分搜索策略，它在间隔一半时开始更多评估。例如。如果必须检查间隔 [0, 100] 并且有 8 个线程比开始评估 n=[47, ..., 54]。当第一个评估完成时，杀死不能产生结果的评估，暂停其他评估，并继续前一个间隔的一半。当间隔略大于线程数 (~1.5x) 时，使用某种策略来覆盖整个间隔的评估，因为要找到结果，您必须检查两个邻居。暂停的评估不会超过 2*num_threads 个。
假设我有一些可计算的谓词 P，它将整数映射到布尔值。我知道 P 0 是真的，我知道一些 N 使得 P N 是假的。我也知道 P n = false 意味着 P (n + 1) is false [*]。我想找到最大 n 使得 P n 为真。
很明显，我可以通过二分法找到解决这个问题的方法。不幸的是，评估 P 是昂贵的（可能需要一个小时左右）。我也有一个闪亮的多核服务器。
如果评估 P 花费固定时间并且我有 2 个线程（比方说），我可以看到我将如何进行搜索。我将区间 [a, b] 分成三个部分并评估 P (2a + b)/3 和 P (a + 2b)/3。一旦两个评估都完成，我就会知道要递归到三个部分中的哪一个。使用两个线程，我的搜索时间将减少三分之一。太棒了！
但是，如果评估 P 的时间变化很大怎么办？在我的具体示例中，可能需要 10 秒到一个小时左右。再次假设我有 2 个线程并按上述方式划分了间隔。也许第一个线程（评估 P (2a+b)/3）首先完成。我如何决定 运行 下一个在哪里？
我想有一些 link 信息论或类似的东西，因为我正在尝试 运行 测试，根据我目前的知识，它会给我最多的信息。但这似乎应该是其他人调查过的问题 - 谁能指出我的论文或类似内容？
[*] 在我关心的具体案例中，测试涉及 运行ning 一个 SMT 求解器，它试图找到一个约束问题的解 X，该约束问题具有 X ≥ n 形式的一个额外约束，其中n是上面的整数。
如果您正在寻找论文参考，您可能会在 CS.SE 上获得更多关注。在这里我只能提供一些启发。
每当一个线程结束时，您可以停止所有其他您现在知道其答案的线程（即，如果您得到 P(n)=T，您可以停止所有正在处理 k<n 的线程，如果 P(n)=F，您可以停止在 k>n) 上工作的所有线程。因此，您现在有 1 个或多个要启动的线程。
从信息论的POV来看，划分现有区间以最小化新区间的最大长度显然是最优的。
但是，由于您在评论中指出：
the SMT solver takes much longer for satisfiable solutions
从 大 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 启动两个新线程。
如果没有更多关于 P 评估时间的知识，例如统计属性或与参数 n 的某种联系，那么最好的策略可能是使用先完成的评估而不是等待其他开始的评估。这是因为持久的评估可以比快速评估持续数百倍。很少有快速评估可以非常快速地缩短搜索间隔，因此根本不需要持续很长时间的评估。
我会尝试二分搜索策略，它在间隔一半时开始更多评估。例如。如果必须检查间隔 [0, 100] 并且有 8 个线程比开始评估 n=[47, ..., 54]。当第一个评估完成时，杀死不能产生结果的评估，暂停其他评估，并继续前一个间隔的一半。当间隔略大于线程数 (~1.5x) 时，使用某种策略来覆盖整个间隔的评估，因为要找到结果，您必须检查两个邻居。暂停的评估不会超过 2*num_threads 个。