Эвристический алгоритм для выравнивания нагрузки среди потоков
Я работаю над многопоточной программой, где у меня есть много рабочих потоков, выполняющих задачи неравной длины. Я хочу к балансу загрузки задачи гарантировать, чтобы они сделали примерно тот же объем работы. Для каждой задачи Ti у меня есть число ci, который обеспечивает хорошее приближение на сумму работы, которая требуется для той задачи.
Я ищу эффективное (O (N) N = количество задач или лучше) алгоритм, который даст мне "примерно" хороший баланс загрузки, учитывая значения ci. Это не должно быть оптимально, но я хотел бы смочь иметь некоторые теоретические границы о том, как плохо получающиеся выделения.
Какие-либо идеи?
6 ответов
Вы хотите реализовать алгоритм кражи работы . Каждый рабочий поток имеет двустороннюю очередь, новые задачи добавляются в конец самой маленькой очереди. Рабочие удаляют задачи из верхней части своей очереди (разделение сверху и снизу снижает конкуренцию), когда у рабочего больше нет заданий, он крадет задание из нижней части самой большой очереди. Это просто и хорошо работает, это алгоритм, на котором, я полагаю, основана параллельная система Microsoft, идущая с .net4.0.
Полученное распределение довольно хорошее, рабочие потоки останутся без работы только в том случае, если во всей системе больше нет доступных заданий.
Nb. Если вы хотите, чтобы какой-то пример кода разорвался на части, мой друг написал систему кражи работы для C #, которую вы можете найти здесь
Хотя предложение относительно проблемы с рюкзаком полезно, вы сказали, что пытаетесь минимизировать чистое время выполнения. Использование ранцевого подхода потребует от вас увеличения размеров рюкзака до тех пор, пока вы не получите приемлемое решение - не очень эффективное.
Если чистое время выполнения ограничено наибольшим временем завершения среди всех потоков, работающих параллельно, я хочу назначить задачи, чтобы МИНИМИЗИРОВАТЬ МАКСИМАЛЬНОЕ время работы для всех потоков. Это может привести к тому, что один или несколько потоков не будут выполнять много работы, поэтому мы на самом деле не «балансируем» работу. Если вы хотите сбалансировать работу, это другая целевая функция. Например, вы можете захотеть минимизировать различия в работе между потоками.
Посмотрите в области планирования работы цеха.Если вы делаете это нечасто, я бы посоветовал использовать генетический алгоритм - если вам нужно делать это часто и более автоматизированным образом, я бы посоветовал провести небольшой поиск в литературе для детерминированных алгоритмов. Надеюсь это поможет.
Я бы посмотрел на алгоритмы распределения нагрузки, например,
В O(N) это кажется простым.
Дадим каждому потоку несколько "очков". Пусть p_i - очки, выделенные потоку T_i. Для каждой задачи выберите поток с наибольшим p_i и вычтите стоимость задачи из p_i. Затем вам нужно только отслеживать потоки, упорядоченные по стоимости, что тривиально за время O(N), и может быть легко сделано за O(log N) со сбалансированным деревом.
Для непрерывной работы не существует минимума в p_i. Если вы хотите избежать ухода оценок в сторону -inf, просто регулярно добавляйте произвольное количество P ко всем оценкам (одинаковое количество для всех оценок).
Edit: Я перепутал N. Выше N - это количество потоков, что противоречит заданному вопросу. При N = количество задач, и T = количество потоков, это приводит к O(N*log T) стоимости. Если T "маленький", то это близко к O(N).
Edit 2: Если все задачи известны заранее, также как и количество потоков, то я думаю, что вычисление оптимального планирования сродни проблеме ранца, и она, во всех общих чертах, NP-полна (так что где-то вы получите экспоненты). Простой анализ на основе затрат, как я описал выше, даст вам относительно хорошее приближение до тех пор, пока все отдельные задачи имеют небольшую стоимость по отношению к общей стоимости, которая должна быть распределена на каждый поток.
Самый простой способ - отсортировать задания по убыванию p_i (но это O (n log n)) и сделать следующее:
- Для каждого потока у нас есть расчетное время выполнения e_n = 0.
- Для каждой задачи я нахожу поток с минимальной задачей e_n enque и e_n = e_n + p_i.
Этот алгоритм должен дать вам лучшие результаты, но с временем O (N M), где N - количество задач, а M - количество потоков. Общая стоимость решения составляет O (N log N + N M), поэтому для M << N равно O (N log N), а для M около N - O (n ^ 2).
Я склонен не пытаться заранее выяснить, как назначить задачи, а выбросить их все в общую рабочую очередь. Любой рабочий поток, которому больше нечего делать, захватывает следующую задачу из очереди, выполняет работу и проверяет очередь для следующей задачи.