[AA-part2] Parallel algorithms

Course: https://ucilnica.fri.uni-lj.si/course/view.php?id=89
Lecturer: prof. dr. Borut Robič
Language: Slovenian
Date: 2014-03-24

Course overview (part 2):

models of parallel computation: PRAM and versions CRCW, CREW, EREW
design and performance of parallel algorithms: simulation of models, Brent theorem
performance guarantees of CRCW, CREW, EREW simulation: O(log n)-time sorting
class NC: efficiently parallel solvable problems, robustness of NC, is P = NC?

Samo predavanja, ustni izpit (snov iz predavanj in seminarske), a ne bo pisnega izpita ali domačih nalog. Pogledali bomo osnovne pojme iz področja modelov računanja in algoritmov. Ustni izpit kadar zelite (lahko isti dan kot Kodek), gremo skozi snov, intuitivno kar vse to pomeni.

Homework: Skupinska seminarska naloga

Poglej za vsakega od modelov računanja (tudi bolj natančne) kaj je bistveno. Do konca naših predavanj.

prednosti
slabosti
razmišljanje o konkretnem problemu in kateri je primeren zanj
koliko me stane, ce preidemo iz enega v drugega
cel svet problemskih prostorov (kot pri zaporednih, npr. nedeterminističnost, aproksimacijski)
katere topologije so primerne za kateri problem, kako aktivnosti v modelu preslikati na dejansko arhitekturo, mapping algoritma na stroj, da ključne komunikacije ne gredo po najdaljših povezavah
pri prijavi teme se nekdo veliko s tem ukvarjal

Uvod v modele računanja

Model računanja je abstrakcija, običajno formalno zapisana, ki zavzema vse kaj je bistvenega za algoritem, porabljen čas ali drug vir.

Modeli:

PRAM
Turingov stroj
Lambda račun
RAM (opisuje Von-Neumannovo arhitekturo)
Rekurzivne funkcije
Postov stroj
Registrski stroj
DNK računanje

Turingov stroj

Turingov stroj uporabimo, da ugotovimo, kateri računski problemi so rešljivi in kateri ne. Za nerešljive probleme ne obstaja noben algoritem.

Kateri računski problemi so rešljivi? S tem se ukvarja teorija izračunljivosti (computability theory).

Ali imajo diofantske enačbe ali sistem enačb rešitev v celih številih? Izkaže se, da algoritem ne obstaja (1972), ki bi znal za katerokoli diofantsko enačbo izpisati ali je rešljiva. Teorija izračunljivosti nam pomaga, da se ne lotevamo nerešljivih problemov.

Kakšen čas/prostor je potreben za rešitev rešljivega računskega problema? S tem se ukvarja teorija računske zahtevnosti.

Na primeru urejanja števil lahko ob ustrezni analizi algoritmov odkrijemo, da ni rešljivo hitreje kot v \(O(n \log n)\) časa.

Turingov stroj je model zaporednega računanja.

Model PRAM

Kaj pa vzporedno (paralelno) računanje? Pri takem računanju sodeluje več procesorjev, ki so sposobnih hkrati reševati en problem in pri tem sodelujejo.

Glavna težava pri modeliranju takega računanja je bila kako čim bolj verno modelirati čas, ki se porablja za komunikacijo med procesorji. Posledično je nastalo več predlogov za model vzporednega računanja.

Eden prvih modelov je bil PRAM (parallel random access machine):

čas potreben za komunikacijo zanemarjamo
rezultati bodo zato optimistični, torej predstavljajo spodnjo mejo za časovno zahtevnost vzp. rač.

[skupni  pomnilnik]    -- potencialno neskončen
 ^     ^         ^
 |     |         |
 v     v         v
[P1]  [P2]  ... [Pn]   -- končno število procesorjev

PRAM (parallel random access machine) ima množico procesorjev \(P_1, P_2, ..., P_n\), ki so povezani s skupnim pomnilnikom sestavljenim iz celic. Pri modeliranju detajle za katere ocenimo, da niso pomembni, ignoriramo.

Model skupnega pomnilnika (značilnosti/idealizacije):

