Zaawansowane algorytmy i struktury danych/Wykład 13

\noindent \Large Moduł ZASD:\ Algorytmy równoległe I \myskip W module tym zajmiemy się przyspieszaniem obliczeń za pomocš korzystania z wielu procesrów (maszyn) działajšcych równolegle. Niestety nie ma ogólnie przyjętego modelu obliczeń równoległych, rozważymy w tym module dwa modele: maszynę PRAM i układy arytmetyczne (logiczne). O ile maszyna PRAM jest modelem wysoko-poziomowym, to układy arytmetyczne sš modelem niskopoziomowym, ale niewštpliwie bardzo istotnym niskopoziomowym, ale niewštpliwie bardzo istotnym. Na poczštku rozważymy wyidealizowany model obleczeń równoległych zwany Równoległš Maszynš ze Swobodnym Dostępem do Pamięci, w skrócie PRAM (od ang. {\em Parallel Random Access Machine}, wymawiany {\em piram}).

\begin{figure}[bhtp] \begin{center} \mbox{\ } \includegraphics[width=10.5cm]{parallel_fig1.eps} \caption{Struktura koncepycyjna PRAMu }

\end{center} \end{figure}

\noindent Maszyna PRAM {\em składa się} z wielu procesorów pracujšcych synchronicznie, korzystšcych ze wspólnej pamięci (która oprócz przechowywania danych służy do komunikacji między procesorami). Każdy procesor jest standardowym komputerm typu RAM (ang. {\em Random Access Machine}). Zakładamy, że procesory sš ponumerowane liczbami naturalnymi. Procesory wykonujš jeden wspólny program, ale wykonanie poszczególnych instrukcji zależy od indeksu procesora. W jednym kroku procesor pobiera dane z pamięci, potem wykonuje operację, którš może być wpisanie pewnych danych. Wszystkie procesory wykonujš jeden krok jednocze�nie. Rówoległo�ć jest wyrażona poprzez następujšcš instrukcję: \myskip \begin{center} \textbf{for all} $i\in X$ \textbf{do in parallel}\ akcja$(i)$. \end{center} \myskip \noindent Wykonanie tej instrukcji polega na wykonaniu dwóch równoległych operacji:

• przydzielenie procesora do każdego elementu ze zbioru $X$,
• jednoczesne wykonanie przez każdy procesor operacji akcja$(i)$.

Przeważnie zapis ``$i\in X$ jest w rodzaju\ ``$1\le i\le n$ je�li $X$ jest zbiorem liczb naturalnych. Litera C (od ang. concurrent) oznacza możliwo�ć jednoczesnego wykonania operacji przez wiele procesorów, E (od ang. exclusive) wyklucza takš możliwo�ć. Operacjami sš R (czytanie, od ang. read) oraz W (zapis, od ang. write) w tej samej komórce przez wiele procesorów w tym samym momencie. Mamy zatem EREW PRAM, CREW PRAM, CRCW PRAM (modelu ERCW nie rozważamy jako zupełnie sztuczny).

Podstawowym naszym mdoelem PRAMu będzie CREW PRAM: wiele procesrów może jednocze�nie czytać z tej samej komórki, ale tylko jeden może zapisywać. \myskip Prostym przykładem obliczenia na CREW jest liczenie kolejnych wierszy trójkšta Pasacala. Poczštkowo zakładamy, że $A=[0,0,0,0,0,1]$. Wykonujemy: \vskip 0.2cm \begin{center} \begin{minipage}{10cm} repeat 6 times

for each $1\le i\le 5$ do in parallel \\ \hspace*{1cm} $A[i]:=A[i]+A[i+1]$ \end{minipage} \end{center} \vskip 0.2cm \noindent Kolejnymi warto�ciami tablicy A sš wektory: \vskip 0.2cm \begin{center} \noindent 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 1

\noindent 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 1

\noindent 0\ \ 0\ \ 0\ \ 0\ \ 1\ \ 1

\noindent 0\ \ 0\ \ 0\ \ 1\ \ 2\ \ 1

\noindent 0\ \ 0\ \ 1\ \ 3\ \ 3\ \ 1

\noindent 0\ \ 1\ \ 4\ \ 6 \ \ 4\ \ 1

\noindent 1\ \ 5\ 10 \ 10\ \ 5\ \ 1 \end{center}

Najważniejszš klasš problemów algorytmicznych stanowiš problemy które można obliczyć w czasie wielomianowo-logarytmicznym używajšc wielomianowej liczby procesorów. Klasę tę oznaczamy przez NC, odpowiadajšce algorytmy nazywamy algorytmami typu NC.

