Многопоточный поиск пополам

Question

Предположим, у меня есть некоторый вычислимый предикат, P, который отображает целые числа в bools.Я знаю, что 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) заканчивается первым.Как мне решить, где запустить следующий?

Я предполагаю, что есть какая-то ссылка на теорию информации или подобное, потому что я пытаюсь запустить тест, который даст мне больше информации, учитывая мои текущие знания.Но похоже, что это должна быть проблема, которую исследовали другие - кто-нибудь может указать мне на бумаги или подобные?

[*] В конкретном случае, который меня волнует, тест включает запуск решателя SMT, пытающегося найтирешение X задачи ограничения с одним дополнительным ограничением вида X ≥ n, где n - целое число выше.

Answer 1

Если нет больше знаний о времени оценки P, например, о статистических свойствах или какой-либо связи с параметром n, то, вероятно, это лучшая стратегия, чтобы использовать оценку, которая была сначала закончена, и не ждать других запущенных оценок.Это потому, что длительная оценка может длиться в несколько сотен раз больше, чем быстрая.Немногие быстрые оценки могут довольно быстро сократить интервал поиска, поэтому длительные оценки вообще не понадобятся для оценки.

Я бы попробовал стратегию, которая заключается в бинарном поиске, который запускает больше оценок на половине интервала.Например, если необходимо проверить интервал [0, 100] и существует 8 потоков, чем начальные оценки для n = [47, ..., 54].Когда первая оценка закончится, убейте оценки, которые не могут быть результатом, приостановите другие оценки и продолжайте ~ половину предыдущего интервала.Когда интервал немного больше, чем число потоков (~ 1,5x), используйте некоторую стратегию, чтобы покрыть весь интервал оценками, так как, чтобы найти результат, вы должны проверить обоих соседей.Будет не более 2 * num_threads приостановленных оценок.

Answer 2

Если вы ищете справочный документ, вы можете получить больше тяги на CS.SE .Здесь я могу предложить только некоторые эвристики.

Всякий раз, когда поток завершается, вы можете остановить все остальные потоки, чей ответ вы теперь знаете (например, если вы получили P(n)=T, вы можете остановить все потоки, работающие на k<nи если P(n)=F, вы можете остановить все потоки, работающие на k>n).Таким образом, теперь у вас есть 1 или более потоков для запуска.

Из теоретико-информационного POV разделение существующих интервалов для минимизации максимальной длины новых интервалов, очевидно, является оптимальным.

Однако, посколькуВы отмечаете в комментарии:

для решения SMT требуется гораздо больше времени * для удовлетворительных решений

Может быть быстрее начать с large n и идти вниз медленно (например, если вы знаете, что P(100)=F и P(1)=T, тестируйте 95, 90, 80 в 3 потоках вместо 25, 50, 75 в соответствии с рекомендациями теории информации).

Вы также можете использовать время выполнения в качестве индикатора вероятного результата.Например, начните свои 3 темы в n=25,50,75.Предположим, что за 1 минуту вы выучите P(75)=F, но два других все еще работают.Затем вы можете уложить поток n=25 в спящий режим (чтобы его разбудили или убили в будущем при необходимости) и запустите два новых потока для 60 и 70.