Přidělování práce v prostředí s distribuovanou pamětí, možnosti urychlení výpočtu a přiřazení procesů na jednotlivé uzly.

Přidělování práce v prostředí s distribuovanou pamětí

Pozn. Přednáška z PPR b_advance.

Faktory ovlivňující rychlost výpočtu

Virtuální topologie, komunikační schéma, distribuované aplikace

Prezentovaná síťová topologie

Fyzická topologie sítě

Výkonnost jednotlivých uzlů v síti

Výpočetní model distribuované aplikace

Každý proces může běžet podle vlastního programu

Řešení obecně

Umístit procesy na uzly sítě takovým způsobem, aby běžely co nejrychleji a zároveň bylo komunikační zpoždění co nejmenší

Může se jednat i o protichůdné požadavky

Zatížení a dostupnost uzlů se může měnit v čase

Jsou tři typy úloh

S konečným časem výpočtu – distribuovaná aplikace má jenom něco spočítat a pak skončí

S teoreticky nekonečným časem výpočtu – distribuovaná aplikace poskytuje službu

Neplatí, že uzel musí být zcela vytížen výpočtem po celou dobu

Processing While in Transit – výpočet se nad daty provádí během jejich přenosu Např. Active Network

Možnosti urychlení

Ve všech uzlech není stejný program

Každý proces má svoje data

Do všech uzlů se zavede stejný program

Do uzlů se zavedou specifická data procesů

Každý proces dokáže zjistit svoje ID a z něj určí sousedy a svůj díl dat

Jeden z procesů je řídící

Obvykle ten první vytvořený

Mívá ID 0, ale konkrétně to závisí na sw

Zpracovává dílčí mezivýsledky

V homogenním distribuovaném prostředí se zjistí celkový objem dat, počet spuštěných procesů a práce se přidělí najednou

Např. cluster z identických stanic a MPI

V heterogenním prostředí je lepší využít dynamické přidělování práce

Uzly nemusejí být stejně výkonné

Ale i v případě, kdy uzly nejsou využívány jednouživatelsky

Např. model farmer-workers, kdy farmáři udělíme čestný titul identický program -> bude k tomu všemu ještě makat jako worker

Urychlení u Farmer-Worker v distribuovaném prostředí, pokud farmer jen kompletuje dílo od workerů a pokud zanedbáme odeslání a příjem zprávy je přibližně S ~ N - 1, tj. přibližně lineární

Hodí se tehdy, když:

Výpočet je v porovnání s objemem zpráv náročný

Např. nemá smysl počítat pole integerů k součtu na jiný uzel, v dnešní době je operace mov zhruba stejně časově náročná jako add, muselo by se tedy vykonat spoustu operací navíc => zpomalení

V heterogenním prostředí se realizuje automatický load balancing viz dále, urychlení pak závisí na velikosti dat ke zpracování jedním procesem, je třeba najít ideální objem dat, který příliš nezpomaluje a zároveň poskytuje dobré urychlení

Příliš malé objemy dat nevedou k urychlení

Příliš velké objemy dat k urychlení už vedou, ale zase se zbytečně příliš čeká na procesy, které z různých důvodů pracují pomaleji než ostatní

Výpočetním výkonu uzlů

Měla by uzel zaměstnat na tak dlouho, aby bylo možné úkolovat uzly v době, kdy ostatní počítají

V první vlně přidělit náhodné velikosti dat od jednoho až dvou násobků objemu zprávy

Tím se na nějakou dobu zabrání konvergenci, kdy bude komunikační linka využívána všemi procesy

Eliminace komunikačního zpoždění překrytím výpočtem

Kromě neblokujících komunikačních operací

Data by se měla spočítat v nějakém přiměřeném čase, aby se na poslední proces nečekalo celou věčnost

Části dat by měly být stejně velké ne podle objemu dat, ale výpočetně

Problémem může být kapacita přenosových kanálů

Objem dat může být příliš velký a tak uzel může nějakou dobu čekat na data

Ideálně se v i-tém kroku

Počítají data

Data z i-1 kroku se posílají dalšímu uzlu v řadě

Přijímají se data, která se budou počítat v i+1 kroku

Překrytí doby komunikace dobou výpočtu => eliminace komunikačního zpoždění, pokud se data déle počítají, než přijímají

Pokud ne, zmenšit objem posílaných dat

N - počet úkolů

Pošleme-li objem vstupních dat k nekonečnu, pak je urychlení N

Předpokládá se prostředí pracovních stanic, které nemusejí být vždy plně vytíženy

Ostatní uzly se označují termínem slave