Niech ${𝒫}$ oznacza klasę problemów wykonywanych w deterministycznym czasie wielomianowym na maszynie sekwencyjnej. Podstawowym problemem teoretycznym algorytmiki równoległej jest pytanie:

\centerline{${𝒫}{=}{𝒩}{𝒞}$?} \myskip Podobnie jak problemy NP-zupełne można zdefiniować probly P-zupełne. Sš to te problemy $X\in {𝒫}$, takie że dla każdego innego problemu $Y\in {𝒫}$ istnieje NC-redukcja Y do X. Inaczej mówišc

\centerline{${𝒫}{=}{𝒩}{𝒞}$ wtedy i tylko wtedy gdy \ $X\in NC$} \myskip Przykłady problemów P-zupełnych:\ programowanie liniowe, maksymalny przepływ w grafie, konstrukcja drzewa DFS, obliczanie warto�ci układów logicznych, sprawdzanie czy gramatyka bezkontekstowa generuje język pusty. \myskip Przez pracę algorytmu równoległego rozumiemy liczbę procesorów pomnożonš orzez czas. Algorytm jest optymalny gdy jego praca jest tego samego rzędu co czas najlepszego znanego algorytmu sekwencyjnego dla danego problemu.

W szczególno�ci interesujš nas algorytmy, które sš jednocze�nie optymalne i sš typu NC. Z praktycznego punku widzenia czynnik $logn$ przy liczbie procesorów i przy pracy algorytmu nie jest zbyt istotny. Natomiast czynnik logarytmiczny jest istotny je�li chodzi o równoległy czas. W tym przypadku potęga logarytmu odgrywa podobnš rolę co potęga wielomianu opisujšcego czas obliczenia sekwencyjnego. Różnica między CRCW i CREW PRAMem w aspekcie klasy NC polega przeważnie na dodaniu jednego czynnika logarytmicznego w funkcji równoległego czasu obliczenia. W przypadku CRCW PRAM założymy, że procesory, je�li wpisujš jednocze�nie do tej samej komórki pamięci, to wpisujš to samo. Na przykład je�li poczštkowo $output=0$ wówczas następujšcy algorytm obliczy logicznš alternatywę w czasie stałym na CRCW PRAM. \myskip for each $1\le i\le n$ do in parallel \\ \hspace*{1cm} if $A[i]=1$ then output=1; \vskip 0.6cm Na CREW potrzebujemy logarytmicznego czasu równoległego aby to zrobić. Pokażemy jeszcze dwa proste problemy, które można na CRCW PRAM wykonać w czasei stałym. Następujšcy algorytm liczy pierwszš pozycję minimalnego elementu w tablicy C[1 . . n] w czasie O(1). \vskip 0.4cm for each $1\le i\le n$ do in parallel $M[i]$ := 0;

for each $1\le i,j\le n$ do in parallel \\ \hspace*{1cm} if $i\ne j$ and $C[i]\le C[j]$ then $M[i]$:=1;

for each $1\le i\le n$ do in parallel \\ \hspace*{1cm} if $M[i]$ = 0 then output :=i ; \myskip Oznaczmy ten algorytm przez $A_1$. Algorytm korzysta z $n^2$ procesorów. Spróbujemy zmniejszyć tę liczbę do $O(n^{1+ϵ})$ zachowujšc czas $O(1)$, dla dowolnie małego $ϵ>0$.

\noindent Niech

