2. Előadás - Végrehajtási módok, modellek
=========================================

Párhuzamos végrehajtási módok
-----------------------------

A programok párhuzamos végrehajtását különböző formában, szinteken valósíthatjuk meg. Egy lehetséges felosztás az alábbi.

**Hálózat szint**

* Több, egymással összekapcsolt számítógépet használunk.
* Elsődlegesen az elosztott rendszerek témaköre foglalkozik ennek hatékony megvalósításával.

**Hardver szint**

* A hardverek egy jelentős része önmagában is képes több műveletet párhuzamosan végrehajtani.
* CPU szintű párhuzamosítás:

	* Instrukció szintű párhuzamosítás (*Instruction Level Parallelism*): out-of-order execution, speculative execution, branch prediction
	* Hyper-Threading: fizikai processzoronként 2 logikai processzor

* Dedikált hardverként az egyik legszemléletesebb példa a videókártya. OpenCL, kernelek

https://en.wikipedia.org/wiki/Instruction-level_parallelism

https://en.wikipedia.org/wiki/Hyper-threading

**Virtuális gépek**

* Egy számítógépen belül több operációs rendszer indítható el párhuzamosan.
* Az erőforrások hatékonyan kihasználhatók különösebb szoftverfejlesztési feladat nélkül.

**Folyamatok**

* Az operációs rendszer ütemezi a folyamatok működését. Amennyiben meg tudja oldani, úgy a párhuzamosan végrehajtható részeket párhuzamosan futtatja.
* Több szekvenciális végrehajtású program időben párhuzamosan tud így futni.
* Operációs rendszer szintjén felügyelhető a működés.
* Egy számítási feladat szempontjából ezek kommunikációjával is megoldhatjuk a párhuzamosítást.
* *Inter Process Communication*, *MPI szabvány*

**Szálak**

* Egy programon belül mi magunk kijelölhetjük azokat a részeket, amelyek végrehajtása időben átfedésbe kerülhet.
* A végrehajtás során nem garantált, hogy valóban párhuzamosan történik majd. (Az operációs rendszer dönti el.)

**Könnyű súlyú szálak**

* A felhasználói térben (*user space*) kerülnek ütemezésre.
* Szokták még nevezni zöld szálaknak, coroutine-oknak.
* Mivel a szálak implementációja rendszerenként eltérő, ezért nincs pontos határvonal a szálak és a könnyűsúlyú szálak között.
* A programozási nyelvekben egyedi megoldások vannak ezek használatára..

Memóriamodellek
---------------

:math:`\rhd` Gondoljuk át a memória és a számítási elemek közötti 1:N, N:1, N:M kapcsolatokat!

Lokális memória
~~~~~~~~~~~~~~~

.. image:: images/local_memory.png

Moduláris memória
~~~~~~~~~~~~~~~~~

.. image:: images/modular_memory.png

Osztott memória
~~~~~~~~~~~~~~~

.. image:: images/shared_memory.png

* Cache
* Cache update probléma
* Kritikus szakasz
* Kölcsönös kizárás

Hálózatok
---------

A párhuzamos végrehajtási mód megvalósítási módjától függetlenül tudjuk vizsgálni a rendszerek topológiáját és a számítási egységek közötti kommunikációt.

* Csomópontként jelöljük a számítási egységeket, esetlegesen a tárakat (memóriát, háttértárat).
* Az élek a kommunikációs csatornákat jelölik.
* A kommunikáció irányával külön is kellhet foglalkozni. Ilyen esetben irányított gráfokat használunk.

Nézzünk egy nagyon egyszerű példát egy ilyen topológiára!

.. image:: images/network_topology.png

Elterjedt topológiák
~~~~~~~~~~~~~~~~~~~~

* Az alapvető probléma az, hogy egy üzenetet (csomagot) el kell juttatni az egyik állomástól a másikig.
* A cél az, hogy ezt minél gyorsabban, hatékonyabban meg tudjuk tenni.
* A hálózatra úgy tekinthetünk, hogy a csomag csak az élek mentén tud haladni.
* Külön problémát jelent, hogy párhuzamosan több csomag is továbbításra kerül.
* Elvileg tetszőleges gráf lehetne a topológia.
* A következők elvi és praktikus okok miatt alakultak így.

Busz
~~~~

.. image:: images/topologies/bus.png

* Az egyik legegyszerűbb összeköttetési forma.
* A csomópontokat célszerű indexelni, amelyeken így értelmezett egy rendezés.
* Tekinthető a fa egy speciális esetének.

:math:`\rhd` Vizsgáljuk meg a :math:`p = 4` esetre a csomópontok közötti távolságokat?

:math:`\rhd` Adjuk meg a (0-nál nagyobb) távolságok eloszlását!

