PA160 Vyrovnání zátěže (Load Balancing) Distribuované plánování (Dist. Scheduling) Odolnost proti výpadkům (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 takové přidělení úloh procesorům, které minimalizuje celkový čas výpočtu PA160 2 Jaro 2006 Grafová reprezentace Máme množinu úloh N se závislostmi, kterou reprezentujeme jako graf G(V, U) Vrcholy jsou procesy Hrana odpovídá závislosti mezi procesy Graf potřebujeme rozložit následujícím způsobem: N = N1 N2 . . . Np při platnosti |Ni| |N|/p kde |Ni| je počet procesů připadajících na jeden procesor PA160 3 Jaro 2006 Shrnutí Vlastnosti Rovnoměrné rozložení zátěže Minimalizace komunikace (minimum hran mezi jednotlivými podgrafy) Problém je NP úplný Používáme heuristické přístupy Rychlost rozložení versus jeho kvalita Dynamické Statické PA160 4 Jaro 2006 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 pořadí je spustit Úzce spolu souvisí (často v distribuovaném systému synonyma) PA160 5 Jaro 2006 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 2006 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 7 Jaro 2006 Rozdělení do tříd podle ceny 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 8 Jaro 2006 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 9 Jaro 2006 Rozdělení do tříd podle závislosti 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 10 Jaro 2006 Lokalita Komunikují všechny úlohy stejně (nebo alespoň podobně)? Je třeba některé spouštět ,,blízko`` sebe? Kdy jsou komunikační závislosti známy? PA160 11 Jaro 2006 Rozdělení do tříd podle lokality 1. Úlohy spolu nekomunikují (nejvýše při inicializaci): snadné 2. Komunikace má známý či predikovatelný průběh: složitější 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 12 Jaro 2006 Přístup k řešení Obecně záleží na tom, kdy je konkrétní informace známa 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í PA160 13 Jaro 2006 Semi-statické vyrovnání zátěže 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`` nerovnováhu) Přepočítá novým statickým algoritmem Často používán v následujících oblastech Částicové simulace Výpočty na pomalu se měnících mřížkách (gridy ­ ovšem v jiném smyslu než používány v předchozích lekcích) PA160 14 Jaro 2006 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řekladači Vhodný pro Množina nezávislých úloh Úlohy s neznámými cenami Lokalita nehraje roli Centralizovaný pool snadno implementovatelný (např. SMP) PA160 15 Jaro 2006 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 16 Jaro 2006 Pevná velikost Typický off-line algoritmus Vyžaduje velmi mnoho informací (počet a cena každé úlohy, . . . ) Je možné nalézt optimální řešení Teoreticky zajímavá, v praxi nepříliš použitelné PA160 17 Jaro 2006 Ří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 Ki = Ri p kde Ri je počet zbývajících úloh a p je počet procesorů. PA160 18 Jaro 2006 Zužování Analogické předchozímu, ale velikost shluku je funkcí i variace ceny úloh Využívá historická data Malá variace = velké shluky Velká variace = malé shluky PA160 19 Jaro 2006 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 PA160 20 Jaro 2006 Distribuované fronty úloh Self-scheduling pro distribuovanou paměť 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 21 Jaro 2006 Difuzní přístup Zavádí závislost na topologii (předchozí neuvažují) 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 22 Jaro 2006 Příklad Distribuovaný systém modelován jako graf V každém kroku se spočte váha úloh zbývajících na každém procesoru Procesory si tuto informaci vymění a následně provedou vyrovnání Možná vylepšení Zohledňuje množství dříve zaslaných dat Lokalita není významným prvkem (přesto zlepšení proti náhodnému rozložení zátěže) PA160 23 Jaro 2006 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 (mohou být rovněž vážené) Vhodné např. pro digitální zpracování signálu (DAG znám) Základní strategie: Rozděl DAG za minimalizace komunikace a zaměstnání všech procesorů (minimalizace času) NP úplné Oproti prostému rozdělení grafu bere do úvahy závislosti mezi úlohami PA160 24 Jaro 2006 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 25 Jaro 2006 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é úrovně (treshold) Kam proces přenést: nejbližší soused (difuze), náhodně, . . . Kde a jaká informace je k dispozici Řízeno: požadavky (sender/receiver), časem (periodické), změnou stavu PA160 26 Jaro 2006 Rozhodnutí řízeno vysílajícím (sender) 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, úlohu nepřenášej Nejkratší: poptej paralelně a náhodně n uzlů; přesuň na nejméně zatížený uzel pod limitem PA160 27 Jaro 2006 Rozhodnutí řízeno přijímajícím (receiver) Pokud odcházející (končící) proces sníží zátěž pod limit, vyber 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, který má nejvyšší zátěž nad limitem PA160 28 Jaro 2006 Příklad: V System ze Stanfordu 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í, ostatní jsou 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řesuň úlohu V opačném případě zkus jiného PA160 29 Jaro 2006 Příklad: Sprite z Berkeley Centralizovaná informace (u koordinátora) Update iniciován změnou stavu Přijímající: stanice bez interaktivního uživatele pod limitem Manuální selekční strategie (uživatel) ­ vždy vysílající Umístění: dotaz na koordinátora Stanice s úlohou se stane vysílajícím, pokud má proces a přijde uživatel PA160 30 Jaro 2006 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 preinstalovaný software PA160 31 Jaro 2006 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ímu 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 PA160 32 Jaro 2006 Migrace v heterogenních systémech Podporována pouze slabá mobilita v klasických modelech Rozvoj s využitím virtuálních strojů: skriptovací jazyky a Java PA160 33 Jaro 2006 Odolnost proti výpadkům Primární problém distribuovaných systémů Základní složky Rozpoznání výpadku Reakce na výpadek Dosažení konsensu PA160 34 Jaro 2006 Klasický příklad pro konsensus 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é současně Komunikace spolehlivá, ale může trvat libovolně dlouho Generálové mohou být zavražděni (armáda bez generála nebojuje) Je možné, aby se generálové shodli na rozhodnutí? PA160 35 Jaro 2006 Nemožnost shody Negativní teoretický výsledek (Fischer, Lynch, Paterson: JACM, 32:2, 1985): V asynchronních systémech nelze v konečném čase dosáhnout konsensu PA160 36 Jaro 2006 Formálnější definice Máme množinu distribuovaných procesů s počátečními stavy {0, 1} Požadujeme, aby se všechny shodly na jedné hodnotě Dodatečná podmínka Musí existovat případ shody jak na stavu 0, tak na stavu 1 (triviální shoda není problém) PA160 37 Jaro 2006 Silná shoda ­ podmínky Žádné dva procesy se neliší ve stavu Výsledný stav musí být výchozím stavem alespoň jednoho ze zúčastněných procesů Každý proces se v konečném čase rozhodne pro nějaký stav a toto rozhodnutí je nerevokovatelné PA160 38 Jaro 2006 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 rozhodnou pro nějaký stav a toto rozhodnutí je nerevokovatelné PA160 39 Jaro 2006 Vlastnosti modelu Asynchronicita Neexistuje horní hranice pro čas, která proces potřebuje k jednomu kroku Neexistuje horní hranice pro čas, který potřebuje doručení zprávy 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 40 Jaro 2006 Důsledky Neexistuje deterministický algoritmus, který vyřeší problém shody v asynchronním systému s procesy, které se mohou 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 ignorováním (případně ,,zabitím``) příliš pomalých procesů Timeouty součástí tzv. Failure Detectors PA160 41 Jaro 2006 Fault tolerantní broadcast Problém shody by byl řešitelný, pokud by existoval vhodný typ fault tolerantního broadcastu Různé typy broadcastů Základní spolehlivý FIFO broadcast Příčinný (Casual) broadcast Atomický broadcast ­ ekvivalentní na řešení problému shody v asynchronním prostředí PA160 42 Jaro 2006 Spolehlivý broadcast Je možno jej zkonstruovat pomocí dvoubodových primitiv send a receive Základní vlastnosti Správnost: Pokud korektní proces p pošle broadcastem zprávu m, pak ji také eventuálně doručí. Shoda: Pokud korektní proces p pošle broadcastem zprávu m, pak ji eventuálně doručí všechny korektní procesy. Integrita: Jakoukoliv zprávu m proces doručí pouze jednou a pouze tehdy, pokud byla dříve poslána nějakým procesem p. PA160 43 Jaro 2006 Difuzní algoritmus Jednoduché řešení Používá send a receive Princip Proces p posílající broadcast označí posílanou zprávu m jednak svým identifikátorem, jednak pořadovým číslem poslané broadcastové zprávy 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 odesilatele a pořadové zprávy) Pokud sám není původní odesilatel, pak ji odešle všem svým sousedům Přijetí se provede pouze jednou, další přišlé zprávy se stejným klíčem se ignorují PA160 44 Jaro 2006 FIFO Broadcast Spolehlivý broadcast neklade žádná omezení na pořadí doručení zpráv Je tedy možné získat následnou zprávu (z pohledu odesilatele) dříve, než je přijata původní FIFO broadcast: zprávy od jednoho vysílajícího musí být doručeny ve stejném pořadí, v jakém je vyslal FIFO broadcast = Reliable broadcast + FIFO uspořádání Pokud proces pošle zprávu m dříve než zprávu m , pak žádný správný proces nedoručí zprávu m dříve než zprávu m. Je možno jej vytvořit jako rozšíření Reliable broadcastu PA160 45 Jaro 2006 Příčinný broadcast FIFO broadcast stále není dostačující: je možno dostat zprávu od třetí strany, která je reakcí na zprávu původní dříve, než obdržíme původní zprávu. Řešení: příčinný broadcast Casual broadcast = Reliable broadcast + Příčinné uspořádání Jestliže skupinové odeslání zprávy m příčinně předchází zprávu m , pak žádný správný proces nedoručí zprávu m dříve než m. Je možno vytvořit jako rozšíření FIFO broadcastu PA160 46 Jaro 2006 Atomický broadcast Ani příčinný broadcast není dostačující: je občas třeba garantovat správné pořadí doručení všech replik Dvě bankovní pobočky: jedna dostane dříve informaci o tom, že má přičíst úrok a teprve následně úložku, druhá naopak. Výsledkem je nekonzistentní stav. Atomic broadcast = Reliable broadcast + Úplné uspořádání Neexistuje v asynchronních systémech PA160 47 Jaro 2006 Timed Reliable Broadcast Cesta k praktické realizaci Zavede horní limit na čas, do něhož se musí zpráva doručit Timed Reliable broadcast = Reliable broadcast + Timeliness Existuje známá konstanta taková, že jestliže zpráva m je skupinově vyslána v čase t, pak žádný správný proces ji nedoručí po čase t + . Dosažitelné v synchronních sítích Existuje transformace, která jakýkoliv Timed Reliable broadcast rozšíří na atomický broadcast. PA160 48 Jaro 2006 Failure Detectors Zavedení částečné synchronizace Rozpoznání špatných (zhroucených) procesů Částečná synchronizace je skryta v detektorech zhroucení Aplikace se od nich dozví, které procesy nekomunikují PA160 49 Jaro 2006 Failure Detectors ­ základní vlastnosti Každý proces má lokální Failure Detector Modul Každý modul si drží seznam potenciálně zhroucených uzlů Lokální proces se ptá pouze lokálního modulu Moduly si mezi sebou vyměňují informaci Jsou nespolehlivé ­ potenciálně zhroucený uzel může být ze seznamu později odstraněn Aplikace pracuje se specifikací, nikoliv implementací PA160 50 Jaro 2006 Perfektní detektor Základní vlastnosti Přesnost: Žádný správný proces se nikdy nedostane do seznamu potenciálně zhroucených v žádném FD Úplnost: Každý skutečně zhroucený uzel se jednou dostane do seznamu potenciálně zhroucených ve všech FD Vhodná abstrakce Těžce implementovatelné Existují zeslabení tohoto modelu PA160 51 Jaro 2006 Zeslabení perfektního detektoru V úplnosti Každý skutečně zhroucený proces je eventuálně zařazen do seznamu některých správných uzlů V přesnosti Některé správné procesy nejsou nikdy zařazeny do žádného seznamu Případně slabší: Existuje čas, po jehož uplynutí není žádný správný proces zařazen v seznamu potenciálně zhroucených žádného správného FD Nejslabší: Existuje čas, po jehož uplynutí některé správné procesy nejsou nikdy zařazeny do seznamu žádného FD PA160 52 Jaro 2006 Problém shody a FD Problém shody je možno vyřešit za použití perfektního detektoru selhání Problém shody je možno vyřešit i za použití slabších FD Problém shody je možno vyřešit za použití FD založeném na zeslabeném předpokladu úplnosti i nejslabším předpokladu přesnosti (to je také nejslabší FD, jehož pomocí lze problém shody vyřešit) PA160 53 Jaro 2006