potencialno neskončen (lahko ga povečaš za koliko želiš, a vsakič končen)
sestavljen iz pomnilniških celic
velikosti celic so enake (npr. vse 32- ali 64-bitne), toda potencialno neskončne
vsaka celica je dostopna vsakemu procesorju \(P_i\)
dostopni čas enak za vsako celico in vsak procesor \(P_i\) (=en korak/enota časa)

Model procesorjev:

potencialno neskončno (npr. \(n, n^2, \sqrt{n}\) procesorjev)
vsi procesorji \(P_i\) izvajajo isti algoritem/program (čeprav bo kdaj kateri delal tudi kaj drugega)
vsi lahko dostopajo do vseh pomnilniških celic v enoti časa

Sočasno dostopanje

Kaj se zgodi, če procesorji sočasno želijo dostopati do iste celice? Odvisno od operacije, ki jo želijo izvesti na celici (branje ali vpis).

sočasno branje: načeloma ni težav v modelu (vsebino celice dobijo vsi v naslednjem koraku)
sočasen vpis: če vsaj dva želita vpisati različno vsebino, ni jasno čigava vsebina bo obveljala (problem!)

Glede na to ločimo več različic PRAMa:

EREW PRAM (exclusive-read, exclusive-write):

v vsakem koraku: iz iste celice lahko bere kvečjemu 1
v vsakem koraku: v isto celico lahko vpiše kvečjemu 1
da je to izpolnjeno mora zagotoviti razvijalec algoritma/programa
model je najbližje realnosti (še najmanj dela za realizacijo)

CREW PRAM (concurrent-read, exclusive-write):

v vsakem koraku: iz iste celice lahko bere več kot 1 procesor
v vsakem koraku: v isto celico lahko vpiše kvečjemu 1 procesor
za to mora zagotoviti razvijalec

CRCW PRAM (concurrent-read, concurrent-write):

v vsakem koraku: iz iste celice lahko bere več kot 1 procesor
v vsakem koraku: v isto celico lahko vpiše več kot 1 procesor (o tem kaj se bo zgodilo se je potrebno dogovoriti)

Kateri procesor bo zmagal pri sočasnem vpisu pri CRCW PRAM? To določa t.i. način sočasnega vpisa (mode) pri CRCW:

skladni vpis (consistent mode):
- vsi procesorji morajo vpisati enak podatek v isto celico
- za to mora poskrbeti razvijalec algoritma
poljuben vpis (arbitrary mode):
- zmagovalec je naključen (za nas)
- to bo moral upoštevati razvijalec (nedeterministično obnašanje)
prednostni vpis (priority mode):
- zmaga procesor z najvišjo prioriteto (npr. z najnižjim indeksom)
- to bo moral upoštevati razvijalec
združeni vpis (fusion mode):
- nad podatki se izvede operacija, njen rezultat pa se vpiše v celico
- operacija (z dvema operandoma) mora biti komutativna in asociativna
- npr. disjunkcija, konjunkcija, max, min, množenje, seštevanje (odštevanje ni komutativno)

Vzporedni algoritmi

Date: 2014-03-31

Tekom predavanj želimo pokazati, da je vseeno katerega od modelov izberemo, saj lahko le-ti drug drugega simulirajo. Cena za simulacijo je logaritemska. Pri vzporednem računanju nas zanimajo poli-logaritmični algoritmi \(\log^p(n)\), ne polinomski \(n^k\).

Tehnika: Preusmerjanje kazalcev (pointer jumping)

Preusmerjanje kazalcev je tehnika/metoda za razvoj vzporednih algoritmov. Posplošitev metode “deli in vladaj” iz razvoja zaporednih algoritmov.

Primer: Rangiranje seznamov (list ranking)

Def. (rangiranje seznama): Dan je seznam L z vozlišči (linked list o->o->o->...->o, vsak vsebuje vrednost \(d[i]\) in kazalec \(next[i]\)). Ne vemo koliko je vozlišč in premikamo se lahko le na naslednjika. Za vsako vozlišče seznama L izračunaj rang (=razdalja tega vozlišča do konca seznama). Razdalja zadnjega do konca je \(0\). Npr.: L->[3]->[2]->[1]->[0]

Zaporedni alg.:

ideja: začnemo na začetku seznama, se sprehodimo do konca in nazajgrede štejemo rang
potrebna dva sprehoda od začetka do konca seznama
\(2n\) obiskov vozlišč => asimptotična časovna zahtevnost \(\Theta(n)\)