:math:`\rhd` Mennyi a maximális és az átlagos távolság a csomópontok között?

Gyűrű
~~~~~

.. image:: images/topologies/ring.png

* Célszerű itt is tudni, hogy merre felé van a címzett (de nem kötelező).

:math:`\rhd` Vizsgáljuk meg a :math:`p = 4` esetre a csomópontok közötti távolságokat?

:math:`\rhd` Adjuk meg a (0-nál nagyobb) távolságok eloszlását!

:math:`\rhd` Mennyi a maximális és az átlagos távolság a csomópontok között?

Rács
~~~~

.. image:: images/topologies/grid.png

* Tetszőleges dimenziós lehet, és nem csak négyzetes.
* A címzést dimenziószám részből álló címekkel előnyös megoldani.

:math:`\rhd` Vizsgáljuk meg a távolságokat egy :math:`4 \times 4` méretű rácsra!

:math:`\rhd` Mennyi a maximális távolság egy :math:`n \times m` méretű rácsban?

Tórusz
~~~~~~

.. image:: images/topologies/torus.png

* Szintén elképzelhető magasabb dimenziós és nem négyzetes változat is.
* Az :math:`n` és az :math:`m` számú plusz él beiktatása jelentősen csökkenti a csomópontok közötti távolságokat.

:math:`\rhd` Hogyan változnak a távolságok a plusz összeköttetéssel egy :math:`4 \times 4` méretű rácshoz képest?

Hiperkocka
~~~~~~~~~~

.. image:: images/topologies/hypercube.png

:math:`\rhd` Hogyan tudjuk címezni a csomópontokat?

:math:`\rhd` Adjuk meg, hogy a dimenziószám függvényében (például :math:`n`-nel jelölve), hogyan változik a csomópontok és az élek száma!

:math:`\rhd` Egy :math:`n` dimenziós hiperkockában mennyi lesz a csomópontok közötti minimális és maximális távolság?

Fa
~~

.. image:: images/topologies/tree.png

* Egy összefüggő, körmentes gráf.
* Szoktak még említeni csillag topológiát. Ezt tekinthetjük a fa speciális esetének.

:math:`\rhd` Hogyan oldható meg a csomópontok címzése (és ezzel kapcsolatosan a routing)?

:math:`\rhd` A példában szereplő fa esetében hogyan alakulnak a csomópontok közötti távolságok? Adjuk meg ezek eloszlását!

Fat-tree
~~~~~~~~

.. image:: images/topologies/fattree.png

* Arra a feltételezésre épül, hogy a magasabb szintek között nagyobb sávszélességre van szükség. (Az "Oszd meg és uralkodj!" elven működő algoritmusoknál igen gyakran ez a helyzet.)

https://en.wikipedia.org/wiki/Fat_tree

https://en.wikipedia.org/wiki/Omega_network


Elvek és modellek
-----------------

Leképzés (map)
~~~~~~~~~~~~~~

* Az egyik legegyszerűbb és leghatékonyabban párhuzamosítható algoritmus.
* Tegyük fel, hogy adott egy :math:`x \in \mathbb{R}^n` vektor! Ki szeretnénk számítani egy :math:`y \in \mathbb{R}^n` vektort, melyre teljesül, hogy :math:`y_i = f(x_i), \forall i`, és :math:`f: \mathbb{R} \rightarrow \mathbb{R}` egy tetszőleges valós függvény.

Hogyan változik a munka, költség, gyorsítás és hatékonyság :math:`p` függvényében?


Osszd meg és uralkodj elv
~~~~~~~~~~~~~~~~~~~~~~~~~

* Felosztás :math:`\rightarrow` művelet :math:`\rightarrow` egyesítés
* Tipikusan rekurzív formában használatos

.. warning::

	A felosztás megfelelő szintjének meghatározása külön érdekes problémakör!
	(Jellemzően nem szerencsés az elemek szintjéig lemenni.)


Pipeline párhuzamosítás
~~~~~~~~~~~~~~~~~~~~~~~

* Tegyük fel, hogy vannak feldolgozandó elemeink, amelyeken adott sorrendben, mindig ugyanazokat a lépéseket kell végrehajtani.
* Feltételezzük, hogy a lépések végrehajtási ideje közel egyenlő.

.. image:: images/pipeline.png

:math:`\rhd` Mekkora gyorsítást tudunk így elérni?

:math:`\rhd` Mennyire lesz ez a módszer hatékony?


Termelő-fogyasztó probléma
~~~~~~~~~~~~~~~~~~~~~~~~~~

* Task pool
* Gyors válaszidő, terhelés kiegyenlítés érdekében használják például.
* Általában sort használnak hozzá.

.. image:: images/producer_consumer.png

:math:`\rhd` Milyen előnyei vannak a módszernek?

