Неоднородное самое раннее время окончания - Heterogeneous Earliest Finish Time

Неоднородное самое раннее время окончания (или HEFT) - это эвристический для планирования набора зависимых задач в сети гетерогенный работники с учетом времени общения.^[1] В качестве входных данных HEFT принимает набор задач, представленных в виде ориентированный ациклический граф, набор рабочих процессов, время выполнения каждой задачи для каждого рабочего и время передачи результатов каждого задания каждому из его дочерних элементов между каждой парой рабочих. Он происходит от список расписаний алгоритмы.

Алгоритм

HEFT выполняется в два этапа.

Приоритезация задач

На первом этапе каждой задаче дается приоритет. Приоритет каждой задачи ${\displaystyle n_{i}}$ обычно обозначается как "восходящий ранг", который рекурсивно определяется следующим образом

${\displaystyle rank_{u}(n_{i})={\overline {w_{i}}}+\max _{n_{j}\in succ(n_{i})}({\overline {c_{i,j}}}+rank_{u}(n_{j}))}$

куда ${\displaystyle n_{i}}$ представляет ${\displaystyle i^{th}}$ задача, ${\displaystyle {\overline {w_{i}}}}$ средний вычисление стоимость работы i среди всех процессоров, ${\displaystyle succ(n_{i})}$ это совокупность всех работ, которые непосредственно зависят от задачи ${\displaystyle n_{i}}$, и ${\displaystyle {\overline {c_{i,j}}}}$ средняя стоимость передачи переменных между заданиями ${\displaystyle n_{i}}$ и ${\displaystyle n_{j}}$ между всеми парами рабочих. Обратите внимание, что вычисление ${\displaystyle rank_{u}(n_{i})}$ зависит от вычисления ранга всех его потомков. Восходящий ранг означает ожидаемое расстояние любой задачи от конца вычисления. Для средних величин типа ${\displaystyle {\overline {w_{i}}}}$ разные средние значения могут дать разные результаты.^[2]

Назначение задач работникам

На втором этапе перед рабочими ставятся задачи. Теперь, когда все задачи расставлены по приоритетам, мы рассматриваем и планируем каждую, начиная с наивысшего приоритета. Задача с наивысшим приоритетом, для которой завершены все зависимые задачи, запланирована на работника, что приведет к самому раннему времени завершения этой задачи. Это время завершения зависит от времени связи для отправки всех необходимых входных данных работнику, времени вычисления задачи на работнике и времени, когда этот процессор становится доступным (он может быть занят другой задачей). HEFT использует политику на основе вставки, которая заполняет достаточно большие промежутки между уже запланированными задачами.

Обсуждение

HEFT пользуется уважением среди эвристические алгоритмы для этой проблемы. Однако в сложных ситуациях может легко не найти оптимального расписания. HEFT - это, по сути, жадный алгоритм, неспособный приносить краткосрочные жертвы ради долгосрочных выгод. Модификация алгоритма, которая смотрит вперед, чтобы лучше оценить качество решения по планированию, может использоваться для обмена времени выполнения на производительность планирования.^[3]

Код

А Python доступна реализация HEFT на github

Рекомендации

1. Топчуоглу, Халук; Харири, Салим; Ву М. (2002). «Эффективное и несложное планирование задач для гетерогенных вычислений». Транзакции IEEE в параллельных и распределенных системах. 13 (3): 260–274. CiteSeerX  10.1.1.119.122. Дои:10.1109/71.993206.
2. Чжао, Хэнань; Сакеллариу, Ризос (2003). Экспериментальное исследование функции ранга гетерогенного алгоритма планирования времени самого раннего финиша. Параллельная обработка Euro-Par 2003. Конспект лекций по информатике. 2790. С. 189–194. CiteSeerX  10.1.1.329.9320. Дои:10.1007/978-3-540-45209-6_28. ISBN  978-3-540-40788-1.
3. Биттенкур, Луис Ф; Сакеллариу, Ризос; Мадейра, Эдмундо Р. М. (2010). Планирование DAG с использованием опережающего варианта гетерогенного алгоритма самого раннего времени окончания. Конференция Euromicro по параллельной, распределенной и сетевой обработке. CiteSeerX  10.1.1.703.3063. Дои:10.1109 / PDP.2010.56.