Ali obstaja vzporedni alg. za PRAM, ki ima (asimptotično) časovno zahtevnost manjšo od \(\Theta(n)\) (npr. \(\Theta(\sqrt(n)))\), \(\Theta(\log^p(n)))\))? Da. Obstaja EREW PRAM z \(n\) procesorji in ima časovno zahtevnost \(O(log(n))\).

Vzporedni alg.:

seznam je končen in sistem dovolj velik
vsakemu vozlišču priredimo lastno PE
ideja: v vsakem koraku alg. se naj seznam razdeli na 2 podseznama, pri tem upoštevamo učinek trganja na vrednosti \(d\) (trganje je preusmerjanje kazalcev)
najprej vsako vozlišče dobi vrednost 1, zadnje 0
lastnost vozlišč:

\[ d[i] = \begin{cases} 0 & \text{if } next[i] = nil \\ 1 + d[next[i]] & \text{else} \end{cases} \]

RankComputation(L):
  forall i inparallel do
    if next[i] = nil then d[i] <- 0 else d[i] <- 1
  while obstaja voišče i: next[i] != nil do
    forall i inparallel do
      if next[i] != nil then
        d[i] <- d[i] + d[next[i]]
        next[i] <- next[next[i]]

Opombe:

forall i inparallel do stavek izvedejo paralelno hkrati vsi tisti procesorji katerih vozlišča so omenjena
prevajalnik mora poskrbeti, da se branja izvedejo pred vpisi
- iz: forall i inparallel do A[i] <- B[i]
- v: forall i inparallel do temp[i] <- B[i]; forall i inparallel do A[i] <- temp[i]
- problem nastane pri: forall i inparallel do A[i] <- A[i-1]
- za to poskrbi prevajalnik
pogoj while obstaja voišče i se da preveriti na:
- CRCW PRAM z združenim vpisom v konstantnem času \(O(1)\)
- EREW PRAM pa je potreben čas \(O(log(n))\)

Primer: Računanje predpon (prefix computation)

Tudi tu se uporablja preusmerjanje kazalcev.

Def. (računanje predpon): Dano je zaporedje \(x_1,...x_n\) in binarna asociativna operacija \(\otimes\). Izračunati je potrebno vrednosti \(y_1,...y_n\), kjer je \(y_1 = x_1\), \(y_{i} = y_{i-1} \otimes x_i\) za \(i >= 2\).

Npr.: \(y_1 = x_1\), \(y_2 = x_1 \otimes x_2\), \(y_3 = x_1 \otimes x_2 \otimes x_3, ...\)

Zaporedni alg.:

zahteva \(O(n)\) časa

Se da na vzp. način hitreje? Da. V času \(O(log(n))\) celo na EREW PRAM z \(n\) PE.

Vzporedni alg.:

vhodne podatke \(x_1,...x_n\) shranimo v seznamu L (linked list)
metoda: preusmerjanje kazalcev

PrefixComputation(L):
  forall i inparallel do
    y[i] <- x[i]
  while obstaja vozlišče i: next[i] != nil do
    forall i inparallel do
      if next[i] != nil then
        y[next[i]] <- y[i] * y[next[i]]
        next[i] <- next[next[i]]

Opomba:

pogoj while obstaja voišče i se da preveriti na:
- CRCW PRAM v \(O(1)\)
- EREW PRAM (z \(n\) PE) pa v \(O(log(n))\)

Problem uporabe računanja predpon: Dano je dvojiško drevo z \(n\) vozlišči (koren na globini \(0\)). Izračunaj globino vsakega vozlišča tega drevesa.

Z zaporednim alg. v \(O(n)\) kateri od obhodov drevesa (depth-first, breadth-first).
Z vzporednim alg. na EREW PRAM (z \(n\) PE) se da problem rešiti v času \(O(log(n))\), tudi za izrojena drevesa. Se prevede na problem računanja rangov.

Ocenjevanje zmogljivosti vzporednih algoritmov

Date: 2014-04-07

Zanimala nas bo cena, delo, pohitritev in učinkovitost vzporednih algoritmov.

Naj bo dan problem \(P\) in njegov primerek velikosti \(n\) (npr. uredi \(n\) števil).

