Grenzen des Parallel Computing

21

Ich bin im weitesten Sinne neugierig auf das, was über Parallelisierungsalgorithmen in P bekannt ist. Ich habe den folgenden Wikipedia-Artikel zu diesem Thema gefunden:

http://en.wikipedia.org/wiki/NC_%28complexity%29

Der Artikel enthält folgenden Satz:

Es ist nicht bekannt, ob NC = P ist, aber die meisten Forscher vermuten, dass dies falsch ist, was bedeutet, dass es wahrscheinlich einige handhabbare Probleme gibt, die "von Natur aus sequentiell" sind und durch Parallelität nicht signifikant beschleunigt werden können

Hört sich das vernünftig an? Gibt es bekannte Fälle, in denen ein Problem in P nicht durch Parallelität beschleunigt werden kann?

Vladimir Levin
quelle
Ja, das klingt vernünftig. Ein Kapitel in dem Buch Computational Complexity von Papadimitriou gibt eine gute Erklärung, um dieses Thema zu lernen.
Tsuyoshi Ito

Antworten:

17

Es ist nicht einmal bekannt, ob NC = P ist, aber P-vollständige Probleme scheinen von Natur aus schwer zu parallelisieren zu sein. Dazu gehören Linear Programming und Horn-SAT. (Im Gegensatz dazu scheinen Probleme in NC einigermaßen leicht zu parallelisieren zu sein.)

Siehe Frage Probleme zwischen NC und P: Wie viele wurden aus dieser Liste gelöst? Hier finden Sie Referenzmaterial (einschließlich Links zu einem klassischen Lehrbuch, das jetzt kostenlos heruntergeladen werden kann) und weitere Informationen zu Problemen, die in P enthalten sind, von denen jedoch nicht bekannt ist, dass sie parallelisiert werden können.

Siehe Frage Verallgemeinertes Ladner-Theorem zur Struktur der Komplexitätsklassen zwischen NC und P. Kurz gesagt, wenn sie sich unterscheiden, gibt es unendlich viele Komplexitätsklassen, die streng zwischen NC und P liegen.

Siehe Frage NC = P Konsequenzen? für eine nette Demonstration von Ryan Williams, dass es möglich ist, Zusammenbrüche in der Hierarchie von Komplexitätsklassen innerhalb von P in vielleicht unwahrscheinlichere Zusammenbrüche wie PSPACE = EXP zu verstärken .

Es ist erwähnenswert, dass eine Konsequenz der P-Vervollständigung von Horn-SAT und der obigen Links darin besteht, dass es nicht möglich zu sein scheint, allgemeine SQL-Abfragen in Datenbanken zu parallelisieren, es sei denn, wir können eine umfangreiche Berechnung nur für die Verwendung umschreiben eine angemessene Menge an Speicher. Dies ist eine rätselhafte Diskrepanz - ich denke, es ist ziemlich unumstritten, zu behaupten, dass es Einschränkungen bei der Komprimierung gibt , aber ich sehe oft Artikel, die auf der Annahme beruhen , dass es möglich ist, jede Datenbankabfrage zu parallelisieren .

András Salamon
quelle
Möglicherweise können Sie einen bestimmten Teil einer Datenbankabfrage nicht oder nur unkompliziert parallelisieren. Eine Datenbankabfrage (mit Ausnahme von Unterabfragen zur Vereinfachung) kann jedoch auf einen vollständigen Tabellenscan über einer verknüpften Tabelle reduziert werden, und diese verknüpfte Tabelle selbst kann immer parallel gescannt werden. Wenn Sie die Parallelitätseinstellungen in Oracle erhöhen, werden daher eher vollständige Tabellenscans als Indizes verwendet.
sclv
@sclv: Das ist wahr, aber im Allgemeinen können die Zwischenverknüpfungen in der Eingabegröße exponentiell sein. Man kann also über Joins parallelisieren, allerdings auf Kosten einer exponentiellen Anzahl von Tupeln.
András Salamon
1
Was halten Sie von der Eingabegröße hier? Auch, wenn Sie einen m haben n o Quer kommt, gibt es immer die Möglichkeit , dass Sie genau zurückkehren können , dass viele Tupel - also dort auf der Worst-Case - gebunden nicht möglich ist besser. Und das ist praktischer als theoretisch, aber im Allgemeinen machen Sie sich keine Sorgen über die Parallelisierung der Leistung eines Prädikats über eine Zeile, sondern über den E / A-Durchsatz, da hier die Grenze in der Regel liegt.
sclv
10

Wenn es bekannte Fälle gäbe, könnten wir P und NC trennen. Es gibt jedoch viele Probleme, von denen bekannt ist, dass sie P-vollständig sind (dh unter logarithmischen Raumverkürzungen), und sie stellen die gleichen Hindernisse für die Darstellung von P = NC dar wie NP-vollständige Probleme für P = NP. Darunter fallen lineare Programmierung und Anpassung (und maximale Flüsse im Allgemeinen).

Ketan Mulmuley bewies bereits 1994 eine Trennung zwischen P und einer schwachen Form von NC (ohne Bitoperationen). In gewissem Sinne setzt sein aktuelles Programm für P vs NP dort an, wo es aufgehört hat ( auf sehr lockere Weise ).

Das Buch ' Limits on Parallel Computation ' enthält mehr dazu.

Suresh Venkat
quelle
2
In acht nehmen. Ich denke nicht, dass Matching P-vollständig ist. Es ist bekannt, dass das Matching in RNC durch Polynomidentitätstests erfolgt (testen Sie, ob die Determinante der Tutte-Matrix des Graphen identisch Null ist). Wenn es P-vollständig wäre, würde der unwahrscheinliche Kollaps P = RNC folgen.
Slimton
argh. Du hast recht. Ich hätte mich an Max Flows halten sollen. danke für die Korrektur.
Suresh Venkat
0

Ich beantwortete die ähnliche Frage. Gibt es bekannte Probleme / Algorithmen im wissenschaftlichen Rechnen, die durch Parallelisierung auf der Computational Science- Site nicht beschleunigt werden können? Lassen Sie es mich hier zitieren, weil es eine praktische Perspektive auf ein sehr konkretes Beispiel eines solchen Problems bietet:

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