Komplexität durch Parallelität reduzieren

10

Ist es möglich (Schrägstrich können Sie ein Beispiel angeben), die Rechenkomplexität eines Problems durch Verwendung eines parallelen Algorithmus zu reduzieren, für den im Verhältnis zur Eingabegröße keine Anzahl von Prozessoren erforderlich ist?

cc.complexity-theory dc.parallel-comp Nick Larsen
quelle
Könnten Sie Ihre Frage etwas klären? Trivial konstante Anzahl von Prozessoren -> bestenfalls können Sie die Laufzeit um einen konstanten Faktor verbessern. Ich denke das war nicht was du meinst?
Jukka Suomela
"Nicht relativ zur Eingabegröße". Was meinst du genau damit? O (1)?
Aryabhata
Ich meine O (1) Prozessoren. @Jukka: Das meine ich. Kann die Komplexität der Berechnungen nur durch Hinzufügen einer Anzahl von Prozessoren im Verhältnis zur Eingabegröße reduziert werden?
Nick Larsen

Antworten:

12

Wenn Sie O (1) -Prozessoren meinen, kann die Rechenkomplexität nicht reduziert werden.

Richten Sie einfach die von jedem Prozessor geleistete Arbeit aus und erledigen Sie sie auf einem einzigen. Wenn Sie sich Sorgen um die Synchronisation machen, kann ein Prozessor dies problemlos emulieren.

Aryabhata
quelle
Danke für die schnelle Antwort. Ist es möglich, die Rechenkomplexität mithilfe einer Reihe von Prozessoren im Vergleich zu etwas anderem als der Eingabegröße zu reduzieren, ohne eine weitere Frage für etwas so eng Verwandtes zu erstellen?
Nick Larsen
2
@ Nick: Etwas anderes als die Eingabegröße ist O (1) :-)
Aryabhata
Danke, ich hatte Probleme, an etwas anderes zu denken, aber ich wollte sicher sein.
Nick Larsen
WRT Ob Sie mit einer Reihe von Prozessoren eine Beschleunigung erzielen können, die mit einer anderen Menge als der Eingabegröße wächst, bin ich mir nicht sicher, ob die Antwort "Nein" lautet. Es gibt Probleme, deren Komplexität mit einem Parameter zunimmt, der sich von der Eingabegröße unterscheidet (obwohl er offensichtlich nicht unabhängig von dieser ist). Was wäre, wenn ich Ihnen bei einem Diagrammproblem eine Reihe von Prozessoren erlauben würde, die sich beispielsweise auf die Baumbreite des Diagramms beziehen?
Aaron Roth
@ Aaron: Wenn die Anzahl der zulässigen Prozessoren irgendwie mit der Eingabe zusammenhängt, können wir nicht mit Sicherheit "Nein" sagen. Natürlich ist es eine bedeutungslose Frage, es sei denn, wir sind spezifisch.
Aryabhata
6

Es gibt ein aufstrebendes Feld grobkörniger paralleler Algorithmen, bei dem die Laufzeit (und der sonstige Rechenressourcenverbrauch) als Funktion der unabhängigen Parameter n (Eingabegröße) und p (Anzahl der Prozessoren) betrachtet werden, häufig unter der natürlichen Annahme n >> p .

Ein guter Ausgangspunkt ist Google für "Bulk-Synchronous Parallelity".

Alexander Tiskin
quelle
Kann sich die Komplexitätsklasse ändern, wenn Sie zulassen, dass die Hardware mit den Eingabedaten skaliert? Ich habe Probleme, das als Laie zu googeln: /
Gerenuk
3

Dieses Papier könnte Sie interessieren:

Superlineare Leistung bei paralleler Echtzeitberechnung von Selim Akl.

Er liefert Beispiele für Rechenprobleme, bei denen "die sequentielle Lösung mehr als mal langsamer ist als eine parallele Lösung mit Prozessoren"; Dies geschieht durch kreative Interpretation des Konzepts eines "Rechenproblems".nnn

Mikhail Glushenkov
quelle
1

Wenn Sie die Aufgabe an Prozessoren (wobei eine Konstante ist) verteilen .ppp

O(f(n)/p)→O((1/p)f(n))→O(cf(n))→O(f(n))c=1/p

TT/p+SomeMoreTime

