VIK Wiki - Felhasználó közreműködései [hu]

Párhuzamos és Grid rendszerek - Záróvizsga tételkidolgozás

2013-06-02T07:06:56Z

Fape:

{{TODO}}

== Párhuzamos rendszerek alapfogalmai ==

=== Flynn-féle architektúra modell ===

{| class="wikitable" border="1"
|-
| colspan="2" rowspan="2" |
| colspan="2" align="center" | Adat (Data)
|-
| align="center" | Egy (Single)
| align="center" | Több (Multiple)
|-
|rowspan="2" align="center" | Utasítás<br />(Instructions)
| align="center" | Egy (Single)
| align="center" | Serial machine (SISD)
| align="center" | Vektor processzor (SIMD)
|-
| align="center" | Több (Multiple)
| align="center" | Pipelines (MISD)
| align="center" | Multiprocesszor (MIMD)
|}

=== Idealizált párhuzamos gép modellje ===
* Több processzor egyazon problémán dolgozik.
* Minden processzornak saját memóriája és címtartománya van.
* Üzenetekkel koordinálnak és adatokat is tudnak átadni.
* A lokális memória elérése gyorsabb.
* Az átviteli sebesség független a csatorna forgalmától.

=== Teljesítményméréshez kapcsolódó fogalmak ===
* Sebességnövekedés (Speed Up): <math>S_n=\frac{T_s}{T_n}</math>
** <math>S_n</math>: N processzorral elért sebességnövekedés,
** <math>T_s</math>: futási idő soros végrehajtás esetén,
** <math>T_n</math>: futási idő N processzor esetén
* Hatékonyság (Efficiency): <math>E_n = \frac{S_n}{N}</math>
** <math>E_n</math>: N processzorral elért hatékonyság
** <math>S_n</math>: N processzorral elért sebességnövekedés
** <math>N</math>: processzorok száma
* Redundancia (Redundancy): <math>r = \frac{C_p}{C_s}</math>
** <math>r</math>: párhuzamos program redundanciája
** <math>C_p</math>: párhuzamos program műveleteinek száma
** <math>C_s</math>: soros program műveleteinek száma
* Amdahl-féle felső határ, N processzorral elértető sebességnövekedés felső határa: <math>S_a = \frac{1}{s+\frac{1-s}{N}}</math>
** <math>s</math>: a feladat nem párhuzamosítható része
** <math>N</math>: processzorok száma
** Az <math>\frac{1-s}{N}</math> tagot elhagyva: <math>Sa < \frac{1}{s}</math>

== Jellegzetes architektúrák ==

=== Architektúrák jellemzői ===
* Processzorok eloszlása
* Homogén vagy heterogén
* A kapcsolat késleltetése és sávszélessége
* Topológia: Háló, gyűrű, fa, hiperkocka, teljes összeköttetés

=== Masszívan párhuzamos, szimmetrikus multiprocesszoros és vektorprocesszoros rendszerek jellemzői ===
???

=== Klaszter koncepció ===
* Gyors hálózattal összekapcsolt gépek
* Gyakran közös fájlrendszer
* CPU vagy tárolási kapacitás növelése
* Paraméter study, vagy párhuzamos alkalmazások

=== Metaszámítógépek ===
???

=== Grid rendszerek ===
???

== Párhuzamosítás, programozási modellek ==

=== Elosztott memória, üzenetküldés, közös memória ===
* Elosztott memória használatának előnyei
** Skálázható
** Költségkímélő
** A redundancia növelésével növekedhet a megbízhatóság
** Speciális feldolgozó eszközökkel is együttműködik
* Elosztott memória használatának hátrányai
** Kommunikáció igényes
** Nem minden algoritmus párhuzamosítható így
** A meglevő soros programokat és a közös memóriát használó alkalmazásokat át kell dolgozni
** Jó speed up értékeket nehéz elérni
** Nehéz nyomkövethetőség

=== Párhuzamos programozási nyelvek és jellemzői ===
* Linda – közös memória modell, Tuple Space.
** Egyszerű modell, de implementációs nehézségek vannak, főleg az üzenetküldéses architektúrákon.
* Express – elosztott memória modell 160 C-ből és fortranból hívható rutin.
* PVM – elosztott memória modell 70 C-ből és fortranból hívható rutin.
** "Szegények" szuperkomputere: a szabad CPU kapacitások összegyűjthetők a munkaállomásokról és a PC-ről
* MPI- szabványos, a gyártók által elfogadott, speciális hw. környezetet is támogató fejl. környezet.
** nem igényli a virtuális gép előzetes felépítését,mert a teljes kommunikációs séma az alkalmazáshoz szerkesztődik.
* OpenMp
** Szálakkal történő párhuzamosítás macerás.
** Nyelvi kiterjesztés
** A programozó a funkcionalitásra koncentrálhat.
** A párhuzamosítás csak lehetőség.
** Shared memóriás párhuzamosítás
** Ipari szabvány
* Cn nyelv
** Standard Ansi C + 2 új kulcsszó (poly és mono)
* Cuda
** GPU
*** A programozható vertex és fragment shaderek beépítésével általános célú eszközzé vált.
*** Vektorprocesszor (SIMD), de pipeline egységek is vannak benne (MISD).
** Ún. thread modell (SIMT)
** A szálak ütemezésével nem kell a programozónak foglalkozni.
** Elrejti a konkrét architektúrát
** Támogatja a heterogén feldolgozás (CPU+GPU)

=== Párhuzamosítási stratégiák ===
* Kényszerű
** A program soros változatát futtatjuk párhuzamosan különböző adatokkal.
** Csak akkor kielégítő módszer, ha a soros változat elviselhető futási idejű.
* Ciklusok párhuzamosítása
** Akkor alkalmazható, ha az egyes iterációk függetlenek egymástól
* Felosztó párhuzamosítás (master / slave)
** Egy felügyelő taszk fut az egyik node-on
** Akkor alkalmazható, ha a felügyelő program feladatai egyszerűbbek mint a többi taszk feladatai.
** Ha a taszkok függetlenek egymástól, akkor jól skálázható a taszkok számának változtatásával.
* Egymást követő
** Minden node a következő node-nak adja tovább a részben feldolgozott adatot.
** Akkor használható, ha a soros része a feldolgozásnak lényegesen rövidebb, mint a párhuzamos rész.
** Rendszerint minden node azonos kódot futtat.
** Különösen alkalmas a gyűrű topológiához.
* Régiók párhuzamosítása
** Az adatfüggőség régiókba lokalizálható.
** Akkor használható, soros végrehajtási idő nagyobb mint a párhuzamos.
** Rendszerint nagy kommunikációigényű.
** Legbonyolultabb.

