Gibt es bekannte Probleme / Algorithmen im wissenschaftlichen Rechnen, die durch Parallelisierung nicht beschleunigt werden können?

Gibt es bekannte Probleme / Algorithmen im wissenschaftlichen Rechnen, die durch Parallelisierung nicht beschleunigt werden können? Beim Lesen von Büchern über CUDA scheint mir, dass die meisten Dinge möglich sind.

Der zentrale Punkt ist die Länge des kritischen Pfades bezogen auf die Gesamtmenge der Berechnung T . Wenn C proportional zu T ist , bietet die Parallelität bestenfalls eine konstante Beschleunigung. Wenn C asymptotisch kleiner als T ist , besteht Raum für mehr Parallelität, wenn die Problemgröße zunimmt. Für Algorithmen, bei denen T in der Eingabegröße N polynomisch ist , ist C ∼ log T der beste Fall$C$$T$$C$$T$$C$$T$$T$$N$$C \sim \log T$ da nur sehr wenige nützliche Größen in weniger als der logarithmischen Zeit berechnet werden können.

Beispiele

• $C = T$ für eine tridiagonale Lösung unter Verwendung des Standardalgorithmus. Jede Operation hängt vom Abschluss der vorherigen Operation ab, sodass keine Möglichkeit für Parallelität besteht. Tridiagonale Probleme können in logarithmischer Zeit auf einem Parallelcomputer mit einer verschachtelten Zerlegungs-Direktlösung, einer Zerlegung von Domänen auf mehreren Ebenen oder mit Mehrfachgittern mit Basisfunktionen gelöst werden, die unter Verwendung der harmonischen Erweiterung konstruiert wurden (diese drei Algorithmen unterscheiden sich in mehreren Dimensionen, können jedoch in 1D genau zusammenfallen).
• Eine dichte untere Dreieckslösung mit einer Matrix hat T = N = O ( m 2 ) , aber der kritische Pfad ist nur C = m = $m\times m$$T = N = \mathcal O(m^2)$ , so kann eine gewisse Parallelität vorteilhaft sein.$C = m = \sqrt T$
• Multigrid und FMM haben beide mit einem kritischen Pfad der Länge C $T = N$ .$C = \log T$
• Explizite Wellenausbreitung für eine Zeit auf einer regelmäßigen Masche der Domäne ( 0 , 1 ) d erfordert k = τ / Δ t ~ τ N 1 / d Zeitschritte (für Stabilität), daher der kritische Pfad mindestens C = k . Der Gesamtarbeitsaufwand beträgt T = k N = τ N ( d + 1 ) / d / C = N , der verbleibende Faktor $\tau$$(0,1)^d$$k = \tau / \Delta t \sim \tau N^{1/d}$$C = k$$T = k N = \tau N^{(d+1)/d}$ . Die maximal mögliche Anzahl von Prozessoren ist $P = T/C = N$ kann nicht durch erhöhte Parallelität wiederhergestellt werden.$N^{1/d}$

Formale Komplexität

Die NC-Komplexitätsklasse charakterisiert diejenigen Probleme, die effizient parallel gelöst werden können (dh in polylogarithmischer Zeit). Es ist nicht bekannt , ob , aber es wird allgemein als falsch vermutet. Wenn dies tatsächlich der Fall ist, charakterisiert P-complete jene Probleme, die "inhärent sequentiell" sind und durch Parallelität nicht signifikant beschleunigt werden können.$NC = P$

Um einen theoretischen Aspekt dazu zu geben, wird $NC$ als die Komplexitätsklasse definiert, die in -Zeit auf einem System mit O ( n k ) -Parallelprozessoren lösbar ist . Es ist noch nicht bekannt , ob P = N C (obwohl die meisten Menschen vermuten , es ist nicht) , wo P die Menge der Probleme auflösbar in Polynomialzeit ist. Die "schwierigsten" Probleme, die zu parallelisieren sind, sind als P- vollständige Probleme in dem Sinne bekannt, dass jedes Problem in P über zu einem P- vollständigen Problem reduziert werden kann$O(log^c n)$$O(n^k)$$P=NC$$P$$P$$P$$P$ C ist (obwohl dies, wie oben erwähnt, wahrscheinlich falsch ist).$NC$Ermäßigungen. Wenn Sie zeigen , dass ein einzelner -komplette Problem in ist N C , beweisen Sie , dass P = $P$$NC$$P=NC$

