1. tétel - Párhuzamos programok hatékonysága

Ismertesse Amdahl és Gustafson törvényét! Definiálja az overhead és a bottleneck fogalmakat! Mutassa be a szemcsézettség és terheléselosztás kapcsolatát!

Egy szekvenciális program futásideje formálisan felírható mint:

\[ T_{total} = T_{setup} + T_{compute} + T_{finalization} \]

Ahol:

• setup: inicializációs lépések
  • pl: adatbetöltés, memória foglalás, hálózati kapcsolat
  • nem párhuzamosítható
• compute: konkrét feladat végrehajtása
• finalization: lezárás
  • pl: eredmények mentése, hálózaton való továbbítása
  • nem párhuzamosítható

A futásidő p darab műveletvégző esetén

\[ T_{total}(p) = T_{setup} + \frac{T_{compute}}{p} + T_{finalization} \]

Amdahl törvénye

• Gene Amdahl 1967-ben publikálta
• Azt modellezi, hogy egy szekvenciális program párhuzamos implementációjának futtatása esetén milyen kapcsolat jelenik meg a processzorok száma és a várható sebességnövekedés között.

A publikált képlete:

\[ S_{latency}(p) = \frac{1}{{(1-f)+\frac{f}{p}}} \]

• S_latency(p): elméleti gyorsulás. A latency itt látenst jelent, nem késleltetést!
• p: műveletvégzők száma
• f: program párhuzamosítható szakasza (0 és 1 közötti szám)

Fontos következtetések:

• p és Slatency(p) közötti összefüggés nem lineáris
  • tehát pl. 2x annyi műveletvégzőtől nem lesz 2x gyorsabb
• a gyorsítás mértéke mindig kisebb, mint a műveletvégzők száma
• fix feladatméretet feltételez, azaz, az erőforrások növelésével nem változik a terhelés, nem lesz nagyobb a feladat, ugyanazt kell megoldani

Bottleneck

• Minden olyan kódblokk, amely szekvenciálisan kell, hogy végrehajtódjon, az rontani fogja az összteljesítményt.
• Bottleneck-ek: a szoftverfejlesztésben azon a komponensek, amelyeknek az áteresztőképessége alacsony, és ez korlátozza a teljes rendszer teljesítményét

Overhead

Az időmennyiség párhuzamos programozásnál, amely a probléma megoldása szempontjából "haszontalan" feladatokkal telt, melyek szekvenciális esetben nem fordultak volna elő.

Például:

1. Műveletvégzők kezelése
2. Műveletvégzők közötti kommunikáció időben adott költsége

Amdahl törvénye nem veszi figyelembe a párhuzamosításhoz implementálandó esetleges további utasításokat, és az ezek végrehajtásához szükséges időt. Ha ezt is figyelembe vennénk, akkor a teljes időhöz megjelenne egy Toverhead tényező, amely p értékével arányos.

Az overhead mértéke függ:

• a konkrét algoritmustól
• környezettől
• konkrét implementációtól,

de \(T_{overhead}(p) = log_{2}(p) \) egy jó közelítés.

Gustafson törvénye

Megadja, hogy ha egy p darab műveletvégzővel rendelkező párhuzamos gép t idő alatt oldaná meg a problémát, akkor mennyi ideig tartana egyetlen szekvenciálisnak.

Gustafson szerint az elméleti elérhető gyorsítás megadható, mint

\[ S_{latency}(p) = 1 - f + pf \]

A szemcsézettség és terheléselosztás kapcsolata

A dekompozíció célja a feladat kisebb, konkurens módon végrehajtható részfeladatokra bontása.

A szemcsézettséggel a részfeladatok méretét és mennyiségét írjuk le.

• A feladat végrehajtása közben az az elsődleges cél, hogy az elérhető műveletvégzők végig kihasználtan dolgozzanak.
• Ideális esetben az összes műveletvégző egyszerre végez, ezzel előállítva a végeredményt, ellenkező esetben az utolsó még dolgozó műveletvégzőt kell bevárniuk a már végzett szálaknak.

Terheléselosztás: a műveletvégzők közötti hatékony kihasználtság elérése

Cél: minden műveletvégző egyszerre végezzen a feladatával.

A szemcsézettség és a terheléselosztás kapcsolódik egymáshoz, ugyanis finoman szemcsézett részfeladatok között kisebbek a különbségek, durva szemcsézettség esetén nagyobbak, ez utóbbi pedig kevésbé hatékony terheléselosztást eredményezhet. Finom szemcsézettség esetén pedig az overhead mértéke lesz jelentős, ugyanakkor hatékonyabb terheléselosztás valósítható meg.