Rup*_*ick 8 algorithm multithreading bisection
假设我有一些可计算的谓词P,它将整数映射到bool.我知道这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秒到1个小时左右.再次假设我有2个线程并且如上所述划分了间隔.也许第一个线程(评估P (2a+b)/3)首先完成.我如何决定下一个的运行方式？
我想有一些信息理论或类似的链接,因为我正在尝试运行测试,根据我目前的知识,这将给我最多的信息.但这似乎应该是其他人调查过的问题 - 任何人都可以指出我的论文或类似内容吗？
[*]在我关心的具体情况中,测试涉及运行SMT求解器,尝试使用X≥n形式的一个额外约束找到约束问题的解X,其中n是上面的整数.
如果您正在寻找论文参考，您可能会在CS.SE上获得更多关注。在这里我只能提供一些启发。
每当一个线程完成时，您可以停止所有其他您现在知道答案的线程（即，如果您得到P(n)=T，您可以停止所有在 上工作的线程k<n，如果P(n)=F，您可以停止所有在 上工作的线程k>n）。因此，您现在有 1 个或多个线程要启动。
从信息论 POV 来看，划分现有区间以最小化新区间的最大长度显然是最优的。
但是，由于您在评论中指出：
SMT 求解器需要更长的时间才能获得令人满意的解决方案
从较大的值开始然后 慢慢n下降可能会更快（例如，如果您知道和，则在 3 个线程中测试 95、90、80，而不是信息论建议的 25、50、75）。P(100)=FP(1)=T
您还可以使用运行时间作为可能结果的指标。例如，在 处启动 3 个线程n=25,50,75。假设 1 分钟后你就学会了P(75)=F，但另外两个仍在运行。然后你可以让n=25线程进入睡眠状态（将来根据需要被唤醒或杀死）并为 60 和 70 启动两个新线程。
| 归档时间： |
|
| 查看次数： |
106 次 |
| 最近记录： |