Czy są jakieś znane problemy / algorytmy w obliczeniach naukowych, których nie można przyspieszyć przez równoległość

27

Czy są jakieś znane problemy / algorytmy w obliczeniach naukowych, których nie można przyspieszyć przez równoległość? Podczas czytania książek na temat CUDA wydaje mi się, że większość rzeczy może być.

parallel-computing

— RNs_Ghost
źródło

Wyszukiwanie binarne nie może zostać przyspieszone (znacznie, tj. Czynnikowo), nawet biorąc pod uwagę hierarchię pamięci.

Algorytm Gram Schmidta: en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process

3

@Anycorn Nie, lewy klasyczny Gram-Schmidt i prawy zmodyfikowany Gram-Schmidt działają dobrze równolegle. Istnieje wiele innych równoległych algorytmów QR, w tym ostatnio spopularyzowany TSQR.

— Jed Brown

@ Rafael: Myślę, że istnieje możliwość przyspieszenia wyszukiwania binarnego według współczynnika log (n), n = # procesorów. Zamiast dzielenia interwału wyszukiwania na części i sprawdzania, gdzie kontynuować, podziel interwał na n części. Być może istnieją bardziej skuteczne sposoby, nie wiem.

— miracle173

32

$C$ $T$ $C$ $T$ $C$ $T$ $T$ $N$ $C \sim \log T$

Przykłady

$C = T$
$m\times m$ $T = N = \mathcal O(m^2)$ $C = m = \sqrt T$
$T = N$ $C = \log T$
$\tau$ $(0,1)^d$ $k = \tau / \Delta t \sim \tau N^{1/d}$ $C = k$ $T = k N = \tau N^{(d+1)/d}$ $P = T/C = N$ $N^{1/d}$

Formalna złożoność

$NC = P$

— Jed Brown
źródło

13

$NC$ $O(log^c n)$ $O(n^k)$ $P=NC$ $P$ $P$ $P$ $P$ $NC$ $P$ $NC$ $P=NC$

$P$ $P$

— Optować
źródło

9

Zacznij od pooglądania Prawa Amdahla . Zasadniczo wszystko, co ma dużą liczbę kroków szeregowych, nieznacznie skorzysta na równoległości. Kilka przykładów obejmuje parsowanie, wyrażenia regularne i większość kompresji o wysokim współczynniku.

Poza tym kluczowym problemem jest często wąskie gardło w przepustowości pamięci. W szczególności w przypadku większości procesorów graficznych twoje teoretyczne klapy znacznie przewyższają liczbę liczb zmiennoprzecinkowych, które możesz dostać się do ALU, ponieważ takie algorytmy o niskiej intensywności arytmetycznej (flops / miss cache) spędzą większość czasu na pamięci RAM.

Wreszcie, za każdym razem, gdy fragment kodu wymaga rozgałęzienia, jest mało prawdopodobne, aby uzyskać dobrą wydajność, ponieważ logika ALU zwykle przewyższa liczbę.

Podsumowując, bardzo prostym przykładem czegoś, co byłoby trudne do uzyskania przyspieszenia z GPU, jest po prostu zliczanie zera w szeregu liczb całkowitych, ponieważ może być konieczne rozgałęzienie, co najwyżej wykonanie 1 operacji (przyrost o jeden) w przypadku znalezienia zera i wykonania co najmniej jednej operacji pobierania pamięci na operację.

Przykładem wolnym od problemu rozgałęziania jest obliczenie wektora, który jest skumulowaną sumą innego wektora. ([1,2,1] -> [1,3,4])

Nie wiem, czy zaliczają się one do „sławnych”, ale z pewnością istnieje wiele problemów, z którymi równoległe przetwarzanie nie pomoże.

— meawoppl
źródło

3

Podany „darmowy przykład rozgałęziania” jest sumą przedrostka, która faktycznie ma dobry algorytm równoległy: http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html Obliczanie liczby zer powinno być wydajne z podobnych powodów. Nie ma jednak możliwości odwrócenia intensywności arytmetycznej ...

— Max Hutchinson

