Многопоточный поиск пополам
Предположим, что у меня есть некоторый вычислимый предикат, P, который отображает целые числа в bools. я знаю это P 0 это правда, и я знаю, что некоторые N, что P N ложно Я тоже знаю что P n = false подразумевает, что P (n + 1) is false [*]. Я хочу найти максимальное такое, что 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 - целое число выше.
2 ответа
Если вы ищете справку на бумаге, вы можете получить больше тяги на CS.SE. Здесь я могу предложить только некоторые эвристики.
Всякий раз, когда поток завершается, вы можете остановить все другие потоки, чей ответ вы теперь знаете (например, если вы получили P(n)=T, вы можете остановить все темы, работающие на k<n, и если P(n)=F, вы можете остановить все темы, работающие на k>n). Таким образом, теперь у вас есть 1 или более потоков для запуска.
Из теоретико-информационного POV деление существующих интервалов для минимизации максимальной длины новых интервалов является, очевидно, оптимальным.
Однако, так как вы заметили в комментарии:
SMT решатель занимает гораздо больше времени для удовлетворительных решений
Это может быть быстрее начать с большой 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.
Если нет больше знаний о времени оценки P, например, о статистических свойствах или какой-либо связи с параметром n, то, вероятно, это лучшая стратегия, чтобы использовать оценку, которая была сначала закончена, и не ждать других запущенных оценок. Это потому, что длительная оценка может длиться в несколько сотен раз больше, чем быстрая. Несколько быстрых оценок могут довольно быстро сократить интервал поиска, поэтому длительные оценки вообще не понадобятся для оценки.
Я бы попробовал стратегию, которая является бинарным поиском, который начинает больше оценок на половине интервала Например, если необходимо проверить интервал [0, 100] и существует 8 потоков, чем начальные оценки для n=[47, ..., 54]. Когда первая оценка закончится, убейте оценки, которые не могут быть результатом, приостановите другие оценки и продолжайте ~ половину предыдущего интервала. Когда интервал немного больше, чем число потоков (~1,5x), используйте некоторую стратегию, чтобы покрыть весь интервал оценками, так как, чтобы найти результат, вы должны проверить обоих соседей. Не будет более 2*num_threads приостановленных оценок.