Algorytmy równoległe dla ukierunkowanej łączności st

Chong, Han i Lam pokazali, że nieukierunkowaną łączność st można rozwiązać na EREW PRAM w czasie z procesorami . Jaki jest najbardziej znany algorytm równoległy dla ukierunkowanej łączności st ? Podaj czas działania, deterministyczny / randomizowany algorytm i zastosowany model PRAM (zakładając, że liczba procesorów jest wielomianowa). Czy istnieją jakieś algorytmy równoległe znane ze specjalnych przypadków ukierunkowanej łączności? $O({\log}n)$ $O(m+n)$ $o({\log}^2{n})$

dc.parallel-comp

— Shiva Kintali
źródło

Wikipedia twierdzi, że procesory poli (n) + czas polilogu w pamięci EREW PRAM są takie same jak NC. Nie znam się dobrze na modelu EREW PRAM, ale czy istnieje związek między czasem ( (a wielomianowo wieloma procesorami) a ? Innymi słowy, czy istnieje sposób na sformułowanie pytania w odniesieniu do obwodów o ograniczonej głębokości?

(\log n)^{i}

$(\log n)^i$

N C^{i}

$NC^i$

— Robin Kothari,

różne równoległe modele pamięci RAM są równoważnymi współczynnikami zapisu do dziennika, więc chociaż EREW PRAM pasuje do NC, może nie być to prawdą w przypadku określonych mocy dziennika.

— Suresh Venkat

Przy odpowiednich ograniczeniach dotyczących zestawu intruzji, czas O (log ^ in) na PRAM CRCW jest dokładnie jednorodny AC ^ i, dla i> = 1.

— Kristoffer Arnsfelt Hansen

Jeśli nie jest skierowany ścieżka, jest to możliwe, aby go znaleźć?

s - t

$s-t$

— Kumar,

Odpowiedzi:

Bezpośrednią osiągalność można łatwo osiągnąć za pomocą procesorów O ( ) i czasu O ) na CRCW-PRAM lub w procesorach O ( ) i czasu O ( ) na EREW-PRAM, gdzie to wykładnik mnożenia macierzy, a to liczba wierzchołków. Poniższy artykuł zawiera oświadczenia O ( ) i O ( $n^3$ $(\log n$ $n^\omega$ $\log^2 n$ $\omega<2.376$ $n$ $n^\omega$ $\log n$ ) czas na CREW-PRAM: „Optymalne algorytmy równoległe dla przechodzenia przejściowego i lokalizacji punktów w strukturach planarnych” Tamassii i Vittera. Inne artykuły twierdzą to samo i cytują ankietę Karpa i Ramachandrana (algorytmy równoległe dla maszyn z pamięcią współdzieloną, w: J. van Leeuwen (red.), Handbook of Theoretical Computer Science). W samym badaniu wspomina się, że przechodnie przechodzenie następuje w AC1, a zatem można je rozwiązać w czasie O (log n) na CRCW-PRAM, ale brakuje części o CREW-PRAM.

Wszystkie podobne do Strassena algorytmy mnożenia macierzy (w tym algorytm Coppersmitha-Winograda) są zasadniczo równoległymi algorytmami działającymi w czasie O ; zamknięcie przechodnie pociąga za sobą dodatkowy log (ale jeśli zezwolisz na nieograniczone wachlowanie, trywialna macierz O ( ) mult może być wykonana na stałej głębokości, a więc osiągalność jest w czasie O na CRCW-PRAM). Problemem otwartym jest poprawa liczby procesorów w stosunku do obecnych najlepszych ~ ; jest to również poważny otwarty problem, jeśli osiągalność jest w NC1, ponieważ oznaczałoby to między innymi L = NL. $(\log n)$ $n^3$ $(\log n)$ $n^{2.376}$

— dziewice
źródło

Czy możesz dodać referencje.

— Shiva Kintali,

Wiem tylko o czasie O (log n) na PRAM CRCW. Czy o to ci chodziło?

— Kristoffer Arnsfelt Hansen

O (logowanie) na CREW jest świetne. Tego właśnie szukam. Chciałbym zaakceptować twoją odpowiedź. Dodaj referencję.

— Shiva Kintali

Potrzebujemy powtórzeń O (logn) mnożenia macierzy, aby rozwiązać łączność st.

— Shiva Kintali,

Jeśli chodzi o algorytmy równoległe, potrzebujesz iteracji O (log n) macierzy mult, aby rozwiązać osiągalność; nie jest tak w przypadku algorytmów sekwencyjnych, ponieważ można wykonywać sprytne rekurencyjne czynności (patrz Fisher i Meyer'71). Jeśli jednak Twój model obliczeniowy pozwala na nieograniczone wachlowanie (jak w przypadku AC1, a więc CRCW PRAM), macierz mult może być wykonana na stałej głębokości, a zatem przechodzenie na przechodzenie można wykonać na głębokości logarytmicznej.

— virgi

Książka „Wprowadzenie do algorytmów równoległych” Josepha Jáji (1992) wymienia następujące wyniki dla przechodniania:

$O(\log n)$ i działają na wspólnej pamięci CRCW. $O(n^3 \log n)$
$O(\log^2 n)$ i działają na PRAMIE ZAŁOGI. $O(n^\omega \log n)$

Jeśli chodzi o pytanie, czy dla specjalnych klas grafów znane jest coś szybszego, ćwiczenie 5.34 w książce podaje następujący przykład, w którym można uzyskać czas na PRAMIE ZAŁOGI: $O(\log n)$

Klasa ukierunkowanych wykresów acyklicznych, takich, że dla każdych dwóch wierzchołków i istnieje co najwyżej jedna ścieżka od do . $u$ $v$ $u$ $v$

— Kristoffer Arnsfelt Hansen
źródło

Wydaje się więc, że znalezienie algorytmu równoległego czasu o (log ^ 2 {n}) na PRAMIE ZAŁOGI dla ogólnych grafów kierowanych jest otwartym problemem.

— Shiva Kintali,

Zauważ, że powiedziałem o (log ^ 2 {n}), a nie O (log ^ 2 {n}).

— Shiva Kintali

Czy zależy Ci na tym, aby praca była niewielka, a nie tylko wielomianowa, istnieje elegancki algorytm Ullmana i Yannakakisa, który pozwala na kompromisy czas / praca. Tabela 1 w moim artykule na temat obliczania silnie połączonych komponentów równolegle podsumowuje równoległe wyniki łączności, o których wiem: http://www.cs.brown.edu/~ws/papers/scc.pdf .

— Warren Schudy
źródło