Złożoność obliczeniowa/Wykład 11: Obliczenia równoległe

Wstęp

W miarę jak technologia zbliża się do wynikających z podstawowych praw fizyki ograniczeń na szybkość obliczeń, wydaje się, że jednym z obiecujących kierunków badań są obliczenia równoległe. W istocie ta idea jest w stanie przynieść nowe możliwości, chociaż należy przyznać, że początkowa fascynacja algorytmami równoległymi nieco zmalała. Tym niemniej teoretyczne zagadnienia, jakie pojawiły się w trakcie badań nad obliczeniami równoległymi, istotnie poszerzyły dziedzinę teorii obliczeń i uczyniły ją jeszcze ciekawszą.

Wprowadzając algorytmy równoległe wraz z odpowiednia technologią, chcielibyśmy uzyskać następujące korzyści:

• Radykalne przyspieszenie obliczeń. Na ogół wymagamy, by czas był funkcją polilogarytmiczną od rozmiaru wejścia.
• Liczba procesorów nie była nierozsądnie duża. Sprowadza się to do wymagania, aby była ona wielomianowa od rozmiaru danych.

Modele obliczeń równoległych

Najważniejsze modele obliczeń równoległych, to:

• PRAM -- równoległa maszyna RAM
• sieci procesorów o ustalonej topologii połączeń -- krata, hiperkostka i wiele innych
• układy logiczne

Podstawowym modelem do opisu algorytmów równoległych jest maszyna PRAM, posłużymy się nią przedstawiając równoległe rozwiązania przykładowych problemów. Technologicznie PRAM nie jest realizowalna, ale abstrahuje od uwarunkowań konstrukcyjnych i pozwala wypowiadać się wystarczająco ogólnie i ściśle o złożoności problemów algorytmicznych. W przeciwieństwie do niej, sieci procesorów o ustalonej topologii praktycznie się produkuje, natomiast poszczególne rozwiązania algorytmiczne dla tych modeli trudniej przenoszą się na inne modele i przez to są mniej ogólne. W naszych rozważaniach ten model pominiemy.

Natomiast układy logiczne stanowią dobrze zbadany model, pozwalający analizować problemy również pod kątem rozwiązań równoległych, i dlatego poświęcimy mu sporo miejsca. Tym bardzie, że na ogół klasy złożoności równoległej definuje się dla tego modelu.

PRAM