\centerline{$P_k(n)=n^{1+{ϵ}_k}$, gdzie ${ϵ}_k=\frac{1}{2^k-1}$.} \myskip \noindent Przypu�ćmy, że mamy algorytm $A_k$ liczenia minimum w czasie $O(1)$ z $O(P_k(n))$ procesorami. Skonstruujemy algorytm $A_{k+1}$ który działa w czasie stałym i używa tylko $O(P_{k+1}(n))$ procesorów. \vskip 0.5cm \noindent Algorytm}\ Parser nie mógł rozpoznać (błąd składni): {\displaystyle A_{k+1'''} :

niech $\alpha =\frac{1}{2^k+1}$;

podziel tablicę C na rozłšczne bloki rozmiaru $n^{\alpha }$ każdy;

równolegle zastosuj algorytm $A_k$ do każdego z tych bloków;

zastosuj algorytm $A_k$ do tablicy C' składajšcej się z $\frac{n}{n^{\alpha }}$ minimów w blokach. \vskip 0.5cm \noindent Algorithm $A_{k+1}$ działa w czasie $O(1)$ korzystajšc z $P_{k+1}(n))$ procesorów. Uzasadnienie pozostawiamy jako ćwiczenie. \vskip 0.3cm \noindent Algorytmy $A_2,A_3,A_4,\dots$ używajš odpowiednio następujšcš (asymptotycznie) liczbę procesorów

$n^{1+\frac{1}{3}},n^{1+\frac{1}{15}},n^{1+\frac{1}{255}},n^{1+\frac{1}{65535}}..$. \myskip Rozważmy jeszcze na CRCW PRAM następujšcy problem pierwszej jedynki: \ dana tablica zerojedynkowa, znale�ć pozycję pierwszej jedynki (od lewej). \myskip Następujšcy algorytm rozwišzuje problem w czasie stałym z kwadratowš liczbš procesorów. Zakładamy na razie, że w cišgu jest jakašs jedynka. \vskip 0.3cm Algorytm Pierwsza-Jedynka-1;

for each $1\le i<j\le n$ do in parallel

\hspace*{0.6cm} if A[i]=1] and A[j]=1 then A[j]:= 0;

for each $1\le i\le n$ do in parallel

\hspace*{0.6cm} if A[i]=1 then FirstOne :=i. \vskip 0.3cm \noindent Możemy podobnie łatwo sprawdzić czy w ogóle jest jedynka. \vskip 0.3cm Algorytm CzyJestJedynka;

jest-jedynka := 0;

for each $1\le i\le n$ do in parallel

\hspace*{0.6cm} if A[i]=1 then jest-jedynka := 1;

\vskip 0.2cm \noindent Oba powyższe algorytmy korzystajš z $O(n^2)$ procesorów. Możemy łatwo tę liczbę zmniejszyć do liniowej. \myskip Algorytm Pierwsza-Jedynka; \vskip 0.1cm (1)\ Podziel tablicę A na segmenty długo�ći $\sqrt{n}$;

(2)\ W każdym segmencie zastosuj algorytm CzyJestJedynka;

(3)\ } Otrzymujemy cišg zerojedynkowy $C$ długo�ci Parser nie mógł rozpoznać (błąd składni): {\displaystyle \sqrt{n'''} jako wynik kroku (2);

(4)\ znajd� pierwszš jedynkę w cišgu C za pomocš algorytmu Pierwsza-Jedynka-1;;

(5)\ Zastosuj algorytm Pierwsza-Jedynka-1 do segmentu odpowiadajšcego \\ \hspace*{1.4cm} pierwszej jedynce w C; \myskip W ten sposób stosujemy trzy razy algorytm o pracy kwadratowej do segmentu długo�ci $\sqrt{n}$, otrzymujemy złożono�ć $O({\sqrt{n}}^2)=O(n)$. Czas jest $O(1)$. Do szybkich obliczeń równoległych najbardziej nadajš się problemy zwišzane z drzewami, chociaż czasami w tych problemach nie widać od razu struktury drzewiastej. Struktura taka odpowiada również drzewu rekursji. Jako przykład rozważmy problem obliczenia sumy $A[1]+A[2]+\dots A[n]$. Dla uproszczenia załóżmy, że n jest potęgš dwójki.

\begin{figure}[htbp] \begin{center} \mbox{\ } \includegraphics[width=10.cm]{parallel_fig2.eps} \caption{ Metoda pełnego zrównoważonego drzewa binarnego:\ układ arytmetyczny obliczania sumy. Maksymalny poziom $m=\log n$.}

\end{center} \end{figure}

\noindent Wysoko�ciš węzła jest jego maksymalna odległo�ć od li�cia, wysoko�ć li�cia wynosi 0. Przez $p$-ty poziom rozumiemy zbiór węzłów o wysoko�ci $p$. Załóżmy, że elementy $A[1],A[2],..A[n]$ sš umieszczone w li�ciach pełnego zrównoważonego drrzewa binarnego, następnie wykonujemy (patrz rysunek): \vskip 0.4cm for $p:=1$ to $\log n$ do

\hspace*{0.5cm} oblicz jedmocze�nie warto�ci węzłów na poziomie $p$-tym; \myskip Drzewo jest strukturš koncepcyjnš, każdemu węzłowi możemy przypisać miejsce w pamięci. W naszym przypadku węzły na poziomie $p$-tym mogš odpowiadać elementom \\ \centerline{$A[2^p],A[2*2^p],..A[3*2^p]\dots$. } Poprzedni algorytm można zapisać w formie: \vskip 0.4cm \noindent for $p:=1$ to $\log n$ do\\ \hspace*{0.5cm} $\mathrm{\Delta }=2^p$; \\ \hspace*{0.5cm} for each $1\le i\le n/\mathrm{\Delta }$ do in parallel \\ \hspace*{0.9cm} $A[i*\mathrm{\Delta }]:=A[i*\mathrm{\Delta }]-\mathrm{\Delta }/2]+A[i*\mathrm{\Delta }]$; \\ wynik := $A[n]$; \myskip \begin{figure}[hbtp] \begin{center} \mbox{\ } \includegraphics[width=9.cm]{parallel_fig3.eps} \caption{Koncepcyjna struktura równoległej wersji metody {\em dziel i zwycieżaj}. }

