Welche Hinweise gibt es, dass ein Algorithmus parallelisiert werden sollte?

Question

Meine bisherige Erfahrung hat mir gezeigt, dass die Parallelisierung eines Algorithmus selbst bei Mehrkernprozessoren nicht immer zu einer spürbaren Beschleunigung führt. Manchmal kann es sogar zu einer Verlangsamung führen. Was sind gute Anhaltspunkte dafür, dass ein Algorithmus durch Parallelisierung erheblich beschleunigt werden kann?

(Natürlich in Anbetracht der Vorbehalte gegen eine vorzeitige Optimierung und deren Zusammenhang mit dem Bösen)

Answer 1

Nun, wenn Sie viele Sperren brauchen, damit es funktioniert, dann ist es wahrscheinlich einer dieser schwierigen Algorithmen, die sich nicht gut parallelisieren lassen. Gibt es einen Teil des Algorithmus, der in separate Teile aufgeteilt werden kann, die sich nicht berühren müssen?