Plánovaní s komunikací a s precedencemi
ooooooooooooooooooooo
Paralelní úlohy s průběžnou komunikací
ooooooo
PB165 Grafy a sítě:
8. Plánování s komunikací
PB165 Grafy a sítě: 8. Plánování s komunikací 1/30
Plánovaní s komunikací a s precedencemi
ooooooooooooooooooooo
Paralelní úlohy s průběžnou komunikací
ooooooo
Plánování s komunikací
(í) Plánování s komunikací a s precedencemi
o Popis problému
Plánování seznamem
a Heuristiky mapování
o Shlukovací heuristiky
Paralelní úlohy s průběžnou komunikací
o Popis problému
o Rozdělení grafu
PB165 Grafy a sítě: 8. Plánování s komunikací 2/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
ˇoooooooooooooooooooo ooooooo
Popis problému
Plánování s komunikací a s precedencemi: přehled
Příklady aplikací
o 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
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ě: 8. Plánování s komunikací 3/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Popis problému
Úlohy a komunikace
Referenční dobu trvaní p-, úlohy /
Precedenční omezení /l --> ;2
Komunikace: s/ze/i/2
* sizenj2'- velikost přenesených dat mezi
úlohami /l a /2
o pokud existuje /l --> /2,
pak s/ze;i;/2 > 0, jinak sizenj2 = 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
a ohodnocení hrany: velikost dat na komunikaci
* ohodnocení vrcholu: referenční doba trvání
PB165 Grafy a sítě: 8. Plánování s komunikací 4/30
Plánovaní s komunikací a s precedencemi
OOÄOOOOOOOOOOOOOOOOOO
Popis problému
Síť a komunikační zpoždění
* Topologie sítě: příklady
Paralelní úlohy s průběžnou komun
ooooooo
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 , i2,jl,j2) pro poslání dat
z úlohy / l úloze /2 ze stroje j i 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í
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komun
oooooooooooooooooooo ooooooo
Popis problému
Doba provádění. Optimalizace.
9 speedj: rychlost zpracování strojem j
o setuptaskj: (inicializační) doba na nastartování úlohy na stroji j
9 Doba provádění p,y úlohy ; na stroji j:
Pii = --T + setuptask/
speedj
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í
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Plánovaní seznamem
Plánování seznamem (list scheduling): algoritmus
Jednoduché efektivní algoritmy
* založeny na seřazení úloh v prioritní frontě
složitost algoritmu dána výpočtem priority
Algoritmus
& 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
0 dokud je fronta neprázdná, prováděj:
o) odebrána úloha zepředu z fronty
9 je vybrán (nejlepší) volný procesor pro spuštění úlohy
* vybraný procesor může např. minimalizovat komunikaci s
předchůdci úlohy
9 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í 7/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Plánovaní seznamem
Priority pro plánování seznamem
* Délka cesty přes uzly /'i, \i... /',,:
n n--1
(\ ^2 Pi + w2
^ S
'ze
'V+l1/1/J
;=i ;=i
* i/i/l, 1/1/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)
 ú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/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komun