V okamžiku, kdy je master vytížen na maximum, zkusí se vyhledat nevytížený uzel

Červ

jednotlivé procesy se mohou replikovat na nevytížených uzlech

červ se skládá z několika segmentů – procesů

počet segmentů je buď pevně stanoven, nebo se při pokročilejší implementaci stanovuje dynamicky podle okolností

nápadně připomíná šíření virů

červ musí být věrohodný pro uživatele pracovních stanic

komponenty červa

inicializační kód ke spuštění master

inicializační kód ke spuštění slave

výpočetní program

ze života červa

nalezení nevytíženého uzlu

žádný uzel nezná globální stav sítě, a proto se každý segment musí postarat o nalezení volné stanice sám za sebe

lze hledat například pomocí broadcast hodila by se synchronizace, protože několik segmentů může soupeřit o stejný uzel

uvolnění uzlu

kontrola růstu

čím větší červ, tím vyšší rychlost výpočtu, ale vznikají další problémy

rychlost nemusí růst lineárně

snaží se o fér využívání všech uzlů

pokud některý uzel selže, proces se restartuje jinde

sám hledá použitelné uzly

možnost selhání

procesy lze relokovat za běhu distribuované aplikace

používá se ukládání obrazu procesu v paměti,

co s otevřenými soubory?

pokud selže výpočet, použije se poslední

pre-emptivnost procesů je implementována pomocí checkpointů

na rozdíl od load-sharingu se předpokládá, že celá síť je dostupná pro výpočet

existuje několik různých metod, které se liší použitelností, účinností, náročností na zdroje (paměť, procesor, …), přesností, spolehlivostí, …

výpočet přiřazení procesů na uzly je proveden ještě před spuštěním distribuované aplikace

výpočet může běžet libovolně dlouho, abychom dosáhli požadované přesnosti předpovědi – pokud ji metoda umožňuje dosáhnout

nelze reagovat na dynamické změny v prostředí

vyžadují předem spoustu informací o chování sítě a aplikace (např. kom. zpoždění, doby běhu procesů)

nereálné požadavky nelze splnit

vliv na přesnost a tedy i rychlost výpočtu

výpočet přiřazení procesů na uzly sítě se provádí za běhu distribuované aplikace

výpočet se odehrává v reálném čase a nemůže si proto dovolit konzumovat příliš mnoho zdrojů

umí se vyrovnat s dynamickými změnami

procesy musí umět pre-empci

potřebné informace lze zjistit až za běhu aplikace, nebo si jich část vyžádat předem

procesy lze přerušit během výpočtu a přemístit je na jiný uzel, aby bylo možné kompenzovat změny v síti

např. některý z procesů mohl skončit svoji činnost, nebo se odebral do dlouhodobého wait-stavu

pokud tuto vlastnost procesy nemají, na změny lze reagovat až při vytváření

mají jeden centrální prvek, arbitr, který rozhoduje o rozdělování zátěže na jednotlivé uzly

centrální prvek je slabé místo, co se stane, když selže?

centralizované správa vyžaduje komunikaci jednoho uzlu se všemi

možnost přetížení

arbitr má přehled o známé síti, a proto lze očekávat, že dokáže zátěž rozdělovat celkem efektivně bez rizik, která jsou jinak spojena s distribuovaným principem

rozhodování o rozdělování zátěže provádí několik až všechny procesy

mohou být distribuovány na několik uzlů

když jeden selže, nic se neděje, pokud ho výpočetní model aplikace nutně nepotřebuje k životu

procesy, které provádějí rozhodování mohou být buď specialisté, anebo to mají jako „vedlejšák“ ke své hlavní činnosti

síť prochází změnami během výpočtu – mění se stav uzlů

adaptivní metody berou do úvahy i několik předchozích stavů při rozhodování o přidělení zátěže

každý proces se může rozhodovat buď sám za sebe, nebo může na rozhodnutí spolupracovat s ostatními

přímo – procesy spolupracují nad konkrétním rozhodnutí

nepřímo – procesy dávají informace o svých rozhodnutích k dispozici ostatním a ty je použijí při svých rozhodnutích

v okamžiku, kdy je uzel zatížen přes určitou mez, začne vyhledávat jiné uzly, kam by přemístil část své zátěže

je to režie navíc, protože čas potřebný na vyhledávání nových uzlů mohl být použit na běh procesů

v okamžiku, kdy zátěž uzlu klesne pod určitou mez, začne vyhledávat jiné uzly, odkud by mohl převzít jejich zátěž

režie se projeví zvýšenou komunikací, uzel má dost volného výpočetního času, který může alokovat pro vyhledávání zátěže

