PA160
Vyrovnání zátěže (Load Balancing) Distribuované plánování (Dist. Scheduling) Odolnost proti vypadkUm (Fault Tolerance)
Vyrovnání zátěže
■ Máme množinu úloh, mezi nimiž existují nějaké závislosti
■ Zpravidla vstup/výstupní
■ Máme dále množinu procesorů, které jsou schopné vzájemné komunikovat
■ Rozložením zátěže rozumíme takove pridelení uloh procesorum, ktere minimalizuje celkový čas výpočtu
PA160 2 Jaro 2010
Grafová reprezentace
■ Máme množinu úloh N se závislostmi, kterou reprezentujeme jako graf G(V, U)
■ Vrcholy jsou procesy
■ Hrana odpovídá datove závislosti mezi procesy
■ Mnozinu vrcholu grafu potrebujeme rozlozit nasledujícím způsobem:
N = N U N2 U ... U Np
pri platnosti
■ IN « |NI/p kde IN je pocet procesu připadajících najeden procesor
■ Pocet hran (resp. jejich cena) spojujících podgrafy je minimalní
PA160
3
Jaro 2010
Shrnutí
■ Vlastnosti
■ Rovnoměrné rozložení zatěže
■ Minimalizace komunikace (minimum hran mezi jednotlivými podgrafy)
■ Problem je NP Úplný
■ Pouzívame heuristicke prístupy
■ Rychlost rozlození versus jeho kvalita
■ Dynamicke
■ Staticke
PA160 4 Jaro 2010
Vyrovnání zátěže a plánování
■ Vyrovnání zátěže: jak rozdělit úlohy mezi procesory
■ Plánování: v jakěm poradí je spustit
■ Úzce spolú souvisí (Často v distribuovaném systěmú synonyma)
PA160
5
Jaro 2010
Rozdělení úloh pro vyrovnání zátěže
Přístup k řešení problému je možno rozdělit podle následujících kritérií:
■ Cena Úlohy
■ Závislosti mezi Úlohami
■ Lokalita
PA160
6
Jaro 2010
Cena úlohy
■ Kdy známe cenu
■ Pred spustením ceieho problému
■ V prubehu řeSení, ale pred spuStením konkretní Úlohy
■ AZ po dokonCení konkretní ulohy
■ Variabilita ceny
PA160
7
Járo 2010
Rozdělení do tříd podle ceny
1. Všechny úlohy mají stejnou cenu: snadné
2. Ceny jsou rozdílné, ale zname: složitéjSí
3. Ceny nejsou znamy předem: nejtéžSí
PA160
8
Jaro 2010
Závislosti Uloh
■ Je pořadí spustení uloh dulezite?
■ Kdy jsou znamy zaavislosti
■ Pred spustením celeho problemu
■ Před spustením ulohy
■ Plnee dynamicky
PA160
9
Jaro 2010
Rozdělení do tříd podle závislosti
1. Úlohý jsou na sobe nezávisle: snádne
2. Závislosti jsou známe Ci predikovatelne: sloZitejSí
■ vlna
■ in- a out- stromý (vývázene nebo nevývázene)
■ obecne orientovane stromý (DAG)
3. Závislosti se dýnamický mení: nejtezSí
■ Např. ulohý prohledávání
PA160 10 Jaro 2010
Lokalita
■ Komunikují všechny úlohy stejně (nebo alespoň podobně)?
■ Je třeba některě spouštět „blízko" sebe?
■ Kdy jsou komunikaCní závislosti znamy?
PA160
11
Jaro 2010
Rozdělení do tříd podle lokality
1. Úlohy spolu nekomunikují (nejvyše při inicializaci): snadné
2. Komunikace ma znamy ci predikovatelny prubeh: složitéjSí
■ Pravidelny (napr. mřízka)
■ Nepravidelny
Napr. PDE řesice
3. Komunikace je predem neznáma: nejtéžsí
■ Např. diskretní simulace udalostí
PA160 12 Jaro 2010
Přístup k řešení
■ Obecne záleží na tom, kdy je konkrétní informace známa
■ Základní třídy:
■ Staticke (off-line algoritmy)
■ Semi-staticke (hybridní)
■ Dynamicke (on-line algoritmy)
■ Možne varianty (nikoliv vycerpavající vycet):
■ Staticke vyrovnaní zateže
■ Semi-staticke
■ Samoplanovaní (self-scheduling)
■ Distribuovane fronty Uloh
■ DAG planovaní
PA160 13 Jaro 2010
Semi-staticke vyrovnaní zateže
■ Pomalá zmena v parametrech, duleZitá lokalita
■ Iterativní prístup
■ PouZije staticky algoritmus
■ PouZije jej pro nekolik kroku (akceptuje „mírnou" nerovnovahu)
■ Přepodta novym statickym algoritmem
■ Často pouZívan v nasledujících oblastech
■ Časticove simulace
■ Vypocty na pomalu se menících mríZkach (gridy - ovsem v jinem smyslu neZ pouZívany v předchoZích lekcích)
PA160
14
Jaro 2010
Self Scheduling
■ Centralizovaný pool připravených úloh
■ Volne procesory výbírají z poolú
■ Nove (pod)úlohý se do poolú přidaavají
■ Púvodne navrZen pro planovaní cýklú v překladaCi
■ Vhodný pro
■ MnoZina nezavislých úloh
■ Úlohý s neznamými cenami
■ Lokalita nehraje roli
■ Centralizovaný pool snadno implementovatelný (napr. SMP)
PA160 15 Jaro 2010
Varianty
■ Self-scheduling nevhodné pro příliš malé úlohy
■ Sdružovaní úloh do shlukú
* Pevna velikost
* Rížene sdružovaní
* Zužovaní (tapering)
* Važene roždelovaní
PA160
16
Jaro 2010
Pevna velikost
■ Týpický off-line algoritmús
■ Výzadúje velmi mnoho informací (pocet a cena kazde úlohý, ...)
■ Je mozne nalezt optimalní řesení
■ Teoretický zajímava, v praxi neprílis poúzitelne
PA160
17
Jaro 2010
Rízeně sdružování
Poúzij velke shlúky na začatkú a mensí na konci
■ Nizsí rezie na začatkú, jemnejsí rozlození na konci
Velikost shlúkú
Ki = \—1
P
kde Ri je pocet zbyvajících úloh a p je pocet procesorú
PA160
18
Jaro 2010
Zužování
■ Analogicke předchozímu, ale velikost shluku je funkcí i variace ceny uloh
■ Vyuzíva historicka data
■ Mala variace => velke shluky
■ Velka variace => male shluky
PA160
19
Jaro 2010
Vážené rozdělování
■ Opet analogie self scheduling
■ Bere do Úvahy i výpoCetní sílu uzlU
■ Vhodne pro heterogenní systemy
■ PouZíva rovneZ historicke informace
PA160
20
Jaro 2010
Distribuované fronty úloh
■ Self-scheduling pro distribuovanou pamět
■ Namísto centralizovaného poolu fronta Uloh
■ Vhodné
■ Distribuované systémy
■ Lokalita nepřílis duleZita
■ Pro staticke i dynamicke zavislosti
■ Neznamou cenu uloh
PA160
21
Jaro 2010
Difuzní prístup
■ Zavádí závislost na topologii (předchozí neuvazují)
■ Vlastnosti
■ Lepe bere do uvahý lokalitu (resp. pozadavký na ni)
■ Ponekud pomalejsí
■ Musí znát cenu ulohý v okamziku jejího výtvorení
■ Nepracuje se závislostmi mezi ulohami
PA160
22
Jaro 2010
Príklad
■ Distribuovaný systém modelován jako graf
■ V každém kroku se spočte váha Uloh zbývajících na každém procesoru
■ Procesory si tuto informaci vymení a nasledne provedou výrovnaní
■ Možna vylepsení
■ Zohlednuje množství drive zaslanych dat
■ Lokalita není vyznamnym prvkem (presto zlepsení proti nahodnemu rozlození zateze)
PA160 23 Jaro 2010
DAG plánování
■ Opet grafovy model
■ Uzly představují ulohy (vypocty; prípadne vazene)
■ Hrany reprezentují závislosti a prípadne komunikaci (mohou byt rovnez vazene)
■ Vhodná např. pro digitalní zpracovaní signaalu (DAG znam)
■ Zakladní strategie: Rozdel DAG za minimalizace komunikace a zamestnaní vsech procesoru (minimalizace casu)
■ NP uplne
■ Oproti prostemu rozdelení grafu bere do uvahy zavislosti mezi ulohami
PA160
24
Jaro 2010
Praktické problémy
■ Kdý je vhodne
■ Pro středne zatízene sýstemý
■ Ú nízko zatízených - vzdý je volný procesor
■ Ú velmi zatízených - nehraje roli
■ Podle ceho rozhodnoút
■ Metriký úrcení výkonú
* Músí být snadno meéřiteln^
* Músí se promítat do optimalizovaných parametrú
■ Úrcení kvalitý
* Prúmerna doba „reakce"
PA160
25
Jaro 2010
Navřh přístupu
■ Merení zateze: fronty, vyuzití CPÚ
■ Rozhodovaní: staticke, dynamicke, adaptivní
■ Soucasti
■ Ktery proces prenest: preferovany nove procesy
■ Kdy proces přenest: vetsinou při dosazení nejake urovne (treshold)
■ Kam proces přenest: nejblizsí soused (difuze), nahodne, ...
■ Kde a jaka informace je k dispozici
* Rízeno: pozadavky (sender/receiver), casem (periodicke), zmenou stavu
PA160
26
Jaro 2010
Rozhodnutí řízeno vysílajícím (sender)
■ Pouze nove ulohý
■ Rozhodnutí: podle lokální kapacitý
■ Umístení
■ Náhodne: výber a posli
■ Limit: výzkousej n uzlu, pokud zádný pod limitem, ulohu nepřenásej
■ Nejkratsí: poptej paralelne a náhodne n uzlu; přesun na nejmene zatízený uzel pod limitem
PA160
27
Jaro 2010
Rozhodnutí řízeno přijímajícím (receiver)
■ Pokud odcházející (končící) proces sníží zátěž pod limit, vyber proces odjinud
■ Vhodne pro nove i cástecne rozpracovane Úlohy
■ Umístení:
■ Limit: vyzkousej sekvencne áž n dáisích uzlů
■ Nejkrátsí: poptej párálelne á náhodne n uzlu, vyber ten, ktery má nejvyssí záteez nád limitem
PA160
28
Járo 2010
Príklád: V System ze Stánfordu
■ Vymena informací iniciovana zmenoú stavú
■ Vyznamne zmeny zateze oznameny vsem úzlúm
■ M nejmene zatízenych úzlú jsoú přijímající, ostatní jsoú posílající
■ Přenosy iniciovany vysílajícím
■ Umístení:
■ Nahodne vyber mozneho přijímajícího
■ Pokúd je jeste přijímajícím (pod limitem), přesún úlohú
■ V opacnem případee zkús jiného
PA160 29 Jaro 2010
Príklad: Sprite z Berkeley
Centralizovaná informace (u koordinátora)
■ Update iniciován zmenou stavu
■ Přijímající: stanice bez interaktivního uZivatele pod limitem
Manualní selekCní strategie (uZivatel) - vZdy vysílající Umístení: dotaz na koordinatora
Stanice s ulohou se stane vysílajícím, pokud ma proces a přijde uZivatel
PA160 30 Jaro 2010
Migrace kodu a procesiu
■ Proces = kod + data + stack
■ Migrace procesu (silná mobilita)
■ Migrace kodu (slabá mobilita)
■ program vZdy startuje z pocatecního stavu
■ Flexibilita
■ Dynamicka konfigurace (na Zadost)
■ Není treba pouZívat preinstalovany software
PA160
31
Jaro 2010
Příklad: Sprite
■ Migrace procesu (i bezícího)
■ Přes sdíleny system souboru
■ Prenos stavu
■ Vsechno uloz do (sdíleneho) swapu
■ Presun tabulky stranek a deskriptory souboru přijímajícímu
■ Zaloz proces u přijímajícího a nahraj nezbytne stranky
■ Předej řízení
■ Jediny problem: komunikacní zavislosti
■ reseno presmerovaním po presunu
PA160 32 Jaro 2010
Migrace v heterogenních systemech
■ Podporovana pouze slaba mobilita v klasickych modelech
■ Rozvoj s vyuzitím virtualních stroju: skriptovací jazyky a Java
PA160
33
Jaro 2010
Odolnost proti výpadkům
■ Primární problém distribuovaných systémů
■ Základní složky
■ Rozpoznání výpadku
■ Réákcé na výpadek
■ Dosažení konsensu
PA160
34
Jaro 2010
Klasický příklad pro konsensus
■ Definice výchozího stavu
■ Mesto obklíCeno 4 armádami
■ KaZda armada ma v Cele generála
■ Rozhodnutí zaUtoCit musí udeiat vSichni 4 generaiove souCasne
■ Komunikace spolehliva, ale muZe trvat libovolne dlouho
■ Generalove mohou být zavraZdeeni (armada bez generala nebojuje)
■ Je mozne, abý se generalove shodli na rozhodnutí?
PA160
35
Jaro 2010
NemoZnost shody
■ Negativní teoreticky vysledek (Fischer, Lynch, Paterson: JACM, 32:2, 1985):
■ V asynchronních systémech nelze v konečném čase dosáhnout konsensu
PA160
36
Jaro 2010
Formainejsí definice
■ Máme mnozinu distribuovaných procesu s pocátecními stavý
e{0, i}
■ Pozadujeme, abý se vsechný shodlý na jedne hodnote
■ Dodatecná podmínka
■ Musí existovat případ shodý jak na stavu 0, tak na stavu i (triviální shoda není problem)
PA160
37
Jaro 2010
Silna shoda - podmínky
■ Žádné dva procesy se neliší ve stavu
■ Vysledny stav musí byt výchozím stavem alespoň jednoho ze zUCastnenych procesU
■ Kazdy proces se v konecnem case rozhodne pro nejaky stav a toto rozhodnutí je nerevokovatelne
PA160
38
Jaro 2010
Slaba shoda - podmínky
■ Žádne dvá procesy se nelisí ve stávu
■ Muze dojít k shode ná ruznych stávech
■ Alespon nektere procesy se v konecnem cáse rozhodnou pro nejáky stáv á toto rozhodnutí je nerevokovátelne
PA160
39
Járo 2010
Vlastnosti modelu
■ Asynchronicita
■ Neexistuje horní hranice pro cas, ktera proces potrebuje k jednomu kroku
■ Neexistuje horní hranice pro cas, ktery potrebuje dorucení zpravy
■ Neexistují synchronizovane hodiny
■ Předavaní zprav v point2point síti
■ Předpokladame:
■ Nejsou chyby v komunikaci
■ Proces bud funguje správne nebo se zhroutil
PA160
40
Jaro 2010
Důsledky
■ Neexistuje deterministický algoritmus, který vyřeší problém shody v asynchronním systemu s procesy, ktere se mohou zhroutit
■ Je totiz nemozne rozlisit nasledující případy
■ Proces neodpovída, protoze se zhroutil
■ Proces neodpovída, protoze je pomaly
■ V praxi překonavano zavedením timeoutu a ignorovaním (případne „zabitím") prílis pomalych procesu
■ Timeouty soucastí tzv. Failure Detectors
PA160 41 Jaro 2010
Fault tolerantní broadcast
■ Problém shody by byl řešitelný, pokud by existoval vhodný typ fault tolerantního broadcastu
■ RUzne typy broadcastu
■ Zakladní spolehlivy
■ FIFO broadcast
■ PríCinny (Casual) broadcast
■ Atomický broadcast - ekvivalentní na řesení problemu shody v asynchronním prostredí
PA160
42
Jaro 2010
Spolehlivý broadcast
■ Je možno jej zkonstruovat pomocí dvoubodových primitiv send
a receive
■ Základní vlastnosti
■ Správnost: Pokud korektní proces p poSle broadcastem zpravu m, pak ji take eventuaine doruCí.
■ Shodá: Pokud korektní proces p posle broadcastem zpravu m, pak ji eventuaine dorucí vsechný korektní procesy.
■ Integrita: Jakoukoliv zpravu m proces dorucí pouze jednou a pouze tehdý, pokud býla dříve poslana nejakým procesem p.
PA160
43
Jaro 2010
Difuzní algoritmus
■ Jednoduche řesení
■ Pouzíva send a receive
■ Princip
■ Proces p posílající broadcast oznac posílanou zpravu m jednak svym identifikatorem, jednak pořadovym císlem poslane broadcastove zpravy a posle ji vsem svym sousedum
■ Přijetí zpravy se pak sklada z:
* Vlastního dorucení zpravy (prave jednou, podle klíce odesilatele a pořradove zpravy)
* Pokud sam není puvodní odesilatel, pak ji odesle vsem svym sousedum
Prijetí se provede pouze jednou, dalsí prisle zpravy se stejnym klícem se ignorují
PA160 44 Jaro 2010
FIFO Broadcast
■ Spolehlivý broadcast neklade žádná omezení na pořadí doručení zprav
■ Je tedý možne získat naslednou zpravu (z pohledu odesilatele) dříve, nez je přijata pUvodní
■ FIFO broadcast: zpravý od jednoho vysílajícího musí být doručený ve stejnem pořadí, v jakem je výslal
■ FIFO broadcast = Reliable broadcast + FIFO usporadaní
■ Pokud proces posle zpravu m dříve nez zpravu m', pak zadný správný proces nedorucí zpravu m' dříve nez zpravu m.
■ Je mozno jej výtvořit jako rozsíření Reliable broadcastu
PA160 45 Jaro 2010
Príčinný broadcast
■ FIFO broadcast stále není dostačující: je možno dostat zprávu od tretí strany, ktera je reakcí na zpravu pUvodní drive, než obdržíme pUvodní zpravu.
■ Resení: príčinný broadcast
■ Casual broadcast = Reliable broadcast + Přícinne uspořadaní
■ Jestliže skupinove odeslaní zpravy m přícinne předchazí zpravu m', pak žadný správný proces nedorucí zpravu m' dríve nez m.
■ Je možno vytvořit jako rozsíření FIFO broadcastu
PA160
46
Jaro 2010
Atomický broadcast
■ Ani příčinný broadcast není dostačující: je občas treba garantovat spravne pořadí doručení vSech replik
■ Dve bankovní pobočky: jedna dostane dříve informaci o tom, že ma přičíst Urok a teprve nasledne Úložku, druha naopak. Výsledkem je nekonzistentní stav.
■ Atomic broadcast = Reliable broadcast + Úplne uspořadaní
■ Neexistuje v asynchronních sýstemech
PA160
47
Jaro 2010
Timed Reliable Broadcast
■ Cesta k praktické realizaci
■ Zavede horní limit na Cas, do néhoZ se musí zprava doruCit
■ Timed Reliable broadcast = Reliable broadcast + Timeliness
■ Existuje znama konstanta A takova, Ze jestliZe zprava m je skupinove vyslana v case t, pak zadný správný proces ji nedoruc po case t + A.
■ Dosazitelne v synchronních sítích
■ Existuje transformace, ktera jakýkoliv Timed Reliable broadcast rozsíří na atomický broadcast.
PA160 48 Jaro 2010
Failure Detectors
■ Zavedení castecne synchronizace
■ Rozpoznaní spatnych (zhroucenych) procesu
■ Častecna synchronizace je skryta v detektorech zhroucení
■ Aplikace se od nich dozví, ktere procesy nekomunikují
PA160
49
Jaro 2010
Failure Detectors - základní vlastnosti
■ Každý proces ma lokalní Failure Detector Modul
■ Každý modul si drží sežnam potencialne zhroucených užlu
■ Lokalní proces se pta použe lokalního modulu
■ Modulý si meži sebou výmenují informaci
■ Jsou nespolehlivé - potencialne žhroucený užel muže být že sežnamu poždeřji odstraneřn
■ Aplikace pracuje se specifikací, nikoliv implementací
PA160 50 Jaro 2010
Perfektní detektor
■ Zakladní vlastnosti
■ Přesnost: Zadny sprävny proces se nikdy nedostane do seznamu potencialne zhroucenych v zadnem FD
■ Úplnost: Kazdy skutecne zhrouceny uzel se jednou dostane do seznamu potencialnee zhroucenych ve vsech FD
■ Vhodna abstrakce
■ Tezce implementovatelne
■ Existují zeslabení tohoto modelu
PA160
51
Jaro 2010
Zeslabení perfektního detektoru
■ V úplnosti
■ Každý skutečně zhroucený proces je eventuálně zařazen do seznamů některých spravných úzlú
■ V presnosti
■ Nektere spravne procesy nejsoú nikdý zařazený do zadneho seznamů
■ Prípadne slabsí: Existuje cas, po jehoz úplýnútí není zadný spravný proces zařazen v seznamú potencialne zhroúcených zadneho spravneho FD
■ Nejslabsí: Existúje cas, po jehoz úplýnútí nektere spravne procesý nejsoú nikdý zařazený do seznamú zadneho FD
PA160
52
Jaro 2010
Problem shodý a FD
■ Problem shody je mozno vyZesit za pouzití perfektního detektoru selhaní
■ Problem shody je mozno vysesit i za pouzití slabsích FD
■ Problem shody je mozno vysesit za pouzití FD zalozenem na zeslabenem psedpokladu uplnosti i nejslabsim psedpokladu psesnosti (to je take nejslabsí FD, jehoz pomocí lze problem shody vyrsessit)
PA16Q
S3
Jaro 2Q1Q