=== Párhuzamos algoritmusok tervezése ===
* Nem egyszerű.
* Kreativitást igényel.
* Számos iterációt tartalmaz.
* Nincs egyszerű recept.
* Vannak betartható, ajánlott lépések, módszerek.

=== Taszk/csatorna modell jellemzői ===
* minden taszk szekvenciális programot futtat
* minden taszknak van saját memóriája
* taszkok csatornákkal kapcsolódnak,
* a csatornák üzenetsorokat valósítanak meg
* taszkok konkurensek, van lokális memóriájuk
* küldés aszinkron, fogadás szinkron
* csatornához in/out portokkal csatlakoznak
* taszkok tetszőlegesen rendelhetők össze a processzorokkal

* A modell közvetlenül hozzárendelhető az idealizált számítógéphez.
* A taszk egy soros kódot reprezentál.
* A csatorna processzorok közötti kommunikációt valósít meg.
* A taszk működése független a taszkprocesszor összerendeléstől, taszkok számától.
* Moduláris felépítést tesz lehetővé.

* Az üzenet egy adott taszknak szól, ezért kevésbé absztrakt, mint a csatorna.
* Az általános üzenetküldéses modell szerint nem lehet dinamikusan új taszkot létrehozni. (Több megvalósításban lehet.)
* Egy processzor csak egy taszkot futtathat. (Több megvalósításban ez sem korlát.)

=== PCAM módszertan ===
==== Particionálás ====
Sok kis részfeladatokra osztás. NEM veszi figyelembe a fizikai gép HW/SW adottságait. Párhuzamosítható részek felderítése.
* Domén dekompozíció:
** Adat vagy paramétertér felosztása. Az adat lehet input, output, vagy közbülső adat.
* Funkcionális dekompozíció:
** Az algoritmus felosztása olyan részekre, melyek párhuzamosíthatók.
** Alapvetően a feladat funkcióiból adódik.
** Az adatokra is figyelni kell.
** Tipikus példa, amikor az adatok particionálása nem járható: keresés fában. – funkcionálisan viszont bontható

===== Hogy sikerült a particionálás? =====
* Jól, ha particionálással kapott taszkok száma nagyságrendileg több mint a proc. száma.
* Jól, ha redundancia mentes.
* Jól ha a taszkok mérete hasonló.
* Jól, ha a probléma méretével a taszkok száma is nő.

==== Kommunikáció megtervezése ====
Részfeladatok közötti adatcsere és szinkronizációs séma kialakítása.
* Kis környezetű (local) és globális
** a taszkok csak kis környezetükben (szomszéd), vagy sok másik taszkkal is kommunikálnak.
* Strukturált és nem strukturált
** rács, gyűrű, ... vagy más
* Statikus és dinamikus
** végrehajtás közben változik
* Szinkron vagy aszinkron
** koordináció hiánya

===== Hogy sikerült a kommunikáció? =====
* Jól, ha közel azonos számú kommunikációt végez minden taszk.
* Jól, ha a taszkok csak lokális környezetükkel kommunikálnak.
* Jól, ha kommunikáció konkurensen párhuzamosan zajlik.
* Különböző taszkok konkurensen kommunikálnak.

==== Agglomeráció ====
Részfeladatok nagyobb egységekbe gyűjtése a hatékonyságnövelés érdekében. A tényleges párhuzamos gép kommunikációs adottságait is figyelembe véve a részfeladatokat nagyobb egységekbe gyűjtjük.
Agglomeráció szükségessége:
* A kommunikáció "költséges"
* A kommunikáció szükségtelen szinkronizációt okoz
* Térfogat-felület effektus (számítás/kommunikáció arány)
* Flexibilitás megtartása

===== Hogy sikerült az agglomeráció? =====
* Jól, ha jelentősen növekedett a lokális kommunikáció
* Jól, ha a skálázhatóság nem romlott.
* Jól, ha az összevont taszkok mérete közel azonos.
* Jól, ha a probléma méretével növekszik a taszkok száma.
* Jól, ha a már nem vonhatók össze feladatok anélkül, hogy a skálázhatóság vagy a terheléskiegyenlíthetőség ne romlana.

==== Leképezés ====
Tényleges HW/SW környezet figyelembe vétele, leképezés a fizikai gépre. A részfeladatok processzorhoz/ feldolgozó elemhez rendelése. Jelentősen befolyásolhatja a terheléskiegyenlítést, ütemezési algoritmust.

===== Hogy sikerült a leképezés? =====
* Jól, ha nem keletkezett szűk keresztmetszet a programban.
* Jól, ha több lehetséges leképezést is megvizsgáltunk.
* Ha figyelemmel voltunk a terheléskiegyenlítésre.

== Grid és elosztott rendszerek ==

=== Hosszú távú ütemezők ===

==== Condor ====
* Elosztott, heterogén rendszerben működik.
* Alapvetően a szabad CPU ciklusok kihasználására tervezték.
* Képes egy működő feladatot áthelyezni az egyik gépről a másikra (migráció).
* Az ún. ClassAds mechanizmussal képes a rendszerben levő változó erőforrásokat az
* igényeknek megfelelően elosztani
* Opportunista környezet.

===== ClassAds =====
* A rendszerben levő erőforrások különböző jellemzőkkel (teljesítmény, architektúra, op. rendszer, stb.) rendelkeznek.
* A job összeállításánál ezekre a jellemzőkre igényeket lehet előírni amit a Condor előírni, rendszer megpróbál kielégíteni. (Párosítja az igényt az erőforrással)
* A job összeállításánál lehetőség van preferenciák megadására, ami alapján a Condor rangsorolni fog és kiválasztja az igénynek leginkább megfelelő gépet.
* Így nincs szükség a batch rendszerekben megszokott sorokra. (Úgyis a rosszat választanánk)

===== Futtatás lépései =====
* A job összeállítása
* Job bejelentése a Condor-nak
* Job-ot a Condor futtatja az általa kiválasztott gép(eken), szükség átmozgatja egy másik gépre.
* Job befejeződik, a Condor e-mail-t küld a felhasználónak.