Daher ist jedes Problem, das vollständig ist, intuitiv schwer zu parallelisieren (obwohl große Beschleunigungen immer noch möglich sind). Ein P- vollständiges Problem, für das wir nicht einmal sehr gute konstante Faktor-Beschleunigungen haben, ist die lineare Programmierung (siehe diesen Kommentar zum OR-Austausch).$P$$P$

Beginnen Sie, indem Sie Amdahls Gesetz aufgreifen . Grundsätzlich profitiert alles mit einer großen Anzahl von seriellen Schritten nur unwesentlich von der Parallelität. Einige Beispiele sind Parsing, Regex und Komprimierung mit einem hohen Verhältnis.

Abgesehen davon ist das Hauptproblem oft ein Engpass in der Speicherbandbreite. Insbesondere bei den meisten GPUs übersteigen Ihre theoretischen Flops die Menge an Gleitkommazahlen, die Sie für Ihre ALUs erhalten können, erheblich, da solche Algorithmen mit geringer arithmetischer Intensität (Flops / Cache-Miss) einen Großteil der Zeit auf RAM warten.

Schließlich ist es unwahrscheinlich, dass ein Teil des Codes, der eine Verzweigung erfordert, eine gute Leistung erbringt, da die ALU-Logik in der Regel über der Nummer liegt.

Zusammenfassend lässt sich sagen, dass ein wirklich einfaches Beispiel für etwas, das mit einer GPU nur schwer zu erreichen ist, einfach die Anzahl der Nullen in einem Array von Ganzzahlen zählt, da Sie möglicherweise häufig verzweigen müssen, um höchstens eine Operation auszuführen (inkrementieren um one) für den Fall, dass Sie eine Null finden und mindestens einen Speicherabruf pro Operation durchführen.

Ein Beispiel, das frei von dem Verzweigungsproblem ist, besteht darin, einen Vektor zu berechnen, der die kumulative Summe eines anderen Vektors ist. ([1,2,1] -> [1,3,4])

Ich weiß nicht, ob diese als "berühmt" gelten, aber es gibt mit Sicherheit eine große Anzahl von Problemen, bei denen das parallele Rechnen nicht hilft.

Die (berühmte) Methode des schnellen Marschierens zur Lösung der Eikonal-Gleichung kann nicht durch Parallelisierung beschleunigt werden. Es gibt andere Methoden (zum Beispiel Schnelldurchlaufmethoden) zum Lösen der Eikonal-Gleichung, die für eine Parallelisierung besser geeignet sind, aber auch hier ist das Potenzial für eine (parallele) Beschleunigung begrenzt.

Das Problem mit der Eikonal-Gleichung ist, dass der Informationsfluss von der Lösung selbst abhängt. Die Informationen fließen grob gesagt entlang der Eigenschaften (dh Lichtstrahlen in der Optik), aber die Eigenschaften hängen von der Lösung selbst ab. Der Informationsfluss für die diskretisierte Eikonal-Gleichung ist sogar noch schlechter und erfordert zusätzliche Näherungen (wie sie implizit bei Schnelldurchlaufmethoden vorhanden sind), wenn eine parallele Beschleunigung gewünscht wird.

Um die Schwierigkeiten bei der Parallelisierung zu erkennen, stellen Sie sich ein schönes Labyrinth vor, wie in einigen Beispielen auf Sethians Webseite . Die Anzahl der Zellen auf dem kürzesten Weg durch das Labyrinth ist (wahrscheinlich) eine Untergrenze für die minimale Anzahl von Schritten / Iterationen eines (parallelen) Algorithmus, der das entsprechende Problem löst.

(Ich schreibe "(wahrscheinlich) ist", weil Untergrenzen notorisch schwer zu beweisen sind und oft einige vernünftige Annahmen über die von einem Algorithmus verwendeten Operationen erfordern.)

Eine andere Klasse von Problemen, die in der Praxis schwer zu parallelisieren sind, sind Rundungsfehler, bei denen die numerische Stabilität durch Serialisierung erreicht wird.

Betrachten Sie beispielsweise den Gram-Schmidt-Prozess und seine serielle Modifikation. Der Algorithmus arbeitet mit Vektoren, so dass Sie möglicherweise parallele Vektoroperationen verwenden, dies ist jedoch nicht gut skalierbar. Wenn die Anzahl der Vektoren groß und die Vektorgröße klein ist, ist die parallele klassische Gram-Schmidt-Methode und die Reorthogonalisierung möglicherweise stabil und schneller als die einzelne modifizierte Gram-Schmidt-Methode, obwohl sie mehr als ein Vielfaches an Arbeit erfordert.