Как распределить вектор из n элементов по p процессорам

#algorithm #parallel-processing #mpi

#алгоритм #параллельная обработка #mpi

Вопрос:

Предположим, у меня есть вектор из n элементов, и я хочу распределить его по p процессам, где n не обязательно кратно p . Каждый процесс имеет ранг от 0 до p-1. Как определить, сколько элементов будет в каждом процессе, чтобы данные распределялись как можно более равномерно?

Например, если n = 14 и p = 4, я хочу распределение, подобное [3, 3, 4, 4] или [3, 4, 3, 4], но не [3, 3, 3, 5] и не [4, 4, 4, 2].

Я хочу функцию f (n, p, r), которая возвращает мне количество элементов для процесса с рангом r.

1. Как насчет классического подхода «фермер / рабочие»? Пример MPI: inf.ed.ac.uk/teaching/courses/ppls/farm.c

2. Не для моего случая. Мне нужно распределить строки из изображения для обработки, поэтому подход «фермер / рабочий» не был бы решением.

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

Ответ №1:

Выполняет ли

 (n   r) / p

работает для вас?

Ответ №2:

Похоже, это частный случай проблемы с упаковкой ячеек. Существует несколько очень хороших алгоритмов аппроксимации, но теоретически это NP-сложно.

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

Шаг 1: отсортируйте элементы по приоритету.
Шаг 2: возьмите элемент с наивысшим приоритетом и поместите его в наименее загруженный процесс.
Шаг 3: Если у вас есть больше элементов, перейдите к шагу 1. Возврат Else.