==== Sun Grid Engne (SUN) ====
* A Condor-hoz hasonló ütemező.
* Queue-kat definiál.
* Hangsúlyos a terhelés kiegyensúlyozása.
* Backup master ütemező
* Check-point.
* Migrálási lehetőség.
* Négy szerepkör:
** master, submit, exec, admin,

==== Egyéb ====
* Torque (Cluster Resources)
* LoadLeveler (IBM)
* Torque (Cluster Resources)

=== Elosztott fájlrendszerek ===

==== AFS (Andrew File System) ====
* Elosztott fájlrendszer, ami fájlok megosztására alkalmas lokális és távolsági hálózaton.
* Transzparens fájlhozzáférést biztosít.
* Az NFS-hez hasonló, annak alternatívájaként jött létre.
* Ma az OpenAFS számos UNIX, LINUX, WINX platformon elérhető.
* A fő cél az volt, hogy egyetemi korlátozott sávszélességű hálózaton hatékony fájlelérést tegyenek lehetővé.

===== AFS cella =====
* Egy AFS cella alá azok a szerverek tartoznak, melyek adminisztrációja közös, és az AFS felé egyetlen közös fájlrendszert alkotnak.
* Tipikusan az egy domain név alá tartozó gépek egy AFS cellát alkotnak.
* Általában a domain név valamilyen változata a cellanév.
* A munkaállomások a felhasználókról

===== Kötetek =====
* A diszkterületet az AFS további részekre, osztja ezek az AFS kötetek.
* Az AFS kötet egy tárolóegység ami a fájlok és katalógusok adatait tárolja.
* Az AFS kötettek fájlok formájában jelennek meg a befogadó operációs rendszerben, így azok könnyen átmozgathatók, akár másik gépre is.
===== Tokenek =====
* Az AFS nem használja a UNIX felhasználói azonosítóját (UID). Ha ezt tenné, akkor minden UNIX gépen azonos UID kiosztásnak kellene lennie, mint az NFS-nél.
* Az azonosításhoz AFS tokent alkalmaznak, ami egy egyedi azonosítást tesz lehetővé.
* Egy token adott ideig (24 óra) érvényes.

===== Cache menedzser =====
* A korlátozott sávszélesség miatt a működés központi eleme a cache, ahova az éppen használt fájlok letöltődnek.
* A cache menedzser feladata a cache-ben tárolt információk frissítése, karbantartása.
* Amennyiben a cache-ben tárolt fájlrészlet változik, úgy azt vissza kel tölteni a szervere.
* Ha a szerveren változik meg a fájl, akkor arról CallBack technikával értesít minden cache-t.

===== Védelem =====
* A védelmi mechanizmus némileg eltér az alap UNIX védelmi rendszertől.
* A UNIX 3x3-as védelmétől pontosabban szabályozható ACL (Access Control List) segítségével.

===== Processzek =====
* Venus: AFS kliens által futtatott processz.
* Vice: AFS szerver által futtatott processz.

===== Fájl műveletek =====
* A kliens munkaállomás a szerverrel csak az open/close műveletek kiszolgálásakor kommunikál.
* A fájl megnyitásakor a Venus a teljes fájlt a cachebe tölti, és a fájl lezárásakor írja azt vissza.
* Az adatok olvasását/írását a lokális másolaton a kernel végzi.
* A Venus a katalógusokat és a szimbólikus linkeket is a lokális gyorsítótárban tárolja.
* A fenti gyorsítótárazási mechanizmus alól a katalógusok módosítása a kivétel, aminek a végrehajtásáért a közvetlenül szerver a felelős.

===== Megvalósítás =====
* A kliens oldali programok a szokásos módon, rendszerhívással kezelik az állományokat.
* A távoli fájlok megnyitásakor Venus processzhez jut a kérés, amit az lebont az útnév alapján.
* Az alacsonyszintű I/O kezelését a befogadó operációs rendszer végzi. A gyorsítótár a lokális gép diszkjén jön létre.

===== AFS előnyei =====
* Gyorsítótárazásból fakadó előnyök:
** Lényegesen csökkenti a hálózati forgalmat.
** Alacsonyabb sávszélességnél is jól használható.
* Helyfüggetlenség:
** Az AFS a földrajzi helyet a szerver oldalon rendeli fájlnévhez. Így a névtér helyfüggetlen.
* Skálázhatóság:
** A rendszer tervezési fázisában igen nagyra (~10000 kliens) tervezték. A kliens/szerver arányt pedig 200:1-re. Mindkét értéket túlteljesíti.
* Single systems image (SSI):
** Egy fájlszerver kialakítása lényegesen egyszerűbb, mint NFS-sel.
* Fokozott biztonság:
** Kerberos használata, ACL használata
* Fájlok egyszerű megosztása
* Egyszerű rendszer menedzsment
* Robosztus
* Replika lehetőség.

===== AFS hátrányai =====
* Minden munkaállomásra installálni kell.
* Háttérszerver komplexitása.
* Tokenek érvényességének lejártából fakadó gondok.

==== Lustre ====
* Objektum-orientált elosztott fájlrendszer.
* Jól skálázható.
* Nagyméretű klaszterekhez, és nagy fájlokhoz tervezték

===== Lustre architektúra =====
* Három fő funkcionális egysége van:
** Metadata szerver (MDS), ami a fájl neveket, katalógusokat, védelmi kódokat és egyéb metaadatot tárol.
** Object storage szerverek (OSS), melyek az adatokat tárolják.
** Kliens ami az adatokat felhasználja, létrehozza.
* Az adatok logikai kötetmenedzsmenttel ellátott RAID tárolókban tárolódnak, amit az OSS és az MDS dedikált módon használ.
* Jelenleg egy módosított ext3 fájlrendszer a logikai tároló, de a SUN dolgozik a ZFS beépítésén.
* Amikor egy kliens fájlt akar elérni, először az MDS-ben meg kell keresnie.
* A fájl egyes darabjai több OSS-en tárolódhatnak, ami a kliens és az OSS között szűk keresztmetszet kialakulását gátolja.
* A kliensek nem módosítják közvetlenül az OSS-ben tárolt adatokat, hanem ezt a OSSre bízzák, szemben a GFS megoldásával.
* Ez a módszer növeli a megbízhatóságot és a hibatűrést.

