Welche Algorithmen können nicht parallelisiert werden?

Gibt es einen Algorithmus, der sich nur schwer parallelisieren lässt oder dessen Forschung noch aktiv ist?

Ich wollte etwas über einen Algorithmus oder ein Forschungsgebiet im Parallel-Computing wissen.

Alles, wonach ich gesucht habe, wurde "parallel" implementiert. Ich möchte mich nur mit unerforschten Bereichen des Parallel-Computing befassen.

algorithms parallel-computing Polynomproton
quelle

Was genau meinst du mit "parallelisieren"? Wahrscheinlich ist jeder Algorithmus parallelisierbar, nur nicht immer gut. (Es könnte auf jeden Fall interessanter sein, neue Algorithmen zu finden .)

Raphael

Sie haben es richtig verstanden. Mein Ziel ist es, Algorithmen zu finden, die sich nur schwer parallelisieren lassen. Können Sie mir mehr darüber erzählen, was Sie damit meinen, neue Algorithmen zu finden?

Polynom Proton

Du hast meine Frage nicht beantwortet. Wie viele Prozessoren erlauben Sie (5,

)? Welche Art von Beschleunigung und / oder Effizienz möchten Sie erreichen (Beschleunigung, lineare Beschleunigung in der Anzahl der Prozessoren, polylogarithmische Gesamtzeit)?

p

$p$

n

$n$

\infty

$\infty$

Raphael

Ab sofort bin ich auf der Suche nach Algorithmen, die sich nur schwer parallelisieren lassen, dh das Feld erkunden, und entscheide mich dann nach dem Studium entsprechend.

Polynom Proton

related: stackoverflow.com/questions/18773937/…

Ciro Santilli

Antworten:

Dies ist im Grunde genommen ein offenes Forschungsproblem im Zusammenhang mit der NC =? P- Frage, bei der NC als Klasse effizient parallelisierbarer Algorithmen angesehen wird.

In einer einflussreichen / umfassenden Umfrage von Berkeley "Die Landschaft des parallelen Rechnens" gibt es Klassen von Algorithmen oder Parallelitätsmustern, die in "Zwerge" unterteilt sind. von den ersten 6 identifizierten sieht es so aus, als ob es relativ schwierig ist, Körper-Probleme effizient zu parallelisieren, wenn zunimmt, da zwischen allen Punkten Wechselwirkungen bestehen . $n$ $n$ $n^2$ $n$

Sie fügten später in der Veröffentlichung 6 weitere hinzu und schlugen vor, dass eine letzte mit dem Namen "FSMs" (S. 14), bei der das Problem darin besteht, FSM-ähnliche Berechnungen (wie den ten Zustand der FSM) zu berechnen , das Gegenteil von "peinlich parallel" sein könnte sie schlagen vor, "peinlich sequentiell" zu nennen. $n$

siehe auch gibt es berühmte algorithmen in sci. comp. das kann nicht parallelisiert werden , scicomp.se

vzn
quelle

Genial, danke für die Links und Erklärung!

Polynom Proton

Dieser Artikel enthält eine Reihe von Problemen, die leicht sequenziell zu lösen, aber nur schwer zu parallelisieren sind: http://en.wikipedia.org/wiki/P-complete

Das Schaltungswertproblem ("Wenn eine Boolesche Schaltung + ihre Eingabe angegeben wird, sagen Sie, was sie ausgibt") ist ein guter Ausgangspunkt - leicht zu verstehen, leicht mit sequentiellen Algorithmen zu lösen, und niemand weiß, ob es effizient parallelisiert werden kann.

Jukka Suomela
quelle

Dies setzt eine komplexitätstheoretische Definition von "parallelisierbar" voraus, die von Interesse sein kann oder nicht.

Raphael

@Raphael: AFAIK, viele klassische P-vollständige Probleme lassen sich nicht nur theoretisch, sondern auch praktisch nur schwer parallelisieren (auch wenn Sie eine relativ kleine Anzahl von Prozessoren haben).

Jukka Suomela

@JukkaSuomela Es gibt auch Fälle, in denen die Komplexitätstheorie auf Härte hindeutet, in der Praxis jedoch gute Ergebnisse erzielt werden. Darüber hinaus bedeuten positive Ergebnisse in der Praxis auch nicht viel .

Raphael

N C = P

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

Aus praktischer Sicht fragen Sie nach inhärent sequentiellen Algorithmen. Es gibt viele Kandidaten, wie zum Beispiel die Hash-Verkettung, von der angenommen wird, dass sie nur sehr schwer parallelisiert werden kann. Hash-Chaining ist in der Kryptographie weit verbreitet. Zum Beispiel wurde das Passwort-Hashing-Schema bcrypt entwickelt, um es schwierig zu machen, den Hash durch Parallelisierung zu beschleunigen. Ein anderes Beispiel ist das wiederholte Quadrieren (wiederum in der Kryptographie).

DW
quelle

Ich habe ein paar Artikel gefunden, in denen die Hash-Verkettung parallelisiert wurde, die ich aber nicht vollständig gelesen habe. Ich werde das gleiche durchgehen. Trotzdem danke für den Input!

Polynom Proton

@TheUknown Links zu diesen Artikeln sind willkommen.

m33lky

@ m33lky Entschuldigung, ich habe keine dieser Papiere bei mir. Dies war vor langer Zeit im Januar und ich setzte endlich meine Forschung zu einem anderen Thema fort. Sie können jedoch online auf Google Scholar nachschlagen und ich bin sicher, Sie werden viele Artikel erhalten

Polynomial Proton

Aus praktischer Sicht ist auch zu erwähnen, dass Parallelisierung nicht viel hilft

Ciro Santilli