load-balancing tradičně měří zátěž v počtu procesů, což není zrovna to nejlepší

metoda vyžaduje pokročilou síťovou architekturu jako jsou Aktivní sítě

Aktivní sítě

 stvořil Pentagon pro vyřešení nedostatků IP protokolu

 např. Any-Cast = metodologie pro adresování a routování, kdy jsou datagramy od jediného odesilatele routovány uzlu, který je topologicky nejblíže v dané skupině potenciálních příjemců (ačkoliv může být zasláno vícero uzlům, pokud mají stejnou adresu). Rozdíl od multicastu, který posílá všem ze skupiny najednou (a vždy), broadcastu, který zasílá jednoduše všem.

 Any-Cast je až v IPv6, aktivní sítě mají PAMcast – Programmable Any-Multicast – služba pro doručování zpráv, která generalizuje jak anycast tak multicast , která doručuje zprávy M z N příjemců, kde 1 <= M <= N

 Dvojice vysílající a příjemce

Vysílající odešle paket na konkrétní adresu, včetně portu, kde předpokládá příjemce

 Pokud tam není, paket se zahodí a vysílající zjistí chybu až timeoutem

Aktivní síť

Paket, nazývaný capsule, je asociován s kódem, který se spustí na každém uzlu, kterým capsule prochází

Vždy je přítomný příjemce

Kód může manipulovat s daty, vlastnostmi (cíl, TTL, atd.) a vykonávat další uživatelsky definované činnosti

Proces se označuje termínem aktivní aplikace 

Distribuovaná aktivní aplikace se skládá z několika aktivních aplikací, které mohou injektovat capsule a zároveň capsule může injektovat aktivní aplikace

Komunikační model sám-sobě

Je možné injektovat capsuli do sítě, aby nasbírala potřebná data a pak je předala procesu, který ji injektoval

 U IP by bylo nutné mít dopředu na každém uzlu, který by capsule mohla navštívit, spuštěný specializovaný proces

 Migrace procesů

Migrující proces změní svoji síťovou adresu, ale ještě ji nedal na vědomí ostatním procesům

Informaci o své nové síťové adrese zanechal na uzlu, odkud migroval

Capsule, která má doručit data, dorazí na uzel, odkud proces odmigroval, tam ho nenajde, ale použije svůj kód, aby si přečetla novou adresu a pouze změní svůj cíl

Ostatní procesy si mohou aktualizovat záznamy až později – lazy update, u IP je nutné vyřešit předem

V aktivní síti je zapotřebí standardizace pouze dvou věcí

 Kód vykonává Execution Environment (EE), na jednom uzlu může být několik EE

 Vše ostatní je pak už aplikačně specifické

Při přerozdělování zátěže (load redistribution) se procesy rozhodují samy za sebe, periodicky sledují své okolí (jako kolonie organismů)

Dosažení vyváženého stavu ne hned, ale postupně

Capsule zjistí síťové okolí uzlu z hlediska topologie, výkonnosti, zatížení, komunikačního zpoždění apod.

Využije se při hledání výhodnějšího uzlu pro odmigrování

Masová migrace - více procesů si vybere stejný uzel, ten se stane přetíženým

Oscilace - proces se může pohybovat po síti, aniž by něco počítal

řešení - zavedení kreditů, od určitého počtu může migrovat

Zbytečná migrace

Přiřazení procesů na jednotlivé uzly

Alokování uzlů 

 Např. pevně daná u paralelního počítače

1 proces dokáže plně využít celý uzel, takže nemá smysl jich na jednom uzlu spouštět několik 

Potenciálně nula až několik procesů na jeden uzel 

Přidělení celé sítě pro jeden výpočet 

Celkový čas výpočtu je pak dán

Dobou k zavedení programů, spuštění procesů a distribuce dat do uzlů

Vlastním výpočetem 

Získáním výsledků z uzlů

Přidělení části sítě jednomu výpočtu

Několik paralelně běžících výpočtů

Na jednom uzlu může běžet několik procesů 

Nelze se spoléhat na odvozená urychlení, protože ta nepočítala se zátěží, kterou vygeneruje neznámý kód 

Nehodí se pro synchronní/lockCstepped algoritmy – na společném uzlu by dva spolupracující procesy na sebe musely čekat dobu výpočtu jednoho kroku 

Identifikace procesů

Jedinečná ID procesů

Interakce send/receive (vše ostatní je na nich postaveno)

Podle přidělení na uzly:

1 uzel – 1 proces

Více procesů na uzlu

Více procesů na uzlu a procesy mohou migrovat (tabulka umístění procesů)
