Których algorytmów nie można zrównoleglać?

Czy istnieje jakiś algorytm, który jest bardzo trudny do zrównoleglenia lub badania są nadal aktywne?

Chciałem wiedzieć o każdym algorytmie lub polu badań w obliczeniach równoległych.

Wszystko, czego szukałem, ma „równoległą” implementację. Po prostu chcę zrobić trochę badań na dowolnym niezbadanym równoległym polu obliczeniowym.

algorithms parallel-computing

— Proton wielomianowy
źródło

Co dokładnie rozumiesz przez „równoległość”? Zapewne każdy algorytm można zrównoleglać, ale nie zawsze dobrze. (W każdym razie bardziej interesujące może być znalezienie nowych algorytmów.)

— Raphael

Masz rację, moim celem jest znalezienie algorytmów, które są trudne do zrównoleglenia. Czy możesz mi powiedzieć więcej o tym, co masz na myśli, znajdując nowe algorytmy?

— Protokół wielomianowy

Nie odpowiedziałeś na moje pytanie. Ile procesorów pozwalasz (5, , , )? Jakiego rodzaju przyspieszenia i / lub wydajności potrzebujesz? (Każde przyspieszenie, przyspieszenie liniowe w liczbie procesorów, całkowity czas logarytmiczny)?

p

$p$

n

$n$

\infty

$\infty$

— Raphael

W tej chwili szukam algorytmów, które trudno jest zrównoleglać, tj. Eksploracji pola, a następnie odpowiednio je analizuję.

— Protokół wielomianowy

powiązane: stackoverflow.com/questions/18773937/...

— Ciro Santilli 新疆改造中心法轮功六四事件

Odpowiedzi:

jest to w zasadzie otwarty problem badawczy związany z pytaniem NC = P, gdzie NC jest traktowane jako klasa algorytmów, które można skutecznie zrównoleglać.

w wpływowym / upowszechniającym badaniu przeprowadzonym przez Berkeleya „krajobraz przetwarzania równoległego” istnieją klasy algorytmów lub wzorców równoległości podzielone na „krasnoludy”. z dniem 1 6 zidentyfikowanych, wygląda -Body problemów może stosunkowo trudno skutecznie parallelize jak wzrasta, ponieważ istnieje interakcje między wszystkimi punktów. $n$ $n$ $n^2$ $n$

dodali 6 innych w dalszej części artykułu i sugerują, że ostatni o nazwie „FSM” (p14), w którym problem polega na obliczeniu obliczeń podobnych do FSM (takich jak ty stan FSM), może być przeciwieństwem „żenująco równoległego” czegoś proponują nazywać „żenująco sekwencyjne”. $n$

zobacz też są znane algorytmy w sci. komp. nie można zrównoleglać , scicomp.se

— vzn
źródło

Genialne, dzięki za linki i wyjaśnienia!

— Protokół wielomianowy

W tym artykule przedstawiono szereg problemów, które można łatwo rozwiązać sekwencyjnie, ale trudno jest je zrównoważyć: http://en.wikipedia.org/wiki/P-complete

Problemem wartość obwodu ( „dany obwód Boolean + swoje wejście, powiedz co wyprowadza”) jest to dobry punkt wyjścia - łatwe do zrozumienia, łatwe do rozwiązania z algorytmów sekwencyjnych, a nikt nie wie, czy to może być parallelised sprawnie.

— Jukka Suomela
źródło

Zakłada to teoretyczną złożoność definicji „równoległego”, która może, ale nie musi, być przedmiotem zainteresowania.

— Raphael

@Raphael: AFAIK, wiele klasycznych problemów z kompletnym P trudno jest zrównoważyć nie tylko w teorii, ale także w praktyce (nawet jeśli masz stosunkowo niewielką liczbę procesorów).

— Jukka Suomela

@JukkaSuomela Są też przypadki, w których teoria złożoności sugeruje twardość, ale rzeczy działają dobrze w praktyce. Co więcej, pozytywne wyniki również niewiele znaczą w praktyce .

— Raphael

Ktoś może chcieć dodać, że od złożoności teoretycznego punktu widzenia, to nie jest wcale jasne, czy nawet nie istnieje „nieodłącznie unparallizable” problemy, przez fakt, że nie wiadomo, czy

, jak vzn robi w jego odpowiedź

N C = P

$\mathsf{NC} = \mathsf{P}$

— Cornelius Brand

Z praktycznego punktu widzenia pytasz o algorytmy z natury sekwencyjne. Istnieje wielu kandydatów, takich jak tworzenie łańcuchów mieszających, które uważa się za bardzo trudne do zrównoleglenia. Łańcuchy mieszające są szeroko stosowane w kryptografii. Na przykład schemat mieszania haseł bcrypt został zaprojektowany, aby utrudnić przyspieszenie skrótu poprzez równoległość. Innym przykładem jest powtarzanie kwadratu (ponownie w kryptografii).

— DW
źródło

Znalazłem kilka artykułów, które mają równoległe tworzenie łańcuchów mieszających, ale nie przeczytałem tego całkowicie. Przejdę przez to samo. W każdym razie dzięki za wkład!

— Protokół wielomianowy

@ TheUknown Linki do tych artykułów będą mile widziane.

— m33lky

@ m33lky Przepraszam, nie mam teraz ze sobą żadnego z tych dokumentów. To było w styczniu i w końcu kontynuowałem badania nad innym tematem. Możesz jednak sprawdzić online na Google Scholar i jestem pewien, że dostaniesz wiele artykułów

— Polynomial Proton

Z praktycznego punktu widzenia warto również wspomnieć, że jeśli algorytm jest związany np. Z pamięcią, to równoległość niewiele pomoże: stackoverflow.com/questions/868568/...

— Ciro Santilli 新疆改造中心法轮功六四事件