Как распределить вектор из n элементов на p процессоров
Предположим, у меня есть вектор из 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.
2 ответа
Кажется, это частный случай проблемы с упаковкой в бункер. Есть несколько очень хороших алгоритмов аппроксимации, но в теории это NP-сложный.
Если вы не можете прочесть страницу вики, я разделю ее на несколько строк. Если вы хотите глубже изучить, возможно, лучшие решения или проанализировать, насколько хорошо работают схемы аппроксимации, во что бы то ни стало.
Шаг 1: сортировка элементов по приоритету.
Шаг 2: возьмите элемент с наивысшим приоритетом и вставьте его в процесс с наименьшей нагрузкой.
Шаг 3: Если у вас есть больше элементов, перейдите к шагу 1. Иначе вернитесь.