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

27

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.

RNs_Ghost
quelle
Die binäre Suche kann auch unter Berücksichtigung der Speicherhierarchie nicht beschleunigt werden (dh um einen Faktor).
3
@Anycorn Nein, links wirkender klassischer Gram-Schmidt und rechts wirkender modifizierter Gram-Schmidt funktionieren parallel gut. Es gibt viele andere parallele QR-Algorithmen, einschließlich des kürzlich populären TSQR.
Jed Brown
@Raphael: Ich denke, es ist möglich, die binäre Suche durch den Faktor log (n), n = # Prozessoren, zu beschleunigen. Teilen Sie das Suchintervall in n Teile, anstatt es in Teile zu unterteilen und zu prüfen, wo es fortgesetzt werden soll. Vielleicht gibt es effizientere Wege, ich weiß nicht.
miracle173

Antworten:

32

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 FallCTCTCTTNClogT 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×mT=N=O(m2) , so kann eine gewisse Parallelität vorteilhaft sein.C=m=T
  • Multigrid und FMM haben beide mit einem kritischen Pfad der Länge C =T=N .C=logT
  • 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 Nτ(0,1)dk=τ/ΔtτN1/dC=kT=kN=τ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.N1/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

Jed Brown
quelle
13

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 kannO(logcn)O(nk)P=NCPPPP C ist (obwohl dies, wie oben erwähnt, wahrscheinlich falsch ist).NCErmäßigungen. Wenn Sie zeigen , dass ein einzelner -komplette Problem in ist N C , beweisen Sie , dass P = NPNCP=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).PP

Opt
quelle
9

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.

meawoppl
quelle
3
Das "verzweigungsfreie Beispiel", das Sie angegeben haben, ist die Präfixsumme, die tatsächlich einen guten Parallelalgorithmus hat: http.developer.nvidia.com/GPUGems3/gpugems3_ch39.html Die Berechnung der Anzahl der Nullen sollte aus ähnlichen Gründen effizient sein. An der Rechenintensität führt jedoch kein Weg vorbei ...
Max Hutchinson
Cool. Darauf stehe ich korrigiert.
Meawoppl
8

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.)

Thomas Klimpel
quelle
Nettes Beispiel, aber ich glaube nicht, dass Sie eine Untergrenze beansprucht haben. Insbesondere können Multigrid-Methoden verwendet werden, um die Eikonalgleichung zu lösen. Wie bei Multigrid für Hochfrequenz-Helmholtz liegt die Herausforderung vor allem in der Gestaltung geeigneter Grobräume. Im Falle eines Labyrinths sollte eine Graphaggregationsstrategie effektiv sein, wobei die grobe Darstellung durch Lösen lokaler (also unabhängiger) Probleme für Segmente des Labyrinths bestimmt wird.
Jed Brown
Wenn sich Multigrid-Methoden gut eignen, bedeutet dies im Allgemeinen, dass die Granularität des Problems geringer ist als die Deskription, und dass der Kurslösungsschritt eine überproportionale Menge an korrekter Antwort liefert. Nur eine Beobachtung, aber die Untergrenze für solche Dinge ist schwierig!
Meawoppl
@JedBrown Aus praktischer Sicht ist das Multigrid für Hochfrequenz-Helmholtz eine ziemliche Herausforderung, im Gegensatz zu dem, was Ihr Kommentar zu implizieren scheint. Und die Verwendung von Multigrid für die Eikonalgleichung ist gelinde gesagt "ungewöhnlich". Aber ich sehe Ihren "theoretischen" Einwand gegen die vorgeschlagene Untergrenze: Zeitversätze von verschiedenen Punkten innerhalb des Labyrinths können berechnet werden, bevor die Zeit zum Erreichen dieser Punkte bekannt ist, und parallel hinzugefügt werden, nachdem die fehlenden Informationen verfügbar sind. In der Praxis sind Allzweck-Parallel-Eikonal-Löser jedoch froh, wenn sie tatsächlich nahe an die Grenze kommen.
Thomas Klimpel
Ich wollte damit nicht andeuten, dass es einfach ist. Die Wellen-Grobräume sind in der Tat sehr technisch. Aber ich denke, wir sind uns einig, dass es in offenen Regionen bereits Möglichkeiten für Parallelität gibt, während in engen "Labyrinthen" (die nur sehr wenig Parallelität mit Standardmethoden aufweisen) das Problem der Hochskalierung leichter zu lösen ist.
Jed Brown
@JedBrown Folie 39 von www2.ts.ctw.utwente.nl/venner/PRESENTATIONS/MSc_Verburg.pdf (ab 2010) sagt Dinge wie "Erweitern Sie den Löser von 2D auf 3D" und "Passen Sie die Methode an Probleme mit stark variierenden Wellenzahlen an". Wellen-Multigrid mag also vielversprechend sein, aber "noch nicht ausgereift" scheint besser geeignet zu sein als "sehr technisch", um seine aktuellen Probleme zu beschreiben. Und es ist nicht wirklich ein Hochfrequenz-Helmholtz-Löser (weil es ein "Vollwellen" -Löser ist). Es gibt andere "ausreichend ausgereifte" Mehrgitter-Helmholtz-Löser ("Vollwellen-Löser"), aber auch diese sind noch "aktive Forschung".
Thomas Klimpel
1

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.

Jakub Klinkovský
quelle