:math:`\rhd` Milyen eseteket nem tud jól kezelni?


Lost Update probléma
~~~~~~~~~~~~~~~~~~~~

**Példa**

Feltételezzük, hogy A és B egy változó értékét szeretné módosítani. A következő műveletek kerülnek végrehajtásra.

* A kiolvassa a változó értékét.
* B kiolvassa a változó értékét.
* A növeli a változó értékét.
* B növeli a változó értékét.

Zárolási mechanizmusok
~~~~~~~~~~~~~~~~~~~~~~

Garantálnunk kell tudni, hogy adott erőforrásokhoz egyidejűleg csak egy valaki férhet hozzá.

**Lakat (Lock)**

* Egy jelzőbittel (*flag*-gel) megoldható.
* Jelezni kell, hogy mikor foglaljuk le, és mikor szabadítjuk fel az erőforrást.

**Szemafor**

* Egy számláló, amely nyilvántartja a lefoglalások és felszabadítások számát.

Kérdések
--------

* Mennyi a 0-nál nagyobb távolságok eloszlása egy 7 csomópontból álló buszon?
* Mennyi az átlagos távolság egy 8 csomópontból álló gyűrűben?
* Egy :math:`6 \times 6 \times 6` rács esetében mennyi élünk lesz? Mennyi lesz a csomópontok közötti maximális távolság?
* Mennyi csomópont és él lesz egy 5 dimenziós hiperkockában? Mennyi ez esetben a maximális távolság?

Feladatok
---------

Szekvencia diagram
~~~~~~~~~~~~~~~~~~

* Keressen példákat szekvencia diagramokra az Interneten! Vizsgálja meg, hogy miben hasonlítanak és különböznek a jelölések!
* Tegyük fel, hogy egy tanár 2 hallgatóval írat dolgozatot. A tanár sorban kiosztja a feladatsort. A hallgatók megoldják a feladatokat, majd beadják ahogy elkészültek. A tanár kiértékeli (egyszerre csak egyet), visszaadja a hallgatóknak átnézésre, majd visszakéri a dolgozatokat. Rajzoljon fel egy lehetséges szekvencia diagramot a dolgozat írásához!

Feladatmegosztás optimalizálása
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Tegyük fel, hogy adott 2 gép, melyek hálózaton keresztül tudnak kommunikálni.

* A feladatokat egységnyieknek tekintjük.
* Összesen 3000 feladat van.
* Az első gép 1 feladatot 10 másodperc alatt old meg, a második pedig 5 másodperc alatt.
* A bemenet az első gépen áll rendelkezésre.
* A második gépre való küldés 2 másodpercet igényel feladatonként.
* A küldés és fogadás ideje alatt a gépek nem tudnak lényegi számítást végezni.
* Az eredményeknek az első gépre kell kerülniük.

Hogyan ossza meg a két gép a feladatokat, hogy a lehető legkevesebb ideig tartson összességében?

* Vezessünk be jelöléseket!
* Próbáljuk meg általánosan is megoldani a problémát!
* Ábrázoljuk grafikonon a párhuzamos végrehajtás idejét!

Mérések algoritmusok bonyolultságára vonatkozóan
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#. Készítsen el egy programot, amellyel egy tömbben lévő számértékeket lehet beolvasni.

   * Írjon egy függvényt az elemek összegének kiszámításához!
   * Valósítsa meg a minimum és a maximum értékének a meghatározását külön függvényekben!
   * Próbálja meg rekurzív függvényekkel is megoldani az előbbi számítási feladatokat!
   * Mérje le, gyűjtse össze táblázatba és ábrázolja grafikonon az iteratív és a rekurzív változatok számítási idejét az elemszám függvényében!
   * Adjon felső becslést a futási időre vonatkozóan! (:math:`T(n) = \mathcal{O}(?)`)

#. Generáljon egy tömböt úgy, hogy az elemek egész értékűek, és mindegyik különbözik!

   * Vizsgálja meg a tömb generálásának számítási idejét az elemszám függvényében!
   * 0.5 valószínűséggel duplikáljon benne néhány elemet!
   * Készítsen olyan függvényt, amely ellenőrzi, hogy a tömb minden eleme egyedi-e!
   * Vizsgálja meg a függvény bonyolultságát!

#. Generáljon egy tömböt, amelyben az elemek lebegőpontos értékek, és szigorúan monoton növekvő sorozatot alkotnak!

   * Készítsen függvényt a tulajdonság ellenörzéséhez!
   * Definiáljon egy függvényt, amely bináris kereséssel keres egy elemet a tömbben!
   * Készítse el az iteratív és a rekurzív változatát!
   * Véletlenszerűen kiválasztott és/vagy generált értékek keresése alapján mérje le a számítási idők eloszlását (adott elemszám mellett)!
   * Hasonlítsa össze az iteratív és a rekurzív változat futási idejét az elemszám függvényében!
   * Ábrázolja az egyes elemszámokhoz tartozó futási idők maximumát!

