Функция/Алгоритм для перераспределения данных равномерно между процессами

Question

У меня есть глобальный массив A, элементы которого изначально распределены неравномерно по нескольким процессам в программе MPI. В интересах балансировки нагрузки я бы хотел перераспределить элементы A, чтобы каждый процесс имел приблизительно одинаковое количество элементов. В перестановке существует большая свобода, потому что упорядочение элементов А несущественно - я не беспокоюсь о том, какие элементы А оказываются в этом процессе. Я бы, конечно, хотел как можно быстрее добиться передачи.

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

Answer 1

Обычно это называется балансировкой нагрузки, как вы уже сказали.

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

В вашем случае сложность возникает из-за того, что всем рангам может потребоваться отправить (и получить) только части своих данных (от) различного количества рангов. Если у вас есть возможность получить полный глобальный A на одном ранжировании, вы можете просто разбросать его с помощью MPI_Scatter. В противном случае вам нужно сделать некоторые расчеты:

• Первый посыл (MPI_Allgather) счетчиком элементов всех рангов к каждому ранга
• сосчитать, сколько элементов каждого ранга должны отправить (получить) и (с) кем.
• Выполняйте отправку/получение или использование односторонней связи.