PB165 Grafy a sítě: Plánování s komunikací
PB165 Grafy a sítě: Plánování s komunikací 1/41
Plánování s komunikací
1 Popis problému
2 Plánování seznamem
3 Heuristiky mapování
4 Shlukovací heuristiky
PB165 Grafy a sítě: Plánování s komunikací 2/41
Plánování s precedencemi: přehled
Příklady aplikací
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
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/41
Úlohy a komunikace
Referenční doba trvání pj úlohy j
Precedenční omezení j1 → j2
Komunikace: sizej1,j2
sizej1,j2: velikost přenesených dat mezi
úlohami j1 a j2
pokud existuje j1 → j2,
pak sizej1,j2 ≥ 0, jinak sizej1,j2 = 0
pokud jsou j1 a j2 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í 4/41
Síť a komunikační zpoždění
Topologie sítě: příklady
každý uzel grafu reprezentuje dual-core procesor
transratei1,i2: přenosová rychlost mezi sousedními stroji i1, i2
setupmesgi : (inicializační) doba na poslání zprávy strojem i
Komunikační zpoždění c(j1, j2, i1, i2) pro poslání dat z úlohy j1
úloze j2 ze stroje i1 na sousední stroj i2
c(j1, j2, i1, i2) =
sizej1,j2
transratei1,i2
+ setupmesgi1
PB165 Grafy a sítě: Plánování s komunikací 5/41
Doba provádění, optimalizace
speedi : rychlost zpracování strojem i
setuptaski : (inicializační) doba na nastartování úlohy na stroji i
Doba provádění pij úlohy j na stroji i:
pij =
pj
speedi
+ setuptaski
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ě: Plánování s komunikací 6/41
Plánování seznamem (list scheduling)
Plánování seznamem = jednoduchý efektivní algoritmus
založeno na seřazení úloh v prioritní frontě
složitost algoritmu závisí na výpočtu
priority určující pořadí spuštění úloh
metody výběru stroje (pro danou úlohu)
Používán i při plánování úloh bez precedencí, kde priorita dána
pořadím přicházejích úloh
úrovní paralelismu
délkou trvání
vlastníkem úlohy
...
PB165 Grafy a sítě: Plánování s komunikací 7/41
Základní algoritmus plánování seznamem
Algoritmus parametrizován funkcemi
výpočet priority P
výběr stroje M
Plánování seznamem(P, M)
1 každé úloze j přiřazena priorita pomocí P(j)
prioritní fronta inicializována úlohami bez předchůdců
úlohy ve frontě řazeny v klesajícím pořadí dle priority
2 pokud existuje volný stroj a fronta je neprázdná, prováděj:
1 jakmile provedeni všichni přímí předchůdci nějaké úlohy,
tak je úloha přidána dle priority do fronty
2 odebrána první úloha z fronty
3 volný procesor je vybrán pro spuštění úlohy j pomocí M(j)
PB165 Grafy a sítě: Plánování s komunikací 8/41
Algoritmus plánování seznamem a aktuální čas t
Při plánování seznamem je nutné pracovat s aktuálním časem t
rozšíříme základní algoritmus tak, aby byla práce s časem zřejmá
Plánování seznamem včetně času(P, M)
1 inicializace aktuálního času t = 0
2 každé úloze j přiřazena priorita pomocí P(j)
prioritní fronta inicializována úlohami bez předchůdců
úlohy ve frontě řazeny v klesajícím pořadí dle priority
3 pokud existuje volný stroj a fronta je neprázdná, prováděj:
1 t = nejdřívější čas, kdy je nějaký stroj volný
2 jakmile provedeni všichni přímí předchůdci j1, . . . , jk nějaké
úlohy j0, tj. ∀l = 1..k : Cl ≤ t
tak je úloha j0 přidána dle priority P(j0) do fronty
3 odebrána první úloha (j) z fronty
4 volný procesor je vybrán pro spuštění úlohy j pomocí M(j)
startovní čas Sj úlohy j je t
PB165 Grafy a sítě: Plánování s komunikací 9/41
Priority pro plánování seznamem
Délka cesty přes uzly j1, j2 . . . jn:
w1
n
j=1
pj + w2
n−1
j=1
sizej,j+1
w1, w2: koeficienty určující poměr mezi dobou trvání a velikostí přenesených dat
Počáteční uzly Begin: uzly bez předchůdců
Koncové uzly End: uzly bez následníků
Možnosti pro výpočet priority P(j0) uzlu j0
úroveň (level) bude dále používána pro výpočet priority
délka nejdelší cesty z uzlu j0 do koncového uzlu
P(j0) = max
∀cesty (j0,j1,...,jk ):jk ∈End
w1
k
j=0
pj + w2
k−1
j=0
sizej,j+1
ko-úroveň (co-level)
délka nejdelší cesty z počátečního uzlu do uzlu j0
PB165 Grafy a sítě: Plánování s komunikací 10/41
Zanedbání komunikace, výběr stroje M
Zanedbání doby na komunikaci:
pokud máme j1 → j2 a úlohy j1 a j2 jsou prováděny na stejném stroji,
tak dobu na komunikaci zanedbáme
Značení: koncový čas Cij úlohy j při zpracování na stroji i
Výběr stroje M(j) pro úlohu j:
pro provádění úlohy jsou vybírány pouze volné stroje
pro provádění úlohy j je vybrán volný stroj i, na kterém bude úloha j
dokončena nejdříve
Cj = min
∀i : volny(i)
Cij
v případě více možností je vybrán stroj s nejmenším indexem
pozor: při výpočtu koncového času úloh, 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í 11/41
Zjednodušení modelu plánování
Předpokládejme, že
doba na poslání dat z úlohy j1 na úlohu j2 nezávisí na tom, mezi
kterými stroji budeme data posílat a odpovídá přímo sizej1,j2
c(j1, j2, i1, i2) = c(j1, j2) = sizej1,j2
w1 = w2 = 1
všechny stroje i mají stejnou jednotkovou rychlost
speedi = 1
doba na nastartování úlohy setuptaski na stroji i je zanedbatelná
⇒ Doba provádění úlohy j není závislá na stroji, tj.
pij =
pj
speedi
+ setuptaski = pj
budeme tedy pro značení doby trvání úlohy j používat pouze pj
⇒ Úlohy lze plánovat přímo podle dle zadané pj a sizej1,j2
PB165 Grafy a sítě: Plánování s komunikací 12/41
Koncový čas Cij úlohy j při zpracování na volném stroji i
Cij spočítán na základě
aktuálního času t (čas, ve kterém úlohu j odebíráme z fronty)
doby provádění pj
komunikace s předchůdci j1 (j1 → j), kteří nebyli prováděni na stroji i
pro volny(i) : Cij = t + pj +
∀j1 : j1 → j,
j1 prováděna na stroji i1, i1 = i
sizej,j1
Tj. uvažujeme 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
Příklad: t = 1
se zanedbáním komunikace bez zanedbání komunikace
(na stejném stroji) (na různých strojích)PB165 Grafy a sítě: Plánování s komunikací 13/41
Výběr stroje: algoritmus (shrnutí)
Výběr stroje M(j) pro úlohu j v čase t
1 Cj = MaxNumber
2 REPEAT
1 i = nejmenší index dosud neprozkoumaného volného stroje
2 spočítáme koncový čas Cij úlohy j na stroji i
Cij = t + pj +
∀j1 : j1 → j,
j1 prováděna na stroji i1, i1 = i
sizej,j1
3 pokud je koncový čas na stroji i lepší,
tak je i novým kandidátem na zpracování úlohy j
IF Cij < Cj THEN M(j) = i
UNTIL jsme neprošli všechny volné stroje
PB165 Grafy a sítě: Plánování s komunikací 14/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
PB165 Grafy a sítě: Plánování s komunikací 15/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
PB165 Grafy a sítě: Plánování s komunikací 16/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
PB165 Grafy a sítě: Plánování s komunikací 17/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
3 1
PB165 Grafy a sítě: Plánování s komunikací 18/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
3 1
PB165 Grafy a sítě: Plánování s komunikací 19/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
3 1
4
5
2
PB165 Grafy a sítě: Plánování s komunikací 20/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
3 1
4
5
2
PB165 Grafy a sítě: Plánování s komunikací 21/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
3 1
4
5
2
5
6
3
PB165 Grafy a sítě: Plánování s komunikací 22/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
3 1
4
5
2
5
6
3
PB165 Grafy a sítě: Plánování s komunikací 23/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
3 1
4
5
2
5
6
3
6
1
7
PB165 Grafy a sítě: Plánování s komunikací 24/41
Plánování seznamem: příklad
Plánování 6 úloh zadaných grafem na 2 stroje se stejnou rychlostí
Fronta:
Úroveň:
Akt.čas:
2
11
0
3
8
0
1
7
3 1
4
5
2
5
6
3
6
1
7
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í 25/41
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í
p1 = 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
sizei1,i2 reprezentuje dobu na přenos dat a je zadán takto:
size1,2 = 1, size2,4 = 3, size4,6 = 1,
size1,3 = 2, size3,5 = 4, size5,6 = 2
PB165 Grafy a sítě: Plánování s komunikací 26/41
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
snadno může dojít ke změně kritické cesty: důsledkem toho, že
⇐ komunikační zpoždění závisí na alokaci úlohy na stroj
⇐ 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 a metod výběru stroje
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í 27/41
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 i na stroji j
pij =
pi
speedj
+ setuptaskj
Komunikační zpoždění
c(j1, j2, i1, i2) =
sizej1,j2
transrate
+ setupmesg × hopsi1,i2 + contdelayi1,i2
předpokládán konstantní transrate a setupmesg
hopsi1,i2: počet hopů mezi stroji i1 a i2, (délka nejkratší cesty mezi
stroji při jednotkovém ohodnocení hran)
contdelayi1,i2: zpoždění dané zatížením linky mezi i1 a i2 (contention
delay)
PB165 Grafy a sítě: Plánování s komunikací 28/41
Heuristiky mapování (mapping heuristics)
Konstruována a udržována směrovací tabulka obsahující
odhadované hodnoty pij a c(j1, j2, i1, i2)
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ě, 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ě: Plánování s komunikací 29/41
Plánování se shlukovacími heuristikami
(clustering heuristics)
Plánování řeší
1 umístění úloh na stroje
2 seřazení úloh na stroji / umístění úloh v čase
Shlukovací heuristiky: primárně řeší umístění (alokaci) úloh na stroje
Následné naplánování úloh v čase na vybraný stroj je realizováno
jednoduchou aplikací plánování seznamem
Shluk: množina úloh, která bude prováděna na stejném stroji
PB165 Grafy a sítě: Plánování s komunikací 30/41
Princip plánování založeného na shlukování
1 Shlukování úloh na nelimitovaný počet plně propojených procesorů
2 Namapování shluků a jejich úloh na daný počet procesorů (m)
provedením následujících operací
1 spojování shluků: pokud je počet shluků vyšší než m
2 fyzické mapování shluků: přiřazení shluků na procesory tak, aby
byla minimalizována komunikace
(na této úrovni uvažována reálná konektivita mezi stroji)
3 uspořádání úloh: úlohy jsou na stroji prováděny tak, by byly
splněny závislosti mezi úlohami,
např. pomocí zjednodušeného plánování seznamem na jeden stroj
PB165 Grafy a sítě: Plánování s komunikací 31/41
Shlukování
Shlukování
bez backtrackingu (abychom se vyhnuli vysoké složitosti), tj.
jakmile jsou jednou shluky spojeny nelze je zpětně rozpojit
Iniciálně: jedna úloha = jeden shluk
Typický krok heuristiky shlukování
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 tzv. paralelního času rozvrhu
PB165 Grafy a sítě: Plánování s komunikací 32/41
Naplánovaný graf úloh
Naplánovaný graf úloh
graf úloh zahrnující aktuální vynulování hran ve shluku
ú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í 33/41
Paralelní čas a dominantní posloupnost
Připomenutí: délka cesty přes uzly j1, j2 . . . jn:
w1
n
j=1
ji + w2
n−1
j=1
sizej,j+1
Dominantní posloupnost:
nejdelší cesta v naplánovaném grafu úloh
Paralelní čas rozvrhu:
doba nutná na provedení dominantní posloupnosti
Pokud w1 = w2 = 1 a sizej1,j2 reprezentuje dobu na přenos mezi j1, j2
⇒ délka cesty odpovídá době na provedení úloh na cestě
⇒ paralelní čas rozvrhu = délka cesty dominantní posloupnosti
PB165 Grafy a sítě: Plánování s komunikací 34/41
Dominantní posloupnost: pří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:
1 2
6543
stroje
čas
3
7 7
7
POZOR: Přenos dat z úlohy 2 na úlohu 7 může být zahájen hned,
jakmile skončí úloha 2 (víme, na kterém stroji úloha 7 poběží)
PB165 Grafy a sítě: Plánování s komunikací 35/41
Algoritmus shlukování
Shlukování
1 Inicializace: všechny hrany označeny jako nevyzkoušené
každá úloha tvoří jeden shluk
2 Seřazení všech hran (j1, j2) v grafu úloh v klesajícím pořadí
dle komunikační ceny (sizej1,j2)
3 REPEAT
1 vynulování největší nevyzkoušené hrany v seřazeném seznamu,
pokud nevzroste paralelní čas
2 hrana je označena jako vyzkoušená
3 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 shlukování
PB165 Grafy a sítě: Plánování s komunikací 36/41
Shlukování: příklad
Problém: Řešení pomocí algoritmu:
1
2
4
1
6
7
2
1
5
3
5 2 2
1
1
1
1
1
0
0 0
00
0
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í 37/41
Spojování shluků
Pokud je shluků méně než strojů
každý shluk přiřadíme na jeden stroj
(zbývající stroje zůstanou volné)
Pokud je shluků stejně jako strojů
shluk = stroj
Pokud máme shluků více je nutné aplikovat spojování shluků
lze využít problému plnění košů (bin packing problem)
plnění předmětů do košů tak, aby byly všechny koše rovnoměrně
naplněny
1 stroj = 1 koš
1 shluk = 1 předmět dané velikosti
velikost shluku S = j∈S pj
cíl: součet velikostí předmětů ve všech koších je přibližně stejný
PB165 Grafy a sítě: Plánování s komunikací 38/41
Shlukovací heuristiky: shrnutí
Plánování pomocí shlukovací heuristiky:
1 shlukování
2 spojování shluků, pokud je shluků více než strojů
3 fyzické mapování spojených shluků na stroje
obecně: přiřazení shluků na procesory tak, aby byla minimalizována
komunikace
4 uspořádání úloh na každém stroji
např. pomocí jednoduchého plánování seznamem
není nutno brát v úvahu M(j), stroj už je předem vybrán
stačí uvažovat prioritu P(j)/úroveň a
seřadit úlohy dle jejich úrovně
přenos dat k následníkům úlohy je zahájen hned po jejím dokončení
(víme, na kterém stroji budou úlohy spuštěny)
úlohy pak mohou být spuštěny na stroji,
jakmile jsou dokončeni všichni jejich předchůdci (a přenesena data)
PB165 Grafy a sítě: Plánování s komunikací 39/41
Uspořádání úloh na stroji: příklad
1
2
4
1
6
7
2
1
5
3
5 2 2
1
1
1
1
1
0
0 0
00
0
—>
0
1
2
4
1
6
7
2
1
5
3
5
2
1
1
1
0
1
1
0
0
0
2
1 2
6543
stroje
čas
3
7 7
PB165 Grafy a sítě: Plánování s komunikací 40/41
Shlukování: cvičení
Vyřešte cvičení z kapitoly plánování seznamem pomocí algoritmu
shlukování. Následně uspořádejte úlohy na stroji (použijte stejný počet
strojů jako máte shluků) a zkonstruujte výsledný rozvrh.
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í 41/41