\end{center} \end{figure}

Drzewa odpowiadajš w pewnym sensie rekursji. Wysoko�ć drzew odpowiada czasowi równoległemu. Podobnie głęboko�ć rekursji odpowiada też czasowi równoległemu. Równoległa wersja tzw. metody dziel i zwyciężaj polega na tym że wywołania rekurencyjne wykonujemy jednocze�nie (patrz rysunek). Oczywi�cie może się zdarzyć, że jedno z nich zakończy się wcze�niej. Tym niemniej algorytm czeka na zakończenie obu wywołań.

Pokażemy dwa przykłady zastosowania metody dziel i zwyciężaj w wersji równoległej. Zaczniemy od sumy elementów tablicy $A[1..n]$. Wynik obliczamy jako $SUMA(1,n)$. Zakładamy znowu, że $n$ jest potęgš dwójki. \myskip \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{funkcja} $SUMA(i,j)$; \\ \hspace*{1.2cm}\textbf{if} $j=i$ \textbf{then return} $A[i]$ \textbf{else }\\ \hspace*{1.8cm}{do in parallel} \\ \hspace*{2.5cm} wynik1 := $SUMA(i,\lfloor (i+j)/2\rfloor$;\\ \hspace*{2.5cm} wynik2 := $SUMA(\lceil (i+j)/2\rceil ,j)$;\\ \hspace*{1.8cm}\textbf{return} wynik1 + wynik2; \vskip0.4cm \end{minipage} \end{center} \myskip \noindent Podobny jest schemat sortowania na PRAMie. Niech $ParallelMerge(x)$ będzie algorytmem który, otrzymawszy tablicę $x$ z posortowanymi lewš i prawš połowš da wyniku tablicę $x$ posortowanš. łatwo to zrobić w czasie $O(\log n)$ z $n$ procesorami. Dla $i>n/2$-ty procesor znajduje w pierwszej połówce sekwencyjnie metodš {\em binary search} najmniejszy element większy od $x[i]$. Wymaga to czasu $O(\log n)$. Potem każdy procesor{\em wie} gdzie wstawić {\em swój} element. W sumie otrzymujemy algorytm sortowania w czasie $O({\log }^2)$ z $n$ procesorami. \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{funkcja} $ParallelSort(x)$; \\ \hspace*{1.2cm}$n:=size(x)$;\\ \hspace*{1.2cm}\textbf{if} $n>1$ \textbf{then } \\ \hspace*{1.8cm}\textbf{do in parallel}\\ \hspace*{2.5cm} $ParallelSort(FirstHalf(x))$;\\ \hspace*{2.5cm} $ParallelSort(SecondHalf(x))$;\\ \hspace*{1.8cm} $ParallelMerge(x)$ \vskip0.4cm \end{minipage} \end{center} \myskip Liczbę procesorów można zmniejszyc do $n/(\log n))$. Natomiast nietrywialnym jest zmniejszenie czasu na CREW PRAM. Zostało to zrobione przez Richarda Cole'a, który skonstruował algorytm działający w czaie $O(\log n)$ z $O(n)$ procesorami maszyny EREW PRAM. Algorytm ten jest bardzo interesujący ale skomplikowany. \newpage Być może najbardziej podstawowym modelem obliczeń równoległych sš układy arytmetyczne (lub logiczne): acyckliczne grafy z przypisaniem pewnych operacji węzłom wewnętrznym. Każdy węzeł liczy pewnš warto�ć w momencie gdy warto�ci jego poprzedników sš policzone. Podobnie jak w drzewie możemy zdefinować pojęcie li�cia: węzeł bez poprzedników. Natomiast graf nie musi mieć jednego korzenia, zamiast korzenia w grafie wyróżniamy węzły wynikowe (na rysunku te z których wychodzi strzałka {\em do nikšd}).

Równoległy czas obliczenia odpowiada maksymalej wysoko�ci węzła. Poziomy definiujemy podobnie jak dla drzewa. Algorytm równoległy w jednym równoległym kroku oblicza kolejny poziom. Liczba procesorów odpowiada z reguły maksymalnemu roziarowi poziomu, chociaż możemy inaczej rozplanować obliczenie gdy jedne poziomy sš duże, a drugie małe (ale możemy wtedy zmienić strukturę grafu tak aby temu odpowiadała).

