Parallele Algorithmen für gerichtete St-Konnektivität

13

Chong, Han und Lam zeigten, dass mit O ( m + n ) -Prozessoren ungerichtete st-Konnektivität auf dem EREW-PRAM in -Zeit gelöst werden kann . Was ist der bekannteste parallele Algorithmus für gerichtete st-Konnektivität ? Bitte geben Sie die Laufzeit, den deterministischen / randomisierten Algorithmus und das verwendete PRAM-Modell an (unter der Annahme, dass die Anzahl der Prozessoren polynomiell ist). Gibt es o ( log 2 n ) zeitparallele Algorithmen, die für spezielle Fälle gerichteter st-Konnektivität bekannt sind?O(logn)O(m+n)o(log2n)

Shiva Kintali
quelle
Laut Wikipedia ist Poly (n) -Prozessoren + Polylog-Zeit auf einem EREW-PRAM identisch mit NC. Ich bin nicht sehr vertraut mit dem EREW PRAM-Modell, aber gibt es eine Verbindung zwischen Zeit (und polynomiell vielen Prozessoren) und N C i ? Mit anderen Worten, gibt es eine Möglichkeit, Ihre Frage in Bezug auf Schaltkreise mit begrenzter Tiefe neu zu formulieren? (logn)iNCi
Robin Kothari
Die verschiedenen parallelen RAM-Modelle sind bis auf die Protokollfaktoren äquivalent. Während also EREW PRAM mit NC übereinstimmt, gilt dies möglicherweise nicht für bestimmte Protokollleistungen.
Suresh Venkat
Bei entsprechenden Einschränkungen des Befehlssatzes ist die O-Zeit (Anmeldezeit) auf einem CRCW-PRAM für i> = 1 genau gleich.
Kristoffer Arnsfelt Hansen
Wenn es ein gerichtet ist Weg ist es möglich , sie zu finden? st
Kumar

Antworten:

13

Die gerichtete st-Erreichbarkeit kann leicht unter Verwendung von O ( ) -Prozessoren und O ( log n ) -Zeit auf einem CRCW-PRAM oder in O ( n ω ) -Prozessoren und O ( log 2 n ) -Zeit auf einem EREW-PRAM mit ω erfolgen < 2.376 ist der Matrixmultiplikations-Exponent und n ist die Anzahl der Eckpunkte. Die folgenden Papier Ansprüche O ( n ω ) und O ( log nn3(lognnωlog2nω<2.376nnωlogn) Zeit auf einem CREW-PRAM: "Optimale Parallelalgorithmen für Transitive Closure und Punktlokalisierung in planaren Strukturen" von Tamassia und Vitter. Andere Veröffentlichungen behaupten dasselbe und zitieren die Umfrage von Karp und Ramachandran (Parallelalgorithmen für Maschinen mit gemeinsamem Speicher, in: J. van Leeuwen (Hrsg.), Handbook of Theoretical Computer Science). In der Umfrage selbst wird erwähnt, dass der transitive Abschluss in AC1 vorliegt und daher in O (log n) auf einem CRCW-PRAM gelöst werden kann, aber der Teil über CREW-PRAM fehlt.

Alle Strassen-ähnlichen Algorithmen für die Matrixmultiplikation (einschließlich der von Coppersmith-Winograd) sind im Wesentlichen parallele Algorithmen, die in O -Zeit ausgeführt werden. Beim transitiven Schließen wird ein zusätzliches Protokoll erstellt (wenn Sie jedoch das unbegrenzte Auffächern der trivialen O ( n 3 ) -Matrix zulassen, kann mult in konstanter Tiefe ausgeführt werden, sodass die Erreichbarkeit auf einem CRCW-PRAM in O ( log n ) -Zeit erfolgt). Es ist ein offenes Problem, die Anzahl der Prozessoren von der derzeit besten zu verbessern ~ n 2.376 ; Es ist auch ein großes offenes Problem, wenn die Erreichbarkeit in NC1 liegt, da dies unter anderem L = NL implizieren würde.(logn)n3(logn)n2.376

virgi
quelle
1
Können Sie bitte die Referenzen hinzufügen.
Shiva Kintali
Ich kenne nur die O (log n) -Zeit in einem CRCW-PRAM. War es das, was du meintest?
Kristoffer Arnsfelt Hansen
O (logn) bei CREW ist großartig. Das ist, wonach ich suche. Ich möchte Ihre Antwort annehmen. Bitte geben Sie die Referenz an.
Shiva Kintali
Wir brauchen O (logn) -Iterationen der Matrixmultiplikation, um die st-Konnektivität zu lösen.
Shiva Kintali
In Bezug auf parallele Algorithmen benötigen Sie O (log n) -Iterationen der Matrix mult, um die Erreichbarkeit zu lösen. Dies ist bei sequentiellen Algorithmen nicht der Fall, da Sie einige clevere rekursive Dinge ausführen können (siehe Fisher & Meyer'71). Wenn Ihr Berechnungsmodell jedoch ein unbegrenztes Fan-In (wie bei AC1 und damit CRCW PRAM) zulässt, kann matrix mult in konstanter Tiefe ausgeführt werden, sodass das transitive Schließen in logarithmischer Tiefe ausgeführt werden kann.
Virgi
7

Das Buch "Eine Einführung in parallale Algorithmen" von Joseph Jája (1992) listet die folgenden Ergebnisse für den transitiven Abschluss auf:

  • O(logn)O(n3logn)
  • O(log2n)O(nωlogn)

O(logn)

  • uvuv
Kristoffer Arnsfelt Hansen
quelle
Es scheint also ein offenes Problem zu sein, in CREW PRAM einen o (log ^ 2 {n}) -Zeitparallelalgorithmus für allgemein gerichtete Graphen zu finden.
Shiva Kintali
Beachten Sie, dass ich o (log ^ 2 {n}) nicht O (log ^ 2 {n}) sagte.
Shiva Kintali
5

Ist es Ihnen ein Anliegen, die Arbeit nicht nur polynomisch, sondern auch klein zu halten? Es gibt einen eleganten Algorithmus von Ullman und Yannakakis, der Zeit- und Arbeitskompensationen ermöglicht. Tabelle 1 in meinem Artikel über die parallele Berechnung stark verbundener Komponenten fasst die mir bekannten Ergebnisse der parallelen gerichteten Konnektivität zusammen: http://www.cs.brown.edu/~ws/papers/scc.pdf .

Warren Schudy
quelle