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

1
Q

Co je to PRAM

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Broadcast

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Suma prefixů a odvozené operace

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Výpočet scan a variant

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Použítí Scan a variant

A
  • 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í)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly