PB165 Grafy a sítě: Plánování s komunikací PB165 Grafy a sítě: Plánování s komunikací 1/33 Plánování s komunikací Q Popis problému Q Plánování seznamem Q Heuristiky mapování Q Shlukovací heuristiky PB165 Grafy a sítě: Plánování s komunikací 2/33 Plánování s komunikací a s precedencemi: přehled Příklady aplikací • plánování komunikující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ě: Plánování s komunikací 3/33 Úlohy a komunikace Referenční dobu trvání p; úlohy ; Precedenční omezení /l —> ;2 Komunikace: s/ze;i;/2 • size;iíj2- velikost přenesených dat mezi úlohami ;1 a /2 • pokud existuje /l /2, pak s/ze/i;/2 > 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 • 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í • Topologie sítě: příklady r^\ 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, Í2J1J2) pro poslání dat z úlohy /l ú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/33 Doba provádění. Optimalizace. • speed]-, rychlost zpracování strojem j 9 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) a 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/33 Plánování seznamem (list scheduling Jednoduché efektivní algoritmy • založeny na seřazení úloh v prioritní frontě 9 složitost algoritmu dána výpočtem priority Algoritmus plánování seznamem 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 O pokud existuje volný stroj a fronta je neprázdná, prováděj: O odebrána první úloha z fronty Q 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/33 Priority pro plánování seznamem • Délka cesty přes uzly ;'i, 12 ... in\ n-l 1/1/1 y^ Pi + w2 y^ s/ze/)(-+i ;=i ;=i • 1/1/I, w/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ů • 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ě: Plánování s komunikací B/33 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) a 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/33 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 • 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) ©- i istroje © 2 / »stroje nx „ 2 cas -i 0 12 3 4 5 6 se zanedbáním komunikace (na stejném stroji) cas 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/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí ©1 ©3 1® ©i PB165 Grafy a sítě: Plánování s komunikací 11/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí ©1 ©3 1® ©i Fronta: 2 3 1 Úroveň: 11 8 7 PB165 Grafy a sítě: Plánování s komunikací 12/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí ©1 ©3 1® ©i ^stroje Fronta: ^31 Úroveň: n 8 7 cas PB165 Grafy a sítě: Plánování s komunikací 13/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí ©1 ©3 1® ©i Fronta: V \3 1 MStr°Je Úroveň: íl k 7 cas PB165 Grafy a sítě: Plánování s komunikací 14/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí ©1 ©3 1® ©i Fronta: V \3 NI jstroje úroveň. Ji ^ X 3 1 cas PB165 Grafy a sítě: Plánování s komunikací 15/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí 01 ©3 1© \ Xf © 2 ©3 ^^ í ^ ©1 Fronta: ^ \ ^stroje Úroveň: il 3|1 2 cas -------------------------------^- 4 5 PB165 Grafy a sítě: Plánování s komunikací 16/33 Plánování seznamem: příklad zanedbána: 4 Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí CD1 (Ä3 1®komunikace H \ y zan' ©2 ,©3 ©i ^stroje Fronta: ^ \3 NI \4 Úroveň: íl k A 5\ 3 1 4 cas PB165 Grafy a sítě: Plánování s komunikací 17/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí CD1 (Ä3 1®komunikace VL \2 1/ zanedbána: y^ yy i->4 ©2 ©3 ©i Fronta: V \3 NI \4 5 ň: íl k A 5\ 6 »stroje Úroveň: 11 3UI4 1 2 cas -----------------------^ PB165 Grafy a sítě: Plánování s komunikací 18/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí CD1 (Ä3 1®komunikace VL \2 1/ zanedbána: V^ Vx 1->z ©2 ©3 ©i >4 2->5 ^stroje 3 1 4 2 5 5 Fronta: ^ \3 NI \4 \5 Úroveň: H k A k 8\ cas —»- PB165 Grafy a sítě: Plánování s komunikací 19/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí CD1 (Ä3 1®komunikace VL \2 1/ zanedbána: V^ Vx 1->z ©2 ©3 ©i >4 2->5 ^stroje 3 1 4 2 5 5 Fronta: ^ \3 \1 \4 \5 6 Úroveň: H k A 5\ 6\ 1 cas —»- PB165 Grafy a sítě: Plánování s komunikací 20/33 Plánování seznamem: příklad Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí CD1 (Ä3 1®komunikace VL \2 1/ zanedbána: y^ yy i->4 O2 , O3 2->5 \2 y 5->6 ©1 Fronta: V \ »stroje Úroveň: Li 3UI4 2 5 5 6 161 cas • 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í 21/33 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í • 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í 22/33 Plánování seznamem: diskuse 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 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í 29/33 Dominantní posloupnost: příklad 3 \ 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í 30/33 Algoritmus shlukovací heuristiky 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 O REPEAT O vynulování největší nevyzkoušené hrany v seřazeném seznamu, pokud nevzroste paralelní čas Q 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í 31/33 Shlukovací heuristiky: příklad Problém: Ř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ě: Plánování s komunikací 32/33 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í 33/33