==== ZFS (Zettabyte File System) ====
* 128 Bit - extra nagy kapacitás
* Pool elvű tárolók – elosztott sávszélesség és kapacitás
* Tranzakció kezelés – Copy on Write
* Snapshots (ro) és klónozás
* Adat integritás – Adat ellenőrző összeg

=== Grid rendszerek osztályozása ===

==== Grid koncepció ====
* Számítógépek erőforrásainak egy adott cél érdekében összefogott halmaza, melyet a felhasználó egységesen, egy egészként kezelve tud elérni a Grid bármely pontjáról.
* A Grid szóhasználat szándékosan utal az elektromos hálózatra (power grid).
* A kezdeti intézményi gridek regionális, nemzeti, ill. világméretű gridekké nőnek, melyek erőforrásait dinamikusan és gazdaságosan lehet elosztani.
* Adat, számítási és információs gridek.

===== Osztályozás =====
* Erőforrás donorok= D
* Erőforrás felhasználók = U

====== A Utility Gridek jellemzői ======
* A donorok profi erőforrás biztosítók (7/24 órás üzemmód)
* Hasonló erőforrások
* Mindenki használhatja az erőforrásokat saját problémáinak megoldására
* Aszimmetrikus kapcsolat a donorok és felhasználók között ( U >> D )
* pl: EGEE, CERN LHC, Open Science Grid

====== A Desktop Grid jellemzői ======
* Akárki adhat hozzá erőforrást
* Heterogén erőforrások, melyek dinamikusan be és kilépnek.
* Egy vagy kevés projekt használhatja az erőforrásokat
* Az erőforrások klienseket futtatnak: Hozzáértés csak szerver oldalon szükséges
* Aszimmetrikus reláció a donorok és felhasználók között ( U << D )
* Előny:
** Egy PC hozzáadása egyszerű
** Installálni, karbantartani egy DG szervert sokkal egyszerűbb
* Típusai
** Global Desktop Grid
*** Cél hogy erőforrásokat gyűjtsön össze tudományos kihívások megoldására
*** Példa: BOINC (SETI@home)
** Local Desktop Grid
*** Célja, hogy egyszerűen összegyűjthetővé tegye a közeli erőforrásokat (egyetem)

==== Jogosultság delegációja ====

===== Grid biztonság =====
Biztonság alatt sokszor eltérő dolgokat értünk:
* Azonosítás/Feljogosítás/Jogok delegálása
** Az alkalmazást futtató felhasználó ne tudja jogosulatlanul használni az erőforrásokat
* Alkalmazás és köztesréteg biztonság
** Az alkalmazásokban való bizalom
** Köztesrétegben való bizalom
* Adatbiztonság
** A rendszerbe bevit/keletkező adatok csak a jogosultak számára legyenek elérhetők
** Az adatátviteli csatornák ne "csöpögjenek"
* Igen jelentős erőforráshalmaz áll jelenleg a felhasználók rendelkezésére.

===== Azonosítás, feljogosítás =====
* Azonosítás: valóban az-e akinek mondja magát
** X.509 tanúsítvánnyal (analógia: személyi igazolvány)
** PKI felhasználásával
* Feljogosítás: mely erőforrásokat használhat.
** komplex elosztott rendszerrel történik (VOMS) (lista, hogy mit kölcsönözhetek).
** erőforrás specifikus
** seite-onként eltérő lehet
** virtuális szervezetek

===== Jogok delegálása =====
* Proxy tanúsítvány:
** Rövidlejáratú és korlátozott felhasználású
** X.509 tanúsítvány (X.509 CGSI kiterjesztéssel)
** Speciális tanúsítvány, amit egy normál végfelhasználó vagy egy másik proxy ír alá
** Támogatja a delegációt (valaki nevében eljárni)
* Delegálás: második szintű proxy tanúsítvánnyal
** A távoli szerver generál proxy tanúsítványt egy új privát/publikus kulccsal, amit elküld a klienshez.
** A kliens aláírja a proxy tanúsítványt visszaküldi a szervernek.
* Így a távoli processz a kliens nevében eljárhat.
** a távoli szerver megszemélyesíti a felhasználót

=== Cloud rendszerek ===

==== Cloud rendszerek ====
* Még nagy a bizonytalanság, többen mást gondolnak róla.
* A hálózati felhőből on-line igénybe venni
** számítási, tárolási kapacitást
** alkalmazást
** egyéb erőforrást
* Lényegében Web 2.0 kiterjesztve ?

==== Softare as a Service (SaaS) ====
* Szoftver alkalmazás igénybevétele web felületen on-line módon
** Clarizen
*** teljes projektmenedzsment
** Google Docs
** SalesForce
** Office 360

==== Infrastructure/ Hardware as a Service (Iaas /HaaS) ====
* Amazon EC2
* HP

==== Platform as a Service (PaaS) ====
* Google App Engine
* Ms Azure
* Force.vom
* Amazon S3, SQS

Párhuzamos és Grid rendszerek - Záróvizsga tételkidolgozás

2013-06-02T07:03:37Z

Fape:

== Párhuzamos rendszerek alapfogalmai ==

=== Flynn-féle architektúra modell ===

{| class="wikitable" border="1"
|-
| colspan="2" rowspan="2" |
| colspan="2" align="center" | Adat (Data)
|-
| align="center" | Egy (Single)
| align="center" | Több (Multiple)
|-
|rowspan="2" align="center" | Utasítás<br />(Instructions)
| align="center" | Egy (Single)
| align="center" | Serial machine (SISD)
| align="center" | Vektor processzor (SIMD)
|-
| align="center" | Több (Multiple)
| align="center" | Pipelines (MISD)
| align="center" | Multiprocesszor (MIMD)
|}

=== Idealizált párhuzamos gép modellje ===
* Több processzor egyazon problémán dolgozik.
* Minden processzornak saját memóriája és címtartománya van.
* Üzenetekkel koordinálnak és adatokat is tudnak átadni.
* A lokális memória elérése gyorsabb.
* Az átviteli sebesség független a csatorna forgalmától.

