Tipp: a diák között a J és K billentyűkkel lehet lépkedni.
Letöltés
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-
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-
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-
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-
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-
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-
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-
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-
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-
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
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 -
