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 新疆改造中心法轮功六四事件