9. Párhuzamos algoritmusok

NC (Nick Class): Olyan algortimusok vannak ebben az oszalyban, amelyek $n^{c_1}$ proceszorral $O((\log n{)}^{c_2})$ idoben futnak.

Tegyuk fel, hogy van egy NC algoritmusunk es ez az algoritmus az $i$-edik lepesben megszamoljuk, hogy hany proceszor dolgozik: $w_i$
Legyen $W:={\sum }_1^t{w}_i$ ahol $t$ a lepesek szama. Ezt a $W$ valtozot az osszmunkanak hivjuk.
Tehat ha $1$ proceszorunk lenne, akkor $W$ lepest kene tennie ahoz hogy szimulalja a parhuzamos algoritmust.

Tetel (Brent 1): Ha letezik olyan algoritmus, amely $t$ lepesben $W$ osszmunkaval szamol, akkor $\forall p\in \mathbb{N}$-re van egy olyan algoritmusunk, amely $p$ proceszorral szamol es $\frac{W}{p}+t$ lepest tesz.
biz.: vegyuk az $i$-edik lepest, $p$ proceszor $\lceil \frac{w_i}{p}\rceil$ lepesben
Igy osszesen ennyi lepesre lesz szuksegunk:

$$\sum _i^t\lceil \frac{w_i}{p}\rceil \le \sum \frac{w_i}{p}+t$$

Azt mondjuk, hogy egy feladat jol parhuzamosithato, ha ez teljesul.

https://dl.acm.org/doi/pdf/10.1145/321812.321815 4. Lemma 2.

Bit-muveletek parhuzamos algoritmusokkal

$a,b<2^n$
All.: $n$ proceszorral $O(\log n)$ lepesben ki lehet szamolni $a+b$ erteket.
biz.:
felfele:
a $j$-edik lepesben a $p_i$ proceszor akkor fog dolgozni, ha $2^j|i$
$p_i$ felelos az $\mathbf{i}i+1.,\dots ,i+2^j-1.$ szamjegyekert.
eredmeny:

• $0$: biztosan nem megy balra
• $1$: biztosan megy balra
• $\ast$: megy balra, ha jon jobbrol

Ekkor minden proceszor $O(1)$ idoben megcsinalja ezt

lefele:
Amikor jovunk lefele, akkor a $p_{16}$ tudja mar a helyes eredmenyt es mostmar csa ka a $8$ -al oszthatok dolgoznak, akkor a $p_{24}$ tudta mar hogy a tole kezdve $8$-nak mi az eredmenye, tegyuk fel hogy ez $\ast$ volt…

Szorzas: A szorzas gyakorlatilag annak felel meg, hogy $n$ darab $2n$ bites szamot osszeadunk.
Tegyuk fel, hogy van $2n^2$ proceszorunk
Az elozo modszerrel maris megy az egesz $O({\log }^{2}n)$ idoben

Az a celunk, hogy $O(\log n)$ futasideju parhuzamos algoritmust kapjunk.
Elso megoldas: 3-2 osszeadas
$d+e=a+b+c$

#                          sum bits                                                  carry bits
#           ((a xor b) xor c) or  ((a xnor b) xnor c)     (a and b and not c) or (a and not b and c) or (not a and b and c)
a + b + c = ((a  ^ b)   ^  c) | ~(~(a  ^   b)  ^   c)  +     (a & b & ~c)     |      (a & ~b & c)    |     (~a & b & b)

A fenti python code minden bitre $O(1)$ lepes es parhuzamosan szamolhato minden bitre. Tehat ha van legalabb $n$ processzurnk akkor az $a+b+c⟹d+e$ atalakitas $O(1)$ lepes.

Ezt meg lehet oldani $O(1)$ idoben $n$ proceszorral.
A $p_i$ proceszor azt csinalja, hogy $a_i+b_i+c_i=2e_i+d_1$

