46 - Model PRAM, suma prefixů a její aplikace

Question 1

Co je to PRAM

Answer 1

• synchronní model paralelního výpočtu
• procesory se sdílenou pamětí a společným programem (procesory komunikují pomocí sdílené paměti)
• Alternativní model k paralelnímu Turingovu stroji
• Všechny procesory řízené společným programem

Procesor

• Aditivní a logické operace
• (Multiplikativní operace)
• Podmíněné skoky
• Přístup ke svému unikátnímu číslu (index)

Paměť

• Náhodný přístup pro všechny procesory
• Reprezentovaná neomezeným počtem registrů
• Neomezená délka slova (dnes není vyžadováno)
• Módy přístupu EREW, CREW a CRCW

Výpočet -> probíhá synchronně po krocích (krok: čtení, lokální operace, zápis)
Teorém - Každý problém, řešitelný PRAMem s p procesory v t krocích je také řešitelný p’≤p procesory v O(t p/p’) krocích

Question 2

Architektury přístupu k paměti a řešení zápisových konfliktů

Answer 2

4 možnosti

• EREW - Exclusive Read, Exclusive Write (velmi omezující)
• CREW - Concurrent Read, Exclusive Write (časté, jednoduché)
• ERCW - Exclusive Read, Concurrent Write (nedává smysl)
• CRCW - Concurrent Read, Concurrent Write (složité)

Řešení zápisových konfliktů u CRCW

• COMMON - všechny hodnoty musejí být stejné, jinak se nezapíše
• ARBITRARY - zapíše se libovolná z hodnot
• PRIORITY - procesory mají přidělenu prioritu, zapíše se hodnota, zapisovaná procesorem s nejvyšší prioritou

relace A ≥ B znamená, co běží na B, bude běžet i na A (A je tolerantnější/stejně tolerantní než B)
priority ≥ arbitrary ≥ common ≥ CREW PRAM ≥ EREW PRAM

Question 3

Broadcast

Answer 3

• Algoritmus pro distribuci hodnoty uložené v paměti do všech procesorů
• pro CREW a CRCW triviální v konst. čase t(n) = O(c)
• pro EREW je třeba simulovat současné čtení - šíření je logaritmické - jeden procesor přečte, předá dalšímu, pak jsou dva, každý jednomu, atd. t(n) = O(log(n))
• • v prvním kroku P1 přečte 𝑥 a zpřístupní jej P2 , v druhém kroku P1 a P2
    zpřístupní hodnotu P3 a P4 , a tak to pokračuje, dokud neznají hodnotu všechny
    procesory.

sekvenčně t(n) = O(n)
EREW t(n) = O(log(n))
CREW, CRCW t(n) = O(c)

Pseudokód
Algoritmus
D - hodnota, která se má rozšířit mezi N procesory
A[1..N] - pole ve sdílené paměti o délce N
procedure BROADCAST(D, N, A)
(1) A[1] = D;
(2) for i = 0 to (log N-1) do
for j = 2i + 1 to 2i + 2 − 1 do in parallel
A[j] = A[j-2i]
endfor
endfor

Question 4

Suma prefixů a odvozené operace

Answer 4

Suma prefixů (někdy také all-prefix-sum nebo allsums či scan)
- je základním kamenem mnoha paralelních algoritmů

= je to operace, jejímž vstupem je:

• binární asociativní operátor ⊕
• uspořádaná posloupnost n prvků 𝑎0 , 𝑎1 , … , 𝑎𝑛 −1
• jejímž výstupem je vektor 𝑎0,𝑎0 ⊕𝑎1,…,𝑎0 ⊕𝑎1 ⊕…⊕𝑎𝑛−1

Příklad

Vstup: [3 1 7 0 4]
Operace: + (sčítání)
Výsledek: [3 4 11 11 15]

využívá se:

• Vyhodnocování polynomů
• Sčítání binárních čísel v hardware
• Lexikální porovnávání řetězců
• Implementace radix-sortu, quick-sortu
• Implementace některých stromových operací

Prescan - Operace prescan je variantou scanu, která pracuje s neutrálním prvkem I, její výsledek je pak posloupnost 𝐼,𝑎0,𝑎0 ⊕𝑎1,…,𝑎0 ⊕𝑎1 ⊕…⊕𝑎𝑛−2 .

Reduce - paralelní suma prefixů

• Operace reduce má stejný vstup jako scan, ale vrací jen poslední prvek posloupnosti, tedy 𝑎0 ⊕𝑎1 ⊕…⊕𝑎𝑛−1
• Reduce může být spočtena pomocí stromu procesorů, za předpokladu, že ⊕ je asociativní (nemusí být komutativní) - očividné

Segmentovaný scan (scan vždy od začátku segmentu)

• na vstupu má navíc posloupnost příznaků, které označují konce segmentů (kde je 1 tam začíná další segment)
• výstup je suma prefixů přes jednotlivé segmenty (tj. suma prefixů, která začíná od začátku v každém segmentu)

Porovnání
Scan - 𝑎0,𝑎0 ⊕𝑎1,…,𝑎0 ⊕𝑎1 ⊕…⊕𝑎𝑛−1 (všechny kromě neutrálního prvku)
Prescan - 𝐼,𝑎0,𝑎0 ⊕𝑎1,…,𝑎0 ⊕𝑎1 ⊕…⊕𝑎𝑛−2 (neutrální prvek + scan bez posledního prvku)
Reduce - 𝑎0 ⊕𝑎1 ⊕…⊕𝑎𝑛−1 (poslední prvek)

