Ograniczenia przetwarzania równoległego

Jestem ciekawy w szerokim znaczeniu tego, co wiadomo na temat algorytmów równoległych w P. Znalazłem następujący artykuł w Wikipedii na ten temat:

http://en.wikipedia.org/wiki/NC_%28complexity%29

Artykuł zawiera następujące zdanie:

Nie wiadomo, czy NC = P, ale większość badaczy podejrzewa, że ​​jest to fałsz, co oznacza, że ​​prawdopodobnie istnieją pewne możliwe do rozwiązania problemy, które są „z natury sekwencyjne” i których nie można znacznie przyspieszyć za pomocą równoległości

Czy to brzmi rozsądnie? Czy znane są przypadki, w których problemu w P nie można przyspieszyć za pomocą równoległości?

Nie wiadomo nawet, czy NC = P, ale problemy z kompletnością P wydają się z natury trudne do zrównoleglenia. Należą do nich programowanie liniowe i Horn-SAT. (Natomiast problemy w NC wydają się dość łatwe do zrównoleglenia.)

Zobacz pytanie Problemy między NC a P: Ile zostało rozwiązanych z tej listy? w celu uzyskania materiałów referencyjnych (w tym linków do klasycznego podręcznika, który jest teraz dostępny do bezpłatnego pobrania) oraz dalszej dyskusji na temat problemów, które są w P, ale nie są znane z możliwości równoległego działania.

Zobacz pytanie Uogólnione twierdzenie Ladnera dotyczące struktury klas złożoności między NC i P. Krótko mówiąc, jeśli się różnią, istnieje nieskończenie wiele klas złożoności ściśle pomiędzy NC i P.

Zobacz pytanie NC = konsekwencje P? dla miłej demonstracji Ryana Williamsa, że ​​możliwe jest wzmocnienie załamań w hierarchii klas złożoności w obrębie P na być może bardziej mało prawdopodobne zawalenia, takie jak PSPACE = EXP .

Warto zauważyć, że jedną z konsekwencji kompletności P Horn-SAT i powyższych linków jest to, że nie wydaje się możliwe równoległe wykonywanie ogólnych zapytań SQL w bazach danych, chyba że możemy przepisać dowolne obliczenia na dużą skalę, aby używać tylko rozsądna ilość miejsca do przechowywania. Jest to zagadkowa rozbieżność - myślę, że dość kontrowersyjne jest stwierdzenie, że istnieją ograniczenia kompresji , ale często widzę artykuły, które wydają się zbudowane na założeniu, że możliwe jest zrównoleglenie dowolnego zapytania do bazy danych.

Cóż, gdyby były znane przypadki, moglibyśmy rozdzielić P i NC. Ale istnieje wiele problemów, o których wiadomo, że są P-kompletne (tj. Przy zmniejszeniu przestrzeni logów) i stanowią one ten sam rodzaj barier w wyświetlaniu P = NC, jak problemy z NP-zupełnością dla P = NP. Wśród nich jest programowanie liniowe i dopasowywanie (i ogólnie przepływy maksymalne).

Ketan Mulmuley udowodnił wynik oddzielający P i słabą formę NC (bez operacji bitowych) już w 1994 roku. W pewnym sensie jego obecny program dla P vs NP startuje z miejsca, w którym zostało przerwane ( w bardzo luźny sposób ).

Książka „ Limits on Parallel Computation ” zawiera więcej informacji na ten temat.

Odpowiedziałem na podobne pytanie Czy są jakieś znane problemy / algorytmy w obliczeniach naukowych, których nie można przyspieszyć przez równoległość na stronie nauk obliczeniowych . Przytoczę to tutaj, ponieważ oferuje praktyczne spojrzenie na bardzo konkretny przypadek takiego problemu:

(Słynna) metoda szybkiego marszu rozwiązywania równania Eikonal nie może zostać przyspieszona przez równoległość. Istnieją inne metody rozwiązywania równania Eikonal (na przykład metody szybkiego zamiatania), które są bardziej podatne na równoległość, ale nawet tutaj potencjał (równoległego) przyspieszenia jest ograniczony.

Problem z równaniem Eikonal polega na tym, że przepływ informacji zależy od samego rozwiązania. Luźno mówiąc, informacja przepływa wzdłuż charakterystyk (tj. Promieni świetlnych w optyce), ale charakterystyki zależą od samego rozwiązania. A przepływ informacji dla dyskretnego równania Eikonal jest jeszcze gorszy, wymagając dodatkowych przybliżeń (jak domyślnie obecne w metodach szybkiego zamiatania), jeśli pożądane jest jakiekolwiek równoległe przyspieszenie.

Aby zobaczyć trudności z równoległością, wyobraź sobie ładny labirynt, jak w niektórych przykładach na stronie Sethiana . Liczba komórek na najkrótszej ścieżce przez labirynt (prawdopodobnie) jest dolną granicą minimalnej liczby kroków / iteracji dowolnego (równoległego) algorytmu rozwiązującego odpowiedni problem.

(Piszę „(prawdopodobnie) jest”, ponieważ dolne granice są notorycznie trudne do udowodnienia i często wymagają pewnych rozsądnych założeń dotyczących operacji używanych przez algorytm.)