oooooooooooooooooooo ooooooo
Plánovaní seznamem
Plánování seznamem: nastavení
* Zanedbání doby na komunikaci:
o 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í
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Plánovaní seznamem
Plánování seznamem: parametry
* Nechť size;j přímo reprezentuje dobu na přenos dat
* Předpokládejme, že i/i/l = w2 = 1
o Rychlost stroje
* pokud bychom předpokládali, že stroje mají stejnou rychlost,
pak lze úlohy přímo rozvrhovat dle zadané p,- a s/ze,i ,2
0^-01 2
Astroje
cas
0 1 2 3 4 5 6
Koncový čas úlohy
* spočítán na základě délky cesty (z p,- a s/ze/i,,^)
* 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/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Plánovaní seznamem
Plánování seznamem: príklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
CD1
(P3 i
komunikace
VL \ 2 1 / zanedbána:
2
, 3 ->4
2->5
5->6
6)1
Fronta: V \3 \1 \4 \5 \6
Istroje ú r o v e ň . Ji ^ X ^ 6\ i
\J/
3 U I 4 I
2 I I 5 I [61 cas
PB165 Grafy a sítě: 8. Plánování s komunikací 11/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Plánovaní seznamem
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:
o 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
a sizenti2 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, s/ze3,5 = 4, size5^ = 2
PB165 Grafy a sítě: 8. Plánování s komunikací 12/30
Plánovaní s komunikací a s precedencemi
oooooooooooooooooooo
Plánovaní seznamem
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
9 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
* např. produkční plánovací systémy pro plánování úloh na
počítačích PBSPro, SGE
Paralelní úlohy s průběžnou komunikaci
ooooooo
PB165 Grafy a sítě: 8. Plánování s komunikací 13/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Heuristiky mapovaní
Heuristiky mapování (mapping heuristics)
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
Pii = --T + setuptaski
speedj
* Komunikační zpoždění
c ( / l , Í2J1J2) = ( -- h setupmesg ) xhopsji j2+contdelayn -o
\transrate )
* 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 ji
(contention delay)
PB165 Grafy a sítě: 8. Plánování s komunikací 14/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Heuristiky mapovaní
Heuristiky mapování (mapping heuristics)
9 Konstruována a udržována smerovací tabulka obsahující
odhadované hodnoty p,y a c(;l, Í2J1J2)
a 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ů
o 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í 15/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
0000000000000*0000000 ooooooo
Shlukovací heuristiky
Rozvrhování se shlukovacími heuristikami
(clustering heuristics)
Rozvrhování řeší
9 alokace úloh na stroje
Q seřazení úloh na stroji / umístění úloh v čase
a Shlukovací heuristiky: řeší alokaci úloh na stroje
* Shluk: množina úloh, která bude prováděna na stejném stroji
a 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 komunikací 16/30
Plánovaní s komunikací a s precedencemi
oooooooooooooooooooo
Shlukovací heuristiky
Shlukovací heuristiky
a 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
Paralelní úlohy s průběžnou komunikaci
ooooooo
PB165 Grafy a sítě: 8. Plánování s komunikací 17/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
ooooooooooooooosooooo ooooooo
Shlukovací heuristiky
Naplánovaný graf úloh
Naplánovaný graf úloh
o 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
JL ....
naplánovaný graf úloh
Aer,
PB165 Grafy a sítě: 8. Plánování s komunikací 18/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Shlukovací heuristiky
Paralelní čas a dominantní posloupnost
o Připomenutí: délka cesty přes uzly ;'i, /2 ... /',,:
n n--l
(\ ^2 Pi + w2
^ S
'ze
'.'+1Wl
;=i ;=i
* Dominantní posloupnost:
nejdelší cesta v naplánovaném grafu úloh
o Paralelní čas rozvrhu:
doba nutná na provedení dominantní posloupnosti
s Pokud wl = 1/1/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í 19/30
Plánovaní s komunikací a s precedencemi
OOOOOOOOOOOOOOOOOÄOOO
Shlukovací heuristiky
Paralelní úlohy s průběžnou komunikací
ooooooo
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:
PB165 Grafy a sítě: 8. Plánování s komunikací
stroje
3 4 5 6
hl1 2 čas
20/30
Plánovaní s komunikací a s precedencemi
oooooooooooooooooooo
Shlukovací heuristiky
Algoritmus shlukovací heuristiky
9 Inicializace: všechny hrany označeny jako nevyzkoušené
každá úloha tvoří jeden shluk
9 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
9 hrana je označena jako vyzkoušená
* 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
Paralelní úlohy s průběžnou komunikaci
ooooooo
PB165 Grafy a sítě: 8. Plánování s komunikací 21/30
Plánovaní s komunikací a s precedencemi
oooooooooooooooooooo
Shlukovací heuristiky
Paralelní úlohy s průběžnou komunikací
ooooooo
Shlukovací heuristiky: prí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ě: 8. Plánování s komunikací 22/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
oooooooooooooooooooo ooooooo
Shlukovací heuristiky
Shlukovací heuristiky: cvičení
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í 23/30
Plánovaní s komunikací a s precedencemi
ooooooooooooooooooooo
Popis problému
Paralelní úlohy s průběžnou komunikací
Paralelní aplikace
o n komunikujících úloh
o m procesorů
* několik úloh prováděno
zároveň na každém
procesoru
Grafová reprezentace
* hranově a vrcholově
ohodnocený
neorientovaný graf
9 ohodnocené vrcholy: úlohy s
danou výpočetní náročností
* ohodnocené hrany:
průběžně komunikující
Paralelní úlohy s průběžnou komunikací
ˇoooooo
Vyvažování záteze: přiřazení
úloh na procesory tak, aby byla
* vyvážená zátěž jednotlivých
procesorů
a minimalizována komunikace
úloh na různvch Drocesorech2V3o
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
ooooooooooooooooooooo oooooo
Rozdělení grafu
Rozdělení grafu (graph partitioning)
* Formulace problému vyvažování zátěže jako
problému rozdělení grafu
o 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 Vk minimalizován
o 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í 25/30
Plánovaní s komunikací a s precedencemi Paralelní úlohy s průběžnou komunikací
ooooooooooooooooooooo oooooo
Rozdělení grafu
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í 26/30
Plánovaní s komunikací a s precedencemi
ooooooooooooooooooooo
Rozdělení grafu
Paralelní úlohy s průběžnou komunikací
oooooo
Dělící hrany (edge separator) vs.
dělící vrcholy (vertex separator)
* Dělící hrany: E5 C f dělí G po odstranění f s z E
na dvě stejně velké nesouvisející komponenty V: V\ a \Z?
 Dělící vrcholy: I/5 C 1/ dělí G po odstranění V$ 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í 27/30
Plánovaní s komunikací a s precedencemi
ooooooooooooooooooooo
Paralelní úlohy s průběžnou komunikací
oooooo
Rozdelení grafu
Rozdělení se souřadnicemi vrcholů
(partitioning with nodal coordinates)
Myšlenka rozdělení pomocí souřadnic vrcholů
o každý vrchol má souřadnice v prostoru --> rozdělení prostoru
F n # Element Mesh otNASA Airfai
 pomocí dělicí přímky, která dělí vrcholy v prostoru na poloviny
PB165 Grafy a sítě: 8. Plánování s komunikací 28/30
Plánovaní s komunikací a s precedencemi
ooooooooooooooooooooo
Paralelní úlohy s průběžnou komunikací
oooooo
Rozdelení grafu
Opakovaná bisekce grafu s dělící přímkou: příklad
PB165 Grafy a sítě: 8. Plánování s komunikací 29/30
Plánovaní s komunikací a s precedencemi
ooooooooooooooooooooo
Paralelní úlohy s průběžnou komunikací
oooooo
Rozdelení grafu
Grafy a sítě v plánování a rozvrhování: shrnutí
O Problém rozvrhování: vlastnosti stroje, omezení, optimalizace
# Precedenční omezení a disjunktivní grafová
reprezentace: korespondence mezi rozvrhem a grafem
 Ohodnocené grafy: obchodní cestující, doba na dopravu,
plánování na počítačových sítích
# Barvení grafu: algoritmus saturace a problémy přiřazení
místností, rezervační problém, plánování operátorů
5 Plánování projektu (precedenční omezení): kritická cesta,
kompromisní heuristika
 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í 30/30