Zaawansowane algorytmy i struktury danych/Wykład 14

Algorytmy równoległe II

W module tym zajmiemy się obliczaniem wyrażeń arytmetycznych i równoległymi obliczeniami na drzewach związanmi z tzw. kontrakcją drzew

Obliczanie wyrażeń arytmetycznych: algorytm jednoczesnych podstawień

Zakładamy, że wyrażenie zadane jest przez program sekwencyjny (w skrócie PS). Prgram taki jestsztywną sekwencją operacji, bez instrukcji warunkowych. PS jest bardzo prostym modelem obliczeńsekwencyjnych. Bardziej precyzyjnie, definiujemy program sekwencyjny jako ciąg instrukcji przypisań postaci$x_i:=W_i$, gdzie $W_i$ jest wyrażeniem arytmetycznym zawierającym $O(1)$ operacji. W przypadku gdy operacjesą logiczne PS nazywamy obwodem logicznym (ang. boolean circuit). Ogólnie problem obliczenia wartości obwodulogiczngo jest P-zupełny, podobnie jest dla arytmetycznych programów sekwecyjnych. Problemy te są w klasie NCgdy graf związany z programem sekwencyjnym jest drzewem, a sam program odpowiada obliczaniu wyrażeniaarytmetycznego, co będziemy dalej zakładać.

Zmienne w programie sekwencyjnym są ponumerowane. Jeśli po lewej stronie instrukcji przypisaniajest zmienna $x_i$ a po prawej zmienna $x_j$ to wymagamy aby $j<i$. Zakładamy, że struktura obliczeń jest drzewem oraz operacje są ze zbioru $\{+,-,*,/\}$.

