PA160 Vyrovnání zátěže (Load Balai Distribuované plánování (Dis Odolnost proti výpadků (Fau Vyrovnání zátěže ■ Grafový model: ■ Mějme graf G(V, U) a rozložme jej tak, že platí: N — Ni U N2 U ... U Np tak, že platíV|iVi ■ Pokud N — {úlohy} (každou se stejnou cenou) a hrana znamená, že úloha i potřebuje komunikovat s úlohou j, (partitioning) grafu znamená * rovnoměrné rozložení zátěže * minimalizaci komunikace ■ Problém je NP úplný - používáme heuristické prístupy ■ Rychlost rozložení versus jeho kvalita PA160 2 Vyrovnání zátěže a plánov ■ Vyrovnání zátěže: jak rozdělit úlohy mezi proces ■ Plánování: v jakém pořadí je spustit ■ Úzce spolu souvisí (často v distribuovaném systi PA160 3 Rozdělení úloh pro vyrovnání Přístup k řešení problému je možno rozdělit podle r kritérií: ■ Cena úlohy ■ Závislosti mezi úlohami ■ Lokalita PA160 4 Cena úlohy ■ Kdy známe cenu ■ Před spuštěním celého problému ■ V průběhu řešení, ale před spuštěním konkrétní úlohy ■ Až po dokončení konkrétní úlohy ■ Variabilita ceny PA160 5 Rozdělení do tříd podle ce 1. Všechny úlohy mají stejnou cenu: snadné 2. Ceny jsou rozdílné, ale známé: složitější 3. Ceny nejsou známy předem: nejtěžší PA160 6 Závislosti úloh ■ Je pořadí spuštění úloh důležité? ■ Kdy jsou známy závislosti ■ Před spuštěním celého problému ■ Před spuštěním úlohy ■ Plně dynamicky PA160 7 Rozdělení do tříd podle závis 1. Úlohy jsou na sobě nezávislé: snadné 2. Závislosti jsou známé či predikovatelní: složitější ■ vlna ■ in- a out- stromy (vyvážené nebo nevyvážené) ■ obecné orientované stromy (DAG) 3. Závislosti se dynamicky mění: nejtěžší ■ Např. úlohy prohledávání PA160 8 Lokalita ■ Komunikují všechny úlohy stejně (nebo alespoň | ■ Je třeba některé spouštět „blízko" sebe? ■ Kdy jsou komunikační závislosti známy? PA160 9 Rozdělení do tříd podle lok; 1. Úlohy spolu nekomunikují (nejvýše při inicializaci 2. Komunikace má známý či predikovatelný průběh ■ Pravidelný (např. mřížka) ■ Nepravidelný Např. PDE řešiče 3. Komunikace je předem neznámá: nejtěžší ■ Např. diskrétní simulace událostí PA160 10 Přístup k řešení Obecně záleží na tom, kdy je konkrétní informao Základní třídy: ■ Statické (off-line algoritmy) ■ Semi-statické (hybridní) ■ Dynamické (on-line algoritmy) Možné varianty (nikoliv vyčerpávající výčet): ■ Statické vyrovnání zátěže ■ Semi-statické ■ Samoplánování (self-scheduling) ■ Distribuované fronty úloh ■ DAG plánování 60 11 Semi-statické vyrovnání zál ■ Pomalá změna v parametrech, důležitá lokalita ■ Iterativní přístup ■ Použije statický algoritmus ■ Použije jej pro několik kroků (akceptuje „mírnou" nerovr ■ Přepočítá novým statickým algoritmem ■ Často používán v následujících oblastech ■ Časticové simulace ■ Výpočty na pomalu se měnících mřížkách (gridy - ovše než používány v předchozích lekcích) PA160 12 Self Scheduling ■ Centralizovaný pool připravených úloh ■ Volné procesory vybírají z poolu ■ Nové (pod)úlohy se do poolu přidávají ■ Původně navržen pro plánování cyklů v překládá ■ Vhodný pro ■ Množina nezávislých úloh ■ Úlohy s neznámými cenami ■ Lokalita nehraje roli ■ Centralizovaný pool snadno implementovatelný (např. S PA160 13 Varianty ■ Self-scheduling nevhodné pro příliš malé úlohy ■ Sdružování úloh do shluků * Pevná velikost * Řízené sdružování * Zužování (tapering) * Vážené rozdělování PA160 14 Pevná velikost Typický off-line algoritmus Vyžaduje velmi mnoho informací (počet a cena k Je možné nalézt optimální řešení Teoreticky zajímavá, v praxi nepříliš použitelné 60 15 Řízené sdružování Použij velké shluky na začátku a menší na konci ■ Nižší režie na začátku, jemnější rozložení na konci Velikost shluku Kí = r—i p kde Ri je počet zbývajících úloh a p je počet pro PA160 16 Zužování ■ Analogické předchozímu, ale velikost shluku je fi ceny úloh ■ Využívá historická data ■ Malá variace =>► velké shluky ■ Velká variace malé shluky PA160 17 Vážené rozdělování Opět analogie self scheduling Bere do úvahy i výpočetní sílu uzlů Vhodné pro heterogenní systémy Používá rovněž historické informace 60 18 Distribuované fronty úlo ■ Self-scheduling pro distribuovanou pamět ■ Namísto centralizovaného poolu fronta úloh ■ Vhodné ■ Distribuované systémy ■ Lokalita nepříliš důležitá ■ Pro statické i dynamické závislosti ■ Neznámou cenu úloh PA160 19 Difúzni přístup ■ Zavádí závislost na topologii (předchozí neuvážu ■ Vlastnosti ■ Lépe bere do úvahy lokalitu (resp. požadavky na ni) ■ Poněkud pomalejší ■ Musí znát cenu úlohy v okamžiku jejího vytvoření ■ Nepracuje se závislostmi mezi úlohami PA160 20 Příklad Distribuovaný systém modelován jako graf V každém kroku se spočte váha úloh zbývajících procesoru Procesory si tuto informaci vymění a následně pi vyrovnání Možná vylepšení ■ Zohledňuje množství dříve zaslaných dat Lokalita není významným prvkem (přesto zlepše náhodnému rozložení zátěže) 60 21 DAG plánování ■ Opět grafový model ■ Uzly představují úlohy (výpočty; případně vážené) ■ Hrany reprezentují závislosti a případně komunikaci (m( vážené) ■ Vhodné např. pro digitální zpracování signálu (D ■ Základní strategie: Rozděl DAG za minimalizace a zaměstnání všech procesorů (minimalizace čai ■ NP úplné ■ Oproti prostému rozdělení grafu bere do úvahy závislos PA160 22 Praktické problémy ■ Kdy je vhodné ■ Pro středně zatížené systémy ■ U nízko zatížených - vždy je volný procesor ■ U velmi zatížených - nehraje roli ■ Podle čeho rozhodnout ■ Metriky určení výkonu * Musí být snadno měřitelné * Musí se promítat do optimalizovaných parametrů ■ Určení kvality * Průměrná doba „reakce" PA160 23 Návrh přístupu ■ Měření zátěže: fronty, využití CPU ■ Rozhodování: statické, dynamické, adaptivní ■ Součásti ■ Který proces přenést: preferovány nové procesy ■ Kdy proces přenést: většinou při dosažení nějaké úrovr ■ Kam proces přenést: nejbližší soused (difúze), náhodne ■ Kde a jaká informace je k dispozici * Řízeno: požadavky (sender/receiver), časem (periodi PA160 24 Rozhodnutí řízeno vysílajícím ( ■ Pouze nové úlohy ■ Rozhodnutí: podle lokální kapacity ■ Umístění ■ Náhodné: vyber a pošli ■ Limit: vyzkoušej n uzlů, pokud žádný pod limitem, úlohi ■ Nejkratší: poptej paralelně a náhodně n uzlů; přesuň ní uzel pod limitem PA160 25 Rozhodnutí řízeno přijímajícím ( ■ Pokud odcházející (končící) proces sníží zátěž pi proces odjinud ■ Vhodné pro nové i částečně rozpracované úlohy ■ Umístění: ■ Limit: vyzkoušej sekvenčně až n dalších uzlů ■ Nejkratší: poptej paralelně a náhodně n uzlů, vyber ten zátěž nad limitem PA160 26 Příklad: V System ze Stanfc Výměna informací iniciována změnou stavu ■ Významné změny zátěže oznámeny všem uzlům M nejméně zatížených uzlů jsou přijímající, ostc posílající Přenosy iniciovány vysílajícím Umístění: ■ Náhodně vyber možného přijímajícího ■ Pokud je ještě přijímajícím (pod limitem), přesun úlohu ■ V opačném případě zkus jiného 60 27 Příklad: Sprite z Berkele Centralizovaná informace (u koordinátora) ■ Update iniciován změnou stavu ■ Přijímající: stanice bez interaktivního uživatele pod limit Manuální selekční strategie (uživatel) - vždy vys Umístění: dotaz na koordinátora Stanice s úlohou se stane vysílajícím, pokud má uživatel 60 28 Migrace kódu a procesů Proces = kód + data + stack Migrace procesu (silná mobilita) Migrace kódu (slabá mobilita) ■ program vždy startuje z počátečního stavu Flexibilita ■ Dynamická konfigurace (na žádost) ■ Není třeba používat přeinstalovaný software 60 29 Příklad: Sprite Migrace procesu (i běžícího) Přes sdílený systém souborů Přenos stavu ■ Všechno ulož do (sdíleného) swapu ■ Přesuň tabulky stránek a deskriptory souborů přijímajíc! ■ Založ proces u přijímajícího a nahraj nezbytné stránky ■ Předej řízení Jediný problém: komunikační závislosti ■ řešeno přesměrováním po přesunu 60 30 Migrace v heterogenních syst< ■ Podporována pouze slabá mobilita v klasických r ■ Rozvoj s využitím virtuálních strojů: skriptovací jc PA160 31 Odolnost proti výpadkůr ■ Primární problém distribuovaných systémů ■ Základní složky ■ Rozpoznání výpadku ■ Reakce na výpadek ■ Dosažení konsensu PA160 32 Klasický příklad pro konser ■ Definice výchozího stavu ■ Město obklíčeno 4 armádami ■ Každá armáda má v čele generála ■ Rozhodnutí zaútočit musí udělat všichni 4 generálové s ■ Komunikace spolehlivá, ale může trvat libovolně dlouho ■ Generálové mohou být zavražděni (armáda bez generá ■ Je možné, aby se generálové shodli na rozhodni PA160 33 Nemožnost shody ■ Negativní teoretický výsledek (Fischer, Lynch, Pc 32:2, 1985): ■ V asynchronních systémech nelze v konečném c konsensu PA160 34 Formálnější definice ■ Máme množinu distribuovaných procesů s počati e {0,1} ■ Požadujeme, aby se všechny shodly na jedné hc ■ Dodatečná podmínka ■ Musí existovat případ shody jak na stavu 0, tak na staví není problém) PA160 35 Silná shoda - podmínk\ ■ Žádné dva procesy se neliší ve stavu ■ Výsledný stav musí být výchozím stavem alespo zúčastněných procesů ■ Každý proces se v konečném čase rozhodne prc a toto rozhodnutí je nerevokovatelné PA160 36 Slabá shoda - podmínky ■ Žádné dva procesy se neliší ve stavu ■ Může dojít k shodě na různých stavech ■ Alespoň některé procesy se v konečném čase ro nějaký stav a toto rozhodnutí je nerevokovatelné PA160 37 Vlastnosti modelu ■ Asynchronicita ■ Neexistuje horní hranice pro čas, která proces potřebuje ■ Neexistuje horní hranice pro čas, který potřebuje doručí ■ Neexistují synchronizované hodiny ■ Předávání zpráv v point2point síti ■ Předpokládáme: ■ Nejsou chyby v komunikaci ■ Proces buď funguje správně nebo se zhroutil PA160 38 Důsledky Neexistuje deterministický algoritmus, který vyre, shody v asynchronním systému s procesy které zhroutit Je totiž nemožné rozlišit následující případy ■ Proces neodpovídá, protože se zhroutil ■ Proces neodpovídá, protože je pomalý V praxi překonáváno zavedením timeoutů a igno (případně „zabitím") příliš pomalých procesů Timeouty součástí tzv. Failure Detectors 60 39 Fault tolerantní broadcas ■ Problém shody by byl řešitelný, pokud by existov fault tolerantního broadcastu ■ Různé typy broadcastu ■ Základní spolehlivý ■ FIFO broadcast ■ Příčinný (Casual) broadcast ■ Atomický broadcast - ekvivalentní na řešení problému i v asynchronním prostředí PA160 40 Spolehlivý broadcast Je možno jej zkonstruovat pomocí dvoubodovýď a receive Základní vlastnosti ■ Správnost: Pokud korektní proces p pošle broadcaster také eventuálně doručí. ■ Shoda: Pokud korektní proces p pošle broadcastem zp eventuálně doručí všechny korektníprocesy. ■ Integrita: Jakoukoliv zprávu m proces doručí pouze jec pokud byla dříve poslána nějakým procesem p. 60 41 Difúzni algoritmus Jednoduché řešení Používá send a receive Princip ■ Proces p posílající broadcast označí posílanou zprávu i identifikátorem, jednak pořadovým číslem poslané broa a pošle ji všem svým sousedům ■ Přijetí zprávy se pak skládá z: * Vlastního doručení zprávy (právě jednou, podle klíče a pořadové zprávy) * Pokud sám není původní odesilatel, pak ji odešle vše Přijetí se provede pouze jednou, další přišlé zprávy se s ignorují 60 42 FIFO Broadcast Spolehlivý broadcast neklade žádná omezení na doručení zpráv Je tedy možné získat následnou zprávu (z pohle dříve, než je přijata původní FIFO broadcast: zprávy od jednoho vysílajícího r doručeny ve stejném pořadí, v jakém je vyslal FIFO broadcast = Reliable broadcast + FIFO usp ■ Pokud proces pošle zprávu ra dříve než zprávu ra/, pal< proces nedoručí zprávu ra/ dříve než zprávu ra. Je možno jej vytvořit jako rozšíření Reliable broa 60 43 Příčinný broadcast FIFO broadcast stále není dostačující: je možno od třetí strany, která je reakcí na zprávu původní obdržíme původní zprávu. Řešení: příčinný broadcast Casual broadcast = Reliable broadcast + Příčinn ■ Jestliže skupinové odeslání zprávy m příčinně předchá; žádný správný proces nedoručí zprávu mf dříve než m Je možno vytvořit jako rozšíření FIFO broadcasti 60 44 Atomický broadcast ■ Ani příčinný broadcast není dostačující: je občas garantovat správné pořadí doručení všech replik ■ Dvě bankovní pobočky: jedna dostane dříve informaci c úrok a teprve následně úložku, druhá naopak. Výsledke nekonzistentní stav. ■ Atomic broadcast = Reliable broadcast + Úplné i ■ Neexistuje v asynchronních systémech PA160 45 Timed Reliable Broadcas Cesta k praktické realizaci Zavede horní limit na čas, do něhož se musí zpr< Timed Reliable broadcast = Reliable broadcast + ■ Existuje známá konstanta A taková, že jestliže zpráva 1 vyslána v čase t, pak žádný správný proces ji nedoručí Dosažitelné v synchronních sítích Existuje transformace, která jakýkoliv Timed Reli rozšíří na atomický broadcast. 60 46 Failure Detectors ■ Zavedení částečné synchronizace ■ Rozpoznání špatných (zhroucených) procesů ■ Částečná synchronizace je skryta v detektorech ■ Aplikace se od nich dozví, které procesy nekomunikují PA160 47 Failure Detectors - základní vie ■ Každý proces má lokální Failure Detector Modul ■ Každý modul si drží seznam potenciálně zhroucc ■ Lokální proces se ptá pouze lokálního modulu ■ Moduly si mezi sebou vyměňují informaci ■ Jsou nespolehlivé - potenciálně zhroucený uzel seznamu později odstraněn ■ Aplikace pracuje se specifikací, nikoliv implemen PA160 48 Perfektní detektor Základní vlastnosti ■ Přesnost: Žádný správný proces se nikdy nedostane d potenciálně zhroucených v žádném FD ■ Úplnost: Každý skutečně zhroucený uzel se jednou do potenciálně zhroucených ve všech FD Vhodná abstrakce Těžce implementovatelné Existují zeslabení tohoto modelu 60 49 Zeslabení perfektního detek V úplnosti ■ Každý skutečně zhroucený proces je eventuálně zaraze některých správných uzlů V přesnosti ■ Některé správné procesy nejsou nikdy zařazeny do žád ■ Případně slabší: Existuje čas, po jehož uplynutí není žá zařazen v seznamu potenciálně zhroucených žádného i ■ Nejslabší: Existuje čas, po jehož uplynutí některé správ nikdy zařazeny do seznamu žádného FD 60 50 Problém shody a FD ■ Problém shody je možno vyřešit za použití perfel selhání ■ Problém shody je možno vyřešit i za použití slab ■ Problém shody je možno vyřešit za použití FD zí zeslabeném předpokladu úplnosti i nejslabším pi přesnosti (to je také nejslabší F D, jehož pomocí i shody vyřešit) PA160 51