Question 5

Výpočet scan a variant

Answer 5

optimální cena c(n)opt = tseq(n)

Scan - SEKVENČNÍ (prostě vypočítáme v cyklu)
Scan - paralení - získáme z prescan tak, že výsledky posuneme doleva a zprava doplníme výsledkem Reduce

Reduce - paralelní (n < p) - máme dost procesorů - strom
- pomocí stromu procesorů, za předpokladu, že ⊕ je asociativní
t(n) = O(log n) (strom má výšku log n)
p(n) = n/2
c(n) = O(n.log n) (neoptimální)

Reduce - paralelní (n > p) - každý procesor spočítá svůj úsek, poté zase strom
- máme méně procesorů než prvků
- každý procesor má svůj úsek, který spočítá sekvenčně, výsledky se pak spojují stromem
t(n) = n/N + log N = O(n/N + log N)
c(n) = N
c(n) = O(n/N).N = O(n) (optimální)

Prescan - paralelní
t(n) = O(n/N)
p(n) = N
c(n) = O(n) (optimální za předpokladu, že log N < n/N)
Algoritmus:

1) UpSweep - první krok - totožné s paralelním reduce, ale každý procesor si pamatuje mezisoučet
2) DownSweep - druhý krok
- kořenu se přiřadí neutrální prvek I
- nyní se provádí log n kroků (každá úroveň jednou), počínaje kořenem, směrem k listům a v každém kroku procesory v té úrovni pracují paralelně:
- uzel dá svému
- -> 1) P synovi svoji hodnotu ⊕ hodnotu L-syna
- -> 2) L-synovi dá svoji hodnotu

Question 6

Použítí Scan a variant

Answer 6

• vyhodnocování polynomů
• rychlé sčítání v HW
• lexikální analýza a porovnávání
• řazení
• hledání regulárních výrazů
• odstranění označených prvků
• apod.

Packing problem
Problém: máme pole v němž jsou náhodně rozmístěny prvky, potřebujeme pole ve kterém budou prvky na jeho začátku v původním pořadí
Postup:
1) Vytvoříme pole příznaků (1 na pozicích, kde je ve vst. poli prvek) - 1 0 0 1 1 0 1 0 0 1
2) Provedeme +-scan na pole příznaků - 1 1 1 2 3 3 4 4 4 5
3) Každý prvek přesuneme na pozici, která je u něj v poli příznaků -> 1 2 3 4 5

Viditelnost
Problém: máme vektor výšek terénu podél sledovacího paprsku. Zjistit, které body terénu jsou viditelné
Řešení:
- Bod je viditelný, pokud žádný bod mezi pozorovatelem a jím nemá větší vertikální úhel.
1) vytvoří se vektor výšek bodů podél pozorovacího paprsku
2) vektor výšek se přepočítá na vektor úhlů
3) pomocí max_prescan se spočte vektor maximálních úhlů pro zjištění viditelnosti bodu stačí určit jeho úhel a porovnat s maximem.

Radix sort - prostě řadíme podle řádu čísla (bitů) postupně
Problém: Radix sort
- V každém kroku se pomocí operace split prvky s n-tým bitem 0 přemístí na začátek řazených čísel a s n-tým bitem 1 na konec
Postup:
- pro prvky spočítáme jejich pozice a pak v konstantním čase přemístíme
- pro prvky s nulovým bitem se jejich pozice získá provedením ⊕ - prescan na invertované pole bitů
- pro prvky s jedničkovým bitem provedu ⊕ scan na reverzované pole bitů (tj. od konce) a výsledek se odečte od n.
t(n) = O(n/N + log N).O(log n) = O(n/N.log n + log n . log N)

Quicksort
Problém: Quicksort
- Jeden z prvků se vybere jako pivot (medián, náhodně, první)
- prvky se rozdělí do 3 skupin (menší, rovné, větší než pivot)
- pro každou skupinu se rekurzivně volá quicksort
Postup:
- Použije se segmentovaný scan a každá skupina bude ve svém vlastním segmentu

1) zkontroluj, zda už prvky nejsou seřazené
- Každý procesor se podívá, zda předchozí procesor má menší, nebo stejnou hodnotu.
- S výsledky se provede and-reduce

2) v každém segmentu najdi pivot a předej jej ostatním procesorům v segmentu.
- Vybírá-li se jako pivot 1. prvek, lze použít segmented-copy-scan, kde binární operátor copy vrací 1. ze svých 2 parametrů: a ← copy(a, b)
(lze také pivota vybírat jinak)

3) v každém segmentu porovnej prvky s pivotem a rozděl segment na 3 části
Pro rozdělení se použije modifikovaný split z radix-sortu.

4) v rámci každého segmentu vlož dodatečné příznaky, které rozdělí segment na 3 segmenty.
Každý procesor se podívá na předchozí prvek a pozná, zda je na začátku segmentu.

5) jdi na krok 1)

Každá iterace má konstantní počet operací scan
Při vhodné volbě pivotů skončí algoritmus po O(log n) krocích,
t(n) = O(n/N + log N).O(log n) = O(n/N.log n + log N. log n)
c(n) = O(n.log N + N. log n. log N) (pro dostatečně malé N optimální)