Przykładem układu arytmetycznego jest drzewo z rysunku powyżej, które opisuje sumowanie n elementów. Zajmiemy się teraz pewnym rozszerzeniem problemu sumowania. Niech $\oplus$ będzie pewnš łšcznš operacjš arytmetycznš (np. suma, mnożenie, maksimum, minimum, pozycja pierwszej jedynki z lewej strony, podobnie z prawej strony).

\noindentProblem sum p[refiksowych.\ dany wektor $x$ rozmiaru $n$, obliczyć cišg $y$ taki, gdzie \myskip \begin{center} $y[1]=x[1]$, $y[2]=x[1]\oplus x[2]$, $y[3]=x[1]\oplus x[2]\oplus x[3]$, \ldots \end{center} gdzie \myskip Opiszemy dwa rekurencyjne algorytmy dla tego problemu. Niech $FirstHalf$, $SecondHalf$ oznaczjš lewš i prawš (odpowiednio) połówkę cišgu. Zakładamy, że n jest potęgš dwójki. \myskip \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} $PrefSums1(x)$; \\ \hspace*{1.2cm}$n:=size(x)$;\\ \hspace*{1.2cm}\textbf{if} $n>1$ \textbf{then } \\ \hspace*{1.8cm}\textbf{do in parallel}\\ \hspace*{2.5cm} $PrefSums1(FirstHalf(x))$;\\ \hspace*{2.5cm} $PrefSums1(SecondHalf(x))$;\\ \hspace*{1.8cm}\textbf{for each } $n/2<j\le n$, \textbf{do in parallel} \\ \hspace*{2.4cm} $x[j]:=x[n/2]\oplus x[j]$;\\ \vskip0.4cm \end{minipage} \end{center} \myskip

Układ arytmetyczny odpowiadajšcy algorytmowi PrefSums1 jest przedstawiony na Rysunku #parallel_fig5 dla $n=4$ i $n=8$. Zauważmy, że zasadniczš czę�Ciš układu dla $n=8$ sš dwie kopie układu dla $n=4$. Dodatkowo dodajemy węzły odpowiadajšcej ostatniej instrukcji w algorytmie PrefSums1.

\begin{figure}[bhtp] \begin{center} \mbox{\ } \includegraphics[width=11.5cm]{parallel_fig5.eps} \caption{Układ arytmetyczny odpowiadajšcy algorytmowi PrefSums1. Kolejne grafy powstajš jako podwójne kopie porzednich grafów (dla $n/2$ elementów) z dodanymi elementami odpowiadajšcymi operacji $x[j]:=x[n/2]\oplus x[j]$. }

\end{center} \end{figure}

\noindent Opiszemy teraz inny algorytm rekurencyjny, w którym mamy tylko jedno wywołanie rekurecyjne (w jednej instancji rekursji).

\myskip \begin{center} \begin{minipage}{12cm} \vskip0.3cm \hspace*{0.6cm}\textbf{Algorytm} $PrefSums2(x)$; \\ \hspace*{1.2cm}$n:=size(x)$;\\ \hspace*{1.2cm}\textbf{if} $n>1$ \textbf{then } \\ \hspace*{1.8cm} utwórz nowš tablicę y;\\ \hspace*{1.8cm} for each } $1\le i\le n/2$ \textbf{do in parallel\\ \hspace*{2.5cm} $y[i]:=x[2i-1]\oplus x[2i]$;\\ \hspace*{1.8cm} $PrefSums2(y)$;\\ \hspace*{1.8cm} for each } $1\le i\le n/2$ \textbf{do in parallel\\ \hspace*{2.4cm} $x[2i]:=y[i]$;\\ \hspace*{2.4cm} if $i>1$ then \ $x[2i-1]:=y[i-1]\oplus x[2i-1]$;\\ \vskip0.4cm \end{minipage} \end{center} \myskip Układ arytmetyczny odpowiadajšcy algorytmowi jest pokazany na rysunku  #parallel_fig4. \begin{figure}[bhtp] \begin{center} \mbox{\ } \includegraphics[width=7.2cm]{parallel_fig4.eps} \caption{Układ arytmetyczny odpowiadajšcy PrefSums2. Kolejny graf składa się z pojedyńczej kopii poprzedniego grafu (dla $n/2$), oraz $n/2-1$ dodatkowych operacji. }

\end{center} \end{figure}