Даже алгоритм распределения работы

Question

Быстрый вопрос о балансировке работы.

Программа обработки файлов параллельно. Допустим, размер файла является приблизительным показателем того, сколько времени потребуется для его обработки. Все файлы известны заранее.

У нас есть N узлов, которые могут работать с файлами. Как распространить эти файлы так, чтобы каждый узел имел самый близкий к среднему объему работы.

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

Кто-то знает это?

Спасибо!

EDIT: Хорошо, извините, я опустил много информации. Я работаю над реализацией MPI. Стандартная система мастер-раб. Один главный узел проверяет целевой каталог, выбирая файлы, которые необходимо обработать, а затем назначает файлы подчиненным задачам MPI, чтобы они могли выполнять свою часть параллельно.

Количество подчиненных узлов меньше 32.
Количество целевых файлов менее 10000.

Answer 1

Вы спрашиваете о классической проблеме мультипроцессорного планирования.Статья в Википедии - хорошее начало для общего обзора алгоритма (http://en.wikipedia.org/wiki/Multiprocessor_scheduling).

Answer 2

Вот мысль. Сортировать пары (имя файла, размер) в порядке убывания. Затем, начиная с самого большого файла, назначьте каждый файл узлу с наименьшим совокупным весом файлов (разрывайте связи, как вам нравится). Подход "один для меня, другой для тебя".

Принимает O (MlogM) для сортировки записей файла M и O (M * N) для распространения (кто-то дважды это проверяет), но я думаю, что алгоритм дает хороший - оптимальный? - Результаты.

Редактировать: после проверки ссылки, предоставленной другим автором, выясняется, что это подход LPT, который используется в P, но который не является оптимальным с точки зрения получения максимально близкого среднего размера.

Answer 3

Если все длины рабочих единиц известны (оценены) заранее, это, в основном, становится проблемой упаковки бункеров (https://en.wikipedia.org/wiki/Bin_packing_problem).). Это решается эвристически с помощью алгоритмов «первого соответствия» и «наилучшего соответствия» (см. Ссылку) .

Answer 4

Я экспериментировал с распараллеливающими функциями сокращения , используя рекурсивные алгоритмы "разделяй и властвуй", и решил, что количество заданий, отправленных на узлы, удовлетворяет неравенству

l >= n / P^2

где l - количество заданий, n - размер исходной рабочей нагрузки и P - количество «узлов», рабочих, процессоров, как вы хотите их называть.

Для ситуаций на большинстве компьютеров& мобильные устройства n будут на много порядков больше, чем P. Вы хотите убедиться, что количество отдельных заданий не так велико, что вы тратите все свое время на их разделение и отправку работникам.