Fajne. W tej kwestii jestem poprawiony.

— meawoppl

8

(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ą niezwykle trudne do udowodnienia i często wymagają pewnych rozsądnych założeń dotyczących operacji używanych przez algorytm.)

— Thomas Klimpel
źródło

Fajny przykład, ale nie wierzę, że twierdziłeś, że dolna granica. W szczególności do rozwiązania równania eikonal można zastosować metody wielosiatkowe. Podobnie jak w przypadku multigrid dla wysokiej częstotliwości Helmholtza, wyzwania dotyczą głównie projektowania odpowiednich grubych przestrzeni. W przypadku labiryntu strategia agregacji grafów powinna być skuteczna, a zgrubną reprezentację określa się przez rozwiązanie lokalnych (a więc niezależnych) problemów dla segmentów labiryntu.

— Jed Brown

Zasadniczo, gdy metody wielosiatkowe mają się dobrze, oznacza to, że ziarnistość problemu jest mniejsza niż deskrytyzacja, i nieproporcjonalna „ilość poprawnej odpowiedzi” pochodzi z etapu rozwiązania kursu. To tylko spostrzeżenie, ale dolna granica tego rodzaju rzeczy jest trudna!

— meawoppl

@JedBrown Z praktycznego punktu widzenia multigrid dla wysokiej częstotliwości Helmholtza jest dość trudny, w przeciwieństwie do tego, co sugeruje twój komentarz. Używanie multigrid do równania eikonal jest co najmniej „rzadkie”. Ale widzę twój „teoretyczny” sprzeciw wobec sugerowanej dolnej granicy: Przesunięcia czasowe z różnych punktów wewnątrz labiryntu można obliczyć, zanim znany jest czas do osiągnięcia tych punktów, i dodać je równolegle, gdy dostępne będą brakujące informacje. Ale w praktyce równoległe eikonalne solwery ogólnego przeznaczenia są szczęśliwe, jeśli faktycznie zbliżają się do granicy.

— Thomas Klimpel

Nie chciałem sugerować, że to było łatwe, zgrubne przestrzenie falowe są rzeczywiście bardzo techniczne. Ale myślę, że zgadzamy się, że już istnieje możliwość równoległości w otwartych regionach, podczas gdy w wąskich „labiryntach” (które ujawniają bardzo niewielką paralelizm ze standardowymi metodami) problem zwiększenia skali jest łatwiejszy do rozwiązania.

— Jed Brown

@JedBrown Slide 39 z www2.ts.ctw.utwente.nl/venner/PRESENTATIONS/MSc_Verburg.pdf (od 2010) mówi takie rzeczy jak „Rozszerz solver z 2D na 3D” i „Dostosuj metodę do problemów z silnie różniącymi się liczbami falowymi ”. Tak więc multigrid falowy może być obiecujący, ale „jeszcze nie dojrzały” wydaje się bardziej odpowiedni niż „bardzo techniczny” do opisu swoich bieżących problemów. I tak naprawdę nie jest to solver Helmholtza o wysokiej częstotliwości (ponieważ jest to solver „pełnej fali”). Są też inne „wystarczająco dojrzałe” wielosieciowe solwery Helmholtza (solwery „pełnej fali”), ale nawet one nadal są „aktywnymi badaniami”.

— Thomas Klimpel

1

Inną klasą problemów, które trudno jest zrównoważyć w praktyce, są problemy wrażliwe na błędy zaokrąglania, w których stabilność numeryczną osiąga się przez serializację.

Rozważmy na przykład proces Gram – Schmidta i jego szeregową modyfikację. Algorytm działa z wektorami, więc możesz użyć równoległych operacji wektorowych, ale to nie jest dobrze skalowane. Jeśli liczba wektorów jest duża, a rozmiar wektora jest niewielki, zastosowanie równoległego klasycznego Gram-Schmidta i reorthogonalizacji może być stabilne i szybsze niż pojedynczego zmodyfikowanego Gram-Schmidta, chociaż wymaga to kilkakrotnie większej pracy.

— Jakub Klinkovský
źródło