7. tétel: Párhuzamos tervezési minták I.

Mutassa be a Single Program - Multiple Data tervezési mintát! Ismertesse a tulajdonságait, az általános felépítését, valamint tipikus használati eseteit! Mutassa be a Loop Parallelism tervezési mintát!

Single Program - Multiple Data

Általános felépítése

  1. Inicializálás

    Lokális allokációs műveletek, ha szükséges akkor más szálakhoz való kapcsolódási pontok definiálása. Implementációtól függően eltérő rutinokat is jelent, de a memóriafoglalás és a kommunikációs csatornák létrehozása mindig megtörténik.

  2. Egyedi azonosító

    Minden szál egyedi azonosítóval rendelkezik, jellemzően 0-tól indexelve. Az azonosításon túl meghatározhatja a szál viselkedését.

  3. Végrehajtás

    A szálak adatoktól és azonosítójuktól függően végrehajtják ugyanazokat az utasításokat. Mindegyik szál ugyanazt a kódot futtatja, csak eltérhet, hogy melyik elágazásba melyik azonosítójú szálat engedjük be.

  4. Adatok elosztása

    Dedikált adatokat, vagy egy közös tároló logikai résztömbjét érik el a szálak. Fontos eleme az SMPD mintának, környezettől függően más-más implementációt jelent. Gyakori adatelérés esetén érdemes az adatot a szál lokális memóriájába másolni, hogy kevesebb kommunikációra legyen szükség.

  5. Befejezés

    A szálak leállítása, vagy bevárása, ha szükséges akkor az eredmények összegyűjtése (globális tárolóba vagy egyik szál lokális memóriájába). Ha olyan a feladat, akkor szükséges lehet egy randevú jellegű szinkronizációs pont létrehozása.

Tulajdonságok

  • Fontos az adatok elosztása
    • Számolni kell ennek az adatok dekompozíciójának, másolásának költségével (overhead)
    • A lokális memóriába másolás így is megérheti, mert kisebb az overhead, mint hálózati kommunikációval
  • Előnyök:
    • könnyen áttekinthető a közös kódbázis miatt
    • overhead csak az indítás, inicializálás és befejezés szakaszban fordulhat elő

Tipikus használati esetek

Jól használható, ha teljesülnek az alábbiak:

  • feladatpárhuzamosság,
  • a feladatok között nincs összefüggés,
  • kommunikációra nincs szükség a szálak között.

Jó hatásfok érhető el geometriai felbontás esetén, ha a problémateret diszkrét alterekre bontjuk, és az ezeken végzett műveleteket külön műveletvégzőkhöz rendeljük: a feladatok ebben az esetben azonosak vagy hasonlóak, míg a szálak közti interakció úgyszintén nem jellemző.

Loop Parallelism

A Loop Parallelism mintát akkor használjuk, ha

  • a megoldandó feladatban feladatpárhuzamosság alakítható ki
  • középpontjában nagy lépésszámú ciklusok állnak
  • a környezet pedig egy közös memóriájú rendszer

Elosztott rendszer esetében a Master/Worker vagy az SMPD minta használható a ciklus feldarabolására.

A minta előnye, hogy nem kell nagyon átalakítani az algoritmust, nem is kell érteni az egészet, csak a számításintenzív ciklust kell azonosítani és függetleníteni az iterációkat.

A minta alkalmazásának lépései

  1. Számításigényes ciklusok felfedezése

    Kód analízise, mérések készítése. Ha a bottleneck egy ciklus, jöhet a következő lépés.

  2. Cikluson belüli függőségek megszüntetése

    • A különböző iterációkat párhuzamosan feldolgozható, (részben) független feladatokká próbáljuk alakítani.
    • Teljesen nem mindig lehet, de a cél a minél nagyobb függetlenség.
    • Jellemzően a közös változókat szükséges elkerülni ideiglenes változók használatával, így a számítási komplexitást memóriaköltséggé alakítjuk.

  3. Ciklusok párhuzamosítása

    • A a kialakított feladatokat hozzárendeljük az elérhető műveletvégzőkhöz
    • Ciklusváltozók tartományának felbontása

  4. Ütemezés optimalizálása

    • A feladatok vélhetően hasonlóak, a komplexitásuk is vélhetően hasonló
      • ha mégsem, a programozó feladata figyelni a terheléseloszlásra