nicht angemeldet
Nicht parallelisierbare Algorithmen?
Gibt es eigentlich Algorithmen, die nicht parallelisierbar sind (für mehrere CPU/GPU Kerne)? Nach meiner Intuition wäre das z.B. der Fall, wenn der Algorithmus sich nach jedem Rechenschritt auf das jeweilige vorherige Ergebnis beziehen muss.
Bei Wikipedia steht: "Es gehört jedoch zu den offenen Fragen der theoretischen Informatik ob alle Algorithmen, welche Probleme der Klassen P oder NP entscheiden, auch parallelisierbar sind. Für viele dieser Algorithmen wurde noch kein entsprechender paralleler Algorithmus gefunden, so dass die meisten Forscher heute davon ausgehen, dass dieses nicht der Fall ist."
Kennt jemand vielleicht einen besonders anschaulichen Fall, bei dem eine Parallelisierung nicht möglich ist?
-
Für viele dieser Algorithmen wurde noch kein entsprechender paralleler Algorithmus gefunden, so dass die meisten Forscher heute davon ausgehen, dass dieses nicht der Fall ist."
Kennt jemand vielleicht einen besonders anschaulichen Fall, bei dem eine Parallelisierung nicht möglich ist?
Wenn man zeigen könnte, daß es nicht möglich ist, dann müßten die Forscher nicht mehr davon ausgehen, dann wüßten sie es.
-
Für viele dieser Algorithmen wurde noch kein entsprechender paralleler Algorithmus gefunden, so dass die meisten Forscher heute davon ausgehen, dass dieses nicht der Fall ist."
Kennt jemand vielleicht einen besonders anschaulichen Fall, bei dem eine Parallelisierung nicht möglich ist?
Wenn man zeigen könnte, daß es nicht möglich ist,
Okay, korrektur: bei dem es anschaulich ist, dass eine parallele Lösung nicht so einfach zu finden ist.
-
-
Kennt jemand vielleicht einen besonders anschaulichen Fall, bei dem eine Parallelisierung nicht möglich ist?
Ein Beispiel wäre z. B. Simulation der Planetenbewegung im Gravitationsfeld mittels iterativer Zeitschritt-Verfahren (z. B. Runge-Kutta). Da für die Berechnung eines Zeitschritts jeweils das vorige Ergebnis bekannt sein muss, kann man verschiedene Zeitintervalle nicht parallel rechnen.
Parallelisieren könnte man wohl noch die Berechnung der einzelnen Zeitschritte, z. B. in dem die Berechnung der Runge-Kutta-Vektoren auf mehrere Prozesse aufgeteilt wird. Ob man damit Zeit gewinnt, hängt von Latenzzeiten bei der Datenübertragung ab; wenn alles in einen GPU-Speicher passt, sind Performance-Gewinne durchaus noch möglich.
Ein weiteres Beispiel, bei dem ich mich mit Parallelisierung schwer tun würde, sind simulierte Turingmaschinen.
MfG
Andreas