===== 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 \alpha\beta kalkulus (math tag nefunguje v nadpisoch) * pouzite v CM LISP * distribuovana datova struktura: xektor -- zoznam dvojic (index, hodnota) * \alpha 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) * \beta 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/