===== Zadání =====
8. Modely paralelních počítačů a komunikačních sítí a principy tvorby paralelních algoritmů
===== Vypracování =====
==== Základní pojmy ====
* distribuovany system -- prepojenie autonomnych procesov
* rozdiel proces/procesor sa zvacsa zanedbava a uvazuje sa 1:1 (inak to ani nema moc zmysel z teoretickeho hladiska urcovania zlozitosti distribuovanych algoritmov)
* zakladne atributy modelov zalezia na viacerych kriteriach
* podla medziprocesorovej komunikacie
* zdielana pamat (shared memory)
* posielanie sprav 1:1 (point-to-point)
* broadcast sprav 1:n
* vzdialene volanie procedur
* podla casovania
* synchronne systemy -- v kazdom kroku su vsetky spravy z predchadzajucich krokov uz dorucene
* asynchronne systemy -- dorucenie spravy moze trvat neobmedzene dlho
* ciastocne (casovo) synchronne systemy -- timestamps + timeouts
* podla chybovosti
* chyby cpu (byzantinske/stop/crash)
* chyby kanalov (strata/duplikacia/porusenie integrity)
* podla hierarchie
* distribuovane -- vsetky procesy su si rovne
* centralizovane -- existuju spravcovske uzly
==== Modely ====
=== PRAM (Parallel Random Access Machine) ===
* abstrahuje od komunikacie a synchronizacie vdaka zdielanej pamati, sustreduje sa na samotny vypocet
* obsahuje identifikatory jednotlivych procesov
* obsahuje neobmedzeny pocet procesorov, zlozitost sa pocita dvomi sposobmi: O(time), O(time * nr_proc)
* problem so sucasnym citanim/zapisom do rovnakeho bloku pamati, riesi sa cez
* exkluzivny pristup (iba jeden proces moze citat/zapisovat pamatovu bunku)
* 1x write, neobmedzene krat read
* neobmedzene krat write aj read, multiple write sa dalej riesi cez
* spolocny -- povoleny iba ak vsetci zapisuju to iste
* vyberovy -- iba jeden pokus o zapis je uspesny
* prioritny -- podla priority, proces s top prioritov ma zapis
* a kadeco ine...
* vlastnosti:
* neobmedzeny pocet procesorov
* pamat je plne dostupna z lubovolneho procesu
* neobmedzena pamat
=== LogP model ===
* snaha o praktickejsiu verziu PRAM pri zachovani lahkej analyzy algoritmov
* asynchronny model, komunikacia cez posielanie sprav
* 4 parametre:
* L - horne ohranicenie zdrzania komunikacneho media (latency)
* o - cena poslania/prijatia spravy (overhead)
* g - minimalny medzera medzi 2 spravami (gap)
* P - pocet procesorov (processor), vsetky su povazovane za rovnako rychle
* priklad: poslanie spravy dlzky m stoji L*m + 2*o
=== BSP (Bulk Synchronous Parallel) model ===
* procesory spojene sietou, kazdy procesor ma vlastnu rychlu pamat
* vypocet sa vykonava cez tzv. supersteps
* jeden superstep sa sklada z:
* lokalny vypocet v kazdom procesore
* komunikacia cez spravy
* barierova synchronizacia
* cena superstepu je rovna cene najzlozitejsieho vypoctu + cene najzlozitejsej komunikacie * koeficient priepustnosti siete + cas na zaverecnu barierovu synchronizaciu
=== ab kalkulus ===
* spravne kalkulus (math tag nefunguje v nadpisoch)
* pouzite v CM LISP
* distribuovana datova struktura: xektor -- zoznam dvojic (index, hodnota)
* zavedie hodnotu do vsetkych procesorov (pouzitelne hlavne na operatory), kazdy index xectoru pocita osobitny proces(or) (Pre binarne plus su na vstupe 2 xectory pre binarne operacie)
* paralelny (logaritmicky) reduce zoznamu nejakym operatorom (foldr/foldl v haskelli)
=== CSP (Communicating Sequential Processes) model ===
* spojitost s "process algebra"
* udalosti a procesy
* viacero operatorov podla stupna ziadaneho paralelizmu
* nedeterministicka volba procesu
* externa volba procesu
* prekladanie (instrukcii) procesov
* klasicka sekvencna kompozicia procesov
* a dalsie [[http://en.wikipedia.org/wiki/Communicating_sequential_processes#Formal_definition|Wikipedia]]
* komunikacia prebieha zdielanim udalosti
=== MapReduce (Google) ===
* obsahuje Map pre filtrovanie a triedenie a Reduce, ktora zhrnie informaciu
* 2 typy uzlov: worker, master
* worker spocita to, co mu master povedal, ze ma spocitat a posle vysledok masterovi
* master prerozdeluje pracu pre nizsie urovne (pri Map, moze pracu pridelit aj masterovi, ktory dalej rozdeluje pre workereov) a ked mu pridu vysledku z nizsej urovni, tak ich podla Reduce kriteria zhrnia a reportne na vyssiu uroven
* velmi jednoduche, vhodne pre masivnu paralelizaciu
=== Sietovy model ===
* asi najcastejsie pouzivany model pre navrh distribuovanych algoritmov (aspon na FI)
* nezavisle uzly (model sa da uvazovat ako graf, kde hrany urcuju komunikacne kanaly)
* asynchronna, ale spolahliva komunikacia (bez straty -- sprava pride, ale nie je zarucene kedy)
* jedine, co je zarucene je, ze sprava nepride pred tym nez je poslana :)
* dolezita je aj topologia (komunikacny graf) siete, pre ktoru sa navrhuje algoritmus
* procesy maju svoj wakeup a terminaciu
* formalne cez prechodove systemy
* zvacsa je najdolezitejsie urcit komunikacnu zlozitost (pocet poslanych sprav) v zavislosti od poctu procesorov
* tj. pocet sprav (pripadne ak su spravy moc odlisne velkostou, tak pocet bitov)
* sietovy model sa dalej deli podla viacerych kriterii
* ma nahodny generator?
* dokaze merat cas?
* ma ocislovane hrany (vie s kym komunikuje?)?
* existuje veduci uzol (sef)?
* ma kazdy uzol unikatny identifikator?
* vo vseobecnosti ma uzol pristup len ku komunikacnym kanalom (nemusi vediet, kto je na druhej strane kanalu)
* kazdy uzol dostane nahranu uplne rovnaku verziu algoritmu (s moznou vynimkou identifikatora, ale ten byt nemusi)
* kazdy uzol vie, ktorym komunikacnym kanalom mu sprava prisla a moze dany kanal identifikovat s odosielatelom spravy
* komunikacne kanaly (hrany) nemusia byt obojsmerne
==== Principy tvorby algoritmov ===
* efektivita algoritmov zavisi od topologie siete
* caste topologie
* uplny graf (kazdy s kazdym)
* kruh (kazdy ma laveho a praveho suseda a su usporiadany do kruhu)
* jednosmerny kruh (kazdy ma len jedneho suseda, po N preposlaniach sa sprava dostane k jej povodcovi)
* 2D/3D mriezka (ako vravi nazov)
* niekedy sa este zvyknu prepajat najlavejsie a najpravejsie uzly mriezok (podobne dolne a vrchne), cim vznika dalsia celkom casto pouzivana topologia
* pre tvorbu paralelnych algoritmov je najprv potrebne zvladnut niekolko principialnych uloh -- komunikaciu medzi nodmi, prehladavanie nodov (broadcast) a volbu sefa
=== Paralelizacia vstupu ===
* pravdepodobne nestoji ani za zmienku, ale asi sa na to mozu v suvislosti s otazkou spytat
* rozdelenie vstupu na P casti, kde P je pocet procesov
* kazdy proces vypocita svoju cast
* **nejde o skutocnu paralelizaciu algoritmu**
**vsetky dalsie problemy sa budu tykat sietoveho modelu**, afaik sa nic moc ine na FI neberie
=== Komunikacia ===
* problem: ako dosiahnut spolahlivu komunikaciu vcetne spravneho poradia sprav
* alternating bit riesenie
* A posiela B opakovane spravu s nejakym ID a caka na ack s danym ID
* B pocuva spravy a po obdrzani spravi zacne posielat opakovane ack A s ID spravy, ktoru obdrzal
* A po obdrzani ack zvysi ID a proces sa moze opakovat
* problem: vysoka latencia
* sliding window riesenie
* podobne ako pri alternating bit, ale posielaju sa spravy, ktore su v nejakom okne
* ked A dostane ack, vyhadi spravu s danym ID z okna a prida do okna novu spravu
* mozne dalsie zrobustnenie: v okne su len spravy, ktore su v blizkom okoli
=== Prehladavanie siete (broadcast) ===
* existuje iniciator (ten, co chce prehladat siet/broadcastnut spravu)
* naivne (shout and echo): pri prvom obdrzani spravy ju posle vsetkym susedom a pocka kym mu vsetci vratia ack, pri druhom obdrzani len vracia ack (problem: zlozitost)
* trocha lepsie:
* odskrtavanim pouzitych susedov
* iniciator si vyberie jedneho suseda (nahodne), odskrtne si ho a posle mu spravu
* kazdy uzol reaguje na prijatie spravy nasledovne:
* ak uz ma vsetkych susedov odskrtnutych, spravu ignoruje
* ak uz nema odskrtnuteho len odosielatela spravy, tak mu spravu vrati
* ak uz mu raz niekto tu spravu posielal, vrati spravu poslednemu odosielatelovi
* inak posle spravu nahodne dalej
* zlozitost je 2*m
* existuje mnozstvo dalsich algoritmov
=== Volba sefa ===
* problem ako sa dohodnut na lidrovi skupiny uzlov
* vsetky uzly sa zobudia s rovnakym cielom -- stat sa lidrom
* uzly by sa mali nejakym sposobom lisit -- id, nahodnostny generator s roznymi "seed" a pod.
* uplny graf (jednoduchy algoritmus), zname unikatne id, naivne riesenie
* uzol posle svoje id vsetkym susedom (tj. vsetkym ostatnym uzlom) a caka, ci dostane od vsetkych suhlas
* pri prijati id spravy uzol porovna svoje id s prijatym, ak je nizsie, tak posle nazad suhlas
* ked niektory uzol dostane suhlas od vsetkych ostatnych uzlov, stava sa sefom a broadcastne to (v uplnom grafu je to jednoduche poslanie spravy vsetkym susedom)
* uplny graf, zname id, technika podmanovania uzlov
* neposielaju sa hned id spravy vsetkym, ale za kazdou spravou sa caka na suhlas (kazdy uzol si pribera dalsie uzly, nad ktorymi "vladne")
* problem: uzol, ktory uz niekomu patri dostane poziadavku na podmanenie od ineho uzlu
* riesenie: zavola na pomoc uzol, ktoremu patri a ten rozhodne (podla ID), ci vyhraju alebo sa vzdaju
* koniec: nejaky uzol vlastni vsetky ostatne uzly (broadcast nie je potrebny, uzly vedia, ze su vlastnene)
* len n log n (optimum), namiesto n*n sprav
* jednosmerne kruhy, zname ID, Chang Roberts
* uzol pri zobudeni posle dalej svoje ID
* pri prijati nejakej ID spravy: porovna prijate ID s vlastnym a
* ak je jeho ID mensie, preposle spravu
* ak je jeho ID vacsie, nerobi nic (uz poslal svoje ID)
* ak sa prijate ID rovna jeho ID, tak vie, ze je sef (sprava preputovala bez zmeny cely kruh) a broadcastne to (na kruhu je to len preposielanie spravy az kym nenarazi znova na jej povodcu)
* ocakavany pocet sprav je v O(n log n), ale najhorsi pripad je v O(n*n)
* obojsmerne kruhy, zname ID, Hirschberg-Sinclair
* zbezna idea: postupne podmanovanie uzlov na obe strany
* zlozitost: O(n log n)
* lubovolny obojsmerny graf, zname ID, GHS
* buduje sa kostra grafu
* uzly sa postupne spajaju po najlacnejsej hrane (cen
* mensi sa pripoji k vacsiemu
* rovnaki sa spoja
* vacsi caka (mensi sa k nemu pripoji)
* detailnejsie na [[http://en.wikipedia.org/wiki/Distributed_minimum_spanning_tree#GHS_algorithm|wiki]]
===== Předměty =====
* [[https://is.muni.cz/auth/predmet/fi/IV100|IV100 Paralelní a distribuované výpočty]]
===== Zdroje =====
http://kedrigern.dcs.fmph.uniba.sk/uda/