#. Generáljon egy szöveges fájlt az angol ábécé kis és nagy betűiből, számjegyekből, szóközökből és sortörésekből véletlenszerűen!

   * A generáláshoz paraméterként használja a generálandó karakterek számát!
   * Készítsen egy függvényt, amelyik meghatározza, hogy mennyi sort tartalmaz a szöveges fájl!
   * Próbáljon rekurzív megoldást is adni a problémára!
   * Hasonlítsa össze az iteratív és a rekurzív változat futási idejét!
   * Határozza meg az üres sorok számát!

Prefix számítás vizsgálata
~~~~~~~~~~~~~~~~~~~~~~~~~~

Tekintsük a prefix számítás esetében egységnyi idejűnek a :math:`\oplus` művelet elvégzését!

#. Készítsen egy programot, amely a CREW_PREFIX algoritmus végrehajtása során elvégzett hívásokat GraphViz segítségével egy hívási fában ábrázolja!

   * A program a kimenetet egy szöveges fájl formájában adja meg!
   * A megjelenítéshez használhat online gráf megjelenítőt, például: https://dreampuf.github.io/GraphvizOnline/
   * A csomópontokban tüntesse fel, hogy a hívás milyen intervallumra vonatkozott!
   * Próbálja megoldani, hogy a program tetszőleges :math:`n` méretű bemenetre működjön!

#. Az EREW_PREFIX algoritmus vizsgálatához készítsen egy programot, amellyel vizsgálható a párhuzamosan elvégzett számítások során a munka, költség, gyorsítás és a hatékonyság mértéke!

   * Egy szövegfájlba mentse le, hogy a számítások során a :math:`t` időpillanatban mennyi számítási egység végzett éppen hasznos munkát! (Itt a sorok mutassák az időt, az oszlopok pedig, hogy melyik számítási egységről van szó! Jelölje ``.`` karakter, hogy ha nem történt hasznos számítás, ``#`` pedig hogy ha igen!)
   * Határozza meg az említett :math:`W`, :math:`C`, :math:`S` és :math:`E` értékeket :math:`n = 100` bemenetméretig!
   * Gyűjtse össze az adatokat egy táblázatba!
   * Ábrázolja grafikonon a bemenet függvényében a gyorsítás és a hatékonyság mértékét!

#. Vizsgálja meg az OPTIMAL_PREFIX algoritmus működését!

   * Írjon fel egy saját példát :math:`n = 16` bemenet esetére! Rajzolja fel az ehhez tartozó Gantt diagramot!
   * Ábrázolja grafikonon, hogy :math:`n` méretű bemenet esetén mennyi processzorra van szükség a számításhoz!
   * Karakter tömb segítségével ábrázolja (például fájlba kimentve), hogy a :math:`t.` időegységben végzett-e hasznos számítást a :math:`p.` processzor!
   * Határozza meg az említett :math:`W`, :math:`C`, :math:`S` és :math:`E` értékeket :math:`n = 100` bemenetméretig!

Hálózati topológiák
~~~~~~~~~~~~~~~~~~~

#. Négyzetes rács topológia esetén végezze el a következő számításokat!

   * Számítsa ki :math:`n = 50`-ig, hogy egy :math:`n \times n` méretű rácsban mennyi csomópont és él van!
   * Határozza meg ezek arányát :math:`n` függvényében, és ábrázolja a kapott eredményt grafikonon!
   * Egy :math:`12 \times 12`-es méretű rács esetében határozza meg a pontok közötti távolságok eloszlását!
   * Ábrázolja a kapott eredményt hisztogramon!
   * Vizsgálja meg, hogy :math:`n = 24`-ig térbeli rács esetében hogyan változik a csomópontok és élek száma!
   * Hasonlítsa össze, hogy :math:`n` függvényében hogyan alakul az élek száma síkbeli és térbeli rácsok esetében!
   * Számítsa ki a csomópontok közötti távolságok eloszlását egy :math:`5 \times 5 \times 5` méretű térrácsban!

#. Végezze el az előbbi számításokat tórusz topológia esetében!

#. Végezzen számításokat hiperkocka topológia esetében!

   * Számítsa ki, hogy 30 dimenzióig hogyan változik a csomópontok és az élek száma!
   * Határozza meg 8 dimenzióban a csomópontok közötti távolságok eloszlását!
   * Ábrázolja a kapott eredményt hisztogramon!
   * Számítsa ki 20 dimenzióig az átlagos távolságokat!
   * Hasonlítsa össze ezeket a csomópontok száma alapján a síkbeli és térbeli rács topológiákkal!