=== Teljesítményméréshez kapcsolódó fogalmak ===
* Sebességnövekedés (Speed Up): <math>S_n=\frac{T_s}{T_n}</math>
** <math>S_n</math>: N processzorral elért sebességnövekedés,
** <math>T_s</math>: futási idő soros végrehajtás esetén,
** <math>T_n</math>: futási idő N processzor esetén
* Hatékonyság (Efficiency): <math>E_n = \frac{S_n}{N}</math>
** <math>E_n</math>: N processzorral elért hatékonyság
** <math>S_n</math>: N processzorral elért sebességnövekedés
** <math>N</math>: processzorok száma
* Redundancia (Redundancy): <math>r = \frac{C_p}{C_s}</math>
** <math>r</math>: párhuzamos program redundanciája
** <math>C_p</math>: párhuzamos program műveleteinek száma
** <math>C_s</math>: soros program műveleteinek száma
* Amdahl-féle felső határ, N processzorral elértető sebességnövekedés felső határa: <math>S_a = \frac{1}{s+\frac{1-s}{N}}</math>
** <math>s</math>: a feladat nem párhuzamosítható része
** <math>N</math>: processzorok száma
** Az <math>\frac{1-s}{N}</math> tagot elhagyva: <math>Sa < \frac{1}{s}</math>

== Jellegzetes architektúrák ==

=== Architektúrák jellemzői ===
* Processzorok eloszlása
* Homogén vagy heterogén
* A kapcsolat késleltetése és sávszélessége
* Topológia: Háló, gyűrű, fa, hiperkocka, teljes összeköttetés

=== Masszívan párhuzamos, szimmetrikus multiprocesszoros és vektorprocesszoros rendszerek jellemzői ===
???

=== Klaszter koncepció ===
* Gyors hálózattal összekapcsolt gépek
* Gyakran közös fájlrendszer
* CPU vagy tárolási kapacitás növelése
* Paraméter study, vagy párhuzamos alkalmazások

=== Metaszámítógépek ===
???

=== Grid rendszerek ===
???

== Párhuzamosítás, programozási modellek ==

=== Elosztott memória, üzenetküldés, közös memória ===
* Elosztott memória használatának előnyei
** Skálázható
** Költségkímélő
** A redundancia növelésével növekedhet a megbízhatóság
** Speciális feldolgozó eszközökkel is együttműködik
* Elosztott memória használatának hátrányai
** Kommunikáció igényes
** Nem minden algoritmus párhuzamosítható így
** A meglevő soros programokat és a közös memóriát használó alkalmazásokat át kell dolgozni
** Jó speed up értékeket nehéz elérni
** Nehéz nyomkövethetőség

=== Párhuzamos programozási nyelvek és jellemzői ===
* Linda – közös memória modell, Tuple Space.
** Egyszerű modell, de implementációs nehézségek vannak, főleg az üzenetküldéses architektúrákon.
* Express – elosztott memória modell 160 C-ből és fortranból hívható rutin.
* PVM – elosztott memória modell 70 C-ből és fortranból hívható rutin.
** "Szegények" szuperkomputere: a szabad CPU kapacitások összegyűjthetők a munkaállomásokról és a PC-ről
* MPI- szabványos, a gyártók által elfogadott, speciális hw. környezetet is támogató fejl. környezet.
** nem igényli a virtuális gép előzetes felépítését,mert a teljes kommunikációs séma az alkalmazáshoz szerkesztődik.
* OpenMp
** Szálakkal történő párhuzamosítás macerás.
** Nyelvi kiterjesztés
** A programozó a funkcionalitásra koncentrálhat.
** A párhuzamosítás csak lehetőség.
** Shared memóriás párhuzamosítás
** Ipari szabvány
* Cn nyelv
** Standard Ansi C + 2 új kulcsszó (poly és mono)
* Cuda
** GPU
*** A programozható vertex és fragment shaderek beépítésével általános célú eszközzé vált.
*** Vektorprocesszor (SIMD), de pipeline egységek is vannak benne (MISD).
** Ún. thread modell (SIMT)
** A szálak ütemezésével nem kell a programozónak foglalkozni.
** Elrejti a konkrét architektúrát
** Támogatja a heterogén feldolgozás (CPU+GPU)

=== Párhuzamosítási stratégiák ===
* Kényszerű
** A program soros változatát futtatjuk párhuzamosan különböző adatokkal.
** Csak akkor kielégítő módszer, ha a soros változat elviselhető futási idejű.
* Ciklusok párhuzamosítása
** Akkor alkalmazható, ha az egyes iterációk függetlenek egymástól
* Felosztó párhuzamosítás (master / slave)
** Egy felügyelő taszk fut az egyik node-on
** Akkor alkalmazható, ha a felügyelő program feladatai egyszerűbbek mint a többi taszk feladatai.
** Ha a taszkok függetlenek egymástól, akkor jól skálázható a taszkok számának változtatásával.
* Egymást követő
** Minden node a következő node-nak adja tovább a részben feldolgozott adatot.
** Akkor használható, ha a soros része a feldolgozásnak lényegesen rövidebb, mint a párhuzamos rész.
** Rendszerint minden node azonos kódot futtat.
** Különösen alkalmas a gyűrű topológiához.
* Régiók párhuzamosítása
** Az adatfüggőség régiókba lokalizálható.
** Akkor használható, soros végrehajtási idő nagyobb mint a párhuzamos.
** Rendszerint nagy kommunikációigényű.
** Legbonyolultabb.

=== Párhuzamos algoritmusok tervezése ===
* Nem egyszerű.
* Kreativitást igényel.
* Számos iterációt tartalmaz.
* Nincs egyszerű recept.
* Vannak betartható, ajánlott lépések, módszerek.

=== Taszk/csatorna modell jellemzői ===
* minden taszk szekvenciális programot futtat
* minden taszknak van saját memóriája
* taszkok csatornákkal kapcsolódnak,
* a csatornák üzenetsorokat valósítanak meg
* taszkok konkurensek, van lokális memóriájuk
* küldés aszinkron, fogadás szinkron
* csatornához in/out portokkal csatlakoznak
* taszkok tetszőlegesen rendelhetők össze a processzorokkal

* A modell közvetlenül hozzárendelhető az idealizált számítógéphez.
* A taszk egy soros kódot reprezentál.
* A csatorna processzorok közötti kommunikációt valósít meg.
* A taszk működése független a taszkprocesszor összerendeléstől, taszkok számától.
* Moduláris felépítést tesz lehetővé.

* Az üzenet egy adott taszknak szól, ezért kevésbé absztrakt, mint a csatorna.
* Az általános üzenetküldéses modell szerint nem lehet dinamikusan új taszkot létrehozni. (Több megvalósításban lehet.)
* Egy processzor csak egy taszkot futtathat. (Több megvalósításban ez sem korlát.)