Przypomnijmy w skrócie najważniejsze cechy modelu PRAM, znanego czytelnikowi z kursu Zaawansowane algorytmy i struktury danych. W maszynie PRAM (ang. Parallel Random Access Machine mamy

• nieograniczoną liczbę procesorów, każdy ma swój numer i swoje własne rejestry
• nieograniczoną wspólną pamięć, jak w maszynie RAM
• mechanizm (szynę) umożliwiający komunikację każdego procesora z pamięcią w tym samym czasie (o konfliktach dostępu poniżej)

Najczęściej dla modelu PRAM (ale i również modelu sieci procesorów o ustalonej topologii) zakłada się, że procesory wykonują synchronicznie ten sam program, operując być może na różnych danych w tej samej pamięci, ale w każdym momencie wykonując taki sam rozkaz. Odstępstwo może być tylko jedno: procesor może w danym cyklu rozkazowym nie wykonywać żadnej czynności, czyli wyłączać się na skutek spełnienia określonych warunków.

Opuszczając techniczne problemy przydziału procesorów do poszczególnych operacji, zapiszmy przykładowy prosty algorytm równoległy: mnożenie macierzy. Stosujemy język "work/time", w którym opisuje się pracę wykonywaną przez program w kolejnych jednostkach czasu, bez podawania dokładnie które procesory wykonuja daną czynność. Słowo kluczowe in-par-do jest skrótem od in parallel do.

Algorytm [Równoległe mnożenie macierzy]

---

Wejście: Macierze $A,B$ rozmiaru $n\times n,n=2^p$.
Wyjście: Iloczyn $C=AB$.
begin
1.  for 1 <= i,j,k <= n  in-par-do
2.    D[i,j,k]:=A[i,k]*B[k,j]
3.  for q=1,2,...,p do
4.    for 1<=i,j<=n, 1<=k<=n/(2**q) in-par-do
5.      D[i,j,k]:=D[i,j,2k-1]+D[i,j,2k]
6.  for 1<=i,j<=n in-par-do
7.    {C[i,j]:=D[i,j]
end

Algorytm działa na $n^3$ procesorach, w czasie równoległym $O(\log n)$. Praca jaką wykonuje jest następująca:

Krok 2: $n^3$

Krok 5: $n^3/2+n^3/4+\dots n^3/n=O(n^3)$.

Krok 7: $n^2$.

W sumie $O(n^3)$. Jest to zatem algorytm optymalny pod względem pracy. Można go w łatwy sposób przekształcić tak, aby zachowana była praca oraz czas, natomiast liczba procesorów była optymalna i wynosiła $O(n^3/\log n)$.

Załóżmy teraz, że na wejściu jest kwadratowa macierz logiczna, $A[i,j]=1$ oznacza, że w grafie istnieje krawędź z $i$ do $j$. Interesuje nas rozwiązanie problemu REACHABILITY.

Ćwiczenie 2.1

{{{3}}}

Obwody logiczne

Owody logiczne poznaliśmy już w module 2. Przekonaliśmy się, że stanowią uniwersalny model obliczeń: mogą symulować maszyne Turinga. Ta własność, a jeszcze bardziej jej dowód, przyda nam się podczas omawiania klas złożoności dla obliczeń równoległych.

Ze względu na podobieństwo do rzeczywistej architektury komputera obwody logiczne wydają się być bardzo realistycznym modelem. Z drugiej strony, w "prawdziwych" komputerach równoległych równocześnie działają procesory, a nie tylko bramki logiczne. Tutaj więc każdą bramkę obwodu traktujemy jako procesor, co wydaje się bardzo ograniczającym założeniem. Tak jednak nie jest, a rezultaty złożonościowe dotyczące obwodów przenoszą się na rzeczywiste obliczenia równoległe.

Równoległość w obwodzie logicznym polega na tym, że bramki na kolejnych poziomach, poczynając od bramek wejściowych do wyjściowych, obliczane są równocześnie. Praca algorytmu (odpowiadająca złożoności sekwencyjnej, czyli po rozwinięciu obliczenia na jednym procesorze) to wielkość obwodu, czyli liczba bramek. Czas równoległy to głębokość obwodu, długość najdłuższej ścieżki od bramki wejściowej do wyjściowej. Warto przypomnieć sobie algorytm, który dla zadanego obwodu oblicza głębokość obwodu oraz poszczególne poziomy.

Ćwiczenie 2.2

{{{3}}}

Definicja 2.3

Rodzina $(W_1,W_2,\dots )$ obwodów logicznych jest jednostajna, jeśli istnieje maszyna Turinga $M$ o złożoności pamięciowej $O(\log n)$, która dla danych wejściowych postaci $1^n$ generuje $W_n$.

Uwaga 2.4

Rodzina układów logicznych, która nie jest jednostajna, może rozwiązać problem nierozstrzygalny! Na przykład, nierozstrzygalny jest język unarny (czyli o słowach nad alfabetem jednoelementowym) $L=\{1^{<M,w>}:$ M akceptuje w $\}$ ($<M,w>$ oznacza kod binarny maszyny M i słowa wejściowego w). Układy dla poszczególnych $n$ są zbudowane w ten sposób, że jeśli $1^n\in L$, to układ oblicza koniunkcję wszystkich wejść, więc akceptuje tylko gdy są to same jedynki, a dla $1^n\notin L$ ma dodatkową bramkę wyjściową generującą zero i żadnych innych połączeń (ignoruje wejście). Nie potrafimy obliczać takich układów dla wszystkich $n$, ale wiemy że one istnieją!

Ćwiczenie 2.5

{{{3}}}

Klasy złożoności

Umownie zakładamy, że algorytm równoległy jest efektywny, jeśli działa w czasie polilogarytmicznym, na wielomianowej liczbie procesorów. O problemie mówimy, że można go efektywnie zrównoleglić, jeśli ten problem posiada efektywny algorytm równoległy. Formalnie definiujemy takie algorytmy wprowadzając klasę NC.

Definicja 3.1

Dla $n\ge 1$ klasa $N^i$ to zbiór języków $L$ takich, że $L$ jest akceptowany przez jednostajną rodzinę układów logicznych rozmiaru wielomianowego i głębokości $O({\log }^{i}n)$. Przyjmujemy oznaczenie $NC=\bigcup _{j>0}N{C}^i$.

Istnieją ciekawe związki między klasami złożoności równoległej czasowej a klasami złożoności pamięciowej -- przy zbliżonych funkcjach ograniczających dany zasób. Podstawowe z nich to poniższe dwa twierdzenia.

Twierdzenie 3.2

$N{C}^1\subseteq L$.

Dowód tego twierdzenia jest jednym z ćwiczeń końcowych.

Twierdzenie 3.3

$NL\subseteq N{C}^2$.

Dowód

Niech $L$ bedzie językiem nad alfabetem 0,1 akceptowanym przez niedeterministyczna maszynę $M$ o złożoności pamięciowej $\log n$. Aby wykazać, że istnieje jednostajna rodzina obwodów logicznych $(W_1,W_2,\dots )$ akceptujących $L$, o głębokości $O({\log }^{2}n)$, należy skonstruować maszynę Turinga $M$, działająca w pamięci logarytmicznej, która dla słowa wejściowego $1^n$ generuje obwód $W_n$ akceptujący zbiór $L\cap \{0,1{\}}^n$. Najpierw opisujemy procedury składowe:

1. Generowanie grafu konfiguracji $G$. Konfiguracja składa się ze

stanu, zawartości taśmy roboczej i położenia głowic na obu taśmach. Nie zawiera ona zawartości taśmy wejściowej, zatem wierzchołki tego grafu zależą, przy ustalonej $M$, tylko od $n$.
Niech $u,v$ będą różnymi konfiguracjami, przy czym $u$ zawiera pozycję $j$ na taśmie wejściowej. Definiujemy krawędź $(u,v)$ w $G$, jeśli $v$ może byc osiągnięta z $u$ w 1 ruchu $M$. Jeśli przejście z $u$ do $v$ ma miejsce tylko gdy $i$-ty bit wejściowego słowa jest równy 1, to etykietujemy tę krawędź jedynką, jeśli tylko dla 0, to zerem, a jeśli niezależnie od tego bitu, to etykieta jest pusta. Wynikiem jest lista wierzchołków i lista krawędzi, z etykietami.
Ponieważ liczba możliwych konfiguracji maszyny $M$ wynosi $O(n)$, więc skonstruowanie takiego grafu jest wykonalne w pamięci logarytmicznej.

1. Konstrukcja obwodu logicznego obliczającego przechodnie domknięcie grafu $H$ o $p$ wierzchołkach. Bramek wejściowych jest $p^2$ i każda informuje o istnieniu lub nie jednej krawędzi. Problem przechodniego domknięcia należy do $N{C}^2$, o czym przekonaliśmy się analizując algorytm równoległy w modelu PRAM dla tego problemu. Zatem procedura 2 działa w pamięci logarytmicznej od rozmiaru grafu.

Algorytm Maszyna Turinga $M$ generująca obwód $W$ o $n$ wejściach, działa następująco:

---

# wywołaj procedurę 1 aby obliczyć rozmiar grafu $G$
# wypisz nowe bramki wejściowe $b_1,\dots ,b_n$
# wywołaj procedurę 2 zmodyfikowaną następująco:
-- za każdym razem gdy wypisujesz na wyjście bramkę wejściową
(odpowiadającą za jakąś krawędź grafu) wywołuj od początku procedurę
1 aby otrzymać etykietę tej krawędzi i jakich konfiguracji dotyczy,
i w zależności czy etykieta jest równa 0, 1 czy pusta, dodaj
odpowiedni układ pobierający jedną z nowych bramek wejściowych $b_i$
-- dodaj układ sprawdzający na końcu czy istniej ścieżka od
konfiguracji początkowej do akceptującej, jego wynik to
wartość wyliczana przez obwód

Zauważmy jeszcze, że w punkcie 3 maszyna $M$ wielokrotnie wywołuje procedurę 2, gdyż ze względu na ograniczenie pamięciowe nie może sobie pozwolić na zapisanie $G$ na taśmie roboczej. Jest to ten sam chwyt, co zastosowany w dowodzie przechodniości redukcji logarytmicznej, w module 2.

Zakończymy ten fragment rozważań własnością, która nie jest niespodzianką.

Twierdzenie 3.4

$NC\subseteq P$.

Ćwiczenie 3.5

{{{3}}}

P-zupełność

Przekonaliśmy się już, że pojęcie NP-zupełności odgrywa fundamentalną rolę w analizie złożoności problemu pod kątem istnienia rowiązań wielomianowych. Okazuje się, że P-zupełność, poza tym że jest to narzędzie badań teoretycznych nad klasami złożoności, dostarcza analogicznych narzędzi do badania, czy dany problem jest łatwy do zrównoleglenia. To co wiadomo w praktyce, to:

• nie znaleziono jak dotąd żadnego języka wspólnego dla klasy NC oraz P-zupełnych
• uzasadniona jest hipoteza, że $NC\subseteq ̸P$.

W tej sytuacji problemy P-zupełne uważa się za trudne do zrównoleglenia.

Przypomnijmy definicję problemu P-zupełnego. Formalnie, pojęcie to definiuje się dla języków -- są one odpowiednikami problemów decyzyjnych, powstałymi przez ustalone kodowanie instancji w słowa.

Definicja 4.1

Język $L\subseteq \{0,1{\}}^{*}$ jest P-zupełny, jeśli $L\in P$ oraz dla każdego języka $L^{\prime }\in P$, istnieje redukcja logarytmiczna $L^{\prime }{\le }_{L}L$.

NP-zupełność możemy definiować za pomocą redukcji wielomianowej lub redukcji Turinga -- dla P-zupełności nie miałoby to sensu. Dlaczego?

Co więcej, redukcja logarytmiczna zachowuje złożoność równoległą. Związek między redukcją logarytmiczną a przynależnością do klasy NC jest następujący:

Twierdzenie 4.2

Jeśli $Q_1{\le }_L{Q}_2$ oraz $Q_2\in N{C}^j,j\ge 2$, to $Q_1\in N{C}^j$.

Ćwiczenie 4.3

{{{3}}}

Metodologia dowodzenia zupełności w klasie P jest taka sama jak w przypadku klasy NP. Ponieważ praktycznie znaczenie P-zupełności jest jednak dużo mniejsze, repertuar metod pojawiających się tutaj nie ma porównania z wielką gamą technik i gadżetów w dowodach NP-zupełności. Większość znanych dowodów posługuje się redukcją z problemu CIRCUIT VALUE lub którąś z jego modyfikacji.

Przypomnijmy, że aby dowieść, że dany problem $\mathrm{\Pi }$ jest P-zupełny, wystarcza:

• wykazać, że $\mathrm{\Pi }\in P$
• wybrać P-zupełny problem $Q$ i zredukować go logarytmicznie do

$\mathrm{\Pi }$.

Rolę pierwszego problemu zupełnego w P gra na ogół problem wartościowania obwodu logicznego.

Problem [CIRCUIT VALUE]

Wejście: Obwód logiczny z ustalonymi wartościami bramek wejściowych
Wyjście: TAK, jeśli wartość logiczna obwodu jest 1, NIE w przeciwnym przypadku.

Twierdzenie 4.4

Problem CIRCUIT VALUE jest P-zupełny.

Dowód

Dany jest język $L\in P$ i deterministyczna maszyna Turinga $M$ rozpoznająca $L$ w czasie wielomianowym. Należy skonstruować maszynę Turinga $M^{\prime }$, która dla zadanego słowa $w\in \{0,1{\}}^{*}$ wygeneruje obwód $C(w)$ z ustalonymi wartościami bramek wejściowych taki, że $M$ akceptuje $w$ wtedy i tylko wtedy gdy $C(w)=1$.

Przypomnijmy sobie redukcję maszyny Turinga do obwodu logicznego, skonstruowaną w module 2. Redukcja ta miała na celu wykazanie, że maszyna Turinga działająca w czasie $T(n)$ może być symulowana przez obwód logiczny o $O(T^2(n))$ bramkach.

Korzystamy z tej samej redukcji, co zapewnia nam warunek "wtedy i tylko wtedy". Uzupełnienia wymaga algorytmiczna strona redukcji. Należy wykazać, że obwód symulujący maszynę może byc skonstruowany przez algorytm o logarytmicznej złożoności pamięciowej.

Łatwo jednak zauważyć, że to prawda. Dla ustalonej $M$ podukłady stosowane w redukcji są tej samej ustalonej postaci. Algorytm redukcji musi je wyprodukować w odpowiedniej ilości, i łączyć w sieć. Ale do tego wystarcza zliczanie -- operacje na indeksach.

Przytoczmy jeszcze dla porządku rzecz oczywistą: problem CIRCUIT VALUE należy do P, co kończy dowód.

Jednym z trudniejszych problemów w klasie P jest problem znajdowania maksymalnego przepływu. Żadnego z wielu algorytmów dla tego problemu nie udało się efektywnie zrównoleglić. Znajduje to odzwierciedlenie w jego P-zupełności. Dowodzimy tej własności dla pewnej szczególnej wersji problemu, mianowicie pytania czy maksymalny przepływ w sieci z całkowitymi przepustowościami jest nieparzysty.

Przyjmijmy oznaczenie: sieć przedstawiamy jako piątkę $N=(V,E,s,t,c)$, gdzie $V$ i $E$ to zbiór wierzchołków i krawędzi, $s$ i $t$ to źródło i spływ, $c$ to funkcja przepustowości krawędzi.

Problem [PARITY MAX FLOW]

Wejście: Sieć $N=(V,E,s,t,c)$
Wyjście: TAK, jeśli maksymalny przepływ jest liczbą nieparzystą, NIE w przeciwnym przypadku.

Twierdzenie 4.5

Problem PARITY MAX FLOW jest P-zupełny.

<flash>file=ZO-11-1.swf|width=250|height=250</flash>

<div.thumbcaption>Rysunek 11.1.

<flash>file=ZO-11-2.swf|width=250|height=250</flash>

<div.thumbcaption>Rysunek 11.2.

Dowód

Do redukcji wybierzmy problem MONOTONE CIRCUIT VALUE. Obwody monotoniczne to takie, w których nie występują negacje. Jest to oczywiście zawężenie problemu CIRCUIT VALUE, dalej jednak P-zupełne (dowód stanowi ćwiczenie). Na wejściu mamy obwód logiczny w postaci grafu skierowanego $G=(V,E),|V|=n$. Przyjmijmy kilka założeń o tym grafie.

Założenie 1: bramka wyjściowa w $G$ jest typu OR. Jeśli tak nie jest (czyli jest AND), to można ją dać na wejście do nowej wyjściowej bramki OR, której drugim wejściem jest nowa bramka ustalona na stałe na 0.

Założenie 2: każda bramka ma stopień wyjściowy co najwyżej 2. Jeśli tak nie jest, to najpierw przekształcamy obwód, tak jak pokazano na rysunku 11.1 CZY TO TEN RYSUNEK??.

Założenie 3: Bramki ponumerowane są w odwrotnym porządku topologicznym -- bramka wyjściowa ma numer 0, poprzedniki każdej bramki mają numery od niej większe. Bramki utożsamiamy z ich numerami. Zobacz kolejny rysunek 11.2 CZY TO TEN RYSUNEK??.

Graf $G$ przekształcamy w sieć $N=(V^{\prime },E^{\prime },s,t,c)$ następująco:

• do zbioru wierzchołków dodajemy zródło $s$ i spływ $t$
• ze źródła prowadzimy krawędź do każdego wierzchołka wejściowego $u$ o wartości 1 i ustalamy jej przepustowość na $d{2}^u$, gdzie $d$ jest stopniem wychodzącym z $u$
• każdej krawędzi $(u,v)$ grafu $G$ dajemy przepustowość $2^u$
• dodajemy krawędź $(0,t)$ z przepustowością 1
• dla każdego wierzchołka $u$ typu OR dodajemy krawędź $(u,s)$ z przepustowością $S(u)$, gdzie $S(u)$ to suma pojemności wchodzących minus suma pojemności wychodzących
• dla każdego wierzchołka $u$ typu AND dodajemy krawędź $(u,t)$ z przepustowością $S(u)$, gdzie $S(u)$ to suma pojemności wchodzących minus suma pojemności wychodzących

Zauważmy, że rozpatrując tylko krawędzie grafu $G$, dla każdej bramki typu AND lub OR przepustowość wchodzącą jest co najmniej dwa razy większa niż wychodzącą -- bo o przepustowości krawędzi decyduje numer jej początku, który jest większy niż numer końca. Zatem krawędzie prowadzące do $s$ i $t$ mają niezerowe przepustowości.

Przepływ $F$ nazywamy standardowym, jeśli przez każdą bramkę, która ma wartość 1, ten przepływ jest maksymalny (równy sumie przepustowości wychodzących) oraz przez każdą bramkę o wartości 0 jest zerowy.

Po pierwsze, przepływ standardowy zawsze istnieje. Najpierw nasycamy wszystkie krawędzie wychodzące ze źródła, co powoduje, że bramki wejściowe z wartością 1 mają pełny przepływ, a bramki wejściowe z wartościa 0 mają przepływ zerowy. Indukcyjnie, jeśli bramka $v$ jest typu OR i ma wartość 1, to co najmniej jeden poprzednik ma wartość 1 i przysyła przepływ wystarczający do nasycenia ewentualnych dwóch odpływów z bramki $v$, ewentualny nadmiar odpłynie do $s$. Jeśli bramka OR ma wartość 0, to oba poprzedniki mają wartość 0, i z założenia indukcyjnego nic nie przysyłają. Podobne rozumowanie działa dla bramek typu AND.

Po drugie, przepływ standardowy jest maksymalny. To łatwo pokazać na podstawie twierdzenia o maksymalnym przepływie i minimalnym przekroju. Wystarczy do jednego podzbioru dać źródło i wszystkie wierzchołki o wartości 1, do drugiego pozostałe.

Na koniec zauważmy, że przepływ standardowy ma wartość nieparzystą wtedy i tylko wtedy, gdy wykorzystuje krawędź z bramki wyjściowej do spływu, a to ma miejsce jedynie gdy obwód na wyjściu ma wartość 1.

Ćwiczenia dodatkowe

Ćwiczenie 6.1

{{{3}}}

Ćwiczenie 6.2

{{{3}}}