Párhuzamos és Grid rendszerek 2. előadás
Letöltés
- Nyomtatáshoz, 3 dia/lap (590K)
- Nyomtatáshoz, 6 dia/lap (586K)
- Képernyőre, 1 dia/lap (színes) (324K)
- E-könyv olvasóhoz, 1 dia/lap (587K)
1.
Párhuzamos és Grid rendszerek (2. ea) párhuzamos algoritmusok tervezése Szeberényi Imre BME IIT <szebi@iit.bme.hu> Az ábrák egy része Ian Foster: Designing and Building Parallel Programs (Addison-Wesley) c. könyvéb l származik. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. M EGYETEM 1782 2013.02.18. -1-
2.
Hol tartunk ? • Megismerkedtünk az alapfogalmakkal • Megismertük a fontosabb párhuzamos architektúrákat: • SMP (NUMA, ccNUMA) • MPP • CLUSTER Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. -2-
3.
Hol tartunk ? /2 • Felvázoltunk fizikai és logikai összeköttetéseket • Egyszer absztrakciós modellt alkottunk a párhuzamos gépek leírására • Említett programozási modellek – Közös memóriás – Elosztott közös memóriás – Üzenet küldéses Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. -3-
4.
Taszk/csatorna modell /1 • • • • 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. 2013.02.18. -4-
5.
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 Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. -5-
6.
Taszk/csatorna modell /3 • Példa: termel -fogyasztó probléma – taszk1: termel – taszk2: fogyasztó Raktár T1 T2 • ha a fogyasztó lassabb, akkor a felhalmozódik a termelt adat • ha a termel a lassabb, akkor vár a fogy. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. -6-
7.
Taszk/csatorna modell /4 • Példa: termel -fogyasztó probléma – taszk1: termel – taszk2: fogyasztó T1 T2 • második csatornán a fogyasztó jelzi, ha kér újabb adatot • a termel ennek hatására termel Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. -7-
8.
Taszk/csat. modell jellemz i • 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é. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. -8-
9.
Taszk/csatorna vs. üzenet • 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.) Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. -9-
10.
Párh. algoritmus példák /1 • Véges differenciák: – 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: Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 10 -
11.
Párh. algoritmus példák /2 • Páronkénti iteráció (pl. atomok kölcsönös egymásra hatása) – 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. 2013.02.18. - 11 -
12.
Párh. algoritmus példák /3 • 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 © BME-IIT Sz.I. 2013.02.18. 1 - 12 -
13.
Párh. algoritmus példák /4 • N újabb csatornával az algoritmus a szimmetria miatt tovább egyszer síthet : – 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 1 4 3 Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2 2013.02.18. - 13 -
14.
Párh. algoritmus példák /5 • Párhuzamos keresés: – fában történ keresés egyszer en párhuzamosítható • Paraméter elemzés: – master-worker algoritmus Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 14 -
15.
Párh. algoritmus példák /6 • Pipeline rendezés: – minden elem megtartja a nagyobbat – a kisebbet továbbküldi • Pipeline merge sort 2|1|6|8 3 1|8 4 87654321 8 6 5 4 72315648 p0 p1 7|3|5|4 Párhuzamos és Grid rendszerek © BME-IIT Sz.I. p2 7 2|6 5 p3 7 3 2 1 - 2013.02.18. - 15 -
16.
Párh. 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. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 16 -
17.
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 és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 17 -
18.
Particionálás • Cél: Párhuzamosítható részek felderítése. A m velet absztrakt, nem veszi figyelembe párhuzamos környezet HW/SW adottságait. • Finom felbontás (sok kis részfeladat) el állítása hatékonyabb és egyszer bb. • A feladatot és az adatokat is kis részekre szedjük. – domén dekompozíció – funkcionális dekompozíció Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 18 -
19.
Domén dekompozíció • Adat vagy paramétertér felosztása. Az adat lehet input, output, vagy közbüls adat. – Példa: Egy 3D rácson minden rácspontban ki kell számolni egy értéket. 1, 2, vagy 3 dimenziós partíció: Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 19 -
20.
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 partícionálása nem járható: keresés fában. – funkcionálisan viszont bontható Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 20 -
21.
Hogy sikerült a partícionálás? • Jól, ha partícioná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 . Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 21 -
22.
Kommunikáció • 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 Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 22 -
23.
Kommunikációs példák /1 Lokális kommunikáció (Jakobi): (Gauss-Seidel): Red-Black ordering: Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 23 -
24.
Kommunikációs példák /2 Globális kommunkáció (szumma): Cs vezeték: Oszd meg és uralkodj: Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 24 -
25.
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ácó konkurensen párhuzamosan zajlik. • Különböz taszkok konkurensen kommunikálnak. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 25 -
26.
Agglomeráció • 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. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 26 -
27.
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 Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 27 -
28.
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. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 28 -
29.
Leképezés (mapping) • Tényleges HW/SW környezet figyelembe vétele, leképezés a fizikai gépre. • Jelent sen befolyásolhatja a terheléskiegyenlítést, ütemezési algoritmust. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 29 -
30.
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. Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 30 -
31.
Komplex példa: mátrix szorzás /1 Mátrix-mátrix szorzás: O(N3) • Partícionálás: – egy Cij-t csak egy processzor számoljon – domén dekompozíció – 1D: – 2D: Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 31 -
32.
Komplex példa: mátrix szorzás /2 • Kommunikáció – 1D: Minden proc.-nak szüksége van a teljes A-ra. – tfh. egy processzor felel s az adatok szétküldéséért és begy jtéséért (pl. SPMD) – T1d = (P-1)*(N2 + 2*N2/P) ≈ P*N2 – A kommunikációs igény processzor számával lineárisan n ! Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 32 -
33.
Komplex példa: mátrix szorzás /2 • Kommunikáció – 2D: Azonos sor ill. azonos oszlop kell A-ból és B-b l. – Algoritmus (Fox’s): 1. C = 0 2. Ismétlés N-1-szer: 3. A átlóit soronként ismételve tegyük egy A'-be 4. Cij = Cij + Bij * A‘ij 5. B = B ciklikus feltolása – T2d = 2*(√P-1)*N2 + (P-1)*N2/P ≈ N2/√P Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 33 -
34.
Komplex példa: mátrix szorzás /4 • Agglomeráció: – A kommunikációs igény felmérésénél láttuk, hogy érdemes lehet nagyobb csoportokat alkotni. – Esetleg más algoritmusok (pl. Cannon) más agglomerációt igényelhetnek. • Leképezés (mapping): – Rács – Fa Párhuzamos és Grid rendszerek © BME-IIT Sz.I. 2013.02.18. - 34 -