46 - Model PRAM, suma prefixů a její aplikace Flashcards
Co je to PRAM
- 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
Architektury přístupu k paměti a řešení zápisových konfliktů
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
Broadcast
- 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.
- v prvním kroku P1 přečte 𝑥 a zpřístupní jej P2 , v druhém kroku P1 a P2
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
Suma prefixů a odvozené operace
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)
Výpočet scan a variant
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
Použítí Scan a variant
- 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í)