Эвристический алгоритм балансировки нагрузки между потоками

Question

Я работаю над многопоточной программой, где у меня есть несколько рабочих потоков, выполняющих задачи неравной длины. Я хочу сбалансировать нагрузку, чтобы убедиться, что они выполняют примерно одинаковый объем работы. Для каждой задачи T _i у меня есть число c _i , которое обеспечивает хорошее приближение к объему работы, которая требуется для этой задачи.

Я ищу эффективный (O (N) N = количество задач или лучше) алгоритм, который даст мне "примерно" хороший баланс нагрузки, учитывая значения c _i . Это не обязательно должно быть оптимально, но я бы хотел иметь некоторые теоретические границы того, насколько плохими будут полученные распределения.

Есть идеи?

Answer 1

Вы хотите реализовать алгоритм кражи работы . Каждый рабочий поток имеет двустороннюю очередь, новые задачи добавляются в конец самой маленькой очереди. Рабочие удаляют задачи из верхней части своей собственной очереди (разделение сверху / снизу снижает конкуренцию), когда у работника больше нет задач, он крадет задание из нижней части самой большой очереди. Это просто и хорошо работает, это алгоритм, на котором основана параллельная система Microsoft, поставляемая с .net4.0.

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

Nb. Если вы хотите, чтобы какой-то пример кода был разорван, мой друг написал рабочую систему кражи для C #, которую вы можете найти здесь

Answer 2

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

Answer 3

Самый простой способ - отсортировать задания по убыванию по p_i (но это O (n log n)) и сделать это:

1. Для каждого потока у нас есть время выполнения e_n = 0.
2. Для каждой задачи я нахожу нить с минимальным заданием 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). </p>

Answer 4

Хотя предложение о проблеме ранца полезно, вы сказали, что пытаетесь минимизировать чистое время выполнения. Использование подхода с рюкзаком потребует от вас увеличения размеров рюкзака до тех пор, пока вы не получите приемлемое решение - не очень эффективное.

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

Посмотрите в области планирования работы магазина. Если вы делаете это нечасто, я бы предложил использовать генетический алгоритм - если вам нужно делать это часто и более автоматизированным способом, я бы предложил выполнить небольшой поиск литературы по детерминированным алгоритмам. Надеюсь это поможет.

Answer 5

Я бы взглянул на алгоритмы распределения нагрузки, например

http://www.ieee802.org/3/trunk_study/february98/congdon.pdf

http://publib.boulder.ibm.com/infocenter/cicstg/v6r0m0/index.jsp?topic=/com.ibm.cicstg600.doc/ccllal0292.htm

Answer 6

В O (N) это кажется легким.

Дайте каждой теме несколько «очков». Пусть p_i точек, выделенных для потока T_i. Для каждой задачи выберите поток с наибольшим значением p_i и вычтите стоимость задачи из p_i. Затем вам просто нужно отслеживать потоки, упорядоченные по счету, что тривиально за O (N) время и может быть легко выполнено за O (log N) с сбалансированным деревом.

Для непрерывной работы не существует минимума в p_i. Если вы хотите избежать того, чтобы баллы не доходили до -inf, просто регулярно добавляйте произвольную сумму P ко всем баллам (одинаковую сумму для всех баллов).

Редактировать: Я неправильно указал N. Выше, N - количество потоков, вопреки заданному вопросу. Если N = количество задач и T = количество потоков, это приводит к стоимости O (N * log T). Если T «маленький», это близко к O (N).

Редактировать 2: Если все задачи известны заранее, а также количество потоков, то я думаю, что вычисление оптимального планирования сродни проблеме ранца , и это является, в общем, NP-полным (так что вы получите где-нибудь экспоненты). Простой анализ, основанный на затратах, который я как-то описал выше, даст вам относительно хорошее приближение, если все отдельные задачи имеют небольшую стоимость по отношению к общей стоимости, которая будет выделена для каждого потока.