какой размер чанка даст наилучшую производительность при использовании master-worker с MPI?

Question

Я использую MPI для анализа программы, которая пытается решить проблему Metric TSP. У меня есть P процессоров и N городов для прохождения.

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

Есть всего (N-1)! маршруты для расчета. каждый работник получает кусок с номером, который соответствует первому маршруту, который он должен проверить, а также последнему. Кроме того, мастер посылает ему самый последний из известных результатов, поэтому он может легко перенести плохие маршруты заранее с некоторой нижней границей остатков.

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

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

Лучший размер куска, который я нашел на данный момент, это (n!) / (N / 2)! , но это не дает такого хорошего результата.

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

Answer 1

Это сильно зависит от не зависящих от вас факторов: реализация MPI, общая нагрузка на компьютер и т. Д. Однако я рискну предположить, что это также сильно зависит от количества рабочих процессов.Следует помнить, что MPI порождает процессы, а не потоки.

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