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.