PB165 Grafy a site: Plánování s komunikací PB165 Grafy a sítě: Plánování s komunikací 1/23 Plánování s komunikací (^ Popis problému (2) Plánování seznamem (3) Heuristiky mapování 0 Shlukovací heuristiky PB165 Grafy a sítě: Plánování s komunikací 2/23 Plánování s komunikací a s precedencemi: přehled Příklady aplikací o plánování komunikujících úloh s precedencemi • acyklický graf precedenčních závislostí mezi úlohami • přenos dat po skončení úlohy následující úlohám • plánování acyklických workflows Algorimy o optimální (polynomiální složitost) • použitelné pouze pro velmi specializované problémy • obtížná rozšiřitelnost na obecné problémy • př. plánování na dvou procesorech, plánování stromů • heuristické plánování seznamem (list scheduling) heuristiky mapování (mapping heuristics) • shlukovací heuristiky (clustering heuristics) PB165 Grafy a sítě: Plánování s komunikací 3/23 Úlohy a komunikace Referenční dobu trvání p-, úlohy ; Precedenční omezení ;1 —> /2 Komunikace: sizenj2 • sizeiij2- velikost přenesených dat mezi úlohami ;1 a /2 o pokud existuje /l —> /2, pak size;iti2 > 0. jinak s/ze;i;/2 = 0 • pokud jsou /l a /2 zpracovány na stejném stroji, tak lze čas na komunikaci (a tedy i velikost přenášených dat) zanedbat Hranově a vrcholově ohodnocený acyklický orientovaný graf • vrcholy: úlohy • orientované hrany: precedenční vztahy mezi úlohami o ohodnocení hrany: velikost dat na komunikaci • ohodnocení vrcholu: referenční doba trvání PB165 Grafy a sítě: Plánování s komunikací Síť a komunikační zpoždění o Topologie sítě: příklady na uzlech dual-core procesor • transratejij2'- přenosová rychlost mezi sousedními stroji o setupmesgj: (inicializační) doba na poslání zprávy strojem j Komunikační zpoždění c(/l, Í2J1J2) pro poslání dat z úlohy ;1 úloze /2 ze stroje ji na sousední stroj j'2 c(il,i2,jl,j2) S/ze;i,/2 transratejij2 + setupmesgji PB165 Grafy a sítě: Plánování s komunikací 5/23 Doba provádění. Optimalizace. o speedj: rychlost zpracování strojem j o setuptaskj: (inicializační) doba na nastartování úlohy na stroji j • Doba provádění p,y úlohy / na stroji j: Pii =-----'—r + setuptaskj speedj 9 Objektivní funkce (performance measure) o minimalizace makespan (čas dokončení poslední úlohy) • do makespan se započítává: doba provádění + komunikační zpoždění PB165 Grafy a sítě: Plánování s komunikací 6/23 Plánování seznamem (list scheduling) Jednoduché efektivní algoritmy • založeny na seřazení úloh v prioritní frontě složitost algoritmu dána výpočtem priority Algoritmus plánování seznamem Q každému uzlu grafu přiřazena priorita prioritní fronta inicializována úlohami bez předchůdců úlohy ve frontě seřazeny v klesajícím pořadí dle priority 9 pokud existuje volný stroj a fronta je neprázdná, prováděj: ® odebrána první úloha z fronty O volný procesor je vybrán pro spuštění úlohy O jakmile provedeni všichni přímí předchůdci nějaké úlohy, tak je úloha přidána dle priority do fronty PB165 Grafy a sítě: Plánování s komunikací 7/23 Priority pro plánování seznamem • Délka cesty přes uzly /'i, /2 ... /„: n n—1 1/1/1 y^ Pi + w2 y^ size;j+\ ;=i ;=i • i/i/l, w/2: koeficienty určující poměr mezi dobou trvání a velikostí přenesených dat o Počáteční uzly: uzly bez předchůdců o Koncové uzly: uzly bez následníků Výpočet priority uzlu / (příklady) a úroveň (level) délka nejdelší cesty z uzlu / do koncového uzlu • ko-úroveň (co-level) délka nejdelší cesty z počátečního uzlu do uzlu / PB165 Grafy a sítě: Plánování s komunikací 8/23 Plánování seznamem: nastavení • Zanedbání doby na komunikaci: • pokud máme /l —> ;2 a úlohy /l a ;2 jsou prováděny na stejném stroji, tak dobu na komunikaci zanedbáme • Výběr stroje: • pro provádění úlohy /je vybrán stroj, na kterém bude úloha dokončena nejdříve (v případě více možností je vybrán stroj s nejmenším indexem) o k provádění jsou vybírány pouze volné stroje • pozor, je třeba brát v úvahu, zda na některém stroji nedojde k zanedbání komunikace PB165 Grafy a sítě: Plánování s komunikací 9/23 Plánování seznamem: parametry • Nechť sizeij přímo reprezentuje dobu na přenos dat • Předpokládejme, že i/i/l = w2 = 1 Rychlost stroje o pokud bychom předpokládali, že stroje mají stejnou rychlost, pak lze úlohy přímo plánovat dle zadané p; a size;ij2 • Koncový čas úlohy • spočítán na základě délky cesty (z p,- a sizen^) • lze uvažovat možné zanedbání komunikace (úloha je ve frontě až v okamžiku, když jsou všichni předchůdci dopočítáni, tj. známe jejich stroj a víme, zda dojde k zanedbání komunikace) 1 2 Astroje Astroje ĽT „ 2 cas i 0 12 3 4 5 6 se zanedbáním komunikace (na stejném stroji) čas 0 12 3 4 5 6 bez zanedbání komunikace (na různých strojích) PB165 Grafy a sítě: Plánování s komunikací 10/23 Plánování seznamem: príklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí (T)l (A3 l(T) komunikace VL \2 1/ zanedbána: V^ \~S l->4 O2 , O3 2->5 ©1 5->6 ^stroje 3 14 Fronta: V \3 NI \4 \5 \6 Úroveň: 11 k A 3\ ^ i 6 [61 čas « tmavší obdélníky v rozvrhu znázorňují dobu, kdy úloha běží • světlejší obdélníky odpovídají době na komunikaci pro danou úlohu • pro 5: komunikace 3^5, pro 6: komunikace 4^6 PB165 Grafy a sítě: Plánování s komunikací 11/23 Plánování seznamem: cvičení Vyřešte následující problém plánování s komunikací a s precedencemi pomocí plánování seznamem: • jsou dány 2 stroje se stejnou rychlostí o je dáno 6 úloh s dobou trvání Pl = 1,P2 = 1,P3 = 2,P4 = 1,P5 = 2,P6 = 1 • jsou dány precedence: 1 —> 2, 2 ^ 4,4 ^ 6,1 —> 3, 3 ^ 5, 5^6 • s/ze/1,/2 reprezentuje dobu na přenos dat a je zadán takto: sizeit2 = l,s/ze2,4 = 3,s/ze4;6 = 1, s/zei;3 = 2, s/ze3,5 = 4, s/ze5)6 = 2 PB165 Grafy a sítě: Plánování s komunikací 12/23 Plánování seznamem: diskuse Výběr úlohy s nejvyšší úrovní = výber úlohy na kritické ceste Problémy při použití heuristiky » změna kritické cesty -<= komunikační zpoždění závisí na alokaci úlohy -<= např. při alokaci na stejné stroje se zanedbatelným zpožděním nebo při nestejnoměrné vzdálenosti strojů (a počtu hopů) Řada heuristik založena na principu (několika) prioritních front • rozsáhlé modifikace priorit umožňují zachytit různé charakteristiky systému např. produkční plánovací systémy pro plánování úloh na počítačích PBSPro, SGE PB165 Grafy a sítě: Plánování s komunikací 13/23 Heuristiky mapování (mapping heuristics) • Modifikace plánování seznamem o Více uvažovány reálné parametry: • topologie sítě, rychlost procesoru, přenosová rychlost, ... • Doba provádění úlohy / na stroji j Pii =-----—t + setuptaski speed j • Komunikační zpoždění c(/l, Í2J1J2) = í-------—------h setupmesg j x hopsjij2 + contdelayjij2 • předpokládán konstantní transrate a setupmesg o hopsjij2'- počet hopů mezi stroji ji a j2, (délka nejkratší cesty mezi stroji při jednotkovém ohodnocení hran) • contdelayjij2'- zpoždění dané zatížením linky mezi ji a _/2 (contention delay) PB165 Grafy a sítě: Plánování s komunikací 14/23 Heuristiky mapování (mapping heuristics) o Konstruována a udržována směrovací tabulka obsahující o odhadované hodnoty p,y a c(il,i2,jl,j2) o pro každý procesor • počet hopů, preferovaná linka pro daný cíl, zpoždění dané zatížením • Úlohy plánovány podle nejvyšší úrovně (podobně jako při plánování seznamem), v případě nejednoznačnosti vybrána úloha s větším množstvím přímých následníků 8 Jakmile jsou dokončeni všichni předchůdci úlohy, tak je úloha naplánována na stroj, kde nejdříve skončí • Koncový čas úlohy na stroji spočítán z • rychlost procesoru, přenosová rychlost, vybraná linka, počet hopů, zpoždění dané zatížením linky PB165 Grafy a sítě: Plánování s komunikací 15/23 Plánování se shlukovacími heuristikami (clustering heuristics) • Plánování řeší G) alokace úloh na stroje Q seřazení úloh na stroji / umístění úloh v čase Shlukovací heuristiky: řeší alokaci úloh na stroje • Shluk: množina úloh, která bude prováděna na stejném stroji • Princip plánování založeného na shlukování Q) Shlukování úloh na nelimitovaný počet plně propojených procesorů © Namapování shluků a jejich úloh na daný počet procesorů (m) prováděním následujících operací spojování shluků: pokud je počet shluků vyšší než m • fyzické mapování: přiřazení shluků na procesory tak, aby byla minimalizována komunikace (na této úrovni uvažována reálná konektivita mezi stroji) » uspořádání úloh: úlohy jsou na stroji prováděny tak, by byly splněny závislosti mezi úlohami PB165 Grafy a sítě: Plánování s komunikací 16/23 Shlukovací heuristiky o Shlukovací heuristiky • bez backtrackingu (abychom se vyhnuly vysoké složitosti), tj. jakmile jsou jednou shluky spojeny nelze je zpětně rozpojit • Iniciálně: jedna úloha = jeden shluk • Typický krok heuristiky • spojení shluků + vynulování hrany, která je spojuje • vynulování hrany: úlohy prováděny na stejném procesoru, kde je čas na komunikaci zanedbatelný • Kritérium pro výběr hrany na nulování redukce paralelního času rozvrhu PB165 Grafy a sítě: Plánování s komunikací 17/23 Naplánovaný graf úloh Naplánovaný graf úloh » graf úloh zahrnující aktuální vynulování hran • úlohy v jednom shluku jsou seřazeny (jako na procesoru) dle nejvyšší úrovně původní graf úloh se 3 shluky naplánovaný graf úloh PB165 Grafy a sítě: Plánování s komunikací Paralelní cas a dominantní posloupnost o Připomenutí: délka cesty přes uzly ;'i, 12 ... in- n n—l w\ y^ Pi + w2 y^ s/ze/)(-+i ;=i ;=i o Dominantní posloupnost: nejdelší cesta v naplánovaném grafu úloh o Paralelní čas rozvrhu: doba nutná na provedení dominantní posloupnosti o Pokud wl = w2 = 1 a size-, j reprezentuje dobu na přenos => délka cesty odpovídá době na provedení úloh na cestě =3- paralelní čas rozvrhu = délka cesty dominantní posloupnosti PB165 Grafy a sítě: Plánování s komunikací 19/23 Dominantní posloupnost: príklad Dominantní posloupnost 1,3,4,5,6,7 s délkou 10, tj. paralelní čas rozvrhu je 10 Odpovídající rozvrh na 3 strojích: stroje 3 3 4 5 6 7 7 1 2 čas PB165 Grafy a sítě: Plánování s komunikací 20/23 Algoritmus shlukovací heuristiky O Inicializace: všechny hrany označeny jako nevyzkoušené každá úloha tvoří jeden shluk © Seřazení všech hran v grafu úloh v klesajícím pořadí dle komunikační ceny 9 REPEAT 9 vynulování největší nevyzkoušené hrany v seřazeném seznamu, pokud nevzroste paralelní čas @ hrana je označena jako vyzkoušená Q když jsou spojeny dva shluky, úlohy jsou uspořádány dle nejvyšší úrovně UNTIL všechny hrany jsou vyzkoušené Komentář: podobně jako existují různé metody plánování seznamem, tak existují různé varianty shlukovacích heuristik PB165 Grafy a sítě: Plánování s komunikací 21/23 Shlukovací heuristiky: príklad Problém: Řešení pomocí algoritmu: seřazení hran, postupné zkoušení na vynulování a spojování shluků: 12 (vynulována, shluk 12), 34 (vynulována, shluk 34), 35 (vynulována, shluk 345), 27 (vynulována, shluk 127), 46 (vynulována, shluk 3456), 56 (vynulována), 13 (nevynulována, paralelní čas by z 10 pro dominantní cestu 1,3,4,5,6,7 vzrostl na 13 s dominantní cestou 1,2,3,4,5,6,7), 67 (nevynulována stejně jako 13) PB165 Grafy a sítě: Plánování s komunikací 22/23 Shlukovaci heuristiky: cvičení Vyřešte cvičení z kapitoly plánování seznamem pomocí shlukovaci heuristiky. Je v řešení nějaký rozdíl? (nápověda: ano, u shlukovacích heuristik víme, na kterém stroji bude úloha zpracovávána předem, a proto je možné zahájit některé komunikace dříve, a tedy rozvrh skončí dříve) PB165 Grafy a sítě: Plánování s komunikací 23/23