Aber KEINE Komplexität ändert sich.

Pratik Deoghare
quelle
1

"Sie können es nicht mit 1 Prozessor berechnen, aber Sie können mit 2 berechnen."

Dies ist nicht möglich, vorausgesetzt, beide Prozessoren sind TMs oder ein weniger leistungsfähiges Modell. Aus Wikipedia für Multi-Tape-Maschinen:

Dieses Modell scheint intuitiv viel leistungsfähiger zu sein als das Einzelbandmodell, aber jedes Mehrbandgerät, egal wie groß das k ist, kann von einem Einzelbandgerät mit nur quadratisch mehr Rechenzeit simuliert werden (Papadimitriou 1994, Thrm 2.1).

Auch für Mehrkopfmaschinen aus "Lineare Zeitsimulation von Mehrkopf-Turingmaschinen mit Kopf-Kopf-Sprüngen" von Walter J. Savitch und Paul MB Vitányi:

Das Hauptergebnis dieser Arbeit zeigt, dass man bei einer Turing-Maschine mit mehreren Lese- / Schreibköpfen pro Band, die die zusätzliche Verschiebungsoperation "Verschieben eines bestimmten Kopfes in die Position eines anderen gegebenen Kopfes" hat, effektiv einen konstruieren kann Multitape-Turing-Maschine mit einem einzigen Lese- / Schreibkopf pro Band, der sie in linearer Zeit simuliert; dh wenn die ursprüngliche Maschine in der Zeit T (n) arbeitet, dann arbeitet die Simulationsmaschine in der Zeit cT (n) für eine Konstante c.

Chazisop
quelle
Hier haben wir ein gutes Beispiel für die Kosten der Abstraktion. Echte Computer (als Implementierungen von RM) können besser parallelisiert werden als TMs.
Raphael
Wofür steht RM? Wenn das ein falscher Typ war und Sie TM meinen, stimme ich nicht zu. Multitape- / Multihead-TMs müssen sich nicht um die Prozessorkommunikation und das Amdahl-Gesetz kümmern. Außerdem sehe ich nicht, wie ein Computer eine bessere Leistung als ein Direktzugriffs-TM erzielen kann und umgekehrt, dh ich glaube, dass sie gleichwertig sind.
Chazisop
0

Vielleicht ist "parallel oder" (wenn zwei Funktionen einen Booleschen Wert zurückgeben, sagen Sie, ob eine von ihnen true zurückgibt, da einer von ihnen, aber nicht beide, möglicherweise nicht beendet werden kann) das, worüber Sie sprechen: Sie können nicht berechnen es mit 1 Prozessor, kann aber mit 2 berechnen.

Dies hängt jedoch stark davon ab, welches Rechenmodell Sie verwenden, ob Sie die Prozesse als Black Box oder als Beschreibung erhalten, die Sie selbst interpretieren können usw.

jkff
quelle
2
Dies scheint falsch zu sein, es sei denn, Sie arbeiten in einem stark eingeschränkten Modell. Ein einzelner Prozessor könnte nur die Anweisungen verschachteln, die sonst auf 2 ausgeführt würden, was höchstens zu einer Verlangsamung von 2x + O (1) führen würde. Ich denke mit "Black Box" meinst du, dass Interleaving unmöglich ist? Selbst dann, wenn Sie Black-Box-Berechnungen beenden können, die zu lange dauern, können Sie dennoch zwei Prozessoren simulieren, indem Sie die erforderliche Rechenlänge für jeden Prozess wiederholt erraten und verdoppeln.
Aaron Roth
Dies setzt jedoch voraus, dass wir Berechnungen beenden können. Ich meine, Sie können nicht parallel oder auf einem Prozessor in einem Modell arbeiten, bei dem Sie nur eine Berechnung ausführen können, bis sie abgeschlossen ist.
jkff
Jetzt verstehe ich, was Sie gemeint haben, aber ich glaube, es ist nicht vollständig. Sie können es auch nicht mit 2 berechnen. Wenn eine Maschine weiterläuft und die andere mit JA antwortet, lautet die Antwort JA. Aber was ist, wenn es NEIN zurückgibt? Sie können nicht deterministisch antworten, da Sie nicht wissen, ob die Maschine noch läuft oder feststeckt (dh das HALTING-Problem).
Chazisop