=== PCAM módszertan ===
==== Particionálás ====
Sok kis részfeladatokra osztás. NEM veszi figyelembe a fizikai gép HW/SW adottságait. Párhuzamosítható részek felderítése.
* Domén dekompozíció:
** Adat vagy paramétertér felosztása. Az adat lehet input, output, vagy közbülső adat.
* Funkcionális dekompozíció:
** Az algoritmus felosztása olyan részekre, melyek párhuzamosíthatók.
** Alapvetően a feladat funkcióiból adódik.
** Az adatokra is figyelni kell.
** Tipikus példa, amikor az adatok particionálása nem járható: keresés fában. – funkcionálisan viszont bontható

===== Hogy sikerült a particionálás? =====
* Jól, ha particionálással kapott taszkok száma nagyságrendileg több mint a proc. száma.
* Jól, ha redundancia mentes.
* Jól ha a taszkok mérete hasonló.
* Jól, ha a probléma méretével a taszkok száma is nő.

==== Kommunikáció megtervezése ====
Részfeladatok közötti adatcsere és szinkronizációs séma kialakítása.
* Kis környezetű (local) és globális
** a taszkok csak kis környezetükben (szomszéd), vagy sok másik taszkkal is kommunikálnak.
* Strukturált és nem strukturált
** rács, gyűrű, ... vagy más
* Statikus és dinamikus
** végrehajtás közben változik
* Szinkron vagy aszinkron
** koordináció hiánya

===== Hogy sikerült a kommunikáció? =====
* Jól, ha közel azonos számú kommunikációt végez minden taszk.
* Jól, ha a taszkok csak lokális környezetükkel kommunikálnak.
* Jól, ha kommunikáció konkurensen párhuzamosan zajlik.
* Különböző taszkok konkurensen kommunikálnak.

==== Agglomeráció ====
Részfeladatok nagyobb egységekbe gyűjtése a hatékonyságnövelés érdekében. A tényleges párhuzamos gép kommunikációs adottságait is figyelembe véve a részfeladatokat nagyobb egységekbe gyűjtjük.
Agglomeráció szükségessége:
* A kommunikáció "költséges"
* A kommunikáció szükségtelen szinkronizációt okoz
* Térfogat-felület effektus (számítás/kommunikáció arány)
* Flexibilitás megtartása

===== Hogy sikerült az agglomeráció? =====
* Jól, ha jelentősen növekedett a lokális kommunikáció
* Jól, ha a skálázhatóság nem romlott.
* Jól, ha az összevont taszkok mérete közel azonos.
* Jól, ha a probléma méretével növekszik a taszkok száma.
* Jól, ha a már nem vonhatók össze feladatok anélkül, hogy a skálázhatóság vagy a terheléskiegyenlíthetőség ne romlana.

==== Leképezés ====
Tényleges HW/SW környezet figyelembe vétele, leképezés a fizikai gépre. A részfeladatok processzorhoz/ feldolgozó elemhez rendelése. Jelentősen befolyásolhatja a terheléskiegyenlítést, ütemezési algoritmust.

===== Hogy sikerült a leképezés? =====
* Jól, ha nem keletkezett szűk keresztmetszet a programban.
* Jól, ha több lehetséges leképezést is megvizsgáltunk.
* Ha figyelemmel voltunk a terheléskiegyenlítésre.

== Grid és elosztott rendszerek ==

=== Hosszú távú ütemezők ===

==== Condor ====
* Elosztott, heterogén rendszerben működik.
* Alapvetően a szabad CPU ciklusok kihasználására tervezték.
* Képes egy működő feladatot áthelyezni az egyik gépről a másikra (migráció).
* Az ún. ClassAds mechanizmussal képes a rendszerben levő változó erőforrásokat az
* igényeknek megfelelően elosztani
* Opportunista környezet.

===== ClassAds =====
* A rendszerben levő erőforrások különböző jellemzőkkel (teljesítmény, architektúra, op. rendszer, stb.) rendelkeznek.
* A job összeállításánál ezekre a jellemzőkre igényeket lehet előírni amit a Condor előírni, rendszer megpróbál kielégíteni. (Párosítja az igényt az erőforrással)
* A job összeállításánál lehetőség van preferenciák megadására, ami alapján a Condor rangsorolni fog és kiválasztja az igénynek leginkább megfelelő gépet.
* Így nincs szükség a batch rendszerekben megszokott sorokra. (Úgyis a rosszat választanánk)

===== Futtatás lépései =====
* A job összeállítása
* Job bejelentése a Condor-nak
* Job-ot a Condor futtatja az általa kiválasztott gép(eken), szükség átmozgatja egy másik gépre.
* Job befejeződik, a Condor e-mail-t küld a felhasználónak.

==== Sun Grid Engne (SUN) ====
* A Condor-hoz hasonló ütemező.
* Queue-kat definiál.
* Hangsúlyos a terhelés kiegyensúlyozása.
* Backup master ütemező
* Check-point.
* Migrálási lehetőség.
* Négy szerepkör:
** master, submit, exec, admin,

==== Egyéb ====
* Torque (Cluster Resources)
* LoadLeveler (IBM)
* Torque (Cluster Resources)

=== Elosztott fájlrendszerek ===

==== AFS (Andrew File System) ====
* Elosztott fájlrendszer, ami fájlok megosztására alkalmas lokális és távolsági hálózaton.
* Transzparens fájlhozzáférést biztosít.
* Az NFS-hez hasonló, annak alternatívájaként jött létre.
* Ma az OpenAFS számos UNIX, LINUX, WINX platformon elérhető.
* A fő cél az volt, hogy egyetemi korlátozott sávszélességű hálózaton hatékony fájlelérést tegyenek lehetővé.

===== AFS cella =====
* Egy AFS cella alá azok a szerverek tartoznak, melyek adminisztrációja közös, és az AFS felé egyetlen közös fájlrendszert alkotnak.
* Tipikusan az egy domain név alá tartozó gépek egy AFS cellát alkotnak.
* Általában a domain név valamilyen változata a cellanév.
* A munkaállomások a felhasználókról

