Algoritmos paralelos para conectividade st direcionada

13

Chong, Han e Lam mostraram que a conectividade st não direcionada pode ser resolvida no EREW PRAM no tempo com os processadores O ( m + n ) . Qual é o algoritmo paralelo mais conhecido para conectividade st direcionada ? Indique o tempo de execução, o algoritmo determinístico / aleatório e o modelo PRAM usado (assumindo que o número de processadores seja polinomial). Existem algoritmos paralelos no tempo ( o log 2 n ) conhecidos por casos especiais de conectividade st direcionada?O(registron)O(m+n)o(log2n)

Shiva Kintali
fonte
A Wikipedia diz que os processadores poli (n) + tempo de polilog em um EREW PRAM são os mesmos do NC. Não estou muito familiarizado com o modelo EREW PRAM, mas há uma conexão entre time (e polinomialmente muitos processadores) e N C i ? Em outras palavras, existe uma maneira de reformular sua pergunta em termos de circuitos de profundidade limitada? (registron)EuNCEu
Robin Kothari
os diferentes modelos de RAM paralela são fatores equivalentes até o log, portanto, embora o EREW PRAM corresponda a NC, isso pode não ser verdadeiro para poderes de log específicos.
Suresh Venkat
Com restrições apropriadas no conjunto de instruções, o tempo O (log ^ in) em um CRCW PRAM é exatamente uniforme AC ^ i, para i> = 1.
Kristoffer Arnsfelt Hansen
Se houver um caminho direcionado , é possível encontrá-lo? s-t
Kumar

Respostas:

13

A acessibilidade direcionada pode ser feita facilmente usando processadores O ( ) e tempo O ( log n ) em um CRCW-PRAM ou em processadores O ( n ω ) e tempo O ( n ω ) e tempo O ( log 2 n ) em um EREW-PRAM em que ω < 2,376 é a multiplicação expoente matriz e n é o número de vértices. O artigo a seguir reivindica O ( n ω ) e O ( log nn3(registronnωregistro2nω<2.376nnωregistron) em um CREW-PRAM: "Algoritmos paralelos ótimos para fechamento transitivo e localização de pontos em estruturas planares" de Tamassia e Vitter. Outros trabalhos afirmam a mesma coisa e citam a pesquisa de Karp e Ramachandran (algoritmos paralelos para máquinas de memória compartilhada, em: J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science). A própria pesquisa menciona que o fechamento transitivo está no AC1 e, portanto, pode ser resolvido em O (log n) em um CRCW-PRAM, mas falta a parte sobre o CREW-PRAM.

Todos os algoritmos do tipo Strassen para multiplicação de matrizes (incluindo o de Coppersmith-Winograd) são essencialmente algoritmos paralelos que são executados no tempo O ; o fechamento transitivo incorre em um log extra (mas se você permitir fan-in ilimitado, a trivial matriz O ( n 3 ) mult pode ser feita em profundidade constante e, portanto, a acessibilidade está no tempo O ( log n ) em um CRCW-PRAM). É um problema aberto para melhorar o número de processadores dos melhores atuais ~ n 2.376 ; também é um grande problema em aberto se a acessibilidade estiver no NC1, pois implicaria L = NL, entre outras coisas.(registron)n3(registron)n2,367

virgi
fonte
1
Você pode adicionar as referências.
Shiva Kintali
Eu só sei sobre o tempo O (log n) em um CRCW PRAM. Foi isso que você quis dizer?
Kristoffer Arnsfelt Hansen
O (logn) no CREW é ótimo. É isso que estou procurando. Eu gostaria de aceitar sua resposta. Por favor, adicione a referência.
Shiva Kintali
Precisamos de iterações O (logn) da multiplicação de matrizes para resolver a conectividade st.
Shiva Kintali 26/09/10
Em termos de algoritmos paralelos, você precisa de O (log n) iterações da matriz mult para resolver a acessibilidade; esse não é o caso de algoritmos seqüenciais, pois você pode fazer algumas coisas recursivas inteligentes (ver Fisher & Meyer'71). No entanto, se seu modelo de computação permitir fan-in ilimitado (como no AC1 e, portanto, CRCW PRAM), a matriz mult pode ser feita em profundidade constante e, portanto, o fechamento transitivo pode ser feito em profundidade logarítmica.
virgi 26/09/10
7

O livro "Uma Introdução aos Algoritmos Paralelos", de Joseph Jája (1992), lista os seguintes resultados para o fechamento transitivo:

  • O(registron)O(n3registron)
  • O(registro2n)O(nωregistron)

O(registron)

  • vocêvvocêv
Kristoffer Arnsfelt Hansen
fonte
Portanto, parece que encontrar um algoritmo paralelo no tempo (log ^ 2 {n}) no CREW PRAM para gráficos direcionados gerais é um problema em aberto.
Shiva Kintali 26/09/10
Note que eu disse o (log ^ 2 {n}) e não O (log ^ 2 {n}).
Shiva Kintali
5

Você se preocupa em manter o trabalho pequeno, não apenas polinomial; há um elegante algoritmo de Ullman e Yannakakis que permite compensações de tempo / trabalho. A Tabela 1 do meu artigo sobre computação de componentes fortemente conectados em paralelo resume os resultados da conectividade direcionada paralela que eu conheço: http://www.cs.brown.edu/~ws/papers/scc.pdf .

Warren Schudy
fonte