8. Modely paralelních počítačů a komunikačních sítí a principy tvorby paralelních algoritmů

• 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

• 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

• 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

• 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

• 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)

• 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 Wikipedia
• komunikacia prebieha zdielanim udalosti

• 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

• 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

• 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

• 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

• 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

• 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

• 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 wiki

• IV100 Paralelní a distribuované výpočty

http://kedrigern.dcs.fmph.uniba.sk/uda/