===== Kötetek =====
* A diszkterületet az AFS további részekre, osztja ezek az AFS kötetek.
* Az AFS kötet egy tárolóegység ami a fájlok és katalógusok adatait tárolja.
* Az AFS kötettek fájlok formájában jelennek meg a befogadó operációs rendszerben, így azok könnyen átmozgathatók, akár másik gépre is.
===== Tokenek =====
* Az AFS nem használja a UNIX felhasználói azonosítóját (UID). Ha ezt tenné, akkor minden UNIX gépen azonos UID kiosztásnak kellene lennie, mint az NFS-nél.
* Az azonosításhoz AFS tokent alkalmaznak, ami egy egyedi azonosítást tesz lehetővé.
* Egy token adott ideig (24 óra) érvényes.

===== Cache menedzser =====
* A korlátozott sávszélesség miatt a működés központi eleme a cache, ahova az éppen használt fájlok letöltődnek.
* A cache menedzser feladata a cache-ben tárolt információk frissítése, karbantartása.
* Amennyiben a cache-ben tárolt fájlrészlet változik, úgy azt vissza kel tölteni a szervere.
* Ha a szerveren változik meg a fájl, akkor arról CallBack technikával értesít minden cache-t.

===== Védelem =====
* A védelmi mechanizmus némileg eltér az alap UNIX védelmi rendszertől.
* A UNIX 3x3-as védelmétől pontosabban szabályozható ACL (Access Control List) segítségével.

===== Processzek =====
* Venus: AFS kliens által futtatott processz.
* Vice: AFS szerver által futtatott processz.

===== Fájl műveletek =====
* A kliens munkaállomás a szerverrel csak az open/close műveletek kiszolgálásakor kommunikál.
* A fájl megnyitásakor a Venus a teljes fájlt a cachebe tölti, és a fájl lezárásakor írja azt vissza.
* Az adatok olvasását/írását a lokális másolaton a kernel végzi.
* A Venus a katalógusokat és a szimbólikus linkeket is a lokális gyorsítótárban tárolja.
* A fenti gyorsítótárazási mechanizmus alól a katalógusok módosítása a kivétel, aminek a végrehajtásáért a közvetlenül szerver a felelős.

===== Megvalósítás =====
* A kliens oldali programok a szokásos módon, rendszerhívással kezelik az állományokat.
* A távoli fájlok megnyitásakor Venus processzhez jut a kérés, amit az lebont az útnév alapján.
* Az alacsonyszintű I/O kezelését a befogadó operációs rendszer végzi. A gyorsítótár a lokális gép diszkjén jön létre.

===== AFS előnyei =====
* Gyorsítótárazásból fakadó előnyök:
** Lényegesen csökkenti a hálózati forgalmat.
** Alacsonyabb sávszélességnél is jól használható.
* Helyfüggetlenség:
** Az AFS a földrajzi helyet a szerver oldalon rendeli fájlnévhez. Így a névtér helyfüggetlen.
* Skálázhatóság:
** A rendszer tervezési fázisában igen nagyra (~10000 kliens) tervezték. A kliens/szerver arányt pedig 200:1-re. Mindkét értéket túlteljesíti.
* Single systems image (SSI):
** Egy fájlszerver kialakítása lényegesen egyszerűbb, mint NFS-sel.
* Fokozott biztonság:
** Kerberos használata, ACL használata
* Fájlok egyszerű megosztása
* Egyszerű rendszer menedzsment
* Robosztus
* Replika lehetőség.

===== AFS hátrányai =====
* Minden munkaállomásra installálni kell.
* Háttérszerver komplexitása.
* Tokenek érvényességének lejártából fakadó gondok.

==== Lustre ====
* Objektum-orientált elosztott fájlrendszer.
* Jól skálázható.
* Nagyméretű klaszterekhez, és nagy fájlokhoz tervezték

===== Lustre architektúra =====
* Három fő funkcionális egysége van:
** Metadata szerver (MDS), ami a fájl neveket, katalógusokat, védelmi kódokat és egyéb metaadatot tárol.
** Object storage szerverek (OSS), melyek az adatokat tárolják.
** Kliens ami az adatokat felhasználja, létrehozza.
* Az adatok logikai kötetmenedzsmenttel ellátott RAID tárolókban tárolódnak, amit az OSS és az MDS dedikált módon használ.
* Jelenleg egy módosított ext3 fájlrendszer a logikai tároló, de a SUN dolgozik a ZFS beépítésén.
* Amikor egy kliens fájlt akar elérni, először az MDS-ben meg kell keresnie.
* A fájl egyes darabjai több OSS-en tárolódhatnak, ami a kliens és az OSS között szűk keresztmetszet kialakulását gátolja.
* A kliensek nem módosítják közvetlenül az OSS-ben tárolt adatokat, hanem ezt a OSSre bízzák, szemben a GFS megoldásával.
* Ez a módszer növeli a megbízhatóságot és a hibatűrést.

==== ZFS (Zettabyte File System) ====
* 128 Bit - extra nagy kapacitás
* Pool elvű tárolók – elosztott sávszélesség és kapacitás
* Tranzakció kezelés – Copy on Write
* Snapshots (ro) és klónozás
* Adat integritás – Adat ellenőrző összeg

=== Grid rendszerek osztályozása ===

==== Grid koncepció ====
* Számítógépek erőforrásainak egy adott cél érdekében összefogott halmaza, melyet a felhasználó egységesen, egy egészként kezelve tud elérni a Grid bármely pontjáról.
* A Grid szóhasználat szándékosan utal az elektromos hálózatra (power grid).
* A kezdeti intézményi gridek regionális, nemzeti, ill. világméretű gridekké nőnek, melyek erőforrásait dinamikusan és gazdaságosan lehet elosztani.
* Adat, számítási és információs gridek.

===== Osztályozás =====
* Erőforrás donorok= D
* Erőforrás felhasználók = U

====== A Utility Gridek jellemzői ======
* A donorok profi erőforrás biztosítók (7/24 órás üzemmód)
* Hasonló erőforrások
* Mindenki használhatja az erőforrásokat saját problémáinak megoldására
* Aszimmetrikus kapcsolat a donorok és felhasználók között ( U >> D )
* pl: EGEE, CERN LHC, Open Science Grid

====== A Desktop Grid jellemzői ======
* Akárki adhat hozzá erőforrást
* Heterogén erőforrások, melyek dinamikusan be és kilépnek.
* Egy vagy kevés projekt használhatja az erőforrásokat
* Az erőforrások klienseket futtatnak: Hozzáértés csak szerver oldalon szükséges
* Aszimmetrikus reláció a donorok és felhasználók között ( U << D )
* Előny:
** Egy PC hozzáadása egyszerű
** Installálni, karbantartani egy DG szervert sokkal egyszerűbb
* Típusai
** Global Desktop Grid
*** Cél hogy erőforrásokat gyűjtsön össze tudományos kihívások megoldására
*** Példa: BOINC (SETI@home)
** Local Desktop Grid
*** Célja, hogy egyszerűen összegyűjthetővé tegye a közeli erőforrásokat (egyetem)

