Dynamické rozvrhování
Bc. Miroslava Plachá
Téma a motivace
* Rozvrh dynamicky se měnící množiny úloh
na dynamicky se měnící množinu clusterů
* Výpočty v Metacentru
* Přístup pomocí programování s
omezujícími podmínkami
* Integrace do simulátoru Alea
Použité nástroje I
* Choco
­ Systém v Javě pro programování s
omezujícími podmínkami
­ Snadná definice omezení, heuristik výběru...
­ Systém model/solver
A + B*C = E
model.addConstraint(Choco.eq(E, Choco.plus(A, Choco.mult(B,C)))
Použité nástroje II
* Alea
­ simulátor gridu s výpadky
­ Java, GridSim
­ integrované algoritmy (FIFO, ESG, PBS...)
­ reálné sady úloh (Metacentrum...)
­ komunikace pomocí zpráv
­ neumožňuje rozvrhnutí úlohy paralelně mezi
dva clustery
Definice problému
* Zdroje
­ jednotlivé clustery/stroje
­ charakteristika (lokace, síť, operační systém,
licence...)
­ počet CPU
* Úlohy
­ uživatelem zadané programy
­ vyžadované parametry zdroje
­ vyžadovaný počet CPU
­ fronta
* Cíl: efektivní rozvržení úloh na zdroje
Optimalizační funkce
* non-delayed jobs
­ počet úloh které skončí do limitu
* tardiness
­ průměrná doba překročení limitu
* waiting time
­ start_time ­ arrival_time
* response time
­ finish_time ­ arrival_time
* slowdown
­ (finish_time ­ arrival_time)/cpu_time
* weighted slowdown (awsd)
­ (cpu_count* cpu_time) * slowdown
* weighted response (awrt)
­ (cpu_count * cpu_time) * response
Model - základní prvky
* Úloha (gridlet)
­ specifická množina požadavků
­ odhad délky trvání (deadline)
* Cluster (resource)
­ množina vlastností
­ počet CPU
­ seznamy resInExec a resSchedule
Struktura CP řešiče
* Seznam non-scheduled jobs
­ nerozvržené úlohy
* CPAddJob
­ metoda reagující na nově příchozí úlohu
* CPSchedule
­ vlastní rozvrhování pomocí kumulativního omezení
* CPuseSchedule
­ posílání úloh na stroje z resSchedule
resInExec
právě běžící
resSchedule
rozvržené úlohy non-scheduled
jobs
nerozvržené
Resource 1
...
resInExec
právě běžící
resSchedule
rozvržené úlohy
Resource n
new job
?
?
CPAddJobCPAddJob
CPScheduleCPuseSchedule
Volání řešiče I
* Zpráva ,,Přijetí úlohy"
* Zpráva ,,Úloha dokončena" ­ volný zdroj
* Zpráva ,,Selhání zdroje"
* Zpráva ,,Obnovení zdroje"
* Nejprve CPuseSchedule ­ maximalizace zatížení
* Podmíněno ­ minimalizace zbytečného rozvrhování
­ čas
­ záleží na zprávě
Volání řešiče II ­ rozbor podmínek
* Deadlock ­ detekována úloha, která nemůže být spuštěná
* EmptyResSchedule
­ nutné rozlišit nechtěný stroj od nevytíženého
­ Existuje resource i : i.resSchedule.size() == 0 AND existuje gridlet j:
isSuitable(i,j).
* Nová úloha (pod limit)
­ CPSchedule
* Volný zdroj
­ CPuseSchedule
­ if (deadlock || EmptyResSchedule) CPSchedule
* Obnovení stroje
­ CPuseSchedule
­ if (CPuseSchedule == 0 || deadlock || EmptyResSchedule) CPSchedule
* Selhání stroje
­ CPuseSchedule
­ if (deadlock) CPSchedule
Algoritmus I
* resource_list ­ list of all resources
* sorted_resource_list ­ list of all resources sorted by the mips count
* resource.resSchedule ­ list of jobs scheduled for resource and currently not running
* resource.resInExec ­ list of jobs currently running on resource
* non_scheduled_jobs ­ list of non-scheduled jobs
* IF scheduler is currently not running
* THEN
* SWITCH message
* CASE ,,new job arrived":
* IF size of non_scheduled_jobs > limit
* THEN
* CPAddJob new_job
* ELSE
* non_scheduled_jobs  non_scheduled_jobs  new_job
* CPSchedule
* FI
* break
Algoritmus II
* CASE ,,free resource":
* CPuseSchedule
* IF deadlock OR ( exists resource from resource_list: resource.resSchedule is empty
* AND exists job from non_scheduled_jobs: job can be run on resource)
* THEN
* CPSchedule
* FI
* break
ˇ
* CASE ,,resource restart occured":
* scheduled := CPuseSchedule
* IF deadlock OR scheduled == 0
* OR ( exists resource from resource_list: resource.resSchedule is empty
* AND exists job from non_scheduled_jobs: job can be run on resource)
* THEN
* CPSchedule
* FI
* break
ˇ
Algoritmus III
* CASE ,,resource failure occured":
* CPuseSchedule
* IF deadlock
* THEN
* CPSchedule
* FI
* break
ˇ
* DONE
* deadlock := false
* FI
CPAddJob
* Možné scénáře
­ úlohu je možné ihned rozvrhnout ­ cena?
­ úlohu není možné rozvrhnout
* Dvojí přístup
­ resourceList = {1, 2, 3}, Dom(g1)... Dom(gn-1) = {1, 2},
Dom(gn) = {1, 2, 3}
­ resSchedule.size() == 0
­ rozvrhnout jen pokud může být spuštěna vs zařadit
do prázdné fronty
* Jak určit limit?
CPAddJob - algoritmus
* job := new job
* IF size of non_scheduled_jobs > limit
* THEN
* FOR resource IN sorted_resource_list DO
* IF job can be currently assign to resource AND resource.resSchedule empty
* THEN
* resource.resInExec  resource.resInExec  job
* break
* FI
* DONE
ˇ
* IF job was not assign
* THEN
* non_scheduled_jobs  non_scheduled_jobs  job
* FI
* FI
Experiment limit I
Runtime
0,00
50,00
100,00
150,00
200,00
250,00
1
CP0
CP20
CP40
CP80
CP120
Waiting time
5800
5900
6000
6100
6200
6300
6400
6500
6600
6700
1
CP0
CP20
CP40
CP80
CP120
Experiment limit II
Response time
25900
26000
26100
26200
26300
26400
26500
1
CP0
CP20
CP40
CP80
CP120
Tardiness
1080,00
1100,00
1120,00
1140,00
1160,00
1180,00
1200,00
1220,00
1240,00
1260,00
1
CP0
CP20
CP40
CP80
CP120
Jak daleko zajít?
* vkládání i do prázdného resSchedule ­ může mít
za následek zhoršení, kterému by se předešlo
rozvrhnutím
* cena vs efektivnost
* Konkrétní čísla v Metacentru:
­ celkem úloh 103655
2%1,5%9%40
2%2%66%0
Ušetřeno rozvrhnutíPřímo resSchedulePřímo resInExecLimit
Jak daleko zajít? Experiment
Waiting time
5800
5900
6000
6100
6200
6300
6400
6500
6600
6700
1
CP0
CP0+
CP40
CP40+
Slowdown
0,00
10,00
20,00
30,00
40,00
50,00
60,00
70,00
80,00
1
CP0
CP0+
CP40
CP40+
CPuseSchedule
* posílání úloh na stroj v pořadí určeném
řešičem.
* potenciální riziko ­ výpadek vs úmyslné
rozvržení
­ přeskočení úlohy v případě výpadku
CPuseSchedule - algoritmus
* scheduled := 0
* FOR resource IN resource_list DO
* WHILE next job in resource.resSchedule AND resource.free_CPUs > 0 DO
* IF next job in resource.resSchedule can be run
* THEN
* resource.resInExec  resource.resInExec  dequeue(resource.resSchedule)
* scheduled++
* ELSEIF next job in resource.resSchedule cannot be ever run
* THEN
* deadlock := true
* dequeue(resource.resSchedule)
* ELSE
* break
* FI
* DONE
* DONE
* RETURN scheduled
CPSchedule
* Určení množiny úloh pro rozvrhování
* Definice omezení
* Výpočet
* Seřazení úloh do resSchedule clusterů
* Zpráva volající CPuseSchedule simulace
časové náročnosti
Soubor úloh pro rozvrhování
* Variabilní
­ seznam non-scheduled jobs
­ obsah resSchedule clusterů
* Pevné
­ blank jobs
­ resInExec clusterů
počet CPU
resource i
blank job
úlohy z
resInExec
t
Proměnné I
* t ­ časový interval na který rozvrhujeme
* Jak dlouho bude úloha trvat?
* čas vs abstrakce (short = 1, normal = 2, long = 3, t = 4)
* Blank úloha i na clusteru j:
­ start[i] = j*t
­ height[i] = maxCPU ­ j.CPU
­ duration[i] = t
* resInExec úloha i na clusteru j:
­ start[i] = j*t
­ height[i] = i.CPU
­ duration[i] = ?
resource 0 resource 1 resource 2
t 2t 3t
Proměnné II
* Nerozvržená úloha i:
­ starts[i]; Dom(starts[i]) = 0 .. t
­ height[i] = i.CPU
­ resource[i]; Dom(resource[i]) = vyhovující stroje
* enum
­ subjob_start[i]; Dom(subjob_start[i]) = 0 .. resList.size() * t
­ subjob_duration[i];
Dom(subjob_duration[i]) = 0 .. min(t, i.duration)
resource j
job i
height[i]
resource[i]
subjob_start[i]
subjob_duration[i]
t
(j + 1)*tj*t
Omezení
* Nerozvržená úloha i:
­ subjob_start[i] = t * resource[i] + starts[i]
­ subjob_duration[i] = min(t - starts[i], min (i.duration, t))
* dovoluje rozvrhnout jen začátek úlohy
* nerozvrhnuté úlohy se ,,schovají" v délce trvání 0
resource j
job i
subjob_start[i]
subjob_duration[i]
(j + 1)*tj*t
starts[i]
Kumulativní omezení
* cumulative(starts, durations, heights, maxCPU)
* ve starts ­ start[i] pro blank a resInExec úlohy,
subjob_start pro nerozvrhnuté
* Jak moc do budoucnosti je efektivní rozvrhovat?
Příliš mnoho úloh - zpomalení
Hledání řešení - heuristiky
* při hledání řešení se pouze přiřazují hodnoty
proměnným resource[i] (enum) a starts[i] (definováno
mezemi)
* heuristika výběru proměnné ­ které i jako první?
­ EarliestGridlet ­ preferuje v minulosti již přiřazené
­ OldestGridlet ­ preferuje nejstarší
­ HeaviestGridlet ­ preferuje ,,největší"
­ SmallestDomain ­ preferuje nejvíce náročnou
* heuristika výběru hodnoty
­ starts[i] - IncreasingDomain ­ co nejmenší čas
­ resource[i] ­ co nejlukrativnější?
* MinimalUsage ­ FreeCPU/(InExec.size() + usage)
­ pokud shoda ­ náhodně
Experiment - heuristiky
Tardiness
1160,00
1180,00
1200,00
1220,00
1240,00
1260,00
1280,00
1300,00
1
HEAVY
OLD
EARLY
Waiting time
5600
5700
5800
5900
6000
6100
6200
6300
1
HEAVY
OLD
EARLY
Hledání řešení - výsledek
* Seznam úloh s přiřazenou začáteční dobou < t
* Chronologické seřazení
* Seřazení dle výšky (nahrazuje 2D přístup)
* Zapsání do fronty resSchedule příslušného
clusteru
* Nepřiřazené úlohy zůstávají v non-scheduled
jobs
t0
resSchedule pro resource ivýsledek kumulativního omezení pro resource i
Optimalizace
* Cena?
* Limit úloh pro provedení?
* Optimalizační funkce?
Riziko nezachycení zprávy
* Rozvrhování trvá x sec a v čase t < x přijde
zpráva
* Volný stroj ­ zpožděná reakce x ­ t sekund
(CPuseSchedule bude voláno)
* Obnovení stroje ­ dtto
* Selhání stroje ­ detekce uvázlé úlohy, jinak OK
* Nová úloha ­ nemůžeme kvůli probíhajícímu
rozvrhování rozvrhnout hned ­ do příštího
rozvrhování možná neefektivnost
Časová náročnost
maximumdéle1s ­ 30sPod 1sCelkem
74 s(80)6,7%93,2%78 333CPmax
116 s(32)4,8%95,2%64 548CP40
100 s(17)14,2%85,8%16 295CP0
Experimenty ­ srovnání I
Response time
24500
25000
25500
26000
26500
27000
27500
28000
28500
1
ESG
ESG+LS
ESG+perLS
PBS
CP40
Runtime
0,00
20,00
40,00
60,00
80,00
100,00
120,00
140,00
160,00
180,00
1
EASY
EDF-BF
ESG
ESG+LS
ESG+perLS
PBS
CP40
Experimenty ­ srovnání II
Waiting time
0
1000
2000
3000
4000
5000
6000
7000
8000
1
ESG
ESG+LS
ESG+perLS
PBS
CP40
Tardiness
0,00
200,00
400,00
600,00
800,00
1000,00
1200,00
1400,00
1600,00
1800,00
1
ESG
ESG+LS
ESG+perLS
PBS
CP40
Experimenty ­ srovnání II
non-delayed jobs
95500
96000
96500
97000
97500
98000
98500
99000
99500
100000
100500
101000
1
EASY
EDF-BF
ESG
ESG+LS
ESG+perLS
PBS
CP40
Slowdown
0,00
20,00
40,00
60,00
80,00
100,00
120,00
1
ESG
ESG+LS
ESG+perLS
PBS
CP40
Experimenty ­ srovnání III
awsd
1,60
1,62
1,64
1,66
1,68
1,70
1,72
1
ESG
ESG+LS
ESG+perLS
PBS
CP40
Awrt
280000,00
285000,00
290000,00
295000,00
300000,00
305000,00
310000,00
315000,00
320000,00
325000,00
330000,00
1
ESG
ESG+LS
ESG+perLS
PBS
CP40
Výhody/nevýhody
* + Snadná definice chytrých heuristik pro výběr proměnných a
hodnot
* Jak určit univerzální heuristiku pro nejrůznější typy sad úloh?
* + Oproti frontovým algoritmům pohled na úlohy jako celek a
přehodnocování jejich pořadí
* + Jednoduché rozšíření funkčnosti i pro rozvrhování na paralelní
clustery
* + Jednoduché přidávání dalších omezení (počet úloh na
uživatele...)
* - časová a paměťová náročnost ­ riziko zahlcení
­ lze detekovat a přejít na jiný, méně náročný algoritmus
* + zvyšování efektivnosti použitím lepšího hardware (-)
* - nedeterministické
* - neodhadnutelné chování