распараллелить пополам

Question

Рассмотрим алгоритм деления пополам, чтобы найти квадратный корень.Каждый шаг зависит от предыдущего, поэтому, на мой взгляд, его невозможно распараллелить.Я не прав?

Рассмотрим также похожий алгоритм, такой как двоичный поиск.

edit

Моя проблема не в делении пополам, но он очень похожУ меня монотонная функция f(mu), и мне нужно найти мю, где f(mu)<alpha.Одно ядро ​​требует 2 минуты для вычисления f(mu), и мне нужна очень большая точность.У нас есть ферма ~ 100 ядер.Моя первая попытка состояла в том, чтобы использовать только 1 ядро, а затем сканировать все значения f с динамическим шагом, в зависимости от того, насколько я близок к alpha.Теперь я хочу использовать всю ферму, но моя единственная идея - вычислить значение 100 f в равных интервалах.

Answer 1

Это зависит от того, что вы подразумеваете под распараллеливанием , и на какой степени детализации.Например, вы можете использовать параллелизм на уровне команд (например, SIMD), чтобы найти квадратные корни для набора входных значений.

Двоичный поиск сложнее, поскольку поток управления зависит от данных, как и число итераций,но вы все еще можете выполнять несколько бинарных поисков параллельно, если вы разрешите максимальное количество итераций (log2 N).

Answer 2

Даже если эти алгоритмы можно распараллелить (и я не уверен, что они могут), в этом нет особого смысла.

Вообще говоря, нет смысла пытаться распараллелить алгоритмы, которые уже имеют сублинейные временные границы (то есть T

Кроме того, неверно (в общем), что все алгоритмы с зависимостями данных не могут быть распараллелены. Например, в некоторых случаях можно настроить конвейер, в котором разные функциональные блоки работают параллельно и последовательно подают данные между ними. В частности, алгоритмы обработки изображений часто поддаются таким схемам.

Проблемы без таких зависимостей данных (и, следовательно, без необходимости обмена данными между процессорами) называются «смущающе параллельными». Эти проблемы представляют собой небольшое подмножество пространства всех проблем, которые могут быть распараллелены.

Answer 3

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