Эвристический алгоритм балансировки нагрузки между потоками
Я работаю над многопоточной программой, где у меня есть несколько рабочих потоков, выполняющих задачи разной длины. Я хочу сбалансировать нагрузку на задачи, чтобы они выполняли примерно одинаковый объем работы. Для каждой задачи Ti у меня есть число ci, которое обеспечивает хорошее приближение к объему работы, которая требуется для этой задачи.
Я ищу эффективный (O(N) N = количество задач или лучше) алгоритм, который даст мне "примерно" хороший баланс нагрузки, учитывая значения ci. Это не должно быть оптимальным, но я хотел бы иметь некоторые теоретические ограничения на то, насколько плохими будут полученные распределения.
Есть идеи?
6 ответов
Вы хотите реализовать алгоритм кражи работы. Каждый рабочий поток имеет двустороннюю очередь, новые задачи добавляются в конец самой маленькой очереди. Рабочие удаляют задачи из верхней части своей собственной очереди (разделение сверху / снизу уменьшает конкуренцию), когда у рабочего больше нет задач, он крадет задание из нижней части самой большой очереди. Это просто и хорошо работает, это алгоритм, на котором основана параллельная система Microsoft, поставляемая с.net4.0.
Результирующее распределение довольно хорошее, рабочие потоки останутся без работы, если во всей системе больше не будет доступных заданий.
В северном направлении Если вы хотите, чтобы какой-то пример кода был разорван, мой друг написал систему кражи работы для C#, которую вы можете найти здесь
Я склонен не пытаться заранее выяснить, как назначать задачи, а бросить их всех в общую рабочую очередь. Любой рабочий поток, которому больше нечего делать, извлекает следующую задачу из очереди и выполняет работу и проверяет очередь на следующую задачу.
Самый простой способ - отсортировать задания по убыванию по 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).
В 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-завершения (так что вы получите экспоненты где-то). Простой анализ на основе затрат, который я как-то описал выше, даст вам относительно хорошее приближение, если все отдельные задачи имеют небольшую стоимость по отношению к общей стоимости, которая будет распределена на каждый поток.
Хотя предложение о проблеме ранца полезно, вы сказали, что пытаетесь минимизировать чистое время выполнения. Использование подхода с рюкзаком потребует от вас увеличения размеров рюкзака до тех пор, пока вы не получите реальное решение - не очень эффективное.
Если чистое время выполнения ограничено самым длинным временем завершения среди всех потоков, работающих параллельно, я хочу назначить задачи, поэтому я минимизирую МАКСИМАЛЬНОЕ время работы для всех потоков. Это может привести к одному или нескольким потокам, которые не выполняют много работы, поэтому мы не "сбалансировали" работу. Если вы хотите сбалансировать работу, тогда это другая целевая функция. Например, вы можете минимизировать различия в работе между потоками.
Посмотрите в области планирования работы магазина. Если вы делаете это нечасто, я бы предложил использовать генетический алгоритм - если вам нужно делать это часто и более автоматизированным способом, я бы предложил выполнить небольшой поиск литературы по детерминированным алгоритмам. Надеюсь это поможет.
Я бы взглянул на алгоритмы для балансировки нагрузки, например