Def.: \(T_{seq}(n)\) označuje časovno zahtevnost najboljšega zaporednega algoritma za reševanje problema \(P\).

Naj bo dan vzporedni algoritem \(A\) za reševanje problema \(P\).

Def.: \(T_{par}(p, n)\) označuje časovno zahtevnost izvajanja algoritma \(A\) za reševanje problema \(P\) na \(p\) procesorjih v PRAM modelu.

Def.: Cena (ang. cost) vzporednega algoritma \(A\) je \(C_p(n) = p \cdot T_{par}(p, n)\). Celoten porabljan čas, tako za računanje kot čakanje.

Def.: Delo (ang. work) vzporednega algoritma \(A\) je \(W_p(n)\). To je število vseh operacij, ki so jih dejansko opravile vse procesne enote pri izvajanju algoritma \(A\).

\[ W_p(n) \leq C_p(n) \]

Cena bo minimalna, kadar vsi procesorji končajo hkrati (in vsi delajo hkrati).

Def.: Pohitritev (ang. speedup) vzporednega algoritma \(A\) je \(S_p(n) = \frac{T_{seq}(n)}{T_{par}(p, n)}\).

Def.: Učinkovitost (ang. efficiency) vzporednega algoritma \(A\) je \(E_p(n) = \frac{S_p(n)}{p}\) (koliko pohitritve nam je v povprečju prinesel posamezen procesor). Če vstavimo formulo za pohitritev, dobimo: \(E_p(n) = \frac{T_{seq}(n)}{C_p(n)}\).

Velja: \(S_p(n) \leq p\) (algoritem bo tekel največ \(p\)-krat hitreje), \(E_p(n) \leq 1\) (učinkovitost bo največ \(1\)).

Izrek o enostavni simulaciji

Govori o izvajanju algoritma na manjšem vzporednem računalniku: Delovanje PRAMa lahko simuliramo z manjšim PRAMom (vzporedni algoritem lahko izvedemo tudi na manjšem vzporednem računalniku). Pri tem dosežemo zmanjšanje zmogljivosti algoritma, a poslabšanje je navzgor omejeno.

Izrek: Naj bo \(A\) vzporedni algoritem, ki se izvaja na PRAMu s \(p\) procesorji \(t\) časa. Manjši PRAM enakega tipa, ki ima \(p' < p\) procesorjev, lahko izvede algoritem \(A\) v času \(O(\frac{t \cdot p}{p'})\). Cena algoritma \(A\) na manjšem PRAMu pa je kvečjemu dvakrat večja od cene na večjem PRAMu:

