Összefogalás • Párhuzamos architektúrák • Párhuzamos programok modellezése • Párh. prog. fejlesztési módszerek
Párhuzamos és Grid rendszerek (12. ea) Összefoglalás
– kevés algoritmus
• Fejlesztési környezetek, nyelvek
Szeberényi Imre BME IIT
– PVM, MPI – OpenMp – Clearspeed – CUDA
<
[email protected]>
M Ű E G Y ET E M 1 7 8 2 Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
-1-
2011.05.04.
Párhuzamos és Grid rendszerek
Flynn-féle architektúra modell DATA
Single
Single
Párhuzamos és Grid rendszerek
Single Instruction Single Data
Single Instruction Multiple Data
SISD (serial machines)
SIMD (vector processors)
Multiple Instruction Single Data
Multiple Instruction Multiple Data
MISD (pipelines)
MIMD (multiprocesszors)
© BME-IIT Sz.I.
●
-3-
2011.05.04.
Processzorok eloszlása
●
Homogén vagy heterogén
●
A kapcsolat késleltetése és sávszélessége
●
Topológia Gyűrűk
Teljesen összekötött
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
memória
memória
CPU 1
CPU 2
CPU 3
●
Ü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.
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
-4-
Minden processzornak saját memóriája és címtartománya van.
• Közös memóriás • Elosztott közös memóriás • Üzenet küldéses Valójában egyik modell sem kötődik szorosan a tényleges architektúrához
Több processzor egyazon problémán dolgozik.
Programozási modell
Hiperkockák
Fák
memória
Összeköttetés ●
●
Hálók
-2-
Multiple
Architektúrák jellemzői
2011.05.04.
Idealizált párhuzamos számítógép
INSTRUCTIONS
Multiple
© BME-IIT Sz.I.
2011.05.04.
-5-
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
-6-
1
Taszk/csatorna modell /1 • • • •
Taszk/csatorna modell /2 • • • • •
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
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
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
-7-
Taszk/csatorna modell /3
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
• Példa: termelő-fogyasztó probléma
– taszk1: termelő – taszk2: fogyasztó
Raktár
– taszk1: termelő – taszk2: fogyasztó
T1
T2
T1
• ha a fogyasztó lassabb, akkor a felhalmozódik a termelt termék • ha a termelő a lassabb, a akkor vár a fogy. © BME-IIT Sz.I.
2011.05.04.
-9-
2011.05.04.
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 10 -
Taszk/csatorna vs. üzenet
• 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é. © BME-IIT Sz.I.
T2
• második csatornán a fogyasztó jelzi, ha kér újabb terméket • a termelő ennek hatására termel
Taszk/csat. modell jellemzői
Párhuzamos és Grid rendszerek
-8-
Taszk/csatorna modell /4
• Példa: termelő-fogyasztó probléma
Párhuzamos és Grid rendszerek
2011.05.04.
• 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.)
- 11 -
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 12 -
2
Párh. algoritmus példák /1
Párh. algoritmus példák /2
• Véges differenciák:
• Páronkénti iteráció (pl. atomok kölcsönös egymásra hatása)
– egy vektor minden elemére T-szer végre kell hajtani a következő műveletet: – Minden elemet egy-egy taszk számol, aki kommunikál a szomszédaival:
– N*(N-1) üzenet kell, esetleg N*(N-1)/2, ha kihasználjuk a szimmetriát. Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 13 -
Párh. algoritmus példák /3
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
1
– hozzunk létre minden i. taszk és i+N/2-dik taszk között egy újabb csatornát. – az adott atomra ható erőket folyamatosan számoljuk, és küldjük is körbe. – N/2 iterációval előáll az eredmény. 0 L0 L1 L2 L3 L4 F0 F1 F2 F3 F4
- 15 -
Párhuzamos és Grid rendszerek
1
4 3
© BME-IIT Sz.I.
2 2011.05.04.
- 16 -
PCAM módszertan 1. Particionálás: Részfeladatokra osztás. NEM veszi figyelembe a fizikai gép adottságait. 2. Kommunikáció megtervezése: Részfeladatok közötti adatcsere és szinkronizációs séma kialakítása. 3. Agglomeráció: Részfeladatok nagyobb egységekbe gyűjtése a hatékonyságnövelés érdekében. 4. Leképezés: A részfeladatok processzorhoz (feldolgozó elemhez) rendelése.
• Párhuzamos keresés: – fában történő keresés egyszerűen párhuzamosítható
• Paraméter elemzés: – master-worker algoritmus
© BME-IIT Sz.I.
- 14 -
2011.05.04.
• N újabb csatornával az algoritmus a szimmetria miatt tovább egyszerűsíthető:
Párh. algoritmus példák /5
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
Párh. algoritmus példák /4
• Körkörös kapcsolat (csatorna) a fenti problémára hatékonyabb üzenetstruktúrát eredményez: L L LL
0 0 0 3 0 – Egy N elemű vektorba minden 3 taszk beteszi a saját adatát (koord., tömeg) és elküldi a szomszédnak. – A bejövő üzenetbe megfelelő helyre ismét 2 elhelyezi a saját adatát és továbbküldi azt. – N-1 lépés után mindenki ismeri az a többiek koordinátáit és tömegét. – F értéke minden lépésben az új partnerek adata alapján akkumulálható.
Párhuzamos és Grid rendszerek
2011.05.04.
- 17 -
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 18 -
3
Domén dekompozíció
Funkcionális dekompozíció
• Adat vagy paramétertér felosztása. Az adat lehet input, output, vagy közbülső adat.
• 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 partícionálása nem járható: keresés fában.
– Példa: Egy 3D rácson minden rácspontban ki kell számolni egy értéket. 1, 2, vagy 3 dimenziós partíció:
– funkcionálisan viszont bontható
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 19 -
Kommunikáció
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 20 -
Kommunikációs példák /1
• Kis környezetű (local) és globális
Lokális kommunkáció (véges elem):
– 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
Red-Black ordering:
– végrehajtás közben változik
• Szinkron vagy aszinkron – koordináció hiánya Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 21 -
Párhuzamos és Grid rendszerek
Kommunikációs példák /2
- 22 -
2011.05.04.
- 24 -
• 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.
Csővezeték: Oszd meg és uralkodj:
© BME-IIT Sz.I.
2011.05.04.
Agglomeráció
Globális kommunkáció (szumma):
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 23 -
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
4
Cluster koncepció • • • •
Ütemezők
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
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
• • • • • • • • 2011.05.04.
- 25 -
Condor (University of Wisconsin) DQS (Florida State University) LoadLeveler (IBM) Maui, Moab (Cluster Resources) LSF (Platform) PBS, OpenPBS (Alatair) Sun Grid Engne (SUN) Torque (Cluster Resources)
Párhuzamos és Grid rendszerek
Elosztott fájlrendszerek
NFS AFS, CODA Lustre, SFS GFS GlusterFS OCFS
• 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.
– – – – –
Gfarm file system Google file system GPFS BigTable Parallel Virtual File System – QFS
Több mint 70! fs Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 27 -
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
Grid hasonlat Mobil
Munkaállomás
M I D D L E W A R E
Erőforrás biztosítás statikus 7/24
Intézet 2
Supercomputer, PC-Cluster
Donor és felhasználó
Donor és felhasználó
Internet Felhasználó N
Felhasználó 1 Spec. erőforr.: Érzékelők, adatgyűjtők
Dinamikus erőforrás igények
Vizualizáció
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
- 28 -
2011.05.04.
Utility Grid modell Intézet 1
G R I D
- 26 -
2011.05.04.
Grid koncepció
• Nagyméretű klaszterekhez • Földrajzilag is elosztott rendszerekhez – – – – – –
© BME-IIT Sz.I.
2011.05.04.
- 29 -
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 30 -
5
LHC
A Utility Gridek jellemzői
Large Hadron Collider
• A donorok profi erőforrás biztosítók (7/24 órás üzemmód) Egyszerűsítés • Hasonló erőforrások Egyszerűsítés • 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
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 31 -
Párhuzamos és Grid rendszerek
LHC
Produces ~15 PByte/year
© BME-IIT Sz.I.
2011.05.04.
Desktop Grid modell Data is stored at CERN and 11 other (tier1) sites Data is processed at CERN, the 11 tier1 sites and ~100 tier2 sites
Dinamikus erőforrás biztosítás Vállalati / Donor: Vállalat /
Egyetemi Szerver Alkalmazás
Egyetem / privát PC
Internet
Donor: Vállalat /
Donor: Vállalat / Egyetem / privát PC
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 33 -
Cloud újabb buzzword? • • • • • • • •
Egyetem / privát PC
Software disztribúció
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 34 -
Cloud computing def.
Metacomputing Utility computing Grid computing SaaS – Softare as a Service HaaS – Hardware as a Service PaaS – Platform as a Service IaaS – Infrastructure as a Service Web 2.0
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
- 32 -
• 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 ?
2011.05.04.
- 35 -
Párhuzamos és Grid rendszerek © BME-IIT Sz.I.
2011.05.04.
- 36 -
6
A Dasein Cloud API
PRAM modell • Parallel Random Access Machine (PRAM) • Elméleti modell a az algoritmusok vizsgálatához Célja: • Algoritmusok osztályozása, komplexitásának vizsgálata. • Párhuzamosíthatóság elvi határainak felfedése. • Új algoritmusok kifejlesztése.
• Java nyelvű, open source (Apache v2.0), aktívan fejlesztett programkönyvtár. • Számos IaaS szolgáltatót (AWS, Terremark, Rejila), privát felhőt (vCloud, vSphere, CloudStack), storage rendszert (Rackspace, Mezeo, a Google App Engine vagy az MS Azure BlobStore szolgáltatása) kezel. • Implementációja épít a platform-specifikus megoldásokra (vSphere VIM), és a jclouds open source API-ra. • http://dasein-cloud.sourceforge.net/ 2011.05.04.
- 37 -
Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
2011.05.04.
- 38 -
OpenMP execution model
OpenMP motivation • Parallelize the following code using threads: for (i=0; i
JOIN
Master thread
FORK
Worker Thread
JOIN
© BME-IIT Sz.I.
FORK
Párhuzamos és Grid rendszerek
• Problems with the code:
– Need mutex to protect the accesses to sum – Different code for serial and parallel version – No built-in tuning (# of processors someone?) Párhuzamos és Grid rendszerek
© BME-IIT Sz.I.
Fork and Join: Master thread spawns a team of threads as needed 2011.05.04.
- 39 -
Általános célú GPU
© BME-IIT Sz.I.
© BME-IIT Sz.I.
2011.05.04.
- 40 -
Egy példa NVIDIA Quadro FX5800 grafikus kártya
• 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). • Jellemzően SIMD • Programozás: CUDA, OpenCl, Cg, …
Párhuzamos és Grid rendszerek
Párhuzamos és Grid rendszerek
2011.05.04.
– PCIe x16 – 240 CUDA mag – 4 GB DDR3 – 78 GFlos double – 933 Gflops single – 189 W – 300Millió háromszög / sec – NVIDIA CUDA
- 41 -
Grir és OO labor Párhuzamos és Grid © BME-IIT rendszerek Sz.I. © BME-IIT Sz.I.
2010.11.09. 2011.05.04.
- 42 -
7
