36 - Model PRAM, suma prefixů a její aplikace.
pondělí 21. května 2018
17:14
PRAM
Parallel Random Access Machine
Synchronní model paralelního výpočtu, procesory komunikují sdílenou pamětí
Skládá se z procesoru a paměti (neomezená)
Je to alternativní model k paralelnímu Turingovu stroji
Skládá se z p procesorů
Procesory musí umět
Aditivní (logické) operace 
[Multiplikativní operace]
Podmíněné skoky na základě porovnání
Architektury:
EREW - exclusive read, exclusive write 
ERCW - exclusive read, concurrent write - nemá opodstatnění, nepoužívá se
CREW - concurrent read, exclusive write 
CRCW - concurrent read, concurrent write - splňují pouze některé architektury, technicky obtížněji realizovatelný. Zde je potřeba specifikovat řešení zápisových konfliktů:
COMMON - všechny zapisované hodnoty musí být shodné 
ARBITRARY - zapisované hodnoty mohou být různé, zapíše se libovolná z nich 
PRIORITY - procesory mají pevné priority, zapíše se hodnota, zapisovaná procesorem s nejvyšší prioritou
Broadcast
hodnota uložená v paměti má být rozšířena mezi N procesory
pro CREW a CRCW řešení v konstantním čase
pro EREW je třeba simulovat současné čtení (P1 přečte D a zpřístupní jej P2, P1 a P2 jej zpřístupní P3 a P4...)
Suma prefixů
Suma prefixů je operace, jejímž vstupem je binární asociativní operátor ⊕ a uspořádaná posloupnost prvků [a0, a1, ..., an-1] a která vrací posloupnost [a0, (a0 ⊕ a1), ..., (a0 ⊕ a1 ⊕ ... ⊕ an-1)] 
Např. jestliže je operátor ⊕ sčítání a vstupní posloupnost [3 1 7 0 4 1 6 3] pak výsledek sumy prefixů je [3 4 11 11 15 16 22 25].
Časová složitost sekvenčího rešení O(n)
Varianty: scan, prescan, reduce
Reduce
Reduce může být spočtena pomocí stromu procesorů, za předpokladu, že ⊕ je asociativní (nemusí být komutativní)
Složitost:
Časová: O(log n)
Procesory: n/2
strom má výšku log n, pro každý pár prvků je nutný 1 procesor
Cena: c(n) = O(n.log n) → což není optimální
+-reduce 
pro n > p
Máme N procesorů. Rozdělíme vstup na N částí a každý proces spočítá reduce svojí části. Potom se vezmou výsledky s spočítá se reduce výsledků. 
Složitost:
Časová: t(n) = O(n/N) 
Procesory: N
Cena: c(n) = O(n/N).N = O(n) → což je optimální
Prescan
UpSweep algoritmus totožný s reduce, ale každý uzel si pamatuje mezisoučet
DownSweep 
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 P synovi svoji hodnotu ⊕ hodnotu L-syna a L-synovi dá svoji hodnotu
+-prescan 
Složitost:
Časová: t(n) = O(n/N) 
Procesory: N
Cena: c(n) = O(n), za předpokladu, že log N < n/N → což je optimální
Scan
Scan se získá z prescan posunem doleva, přidáním reduce
Aplikace sume prefixů
Packing problem
Máme k vstupních položek, rozmístěných v poli o n pozicích, k<n
Algoritmus:
Spočteme pole binárních příznaků, 1-položka existuje, 0-neexistuje 
Spočteme +-scan tohoto pole 
Přesuneme položky na správné pozice
Carry Look Ahead Parallel Binary Adder
Spočteme *-scan pole D a tím dostaneme všechny bity přenosu v logaritmickém čase
Potřebujeme n-1 procesorů
Radix sort
Bitový radix sort (radix = 2) – v každém kroku se bere v úvahu 1 bit klíče a pomocí operace split se prvky s nulovým bitem přemístí na začátek řazeného pole řazených čísel a s jedničkovým bitem na konec
Jak udělat split ? - sekvenční složitost je O(n)
Idea – pro každý prvek určíme správnou pozici a v konstantním čase přemístíme (EREW)
Postup  - 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
Split má stejnou složitost jako scan
Radix Sort: t(n) = O(n/N + log N).O(log n) = [file] n + log n . log N) 
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) a pro každou skupinu se rekurzivně volá quicksort
Použije se segmentovaný scan a každá skupina bude ve svém vlastním segmentu
Algoritmus
– (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ů: u a ‹ copy(a, b)
    » To má za následek rozšíření pivota v celém segmentu (lze také pivota vybírat jinak)
– (3) v každém segmentu porovnej prvky s pivotem a rozděl segment na 3 části (=, <, >). Po 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, takže složitost je:
t(n) = O(n/N + log N).O(log n) = [file] n + log N. log n)
c(n) = O(n.log N + N. log n. log N) -› pro dostatečně malé N optimální        
Notes*
Kdo me primarne zkousel: Fučík
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Fučík chtěl, abych to vzal stručně. Takže jsem řekl, co je to PRAM, jaké máme módy přístupu do paměti (EREW, ERCW, CREW, CRCW, přičemž se extra ptal na ERCW, že nemá smysl), jak se řeší konflikty včetně priorit (COMMON <= ARBIRTARY <= PRIORITY). Pak jsem přešel na sumu prefixů. Řekl jsem, že je to základní kámen paralelních algoritmů, vstupy a výstupy, přičemž výstup se mi blbě popisoval ústně, tak mi řekl, ať mu ukážu příklad. Na posloupnosti (1, 2, 3, 4, 5) a operaci + to bylo dost v pohodě. To mu stačilo. A
From <[link]> 
Kdo me primarne zkousel: Doc. Dr. Ing. Otto Fučík
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Během minuty na přípravu jsem na tabuli namaloval schéma, na kterém jsem vyznačil SCAN, PRESCAN, REDUCE.
Pak mě zkoušející řekl, abych začal modelem PRAM. Stačil obecný popis, tak jak se učí v PRL.
K popisu jsem pak dodal způsoby řešení zápisových konfliktů (ARBITRARY, PRIORITY, COMMON).
To k PRAM stačilo.
Pak se mě zkoušjící psal na způsob výpočtu sumy prefixů - popsal jsem binární strom a operace DOWNSWEEP a UPSWEEP a to bylo vše. A
From <[link]> 
Kdo me primarne zkousel: Zbořil (jen a pouze on)
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Začal jsem, co je to PRAM (procesor s vlastní pamětí, registry) to se mu trochu nelíbilo a opravil mě, že to není tak úplně procesor, ale spíš model. Tak jsem řekl, že je to synchronní paralelní výpočetní model, popsal slovy, jak je to propojené: že má každý procesor vlastní paměť, procesory komunikují sdílenou pamětí, jsou všechny řízeny jedním vyšším procesorem, to bylo OK. Pak se zeptal něco ve smyslu, jestli má každý PRAM vlastní program nebo něco v tom smyslu, s odpovědí byl spokojený, ale už nevím, co jsem řekl. Pak chtěl hlavně tu sumu prefixů, tak jsem popsal, že do ní vstupuje asociativní operátor a vektor uspořádaných hodnot, to se doptal, co znamená, že je to uspořádaný. Potom jsem popsal, co je výstupem (A0, A0+A1, ... A0+A1+...+An-1). Pak jsme se trochu nepochopili, co vlastně chce slyšet. Začal mluvit o neutrálním prvku, který jsem nezmínil. Potom teda, jak se to provede. Ústně jsem se snažil popsat strom, potom teda, ať to namaluju. Při stromu chtěl slyšet slovo "reduce", které mě nenapadlo v tu chvíli. Pak jsem řekl UpSweep, DownSweep. Zajímala ho časová složitost - řekl jsem nahoru je log, dolů je log, úplně by mu stačilo jenom "logaritmická". Ještě chtěl nějaký příklad využití, to jsem si vzpomněl jenom na tu viditelnost, tak se trochu pousmál, že jsem si vybral zrovna tu těžší věc, že ještě Packing problém, to jsem mu odkývl a OK. Pak už myslím zvonil budík a Sekanina, ať jdu na druhou otázku. Tohle za B (čekal jsem trochu horší)
From <[link]> 
Kdo me primarne zkousel:Zbořil František, doc. Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Začal jsem významem zkratky PRAM, že to má pamět a procesory, načež jsem se zamotal do toho, jestli to má lokální nebo sdílenou paměť a jak mezi sebou komunikují (věděl jsem možnosti, ale ne konkrétně v PRAM). Potom, že přejdeme k sumě prefixů, kde jsem se snažil popsat, co to dělá. Následně chtěl říct, jak to teda probíhá paralelně (jak jsou uspořádány procesory) a tam jsem tápal. Navedl mě na UpSweep, kde mi to docvaklo, a at to ukážu na příkladě se součtem. Nakreslil jsem součet do stromu a po zazvonění budíku jen slovně potom popsal DownSweep (nepřesně). Známka - E.
From <[link]> 
Kdo me primarne zkousel: Drahansky
Rekl jsem, ze je to synchronni model paralelniho vypoctu a pak jsem chtel skoncit na EREW atd. tak me zastavil, ze to je moc hopem. Chtel vedet co znamena zkratka PRAM, jak jsou procesory spojeny a jak komunikuji. Pak me nechal teda zapsat ty metody cteni a zapisu vcetne konfliktu (Common, Arbitrary a Priority). Nakonec chtel prejit na sumu prefixu ale tam jsem mu stihl rict jen reduce a zazvnonil budik.
From <[link]> 
Kdo me primarne zkousel: Bidlo
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: PRAM nechtel vubec, na listku bylo primo "Suma prefixu v paralelnich systemech a jeji pouziti". Popsal jsem reduce, scan a prescan. On at mu to ukazu na jednouchem prikladu a ze se mam zamerit na to, jak je to v paralelnich systemech. Tak jsem to ilustroval situaci ve sdilene pameti - tedy nejprve reduce (up-sweep), pak clean a down-sweep - ze to je vlastne reduce plus prescan a odstraneni 0 ze zacatku. Pak se me zeptal na slozitost toho alg., tak jsem rekl, ze je to stromove, takze log n. Chtel vedet za jakych podminek - tedy za jakeho poctu cpu. Tady jsem poprve znejistel, pac jsem to nevedel. Ale navedl me na to, takze v poho: p(n) = n/2. To uz pipal budik. Tak jeste at mu rychle reknu nejakou aplikaci - vytasil jsem se s packing problemem, ktery jsem strucne popsal. Byl moc fajn, hodnoceni A.
From <[link]> 
Kdo me primarne zkousel: Jen Kořenek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Opet rychlovka, mluvil jsem jen o PRAM. Ze to je paralelni výpočetní model, se sdílenou pamětí. Společné řízení. Přístupy do paměti (EREW ...apd) u CRCR jeste popsat common,arbitrary,priority. Chtel abych rekl ze ten Exclusice Read se týka čtení z jednoho místa z paměti. trosku jsem motal. Ale zvonek uz dávno zvonil, takze dal jsme se nedostali. Pohodicka.
From <[link]> 
Kdo me primarne zkousel: Kořenek 
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: Chtěl podrobně PRAM a věci kolem sdílené paměti, tam jsme strávili nejvíce času. Potom chtěl definici sumy prefixů a napsat jak teda to výsledné pole vypadá. Chvíli jsme si tam nerozuměli, ale bylo to dobré.
From <[link]> 
Kdo me primarne zkousel: Fučík
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Začal jsem obecně, co to je, k čemu to slouží, potom režimy EREW, CREW, ERCW, CRCW a paměťový konflikty. Ptal se i na vyjadřovací sílu, co má vyšší, jestli Common nebo Priority a jaká je mezi tím relace. To jsem mu řekl. Pak se doptal Zbořil ml. ještě na to, jestli jde provést AND paralelně v konst. čase. Nějak jsem to zahrál do outu, a nakonec řek, že co zapíšou procesory nakonec, který nemaj jedničku, tak jsem řekl NULU. 
From <[link]> 
Kdo me primarne zkousel: Korenek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli: zacal som s PRAM modelom, ale moc som o nom nevedel tak som sa snazil prejst na sumu prefixov. Nejake vseobecne veco o PRAM chcel: co to je, ako to funguje, ze ma zdielanu pamat. Potom sa pyatl na rezimy pristupu do pamate (EREW, CREW ...), tak to som mu povedal. Potom som poisal sumu prefixov a ako sa pocita
From <[link]> 
Kdo me primarne zkousel: Fučík
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Fučík mě nechal nejdřív mluvit o PRAM, pak se mě na něj ptal celkem dopodrobna, ale jen věci co jsou ve slidech. Chtěl tam po mě potom i nějaký ten teorém. Vím, že tam je ale neuměl jsem ho. Naštěstí řekl mladý Zbořil, že to nemusíme umět, což mě zachránilo.
From <[link]> 
Kdo me primarne zkousel: Fucik
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Chcel len model PRAM a vsetko co sme sa o tom ucili. Nechal ma hovorit sameho, ked som ostal nachvilu ticho a rozmyslal som ze zoberem fixku a idem na sumu prefixov tak sa ma pytal to co som este nepovedal a nakoniec sme sa k tej sume nedostali lebo povedal ze mu to staci. B
From <[link]> 