==== Jogosultság delegációja ====

===== Grid biztonság =====
Biztonság alatt sokszor eltérő dolgokat értünk:
* Azonosítás/Feljogosítás/Jogok delegálása
** Az alkalmazást futtató felhasználó ne tudja jogosulatlanul használni az erőforrásokat
* Alkalmazás és köztesréteg biztonság
** Az alkalmazásokban való bizalom
** Köztesrétegben való bizalom
* Adatbiztonság
** A rendszerbe bevit/keletkező adatok csak a jogosultak számára legyenek elérhetők
** Az adatátviteli csatornák ne "csöpögjenek"
* Igen jelentős erőforráshalmaz áll jelenleg a felhasználók rendelkezésére.

===== Azonosítás, feljogosítás =====
* Azonosítás: valóban az-e akinek mondja magát
** X.509 tanúsítvánnyal (analógia: személyi igazolvány)
** PKI felhasználásával
* Feljogosítás: mely erőforrásokat használhat.
** komplex elosztott rendszerrel történik (VOMS) (lista, hogy mit kölcsönözhetek).
** erőforrás specifikus
** seite-onként eltérő lehet
** virtuális szervezetek

===== Jogok delegálása =====
* Proxy tanúsítvány:
** Rövidlejáratú és korlátozott felhasználású
** X.509 tanúsítvány (X.509 CGSI kiterjesztéssel)
** Speciális tanúsítvány, amit egy normál végfelhasználó vagy egy másik proxy ír alá
** Támogatja a delegációt (valaki nevében eljárni)
* Delegálás: második szintű proxy tanúsítvánnyal
** A távoli szerver generál proxy tanúsítványt egy új privát/publikus kulccsal, amit elküld a klienshez.
** A kliens aláírja a proxy tanúsítványt visszaküldi a szervernek.
* Így a távoli processz a kliens nevében eljárhat.
** a távoli szerver megszemélyesíti a felhasználót

=== Cloud rendszerek ===

==== Cloud rendszerek ====
* Még nagy a bizonytalanság, többen mást gondolnak róla.
* A hálózati felhőből on-line igénybe venni
** számítási, tárolási kapacitást
** alkalmazást
** egyéb erőforrást
* Lényegében Web 2.0 kiterjesztve ?

==== Softare as a Service (SaaS) ====
* Szoftver alkalmazás igénybevétele web felületen on-line módon
** Clarizen
*** teljes projektmenedzsment
** Google Docs
** SalesForce
** Office 360

==== Infrastructure/ Hardware as a Service (Iaas /HaaS) ====
* Amazon EC2
* HP

==== Platform as a Service (PaaS) ====
* Google App Engine
* Ms Azure
* Force.vom
* Amazon S3, SQS

Párhuzamos és Grid rendszerek - Záróvizsga tételkidolgozás

2013-06-02T06:47:40Z

Fape: Új oldal, tartalma: „== Párhuzamos rendszerek alapfogalmai == === Flynn-féle architektúra modell === {| class="wikitable" border="1" |- | colspan="2" rowspan="2" | | colspan="2" align…”

Párhuzamos és Grid rendszerek

2013-06-02T05:58:18Z

Fape:

{{GlobalTemplate|Infoszak|ParhuzamosEsGridRendszerek}}

* Tárgyfelelős: Dr. Szeberényi Imre
* Tárgyhonlap: http://bagira.iit.bme.hu/~szebi/parh_grid_msc.html

==ZH kérdések==

* Flynn féle architektúramodell
* Sorolj fel pár hosszútávú ütemezőt és jellemezd őket
* Milyen GRID modellek vannak és jellemzőik
* jogosultság delegáció gLite rendszerben
* mi a szerepe VO-k nak.
* milyen környezetben (SMP,MPP,Cluster) használható az [[OpenMP]]
* SMP, MPP, Cluster jellemzése
* Proxy tanúsítvány működése infrastruktúra [[GRIDekben]]
* milyen hozzáférési módokat nyújt a gLite SRM?
* Cloud vs. GRID hasonlóságok és különbségek
* Micsoda a SaaS, PaaS, [[IaaS]]
* Dasein API rövid jellemzése

==Vizsgák==
* [[ParhuzamosEsGridRendszerekVizsga20110525|Vizsga 2011.05.25.]]

==Záró vizsga==
* [[Párhuzamos_és_Grid_rendszerek_záróvizsga_tétel_kidolgozás|Záróvizsga tétel kidolgozás]]

-- [[FaPe|FaPe]] - 2011.05.30.

[[Category:Infoszak]]

Párhuzamos és Grid rendszerek

2013-06-02T05:54:08Z

Fape:

{{GlobalTemplate|Infoszak|ParhuzamosEsGridRendszerek}}

* Tárgyfelelős: Dr. Szeberényi Imre
* Tárgyhonlap: http://bagira.iit.bme.hu/~szebi/parh_grid_msc.html

==ZH kérdések==

* Flynn féle architektúramodell
* Sorolj fel pár hosszútávú ütemezőt és jellemezd őket
* Milyen GRID modellek vannak és jellemzőik
* jogosultság delegáció gLite rendszerben
* mi a szerepe VO-k nak.
* milyen környezetben (SMP,MPP,Cluster) használható az [[OpenMP]]
* SMP, MPP, Cluster jellemzése
* Proxy tanúsítvány működése infrastruktúra [[GRIDekben]]
* milyen hozzáférési módokat nyújt a gLite SRM?
* Cloud vs. GRID hasonlóságok és különbségek
* Micsoda a SaaS, PaaS, [[IaaS]]
* Dasein API rövid jellemzése

==Vizsgák==
* [[ParhuzamosEsGridRendszerekVizsga20110525|Vizsga 2011.05.25.]]

==Záró vizsga==
* [[Párhuzamos_és_Grid_rendszerek_zarovizsga_tetel_kidolgozás|Záróvizsga tétel kidolgozás]]

-- [[FaPe|FaPe]] - 2011.05.30.

[[Category:Infoszak]]