Какой алгоритм лучше всего использовать при работе с параллельными процессорами?

Question

Если бы у меня была машина с несколькими процессорами и пыталась решить огромную проблему, какой алгоритм был бы лучше всего для решения этой проблемы?

Алгоритм динамического программирования, жадности или разделения и покорения?

Answer 1

Это очень широкий вопрос, и многие вещи будут зависеть от конкретной проблемы, которую вы пытаетесь решить, но то, что вы ищете, может ли алгоритм выполнить свои шаги параллельно. Это можно сделать только в том случае, если результат одного шага не зависит от результата другого.

• Здесь мы ничего не можем сказать о жадных алгоритмах. Они определяются только как лучший локальный шаг вперед.
• Divide and conquer делит проблему на отдельные части, каждая из которых может быть индивидуально решена, поэтому это часто является хорошим кандидатом для параллельной работы.
• Динамическое программирование можно рассматривать как своего рода разделение и завоевание, но теперь вы решаете небольшую часть проблемы, а затем используете ее для решения большей части и т. Д. Например, проблема ранца часто используется в качестве варианта использования для динамического программирования. Вы можете решить проблему, начиная с тривиально маленького рюкзака и оттуда выстроить свое решение. Проблема здесь в том, что каждое решение зависит от решения меньшей задачи. Если отдельные этапы не могут быть разделены между потоками, это невозможно распараллелить.

Как правило, деление и завоевание, по-видимому, являются вашим лучшим выбором для параллельной работы.

Answer 2

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

Жадность - это однопоточная резьба. Может быть сделано многопоточное, но не огромное преимущество imo. В любом случае, вы можете использовать пул потоков для съемки с лучшими 5 матчами ... Это было бы проще всего реализовать.

The Divide and Conquer - рекурсивный. Если вы создадите новый поток, по-прежнему потребуется синхронизация, но он может воспользоваться преимуществами нескольких процессоров. Я думаю, что это будет второй более простой способ для реализации многопоточных.

Характер проблемы, которую вам нужно решить, будет определять, какой метод программирования вы должны использовать, а не номера ядра процессора.

Примите во внимание затраты времени на переключение контекстов между потоками!