Неоднородное самое раннее время окончания

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

Алгоритм

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

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

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

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

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

Постановка задач работникам

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

Обсуждение

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

Код

Реализации HEFT доступны на GitHub на языках программирования C++ , ^{[ 5 ]} и Питон . ^{[ 6 ]}

Ссылки

^ Топчуоглу, Халук; Харири, Салим; Ву, М. (2002). «Эффективное и несложное планирование задач для гетерогенных вычислений». Транзакции IEEE в параллельных и распределенных системах . 13 (3): 260–274. CiteSeerX 10.1.1.119.122 . дои : 10.1109/71.993206 . S2CID 17773509 .
^ Чжао, Хэнань; Сакеллариу, Ризос (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 .
^ Биттенкур, Луис Ф; Сакеллариу, Ризос; Мадейра, Эдмундо Р.М. (2010). Планирование DAG с использованием упреждающего варианта алгоритма неоднородного времени самого раннего окончания . Конференция Euromicro по параллельной, распределенной и сетевой обработке. CiteSeerX 10.1.1.703.3063 . дои : 10.1109/PDP.2010.56 .
^ Арабнежад, Хамид; Барбоса, Хорхе Г. (2014). «Алгоритм планирования списка для гетерогенных систем с помощью оптимистической таблицы затрат» . Транзакции IEEE в параллельных и распределенных системах . 25 (3): 682–694. дои : 10.1109/TPDS.2013.57 . ISSN 1045-9219 .
^ Мишра, Юврадж (VanillaBase1lb) (2021). «Реализация неоднородного планирования первого времени окончания в C++» . Гитхаб . {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )
^ Роклин, Мэтью (mrocklin) (2013). «Эвристика статического планирования» . Гитхаб .

[1] Топчуоглу, Халук; Харири, Салим; Ву, М. (2002). «Эффективное и несложное планирование задач для гетерогенных вычислений». Транзакции IEEE в параллельных и распределенных системах . 13 (3): 260–274. CiteSeerX 10.1.1.119.122 . дои : 10.1109/71.993206 . S2CID 17773509 .

[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 .

[4] Арабнежад, Хамид; Барбоса, Хорхе Г. (2014). «Алгоритм планирования списка для гетерогенных систем с помощью оптимистической таблицы затрат» . Транзакции IEEE в параллельных и распределенных системах . 25 (3): 682–694. дои : 10.1109/TPDS.2013.57 . ISSN 1045-9219 .

[5] Мишра, Юврадж (VanillaBase1lb) (2021). «Реализация неоднородного планирования первого времени окончания в C++» . Гитхаб . {{cite web}}: CS1 maint: числовые имена: список авторов ( ссылка )

[6] Роклин, Мэтью (mrocklin) (2013). «Эвристика статического планирования» . Гитхаб .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]