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

Párhuzamos rendszerek alapfogalmai

Flynn-féle architektúra modell

		Adat (Data)
		Egy (Single)	Több (Multiple)
Utasítás (Instructions)	Egy (Single)	Serial machine (SISD)	Vektor processzor (SIMD)
	Több (Multiple)	Pipelines (MISD)	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): $S_{n}={\frac {T_{s}}{T_{n}}}$
  • $S_{n}$: N processzorral elért sebességnövekedés,
  • $T_{s}$: futási idő soros végrehajtás esetén,
  • $T_{n}$: futási idő N processzor esetén
• Hatékonyság (Efficiency): $E_{n}={\frac {S_{n}}{N}}$
  • $E_{n}$: N processzorral elért hatékonyság
  • $S_{n}$: N processzorral elért sebességnövekedés
  • $N$: processzorok száma
• Redundancia (Redundancy): $r={\frac {C_{p}}{C_{s}}}$
  • $r$: párhuzamos program redundanciája
  • $C_{p}$: párhuzamos program műveleteinek száma
  • $C_{s}$: soros program műveleteinek száma
• Amdahl-féle felső határ, N processzorral elértető sebességnövekedés felső határa: $S_{a}={\frac {1}{s+{\frac {1-s}{N}}}}$
  • $s$: a feladat nem párhuzamosítható része
  • $N$: processzorok száma
  • Az ${\frac {1-s}{N}}$ tagot elhagyva: $Sa<{\frac {1}{s}}$

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