\[ C_{p'} \leq 2C_p \]

Dokaz: Vsak korak algoritma \(A\) lahko manjši PRAM izvede kvečjemu v \(\lceil\frac{p}{p'}\rceil\) časa.

Manjši PRAM izvede cel algoritem \(A\) v času \(t' = t \lceil\frac{p}{p'}\rceil = O(\frac{t \cdot p}{p'})\).

Cena: \(C_{p'} = p' \cdot t' = p' \cdot t \lceil\frac{p}{p'}\rceil \leq p' \cdot t \cdot (\frac{p}{p'} + 1) = tp + tp' \leq tp + tp = 2tp = 2C_p\) (manj procesorjev, večji čas).

Vprašanje: Kaj, če je \(p' = 1\)? To je še PRAM, toda z enim procesorjem, kar pa je že model RAM za zaporedno računanje. Iz izreka sledi (ker je \(p' = 1\)):

Algoritem \(A\) lahko simuliramo na zaporednem modelu v času \(O(tp)\).
Zaradi izreka je \(C_1 \leq 2C_p\) in po drugi strani je \(C_1 = 1 \cdot T_{par}(1, n) \geq T_{seq}(n)\), zato: \(\frac{1}{2}T_{seq}(n) \leq C_p(n)\).
Iz tega sledi: \(C_p(n) = \Omega(T_{seq}(n))\) (cena vzporednega algoritma je navzdol omejena z najboljšo časovno zahtevnostjo zaporednega algoritma).

Denimo, da je \(C_p(n) = \Theta(T_{seq}(n))\). Ker je \(C_p(n)\) po definiciji enaka \(p \cdot T_{par}(p,n)\), sledi da je: \(p \cdot T_{par}(p,n) = \Theta(T_{seq}(n))\). Torej je: \(T_{par}(p,n) = \Theta(\frac{T_{seq}(n)}{p})\). Algoritem \(A\) na \(p\) procesorjih bi bil \(p\)-krat hitrejši od najhitrejšega zaporednega algoritma. Očitno \(A\) izkorišča vseh \(p\) procesorjev ves čas reševanja problema in reši problem v najmanjšem možnem času.

Posledica (in definicija): Vzporedni algoritem je učinkovit, če zanj velja:

\[ C_p(n) = \Theta(T_{seq}(n)) \]

Koliko procesorjev rabimo?

\[ p = \Theta(\frac{T_{seq}(n)}{T_{par}(p, n)}) = \Theta(S_p(n)) \]

Velja tudi \(S_p(n) = \Theta(p)\) (če obrnemo). Pri učinkovitem vzporednem algoritmu je pohitritev približno \(p\)-kratna.

Diskusija

Intuicija: Več procesorjev reši problem v krajšem času.
Teorija: Če je vzporedni algoritem učinkovit, potem \(p\) procesorjev reši problem \(p\)-krat hitreje kot najboljši zaporedni algoritem.
Praksa: Izkaže se, da ko \(p\) preseže neko mejno vrednost (ta je odvisna od problema in algoritma), potem \(S_p(n)\) ni več linearna funkcija od \(p\). Lahko dodajamo procesorje, vendar pohitritev ne bo linearna, zato učinkovitost pada (vsak procesor prispeva k pospešku manj, kot bi lahko).

Kaj je vzrok za upad pohitritve? Običajno je vzrok komunikacija med procesorji.

Brentov izrek

Vzpostavlja povezavo med št. procesorjem in št. operacij, ki so bile izvedene.

Izrek: Naj bo \(A\) vzporedni algoritem, ki se izvaja na nekem PRAMu z neomejenim št. procesorjev \(t\) časa in pri tem izvede \(m\) operacij. Algoritem \(A\) se lahko izvede na PRAMu enakega tipa in na \(p\) procesorjih v času \(t'\):

\[ t' = O(\frac{m}{p} + t) \]

Dokaz: Recimo, da \(A\) na prvem PRAMu v \(i\)-tem koraku (\(i\) gre od 1 do \(t\)) izvede \(m(i)\) operacij. Torej vseh operacij je \(\sum_{i=1}^t m(i) = m\). Drugi PRAM \(i\)-ti korak algoritma \(A\) lahko izvede v daljšem času (ker ima na voljo omejeno število procesorjev)—v \(\lceil\frac{m(i)}{p}\rceil\) korakih. Vseh korakov na drugem PRAMu je zato:

\[ \sum_{i=1}^{t} \lceil\frac{m(i)}{p}\rceil \leq \sum_{i=1}^{t} ( \frac{m(i)}{p} + 1 ) = \frac{1}{p} \cdot \sum_{i=1}^{t} m(i) + \sum_{i=1}^{t} 1 = \frac{m}{p} + t \]

Uporaba: V problemu so dana števila \(x_1,\ldots,x_n\), izračunaj maksimum teh števil na EREW PRAM.

EREW PRAM bi računal max z drevesnim algoritmom:

x1     x2     x3     x4    x5     x6    x7    x8
  \   /         \   /        \   /       \   /
   [ ]           [ ]          [ ]         [ ]
    \...
...
4 procesorji na 1. nivoju
2 na 2. nivoju
1 na zadnjem nivoju

Če ima PRAM na voljo vsaj \(\frac{n}{2}\) procesorjev (tj. \(\Theta(n)\)), lahko izračuna maksimum v času \(\Theta(\log{n})\).

Vprašanja:

Kaj pa če bi bilo na voljo le npr. \(O(\sqrt{n})\) procesorjev, kako to vpliva na čas računanja?
Za največ koliko lahko zmanjšamo št. procesorjev (asimptotično), da se bo drevesni algoritem še vedno izvedel v času \(\Theta(\log{n})\)?

Uporabimo Brentov izrek:

Drevesni algoritem traja \(t = \log{n}\) korakov na neomejenem PRAMu.
Število vseh operacij, ki jih izvede, je \(m = n - 1\) (število notranjih vozlišč v drevesu).
Če je na voljo le \(p\) procesorjev, lahko izvedejo drevesni algoritem v času \(O(\frac{n-1}{p} + \log{n})\) (po Brentu).
Odgovor na 1. vprašanje: če bi bil \(p=\Theta(\sqrt{n})\), potem bi bil čas algoritma \(t = O(\frac{n-1}{k \cdot \sqrt{n}} + \log{n})\), kar je \(O(\sqrt{n} + \log{n})\) (\(k\) nesemo ven, delimo s \(\sqrt{n}\), zanemarimo \(\frac{1}{\sqrt{n}}\)), kar je \(O(\sqrt{n})\).
Odgovor na 2. vprašanje: če za \(p\) vzamemo \(p=\Theta(\frac{n-1}{\log{n}})\) procesorjev, potem bi drevesni algoritem tekel v času \(O(\frac{n-1}{\frac{n-1}{\log{n}}} + \log{n}) = O(\log{n})\).

Npr.: Če imamo 1024 števil (\(n=1024\)). Na običajen način bi rabili \(\frac{n}{2} = 512\) procesorjev. Lahko pa jih vzamemo 100 in bomo algoritem lahko izvedli v času, ki je primerljiv s prejšnjim.

Primerjava modelov PRAM

Date: 2014-04-14

Gre za izreke o razlikovanju modelov PRAM (ang. model separation theorems).

Vprašanje: Ali se CRCW, CREW in EREW PRAM modeli res razlikujejo po svoji “moči”? Če se, za koliko?

Motivacija: Lažje je sestaviti paralelni algoritem za CRCW kot pa za EREW. Ali je povečanje časa pri prehodu iz CRCW na EREW lahko poljubno veliko?

Kako to ugotovimo? Če se ti modeli res razlikujejo, po svoji “moči”, potem morata obstajati dva problema, \(P_1\) in \(P_2\), na katerih se pokaže razlika v njihovi “moči”.

\[ CRCW \supset CREW \supset EREW \]

Posamezna množica predstavlja probleme, ki jih je posamezen model sposoben rešiti v danem času (asimptotično gledano). CRCW je sposoben rešiti največ problemov v danem času, CREW malo manj, EREW pa najmanj. Domnevamo, da so ti razredi strogo vsebovani en v drugem.

Ta dva problema, ki ju iščemo, sta med EREW in CRCW. \(P_1\) je v CRCW, \(P_2\) pa v CREW.

\(P_1\) reši CRCW v nekem času \(T(n)\), v katerem ga CREW ne more
\(P_2\) reši CREW v nekem času \(T'(n)\), v katerem ga EREW ne more

Kako najdemo taka problema, če sploh obstajata?

Odnos CRCW-CREW (patološki problem \(P_1\))

Ali obstaja problem \(P_1\), ki ga z enakim št. procesorjev CRCW reši asimptotično hitreje kot katerikoli CREW?

Da. \(P_1\) je problem iskanje največjega števila med danimi \(n\) števili (\(\mbox{max} \{A[1], A[2], \ldots, A[n]\}\)).

Trditev: CRCW PRAM (z \(n^2\) PE) reši \(P_1\) v času \(O(1)\) (če damo zadosti procesorjev, reši to v konstantnem času).

Dokaz: Konstrukcija algoritma:

IzracunajMax(A, n):
  # m[i] bo true, dokler se ne najde število, ki je večje od A[i]
  forall i in {1,...,n} inparallel do:
    m[i] := true

  # za vse različne pare števil i,j:
  #   če najdemo nek A[j], ki je večji od A[i], potem A[i] ne more biti maksimalen element
  forall i,j in {1,...,n}, i!=j inparallel do:
    if A[i] < A[j]:
      m[i] := false

  forall i in {1,...,n} inparallel do:
    if m[i] == true:
      max := A[i]

  return max

Na CRCW (z \(n^2\) PE) algoritem zahteva konstanten čas (\(O(1)\)).

Kaj pa CREW? Ta ne dopušča sočasnega vpisovanja iz večih procesorjev. Tega CREW ne zmore v enem koraku, ker ne sme izpisovati več podatkov v isto lokacijo. CREW lahko to izvede v času, ki je kvečjemu \(O(\log{n})\) (z zapisovanjem z drevesi).

Pri prehodu iz CRCW na CREW pridobimo faktor \(\log{n}\).

Odnos CREW-EREW (patološki problem \(P_2\))

Ali obstaja problem \(P_2\), ki ga z enakim št. procesorjev CREW reši asimptotično hitreje kot katerikoli EREW?

Da. \(P_2\) je problem pripadnost množici (ang. membership problem): Ali je dani \(x\) element dane množice \(\{x_1, \ldots, x_n\}\)? Sprašujemo, ali je \(x\) v množici.

Trditev: CREW PRAM (z \(n\) PE) lahko reši \(P_2\) v času \(O(1)\).

Dokaz: Algoritem intuitivno dokažemo:

Vsakemu elementu \(x_i\) je dodeljen svoj PE (označimo ga s \(p_i\)). Dana je spremenljivka \(rez\), ki bo na koncu 1, če bomo za \(x\) ugotovili, da pripada množici, oz. 0 sicer. Na začetku (ob inicializaciji) nastavimo \(rez\) na 0. Vsak \(p_i\) istočasno prebere \(x\) (hkrati to lahko naredijo v CREW v času \(O(1)\)) in to primerja s svojim \(x_i\). Če je rezultat primerjanja pozitiven (\(x=x_i\)), potem PE vpiše v rezultat rez = true (kvečjemu eden bo vpisal true v rez—to je dobro, ker imamo CREW).

Kaj pa EREW? Ne, v konstantnem času tega ne zmore. Potrebuje vsaj \(\Omega(\log{n})\) korakov.

Težava: Kako naj si PE priskrbijo vsak svojo kopijo števila \(x\) v času \(O(1)\)?

Kaj pa če bi bilo \(n\) kopij že na voljo? Bi šlo, toda vstavljanje \(n\) kopij zahteva \(\lceil\log{n}\rceil\) korakov.

Izrek o simulaciji

Našli smo \(P_1\) in \(P_2\), ki ločita posamične modele PRAM za faktor vsaj \(\Omega(\log{n})\). Temu faktorju rečemo ločevalni faktor (ang. separation factor).

Če gremo iz CRCW na bolj realen model CREW, plačamo ceno vsaj \(\Omega(\log{n})\). Isto se zgodi pri prehodu iz CREW na EREW.

Vprašanje: Ali obstajajo \(P'_1 in P'_2\), ki povzročita (imata) še večji ločevalni faktor? Torej, ali se modeli CRCW, CREW, EREW razlikujejo za poljubno velik razločevalni faktor? Ne. Razločevalni faktor je navzgor omejen, kar je dobro. Zgornja meja je kvečjemu \(O(\log{n})\).

Modeli se med seboj razlikujejo natanko za \(\log{n}\).

Izrek: Vsak vzporedni algoritem potrebuje na modelu CRCW PRAM (s \(p\) procesorji) kvečjemu \(O(\log{p})\)-krat manj časa kot ga rabi na modelu EREW PRAM (s \(p\) procesorji).

Praktična posledica tega izreka je:

Sestavi algoritem za CRCW PRAM (ker je lažje).
Analiziraj ga in določi \(T_{par}\).
Ta algoritem bi tekel na EREW PRAM v času, ki je \(T_{par} \cdot O(\log{p})\).

Ponovitev

Date: 2014-05-05

Vprašanje: Koliko je en model močnejši od drugega?

Če tisto kar zmore rešiti najhitrejši med njimi (CRCW) v času \(t\), bo najpočasnejši (EREW) porabil \(log(p) \cdot t\) časa oz. odvisen od logaritma števila procesorjev v najslabšem primeru. To je dobro, saj nas zanimajo poli-logaritmični algoritmi in zaradi tega ostajamo v istem prostoru.

Tehnika: Vzporedno urejanje (urejanje na PRAM)

Zaporedni alg.:

uredi \(n\) števil
uporabljamo tudi operacijo primerjanja (se da tudi brez, npr. Bucket sort pri APS)
\(T_{seq}(n) = \Theta(n \log n)\) (npr. Heap sort)
\(\Theta(n \log n)\) je tudi spodnja meja za urejanje (dokaz pri APS)

Vzporedni alg.:

v kolikšnem času in s koliko PE se da urediti \(n\) števil na vzporeden način?

Naj bo \(S\) algoritem za vzp. urejanje na PRAM s \(p\) procesorji.

Vemo že \(C_p(n) = \Omega(T_{seq}(n))\) (cena alg. \(S\) je navzdol omejena s časom najhitrejšega zap. alg. za urejanje). Iz definicije sledi:

\[ p \cdot T_{par}(p,n) = \Omega(n \log n) \]

Vzemimo \(p = n\) in po deljenju z \(n\): \(T_{par}(n,n) = \Omega(\log n)\). Torej čas za vzp. urejanje \(n\) števil je vsaj \(\Theta(\log n)\). Ne vemo, če se da doseči, torej morda tudi asimptotično več.

Ali se da z \(n\) PE urediti \(n\) števil prav v času \(\Theta(\log n)\)? (Šteje le konstruktiven dokaz—t.j. konstrukcija takšnega algoritma.) Da. To je pokazal Richard Cole, 1986.

Primer: Cole-ov algoritem (skica)

Temelji na urejanju z zlivanjem (merge sort). Če je \(n\) števil bo potrebnih \(\log n\) vzp. zlivanj.

Primer: \(\{1, 2, ..., 8\}\)

Ker je vseh vzp. zlivanj \(\log n\), bo čas \(T_{par}(n,n) = \Theta(\log n)\) dosežen le, če bo vsako posamično vzp. zlivanje zahtevalo samo \(O(1)\) časa. Kako? Izkoriščamo informacije od prejšnjih zlivanj (ranks, compare-exchange operations in hypercube).

Izrek (R. Cole): Zaporedje \(n\) števil lahko uredimo na PRAM CREW z \(\Theta(n)\) PE v času \(T_{par}(n,n) = \Theta(\log n)\). (Na EREW PRAM pa \(O(\log^2 n)\).)

Vendarle je v končni fazi/praksi vseeno smiselno pogledati čas izvajanja oz. konstante.

Osnovni razred vzp. zahtevnosti (pomen modela PRAM)

Def.: Računski problem je v razredu NC, če je rešljiv na modelu PRAM z \(O(n^k)\) procesorjev v času \(O(\log^c n)\).

Opomba: NC se po domače imenuje Nick’s Class (po Nick Pippenger).

Zakaj takšen pogoj? Če je v zap. svetu “hiter” algoritem le tisti, ki je polinomski, je v vzp. svetu “hiter” algoritem le tisti, ki je polilogaritmičen.

Teoretično lahko konstruiramo vzp. algoritme, ki uporabljajo eksponentno mnogo procesorjev (včasih je tak algoritem zelo hiter). Toda taki vzp. algoritmi v praksi tečejo bolj počasi kot trdi teorija! Vir težav je 3-dimenzionalen prostor realnosti. Četudi bi zgradili vzp. računalnik z eksponentnim številom PE in te zgnetli na najmanjši možni prostor, se povezave in PEji ne morejo zgnesti na ta prostor ne da bi se vsaj ena povezava bistveno podaljšala.

NC = razred rač. problemov, ki so v praksi hitro rešljivi na vzporeden način.

Veliko vprašanje vzp. računanja: \(P \stackrel{?}{=} NC\) (ali nam realna vzporednost bistveno kaj prinese)?

Povzetek

PRAM je (videti) nerealističen model (ker ima neomejen skupni pomnilnik, takojšen dostop do vsake celice, zanemarja čas komunikacije) (danes že poznamo vrsto bolj realističnih)
kljub temu pa obstoj PRAM algoritma za dani problem:
1. pove nekaj o inherentnih lastnostih problema (npr. o njegovi dovzetnosti za paralelizacijo) (npr. polinomski GCD se upira paralelizaciji in je NC-poln)
2. lahko vodi do bolj praktičnega/realnega algoritma (za vzp. računalnik z dano arhitekturo, ki običajno namreč ni polni graf)
če nam ne uspe sestaviti za PRAM, ki je enostaven, je še manjša verjetnost da nam bo na kompleksnejšem modelu

Splošno mnenje: Le PRAM algoritmi, ki imajo optimalno ceno (tj. \(C_p(n) = \Theta(T_{seq}(n))\)) bodo v praksi morda relevantni. Med temi pa nas najbolj zanimajo tisti, ki imajo minimalen \(T_{par}\).