PB165 Grafy a sítě: 8. Plánování s komunikací PB165 Grafy a sítě: 8. Plánování s komunikací 1/39 ooooooooooooooooooooo Plánování s komunikací Q Plánování s komunikací a s precedencemi • Popis problému • Plánování seznamem 9 Heuristiky mapování » Shlukovací heuristiky Q Paralelní úlohy s průběžnou komunikací • Popis problému • Rozdělení grafu PB165 Grafy a sítě: 8. Plánování s komunikací 2/39 _ooo oooooooooooooooo Plánování s komunikac, jmi: přehled Příklady aplikací • plánování paralelních úloh s precedencemi • acyklický graf precedencních závislostí mezi úlohami • přenos dat po skončení úlohy následující úlohám • plánování acyklických workflows Algorimy • 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ě: 8. Plánování s komunikací 3/39 o«ooooooooooooooooooo Úlohy a komunikace Referenční dobu trvání p; úlohy i Precedenční omezení ;1 —> /2 Komunikace: $izeaj2 • sizenj2'- velikost přenesených dat mezi úlohami /l a /2 a pokud existuje /l —s- /2, pak s/ze;i;/2 > 0, jinak size;ij2 = 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 • ohodnocení hrany: velikost dat na komunikaci • ohodnocení vrcholu: referenční doba trvání PB165 Grafy a sítě: 8. Plánování s komunikaci Plánovaní s komunikaci a s precedencemi oo«oooooooooooooooooo Paralelní úlohy s pri. OOOOOOO bezno u komu mkaci Síť a komunikační zpo; • Topologie sítě: příklady ry na uzlech dual-core procesor • transratejij2'- přenosová rychlost mezi sousedními stroji • setupmesgj: (inicializační) doba na poslání zprávy strojem j • Komunikační zpoždění c(/l, i2,jl,j2) pro poslání dat z úlohy /l úloze Í2 ze stroje ji na sousední stroj j2 c(il,i2,jl,j2) S/ze;i,/2 transratejij2 + setupmesgji PB165 Grafy a sítě: 8. Plánování s komunikací 5/39 Plánovaní s komunikaci a s precedencemi ooo«ooooooooooooooooo Paralelní úlohy s průběžnou komu OOOOOOO mkaci Doba provádění. Optir • speed]-, rychlost zpracování strojem j • setuptaskj: (inicializační) doba na nastartování úlohy na stroji j • Doba provádění p,y úlohy / na stroji j: Pi Pü speedj + setuptaskj • Objektivní funkce (performance measure) • 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ě: 8. Plánování s komunikací 6/39 •oooooooooooooooo Plánování seznamem (list algoritmus Jednoduché efektivní algoritmy a založeny na seřazení úloh v prioritní frontě » složitost algoritmu dána výpočtem priority Algoritmus O 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 Q dokud je fronta neprázdná, prováděj: O odebrána úloha zepředu z fronty O je vybrán (nejlepší) volný procesor pro spuštění úlohy • vybraný procesor může např. minimalizovat komunikaci předchůdci úlohy Q 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ě: 8. Plánování s komunikací • Délka cesty přes uzly i\, \i ■ ■ ■ in'- n n—1 1/1/1 y^ Pi + w2 y^ size;j+\ ;=i 1=1 • i/i/l, 1/1/2: koeficienty určující poměr mezi dobou trvání a velikostí přenesených dat • Počáteční uzly: uzly bez předchůdců a Koncové uzly: uzly bez následníků Výpočet priority uzlu (příklady) • ú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ě: 8. Plánování s komunikací 8/39 oooooo»oooooooooooooo Plánování seznamem: mim • Zanedbání doby na komunikaci: • pokud /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 procesor, na kterém bude úloha dokončena nejdříve (v případě více možností je vybrán stroj s nejmenším indexem) • pozor, je třeba brát v úvahu, zda na některém stroji nedojde k zanedbání komunikace PB165 Grafy a sítě: 8. Plánování s komunikací 9/39 ooooooo«ooooooooooooo Plánování seznamem: • Nechť size;j přímo reprezentuje dobu na přenos dat • Předpokládejme, že i/i/l = w2 = 1 • Rychlost stroje • pokud bychom předpokládali, že stroje mají stejnou rychlost, pak lze úlohy přímo rozvrhovat dle zadané p; a sizenj2 1 Astroje s__ cas 0 12 3 4 5 6 • Koncový čas úlohy • spočítán na základě délky cesty (z p,- a sizenji) • 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) PB165 Grafy a sítě: 8. Plánování s komunikací 10/39 OOOOOOOO0OOOOOOOOOOOO Plánování seznamem: mám Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí ©1 ©3 !© \ \ y @2 ©3 ©i PB165 Grafy a sítě: 8. Plánování s komunikací 11/39 OOOOOOOO0OOOOOOOOOOOO Plánování seznamem: mám Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí ©I ©3 !© \ \ y "7)2 (ľ)3 ©1 Fronta: ¥ \3 1 nStr°Je Úroveň: li k 7 cas —>- PB165 Grafy a sítě: 8. Plánování s komunikací 12/39 OOOOOOOO0OOOOOOOOOOOO Plánování seznamem: mám Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí ©I ©3 !© \ \ y "7)2 (ľ)3 ©1 Fronta: \ \3 NI |stroje úroveň: íl & A 3JT cas —>- PB165 Grafy a sítě: 8. Plánování s komunikací 13/39 OOOOOOOO0OOOOOOOOOOOO Plánování seznamem: mám Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí (T)l (T)3 l(T) komunikace VL \2 1/ zanedbána: ^Ä \->/ l->4 T)2 (5)3 ©1 Fronta: ¥ \3 NI \4 Úroveň: íl k A S\ yistroje 3TTTX cas —>- PB165 Grafy a sítě: 8. Plánování s komunikací 14/39 OOOOOOOO0OOOOOOOOOOOO Plánování seznamem: mám Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí (T)l (T)3 l(T) komunikace VL \2 1/ zanedbána: ^Ä \->/ l->4 ^)2 ©3 2->5 ©1 Fronta: ¥ \3 NI \4 \5 Úroveň: li Ifck A S\ & yistroje 3TTTX cas —>- PB165 Grafy a sítě: 8. Plánování s komunikací 15/39 OOOOOOOO0OOOOOOOOOOOO Plánování seznamem: mám Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí (T)l (T)3 l(T) komunikace VL \2 1/ zanedbána: ^Ä \->/ l->4 ^)2 ©3 2->5 V V 5->6 ©1 Fronta: ¥ \3 NI \d \5 \6 Istroje úroveň. Ji k A ^ ^ i 3TTTX [61 čas PB165 Grafy a sítě: 8. Plánování s komunikací 16/39 ooooooooo«ooooooooooo Plánování seznamem: uvalili 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í • 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 • size;ij2 reprezentuje dobu na přenos dat a je zadán takto: size\t2 = 1, s/ze2,4 = 3, s/ze4;6 = 1, s/zei;3 = 2, sizes* = 4, s/ze5fi = 2 PB165 Grafy a sítě: 8. Plánování s komunikací 17/39 OOOOOOOOOO0OOOOOOOOOO Plánování seznamem: Mmá Výběr úlohy s nejvyšší úrovní = výběr úlohy na kritické cestě 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ů) Rada heuristik založena na principu (několika) prioritních front • rozsáhlé modifikace priorit • např. produkční plánovací systémy pro plánování úloh na počítačích PBSPro, SGE PB165 Grafy a sítě: 8. Plánování s komunikací 18/39 ooooooooooo«ooooooooo Heuristiky mapování (maf • Modifikace plánování seznamem • Více uvažovány reálné parametry: • topologie sítě, rychlost procesoru, přenosová rychlost, • Doba provádění úlohy ; na stroji j Pij^ • Komunikační zpoždění sizen j2 speed j + setuptaskj c(ií,i2,jí,j2) + setupmesg xhopsji ;2+contdeiay;i n transrate ) • předpokládán konstantní transrate a setupmesg • 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 j2 (contention delay) PB165 Grafy a sítě: 8. Plánování s komunikací 19/39 OOOOOOOOOOOO0OOOOOOOO Heuristiky mapování (maf • Konstruována a udržována směrovací tabulka obsahující • odhadované hodnoty p,y a c(;l, Í2J1J2) 9 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ů • 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ě: 8. Plánování s komunikací 20/39 ooooooooooooo«ooooooo Rozvrhování se shlukovao (clustering heuristics) • Rozvrhování řeší O alokace úloh na stroje O 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 rozvrhování založeného na shlukování O Shlukování úloh na nelimitovaný počet plně propojených procesorů O 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ě: 8. Plánování s komunikaci 21/39 oooooooooooooo»oooooo Shlukovací heuristiky • 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ě: 8. Plánování s komunikací 22/39 ooooooooooc oo«ooooo 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ě: 8. Plánování s komunikací 23/39 Plánovaní s komunikaci a s precedencemi oooooooooooooooo«oooo Paralelní úlohy s průběžnou komu OOOOOOO mkaci Shlukovací heuristiky Paralelní čas a dominantní p osloupnosl _ • Připomenutí: délka cesty přes uzly ;'i, "12 ... /'„: n-l 1/1/1 y^ pi + n/2 y^ s/ze/)f-+i ;=i ;=i • Dominantní posloupnost: nejdelší cesta v naplánovaném grafu úloh • Paralelní čas rozvrhu: doba nutná na provedení dominantní posloupnosti • Pokud n/1 = M/2 = 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ě: 8. Plánování s komunikací 24/39 ooooooooooooooooo«ooo Dominantní posloupnost: mam Dominantní posloupnost 1,3,4,5,6,7 s délkou 10, tj. paralelní čas rozvrhu je 10 stroje Odpovídající rozvrh na 3 strojích: PB165 Grafy a sítě: 8. Plánování s komunikací 3 4 5 6 m cas 5/39 oooooooooooooooooo«oo ooooooo Algoritmus shlukovací 1 O Inicializace: všechny hrany označeny jako nevyzkoušené každá úloha tvoří jeden shluk O Seřazení všech hran v grafu úloh v klesajícím pořadí dle komunikační ceny Q REPEAT O vynulování největší nevyzkoušené hrany v seřazeném seznamu, pokud nevzroste paralelní čas O hrana je označena jako vyzkoušená 9 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ě: 8. Plánování s komunikací 26/39 ooooooooooc oooooo»o Shlukovací heuristiky: Problém: Etil Řešení pomocí algoritmu: Postup: 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ě: 8. Plánování s komunikací 27/39 oooooooooooooooooooo« Shlukovací heuristiky: Balil Vyřešte cvičení z kapitoly plánování seznamem pomocí shlukovací 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ě: 8. Plánování s komunikací 28/39 ooooooooooooooooooooo Paralelní úlohy s pi\ Paralelní aplikace • n komunikujících úloh 9 m procesorů • několik úloh prováděno zároveň na každém procesoru Grafová reprezentace • hranově a vrcholově ohodnocený neorientovaný graf • ohodnocené vrcholy: úlohy s danou výpočetní náročností • ohodnocené hrany: průběžně komunikující úlohy s komunikační náročností PB165 Grafy a sítě: 8. Plánování s komunikací 29/39 ooooooooooooooooooooo Paralelní úlohy s pi\ Paralelní aplikace • n komunikujících úloh 9 m procesorů • několik úloh prováděno zároveň na každém procesoru Grafová reprezentace • hranově a vrcholově ohodnocený neorientovaný graf • ohodnocené vrcholy: úlohy s danou výpočetní náročností • ohodnocené hrany: průběžně komunikující úlohy s komunikační náročností PB165 Grafy a sítě: 8. Plánování s komunikací Vyvažování zátěže: přiřazení úloh na procesory tak, aby byla • vyvážená zátěž jednotlivých procesorů • minimalizována komunikace úloh na různých procesorech 30/39 ooooooooooooooooooooo Rozdělení grafu (gr • Formulace problému vyvažování zátěže jako problému rozdělení grafu • Rozdělení grafu G = (V, V) na V = Vx U • • • U Vm tak, že je • součet ohodnocení vrcholů „zhruba stejný" » součet ohodnocení hran spojující různé Vj a V k minimalizován • Speciální případ: V = V\ U V2 bisekce grafu (graph bisection) • Jak nalézt vhodné rozdělení grafu? • problém optimálního rozdělení je NP-úplný • už pro bisekci: prohledání všech podmnožin množiny vrcholů (podmnožina a její doplněk tvoří Vi a V2) • nutné použít dobré heuristiky PB165 Grafy a sítě: 8. Plánování s komunikací 31/39 ooooooooooooooooooooo Heuristika: opakovaná bisekce grafu Základní používaný princip při rozdělení grafu: rozdělení množiny vrcholů V na 2k částí: rekurzivní bisekce grafu /c-krát 58 dělících hran PB165 Grafy a sítě: 8. Plánování s komunikací 32/39 ooooooooooooooooooooo Dělící hrany (edge i dělící vrcholy (vertex separator • Dělící hrany: £5 C £ dělí G po odstranění £s z E na dvě stejně velké nesouvisející komponenty V: V\ a \Z? • Dělící vrcholy: V$ Q V dělí G po odstranění Vs a všech jejich hran na dvě stejně velké nesouvisející komponenty V: V\ a V2 ~x~: Es — zelené hrany Vs — červené vrcholy PB165 Grafy a sítě: 8. Plánování s komunikací 33/39 ooooooooooooooooooooo Rozdělení se souřau (partitioning with nodal coordinates) Myšlenka rozdělení pomocí souřadnic vrcholů • každý vrchol má souřadnice v prostoru —► rozdělení prostoru Rn^EkmentMeshothlAĚAAirtoi Ľ.SJ C6 0.7 z r-OJ 0.4 c.:-CS. l§§Íͧllp- pomocí dělicí přímky, která dělí vrcholy v prostoru na poloviny PB165 Grafy a sítě: 8. Plánování s komunikací 34/39 ooooooooooooooooooooo Opakovaná bisekce PB165 Grafy a sítě: 8. Plánování s komunikací 35/39 ooooooooooooooooooooo Opakovaná bisekce PB165 Grafy a sítě: 8. Plánování s komunikací 36/39 ooooooooooooooooooooo Opakovaná bisekce PB165 Grafy a sítě: 8. Plánování s komunikací 37/39 ooooooooooooooooooooo Rozdělení grafu Opakovaná bisekce grafu s dělící přímkou: příklad PB165 Grafy a sítě: 8. Plánování s komunikací 38/39 O Problém rozvrhování: vlastnosti stroje, omezení, optimalizace O Precedenční omezení a disjunktivní grafová reprezentace: korespondence mezi rozvrhem a grafem O Ohodnocené grafy: obchodní cestující, doba na dopravu, plánování na počítačových sítích O Barvení grafu: algoritmus saturace a problémy přiřazení místností, rezervační problém, plánování operátorů O Plánování projektu (precedenční omezení): kritická cesta, kompromisní heuristika O Plánování s komunikací a s precedencemi: plánování seznamem, heuristiky mapování, shlukovací heuristiky Q Paralelní úlohy s průběžnou komunikací: vyvažování zátěže a rozdělení grafu Rozvrhování na Fl: PA167 Rozvrhování, PA163 Omezující podmínky PB165 Grafy a sítě: 8. Plánování s komunikací 39/39