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

Question

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

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

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

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

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

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

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

Answer 1

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

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