Гетерогенді ерте аяқталу уақыты - Heterogeneous Earliest Finish Time

Гетерогенді ерте аяқталу уақыты (немесе HEFT) - бұл эвристикалық тәуелді тапсырмалар жиынтығын желіге жоспарлау гетерогенді байланыс уақытын ескеретін жұмысшылар.[1] Кірістер үшін HEFT а ретінде ұсынылған тапсырмалар жиынтығын алады бағытталған ациклдік график, жұмысшылар жиынтығы, әр жұмысшының әрқайсысының тапсырмасын орындау уақыты және әр жұп арасындағы жұмыс нәтижелерін әр баладан әр балаға жеткізу уақыты. Ол төмен түседі тізімді жоспарлау алгоритмдер.

Алгоритм

HEFT екі фазада жүзеге асырылады.

Тапсырмаларға басымдық беру

Бірінші кезеңде әр тапсырмаға басымдық беріледі. Әр тапсырманың басымдығы әдетте келесідей рекурсивті түрде анықталатын «жоғары дәрежесі» ретінде белгіленеді

қайда білдіреді тапсырма, орташа болып табылады есептеу барлық процессорлар арасында i жұмыс құны, бұл бірден тапсырмаға тәуелді барлық жұмыс жиынтығы , және - бұл жұмыс орындары арасында ауысатын айнымалылардың орташа байланыс құны және барлық жұмысшылар жұбы арасында. Есептеу екенін ескеріңіз оның барлық балаларының дәрежесін есептеуге байланысты. Жоғары деңгей кез-келген тапсырманың есептеу аяқталғанға дейінгі қашықтығын білдіреді. Сияқты орташа шамалар үшін әр түрлі орташа көрсеткіштер әртүрлі нәтиже беруі мүмкін.[2]

Жұмысшыларға тапсырмалар беру

Екінші кезеңде жұмысшыларға міндеттер жүктеледі. Енді барлық міндеттерге басымдық берілгендіктен, біз әрқайсысын жоғары басымдылықтан бастап қарастырамыз және жоспарлаймыз. Барлық тәуелді тапсырмалар аяқталған ең жоғары басымдығы бар тапсырма жұмысшыға белгіленеді, ол осы тапсырманың ең ерте аяқталуына әкеледі. Бұл аяқталу уақыты жұмысшыға барлық қажетті кірістерді жіберу үшін байланыс уақытына, жұмысшының тапсырмасын есептеу уақытына және сол процессор қол жетімді болатын уақытқа байланысты болады (ол басқа тапсырмамен айналысуы мүмкін). HEFT жоспарланған тапсырмалар арасындағы жеткілікті мөлшердегі алшақтықтарды толтыратын кірістіруге негізделген саясатты қолданады.

Талқылау

HEFT арасында құрметке ие эвристикалық алгоритмдер бұл мәселе үшін. Алайда, күрделі жағдайларда оңтайлы жоспарлауды оңай таба алмауы мүмкін. HEFT - бұл ашкөздік алгоритмі және ұзақ мерзімді пайда үшін қысқа мерзімді құрбандық шалуға қабілетсіз. Жоспарлау шешімінің сапасын жақсарту үшін алда күтілетін алгоритмнің модификациясы жоспарлау өнімділігі үшін жұмыс уақыты үшін пайдаланылуы мүмкін.[3]

Код

A Python HEFT қолдану мүмкіндігі бар github-та

Әдебиеттер тізімі

  1. ^ Топчуоглу, Халук; Харири, Салим; Wu, M. (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). Аяқталуының алгоритмінің гетерогенді алгоритмінің түрін қолдану арқылы кесте құру. Параллельді, үлестірілген және желілік өңдеу бойынша Euromicro конференциясы. CiteSeerX  10.1.1.703.3063. дои:10.1109 / PDP.2010.56.