9. tétel - Parallel sum & prefix scan

Mutassa be a párhuzamos összegzés módszereit! Mely esetekben használható a redukció? Hogyan párhuzamosítható a részösszegek számítása? Ismertesse a prefix scan algoritmusát!

Redukció

1. Képzeljünk el egy feje tetejére állított bináris fát
2. Pontosan annyi levéleleme van, mint ahány összegzendő elemünk
3. Ha a közbülső elemek értékét a gyermekelemeik összegében határozzuk meg, akkor a gyökérelembe kerül az összeg
4. Így az összegzés \(logN\) darab konkurens lépésben megoldható, míg szekvenciálisan \(O(n)\) komplexitású lett volna
5. Szinkronizációs pontok szükségesek: az előző szint részeredményeit be kell várni, hogy a következő szint megoldását megkezdjük
6. A részeredményeket tárolhatjuk külön, vagy felülírhatjuk a tömb elemeit, ha ez nem gond
7. Ha a tömb elemszáma (n) páratlan, akkor a szélső eseteket külön kell vizsgálni

Lépések

Megvalósítás

Megvalósítás vizualizálása

Adatdekompozíciós módszer

1. A redukció akkor hatékony, ha szintenként az egyes konkurens műveletekhez dedikált műveletvégző párosul
   • ehhez 8 elemnél 4 műveletvégző kell, ami jelentős ilyen kevés elemre
   • ezt oldja meg az adatdekompozíció módszere
2. Durvább szemcsézettségű megoldás, mint a redukció
3. Nagyobb blokkokat határozunk meg
4. A résztömböket dolgozzuk fel párhuzamosan
5. A szálak számának meghatározása történhet az elérhető műveletvégzők száma alapján

Megvalósítás

t: a szálak száma
i: a szál azonosítószáma
feltételezzük, hogy a tömb mérete osztható a szálak számával

• sum tömb t elemből áll, melyek kezdeti értéke 0
• Minden szálnak van egy dedikált eleme a sum tömbben, ebbe összegzi a saját résztömbjét
• Miután minden szál végzett, a sum tömb elemeinek összege adja az összes elem összegét.

Prefix Scan

• Részösszegek számítására szolgáló módszer
• Bemenete: n elemű tömb
• Kimenete: n elemű tömb, ahol a tömb i. elemében az elemek összege van, az első elemtől az i.-ig
  • inkluzív prefix scan: az összegbe beleszámoljuk az i. elemet is
  • exkluzív prefix scan: az i. elem nem számít bele
• A prefix scan szekvenciálisan is implementálható, de ekkor a komplexitása O(n).

Párhuzamos megvalósítás

Ha részletes magyarázatra van szükséged az algoritmus lépéseiről, itt találod a jegyzetben.

Adatdekompozíción alapuló megvalósítás

• A párhuzamos prefix scan is sok műveletvégzőt igényel, így itt is érdemes lehet adatdekompozícióval próbálkozni

1. Az eredeti tömb geometriai dekompozíciója, a műveletvégzők számához igazodó darabszámú résztömb létrehozása
2. A szétdarabolt tömb elemein helyi inkluzív prefix scan futtatása
3. Miután a helyi műveletek véget értek, a prefix scan által előállt eredménytömbök utolsó elemeit (résztömbök összegeit) külön munkatömbbe gyűjtjük
4. Ezen elemek exkluzív prefix scanjét kiszámoljuk
5. A második lépésben előállt résztömbök elemeit a negyedik pontban kiszámolt tömbben tárolt értékekkel megnöveljük
6. Ezáltal előáll az eredeti tömb inkluzív prefix scanje.