Sekwencyjna pojedyńcza operacja podstawiania polega na zastąpieniu zmiennej $x_j$ w danym wyrażeniu $W_i$,gdzie $i>j$ przez $W_j$ oraz redukcji wyrażenia po podstawieniu. \myskip Mówimy, że zmienna $x_j$ jest {\embezpieczna} gdy jej prawa strona w programie sekwencyjnym (wyrażenie $W_j$) zawiera co najwyżej jednązmienną. W przykładzie poniżej pierwsze 5 zmiennych są bezpieczne. \myskip Przykład.\\ Rozważmynastępujący program sekwencyjny $P$:\begin{quote}$x1=1$, $x2=2$, $x3=6$, $x4=4$, $x5=x3+2$, \\$x6=x2+x1$, $x7=3*x6+2*x5$, $x8=2*x7+x4$.\end{quote}Na przykład po wykonaniu wszystkich bezpiecznych podstawień (w tym wypadku tylko zastąpienie$x5$ przez $x3+2$) do prawej strony dla x7 otrzymujemy \\\centerline{$x7=3*x6+2*x3+4$. } Operacja {\em \textsl{Reduce}} polega na wykonaniu jednocześnie wszystkichbezpiecznych podstawień we wszystkich wyrażeniach $W_i$. W programie rozważamy tylko te zmienne, które sąistotne z punktu widzenia liczenia ostatecznego wyniku $x_n$. Zmienne te nazywamy istotnymi, są one osiągalneze zmiennej $x_n$ w grafie programu.Oznaczmy przez \textsl{Reduce}(P) nowy program sekwencyjny, bez zmiennych nieistotnych.\myskip\begin{center}\begin{minipage}{10cm}\begin{tabbing}first \= sec \= \kill\> Algorytm JP \\\\> (Algorytm Jednoczesnych-Podstawien)\\\> repeat } \{Operacja {\em \textsl{Reduce}}\\\\> for each $x_i$ do in parallel \\\> \> wykonaj jednoczesnie wszystkie bezpieczne podstawienia w $W_i$.\\\> until $x_n$ obliczone; \\\end{tabbing}\end{minipage}\end{center}\myskip Historia algorytmu dla przykładowego programu P danego powyżej wygląda następująco, gdzie </math>P=P_0,\P_{i+1}= \textsl{Reduce}(P_i)</math>. \vskip .1cm $P_1$:

\noindent \hspace*{1cm} </math>x3 = 6$;$x6= 3</math>;\\\hspace*{1cm}$x7=3*x6+2*x3+4$;\\\hspace*{1cm}$x8=2*x7+4$.\vskip .1cm $P2$:

\noindent \hspace*{1cm} </math>x7 =25</math>, $x8=2*x7+4$. \vskip .1cm $P_3$:

\noindent \hspace*{1cm}$x8=54$.\vskip .1cm Pokażemy, że algorytm wykonuje $O(\log n)$ iteracji. Udwodnimy bardzo precyjne oszacowanie: rozmiarnajmnieszego programu sekwencyjnego, który wmaga $k$ iteracji jest równy $k$-tej liczbie Fibonacciego. Jest tozaskakująco podobne do analogicznego faktu dla drzew AVL, czas równoległy odpowiada wysokości drzewa.

Grafem obliczeń $T={𝒢}{(}{𝒫}{)}$ programu sekwencyjnego $P$ jest skierowany graf acykliczny którego węzłyodpowiadają zmiennych biorącym aktualnie udział w obliczeniu $x_n$. Synami węzła $x_i$ (zmiennej) są zmiennewystępujące w danym momencie w $W_i$. Graf $T$ zawiera tylko węzły osiągalne z korzenia $x_n$. Przezrozmiar rozumiemy liczbę węzłów grafu (liczbę zmiennych w przypadku PS).

Zauważmy, że w danej iteracjialgorytmu \textsl{JP} rozmiar grafu $T$ może być znacznie mniejszy niż $n$, ponieważ wiele zmiennych możebyć nieosiągalnych z korzenia.

Jedna iteracja \textsl{Reduce} ($P_i\to P_{i+1}$) odpowiadanastępującej operacji $Contract({𝒢}(P_i))$,\ patrz rysunek.\myskip\begin{minipage}{12cm}\begin{description}\itemFunkcja Contract:\item(1)usuwamy wszystkie węzły powadzące do liści (operacja zwana {\em Rake})\item(2) jednocześnie, w tym samym czasie co krok (1), dla każdej krawędzi $(v,w)$ takiej, że $w$ matylko jednego następnika $u$ krawędź $(v,w)$ zastępujemy przez $(v,u)$ (operacja zwana {\em Compress})\end{description}\end{minipage}\begin{figure}[bhtp]\begin{center}\mbox{\ }\includegraphics[width=10.5cm]{expr4.eps}\caption{ Składowe operacje jednej iteracji Contract(T): {\em Compress} oraz {\em Rake}. } \end{center}\end{figure}

W rzeczywistości możemy zapomnieć o algorytmie \textsl{JP} i maszynie PRAM. Obliczanie na drzewie jestsamo w sobie sensownym modelem obliczeń równoległych. Czas równoległy jest liczbą iteracji, któraprzekształca początkowe drzewo w drzewo jednoelementowe. Z każdą krawędzią

$e=(x_i,x_j)$

grafu

${𝒢}{(}{𝒫}{)}$

jest związana pewna funkcja

$f_e(x)$

postaci:

$f_e(x)=\frac{ax+b}{cx+d},$

gdzie

$a,b,c,d$

są pewnymistałymi. Początkowo funkcja ta jest identycznościowa. Jeśli w danym momencie następnikami węzła

$x_i$

są</math>x_j,\ x_k

$,oraz$

e1=(x_i,x_j),\ e2=(x_i,x_k)Parser nie mógł rozpoznać (błąd składni): {\displaystyle to wartością zmiennej } x_i

$jest:$

f_{e1}(x_j) \otimesf_{e2}(x_k)</math>, gdzie

$\otimes$

jest operacją arytmetyczną odpowiadającą w ezłowi

$x_i$

, w grafie obliczeńoperacja ta jest niezmienna, podstawianie wyrażeń za zmienne odbywa się na funkcjeach na krawędziach. Jeśliwartości </math>x_j,x_kParser nie mógł rozpoznać (błąd składni): {\displaystyle są obliczone (zmienne te odpowiadają aktualnie liściom) to wartość } f_{e1}(x_j) \otimesf_{e2}(x_k)</math> jest konkretną końcową wartością zmiennej

$x_i$

. \vskip 0.1cmRozważamy też {\emspłaszczoną} wersję

$T^{\prime }=squash(T)$

drzewa T, odpowiadającą algorytmowi kontrakcji. W drzewie T' wewnętrznewęzły odpowiadają zmiennych programu sekwencyjnego lub krawędziom między zmiennymi, wartością krawędzi

$e$

jest funkcja

$f_e$

reprezentowana przez cztery stałe

$a,b,c,d$

. Jeśli krawędź

$e1=(x,z)$

jest kompozycjądwóch krawędzi

$e1=(x,y),e2=(y,z)$

to wartością

$f_e$

jest kompozycja funkcji

$f_{e1},f_{e2}$

. Kompozycjata polega na wykonaniu operacji na czterch stałych odpowiadających funkcjom. Jeśli zależność jest tylko odjednej krawędi to automatycznie rozumiemy że funkcja odpowiadająca pominiętej krawędzi jestidentycznościowa (a takie są początkowo wszystkie funkcje w początkowym grafie

${𝒢}{(}{𝒫}{)}$

). Nanastępującym przykładzie pokażemy jak działa operacja Contract i w jaki sposób związana jest ona zalgorytmem \textsl{JP}.

\begin{figure}[bhtp]\begin{center}\mbox{\ }\includegraphics[width=13cm]{tree_contr1.eps}\caption{ Przykładowe drzewo $T$ wyrażenia, początkowe wartości w liściach są podane w kwadracikach, numerywęzłów są w podane w nawiasach.} \end{center}\end{figure}

\begin{figure}[bhtp]\begin{center}\mbox{\ }\includegraphics[width=13cm]{tree_contr4.eps}\caption{Drzewo $T_1=Contract(T)$ razem z dodatkowymi funkcjami na krawędziach. Brak funkcji oznaczafunkcję identycznościową. } \end{center}\end{figure}

\begin{figure}[bhtp]\begin{center}\mbox{\ }\includegraphics[width=14.5cm]{tree_contr2.eps}\caption{Kolejne drzewa $T_3,T_4,T_5$. Algorytm wykonuje 4 kontrakcje. } \end{center}\end{figure}

\begin{figure}[bhtp]\begin{center}\mbox{\ }\includegraphics[width=16cm]{tree_contr3.eps}\caption{{\em Spłaszczone} drzewo $T^{\prime }=squash(T)$ liczące to samo co drzewo T, ale mające mniejszą wysokość(ogólnie logarytmiczną). Drzewo to można jeszcze bardzij spłaszczyć kompresując łańcuchy dwukrawędziowe(eliminując węzły wewnętrzne mające dokładnie jednego syna).} \end{center}\end{figure}

Załóżmy, że graf

${𝒢}{(}{𝒫}{)}$

programu sekwenycjnego P jest drzewem T.Wtedy liczba iteracji algorytmu JP jest równa liczbie kontrakcji drzewa T, po której korzeń T staje sięliściem. Przez

$TIME(n)$

oznaczmy maksymalną liczbę kontrakcjipotrzebnych do zredukowania do jednego węzła drzewa o

$n$

węzłach. Niech

$Fi{b}_n$

będziem

$n$

-tą liczbą Fibonacciego,gdzie

$Fi{b}_0=1,Fi{b}_1=2$

.Udowodnimy:\vskip 0.2cm \noindent Twierdzenie.}\mbox{ \\(a)\

$TIME(Fi{b}_n)=n$

.\\(b)}\ Parser nie mógł rozpoznać (błąd składni): {\displaystyle Fib_k \le n < Fib_{k+1'''\ \Rightarrow \ TIME(n)=k} . \myskip Jako bezpośredni wniosek otrzymujemy:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \log_{\phi}+c \le TIME(n) \le \log_{\phi}+c,\ \textrm{dla pewnej stałej c},}

gdzie

$\mathrm{\Phi }=\frac{1+\sqrt{5}}{2}$

jest liczbą tzw. złotego podziału (w przybliżeniu

$\mathrm{\Phi }\approx 1.6$

).\myskip %----------------------------------------------------------------------------Udowodnimy najpierw, że

$TIME(Fi{b}_k)\ge k$

. Niech

$T_k$

będzie

$k$

-tym drzewem Fibonacciego, zdefiniowanym narysunku. Drzewo

$T_{k+2}$

powstaje przez utożsamienie korzeni dwóch początkowo rozłącznych wierzchołkowodrzew

$T_k$

i

$T_{k+1}$

, oraz dodanie nowego korzenia.

\begin{figure}[bhtp]\begin{center}\mbox{\ }\includegraphics[width=10.5cm]{fib_trees.eps}\caption{Drzewa Fibonacciego. } \end{center}\end{figure}

Pozostawiamy jako ćwiczenie uzasadnienie tego, że $|T_k|=Fi{b}_k$ oraz $Contract(T_k)=T_{k-1}$. \myskipWynika stąd, że$TIME(Fi{b}_k)\ge k$. \myskip Przejdziemy teraz do dowodu następującego faktu.\myskip Lemat o kontrakcji.}\mbox{ \

$n\le Fi{b}_k\Rightarrow TIME(n)\le k$.\myskip Wprowadzamy pojęcie {\em statycznego węzła}, jako liścia, który nigdy nie może być {\em odcięty},nie możemy usunąć krawędzi prowadzącej do niego. Poza tym operacja kontrakcji działa tak jak poprzednio. Narysunkach statyczny węzeł jst zaznaczony jalo kwadracik. Jeśli drzewo ma dokładnie jeden statyczny węzeł,to po pewnej liczbie kontrakcji otrzymujemy drzewo składające się tylko z korzenia i tego węzła. Oznaczmyprzez $TIM{E}^{\prime }(n)$ maksymalną liczbę kontrakcji dla drzewa mającego n węzłów, które doprowadzają do takiejsytuacji. W liczbę n nie wliczamy węzła statycznego. \myskip Pozostawiamy jako ćwiczenie dowód tego, że$TIM{E}^{\prime }(Fi{b}_k+1)>k$.\myskip\noindent Następujący dosyć oczywisty fakt jest użyteczny w dalszym dowodzie Lematu o Kontrakcji.\myskip\noindent Fakt.\Niech $x\in T$, oraz $T^{\prime },T_x$ będą takie jak pokazane na Rysunku #fig12. Jeśli $t$ kontrakcji redukuje$T^{\prime }$ do drzewa rozmiaru jeden (nie licząc węzła statycznego), to po $t$ kontrakcjach drzewo $T$ redukuje siędo pojedyńczego węzła staje się drzewem złożonym tylko z korzenia któreggo jedynem następnikiem jest liść lub element drzewa $T_x$. \myskip

\begin{figure}[hbt]\unitlength=1.00mm \special{em:linewidth 0.4pt} \linethickness{0.4pt}\begin{picture}(85.33,19.11)\put(36.00,12.00){\line(3,4){5.33}} \put(41.33,19.11){\line(3,-4){5.33}} \put(46.67,12.00){\line(-1,0){4.00}}\put(36.33,12.00){\line(1,0){4.00}} \put(41.33,12.00){\circle{0.89}} \put(41.00,10.67){\line(-3,-4){4.00}}\put(42.33,10.67){\line(3,-4){4.00}} \put(46.33,5.33){\line(-1,0){9.00}} \put(77.33,19.11){\line(-3,-4){5.33}}\put(77.33,19.11){\line(3,-4){5.33}} \put(82.67,12.00){\line(-1,0){3.67}} \put(72.00,12.00){\line(1,0){4.33}}\put(76.33,10.67){\rule{2.33\unitlength}{2.22\unitlength}} \put(80.00,6.67){\line(-3,-4){4.00}}\put(81.33,6.67){\line(3,-4){4.00}} \put(85.33,1.33){\line(-1,0){9.00}} \put(80.67,8.00){\circle{0.89}}\put(27.67,12.00){\makebox(0,0)[cc]{T}} \put(68.67,16.00){\makebox(0,0)[cc]{T'}}\put(71.00,3.56){\makebox(0,0)[cc]{T${}_x$}} \put(84.00,8.00){\makebox(0,0)[cc]{$x$}}\put(77.67,14.67){\makebox(0,0)[cc]{$x$}} \put(41.67,14.67){\makebox(0,0)[cc]{$x$}}\end{picture}\caption{Graficzna definicja drzew $T^{\prime }$, $T_x$.} \end{figure}\myskip Udowodnimy lemat, który będzie rozszerzeniem Lematu o kontrakcji. Celowo wzmacniamy tezę aby ułatwićdowód przez indukcję.\myskip Wzmocniony Lemat o kontrakcji.

\begin{tabbing}{lll}firstleve\=secon\= \kill\>(a) \> $n<FI{B}_k\Rightarrow TIME(n)<k-1$; \\\>(b) \>$n\le FI{B}_k\Rightarrow TIM{E}^{\prime }(n)<k$.\\\end{tabbing}\myskip Dowód przeprowadzamy przez indukcję ze względu na $k$. Dla $k=1$, $k=2$ łatwo sprawdzić, że tezazachodzi. \noindent Załóżmy teraz, że teza zachodzi dla wszystich $k^{\prime }$ mniejszych niż dane$k>2$.\myskip Dowód punktu (a)

Rozważmy drzewo

$T$

takie, że

$|T|<FI{B}_k$

. Niech

$x$

będzie najniższym (o najmnieszej wysokości) węzłem,takim że

$|T_x|\ge FI{B}_{k-1}$

. Niech

$p$

,

$q$

będą następnikami

$x$

, patrz Rysunek #fig13. (Jeśli

$x$

ma tylko jednego następnika to nazwijmy go

$p$

). Zatem

$|T_p|,|T_q|<FI{B}_{k-1}$

Udwodnimy, że po

$k-1$

-szej kontrakcjikorzeń

$T$

staje się liściem. Możliwe są dwa przypadki: \myskip Przypadek I: Po kontrakcji

$(k-2)$

-giej węzeł

$x$

jest liściem. \vskip 0.2cm Z założenia indukcyjnego wynika, że drzewo

$T1$

jestzredukowane do korzenia z jednym następnikiem, który jest wewnątrz

$T_x$

. ponieważ wszystkie węzły w

$T_x$

stały się liśćmi (gdyż korzeń

$T_x$

stał się liściem) to w następnej kontrakcji wykonujemy operacjęRake i korzeń całego drzewa staje się liściem.

\begin{figure}\unitlength=1.00mm \special{em:linewidth 0.4pt} \linethickness{0.4pt}\begin{picture}(116.33,32.00)\put(21.33,24.00){\line(3,4){6.00}} \put(27.33,31.56){\line(3,-4){6.00}} \put(33.33,23.56){\line(-1,0){5.00}}\put(21.33,23.56){\line(1,0){5.33}} \put(27.67,23.56){\circle{0.89}} \put(27.00,22.22){\line(-3,-4){4.00}}\put(28.67,22.22){\line(3,-4){4.00}} \put(22.33,15.56){\circle{0.89}} \put(33.67,15.56){\circle{0.89}}\put(22.33,14.22){\line(-3,-4){4.33}} \put(22.67,13.78){\line(3,-4){4.00}} \put(26.67,8.44){\line(-1,0){8.67}}\put(33.33,13.78){\line(-3,-4){4.00}} \put(34.00,13.78){\line(3,-4){4.00}} \put(38.00,8.44){\line(-1,0){8.33}}\put(27.67,26.22){\makebox(0,0)[cc]{x}} \put(36.67,15.56){\makebox(0,0)[cc]{q}}\put(19.67,15.56){\makebox(0,0)[cc]{p}} \put(64.00,18.67){\line(-3,-4){4.00}}\put(65.67,18.67){\line(3,-4){4.00}} \put(59.33,12.00){\circle{0.89}} \put(70.67,12.00){\circle{0.89}}\put(59.33,10.67){\line(-3,-4){4.33}} \put(59.67,10.22){\line(3,-4){4.00}} \put(63.67,4.89){\line(-1,0){8.67}}\put(70.33,10.22){\line(-3,-4){4.00}} \put(71.00,10.22){\line(3,-4){4.00}} \put(75.00,4.89){\line(-1,0){8.33}}\put(73.67,12.00){\makebox(0,0)[cc]{q}} \put(56.67,12.00){\makebox(0,0)[cc]{p}}\put(56.00,24.00){\line(3,4){6.00}} \put(62.00,31.56){\line(3,-4){6.00}} \put(68.00,23.56){\line(-1,0){5.00}}\put(56.00,23.56){\line(1,0){5.33}} \put(62.33,23.56){\circle{0.89}} \put(62.33,26.22){\makebox(0,0)[cc]{x}}\put(64.67,19.11){\circle{0.89}} \put(68.33,18.67){\makebox(0,0)[cc]{x}} \put(54.34,27.56){\makebox(0,0)[cc]{T1}}\put(49.33,11.11){\makebox(0,0)[cc]{T${}_x$}} \put(13.33,21.78){\makebox(0,0)[cc]{T}}\put(64.56,1.33){\makebox(0,0)[cc]{case (I)}} \put(96.00,24.00){\line(3,4){6.00}}\put(102.00,31.56){\line(3,-4){6.00}} \put(108.00,23.56){\line(-1,0){5.00}} \put(96.00,23.56){\line(1,0){5.33}}\put(102.33,23.56){\circle{0.89}} \put(101.67,22.22){\line(-3,-4){4.00}} \put(103.33,22.22){\line(3,-4){4.00}}\put(108.33,15.56){\circle{0.89}} \put(108.00,13.78){\line(-3,-4){4.00}} \put(108.67,13.78){\line(3,-4){4.00}}\put(112.67,8.44){\line(-1,0){8.33}} \put(102.33,26.22){\makebox(0,0)[cc]{x}}\put(111.33,15.56){\makebox(0,0)[cc]{q}} \put(94.00,11.56){\circle{0.89}} \put(94.00,10.22){\line(-3,-4){4.33}}\put(94.33,9.78){\line(3,-4){4.00}} \put(98.33,4.44){\line(-1,0){8.67}} \put(91.33,11.56){\makebox(0,0)[cc]{p}}\put(96.00,14.22){\rule{1.67\unitlength}{2.22\unitlength}} \put(100.33,16.00){\makebox(0,0)[cc]{p}}\put(87.00,7.56){\makebox(0,0)[cc]{T${}_p$}} \put(116.33,24.00){\makebox(0,0)[cc]{T2}}\put(100.34,1.31){\makebox(0,0)[cc]{case(II)}}\end{picture}\caption{Drzewo $T$ i jego dekompozycja: $|T|<FI{B}_k$,$|T1|\le FI{B}_{k-2}$, $|T_x|\ge FI{B}_{k-1}$, $|T_p|<FI{B}_{k-1}$.} \end{figure}\myskip Przypadek II:\ Korzeń drzewa $T_x$ wymaga co najmniej $k-1$ kontrakcji by stał się liściem.\vskip 0.2cm Dla drzewa $T$ niech $v\notin R$ będzie dodatkowym węzłem, a $R\otimes v$ będzie nowym drzewemo korzeniu </math>vParser nie mógł rozpoznać (błąd składni): {\displaystyle mającym jednego następnka - korzeń R. łatwo widać, że co najmniej jedno z drzew } T_p\otimesx</math> lub $T_q\otimes x$ wymaga co najmniej $k-1$ kontrakcji aby korzeń stał się liściem. Przyjmijmy, bezstarty ogólności że jest to pierwsze z nich.

Z założenia indukcyjnego wynika, że $|T_p\otimes x|\ge FI{B}_{k-1}$ (zatem $|T_p|=FI{B}_{k-1}-1)$. Wynika stąd,że drzewo $T2$ z węzłem statycznym, patrz Rysunek [[#fig13}, jest {\em małe}:\ Parser nie mógł rozpoznać (błąd składni): {\displaystyle |T2| \le FIB_{k-2]]} .

W tej sytuacji z założenia indukcyjnego (b) wynika, że drzewo $T2$ jest zredukowane do korzenia z jednymliściem po $k-2$ kontrakcjach. Wszystkie węzły $T_p$ stają się liścmi po$k-2$ kontrakcjach na mocy założenia indukcyjnego (a).Zatem, podobnie jak w przypadku I korzeń całego drzewa staje się liściem po k-1 kontrakcjach.\myskip Dowód punktu (b).\myskip Przypadek ten rozpatruje się podobnie jak punkt (a), stosującodpowiednią dekompozycję drzewa $T$.Dowód ten pozostawiamy jako ćwiczenie.\vskip 0.3cm\noindentObserwacja.\Możliwe są różne inne definicje kontrakcji drzew. Na przykład moglibyśmy rozważać że w jednej iteracji kontrakcji napierw wykonujemy Rake (usuń liście) a dopiero potem Compress. My wykonywaliśmy to w jednym kroku równocześnie, co wydaje się bardzoej naturalne.\end{document}