Ezzel az eljarassal $3$ szam osszeget tudom redukalni $2$ szam osszegere.
Mivel jo sok proceszorunk van ezert tudjuk ezt a $3-2$ redukciot csinalni az osszes tagra az osszegben parhuzamosan.
Igy $n$ szam osszeget egy lepesben tudjuk $\frac{2}{3}n$ szam osszegere redukalni.
Addig redukalunk ameddig csak tudunk es igy a vegso futasi ido a kovetkezo lesz: $O\left({\log }_{\frac{3}{2}}n+\log n\right)=O(\log n)$

Masodik megoldas: negativ szamjegyek
A kovetkezo alakra atalakitok egy szamot:

$$x=\sum b_i{4}^i$$

ahol $-3\le b_i\le 3$

Egy binaris szamot ebbe az alakba atvaltani konstans ido, mert csak minden bit part nezzuk.
A visszavaltast nem neztuk meg oran de meg lehet oldani $O(\log n)$ lepesben $n$ proceszorral.

Azt allitom, hogy ilyen alakban ket szamot mar ossze lehet adni $O(1)$ idoben.

A $p_i$ proceszor osszeadja az $x_i$ es $y_i$ szamjegyeket es igy kapunk egy $-6$ es $6$ kozotti szamot.
TODO

input: formula a kovetkezo alakban:

$$f(x_1,\dots ,x_n)=(((((x_1+x_3)\cdot x_6)-(x_3\cdot 5))\dots )\dots )$$

Def.: Algebrai fa. Absztrakt szintaxis faja az algebrai kifejezesnek.
Def.: Ennek a fanak a merete a nemlevel csucsoknak a szama, azaz a muveleti jelek szama. jel.: $|F|$

input: algebrai fa
cel: masik fa, ami ugyanazt szamolja es a melysege $\le 3\log |F|+1$

Tetel (Brent 2): Letezik ilyen fa. (https://sci-hub.st/10.1109/T-C.1973.223757)
biz.:
1.) Tegyuk fol hogy van egy $F$ fank, vegyuk annak egy $z$ csucsat es leszarmazottait.
$z$: facsucs, illetve egy uj valtozo
$z$-nek a leszarmazottait kidobjuk es igy kapunk egy $F^{\prime }$ fat es $z$ helyebe az uj $z$ valtozot irjuk.
Eszrevetel:
$f^{\prime }(x_1,\dots ,x_n,z)=f_1(x_1,\dots ,x_n)\cdot z+f_0(x_1,\dots ,x_n)$
$F^{\prime }{|}_{z=0}\to f_0$
$F^{\prime }{|}_{z=1}\to f_1+f_0$

2.)
All.: Minden faban letezik olyan $z$ csucs melyre:
$F_1^z\le \frac{|F|}{2}$
$F_2^z\le \frac{|F|}{2}$
$F_1^z+F_2^z+1\ge \frac{|F|}{2}$

3.) Indukcioval:
Ha $|F|=1\to$ OK
todo

Legyen $A,B\in {\mathbb{R}}^{n\times n}$
Az APL nyelvnen:
$AB=A+\circ \ast B={\sum }_{k=1}^n{a}_{i,k}\cdot b_{k,j}$
$A^n$ $O(\log n)$ szorzas $\to$ $O({\log }^{2}n)$

$AB:=A\vee \circ \wedge \to A^n$
$A:$ A $G$ $n$ csucsu grap szomszedasgi matrixa, foatloban $1$-esek.
All.: $A^l(i,j)=1$, ha letezik $\le l$ elu $i\to j$ ut

$AB:=AL\circ +B$ ahol $L$ egy elbaszott $L$ betu mert valamiert nagyon kell APL nyelvben irni.

$$A(i,j):=\{\begin{array}{ll}c(i,j)& \text{ha }ij\text{ nem el}\\ +\infty & \text{ha }ij\text{ nem el, de }i\ne j\\ 0& \text{kulonben}\end{array}$$

All.: $A^l(i,j)$ legrovidebb $\le l$ elu $i\to j$ seta