A recursão pode ser feita em paralelo? Isso faria sentido?

Digamos, estou usando um algo recursivo simples para fibonacci, que seria executado como:

fib(5) -> fib(4)+fib(3)
            |      |
      fib(3)+fib(2)|
                fib(2)+fib(1)

e assim por diante

Agora, a execução ainda será seqüencial. Em vez disso, como codificaria isso para que fib(4)e fib(3)seja calculado gerando 2 threads separados e, em seguida fib(4), 2 threads sejam gerados para fib(3)e fib(2). O mesmo para quando fib(3)é dividido em fib(2)e fib(1)?

(Estou ciente de que a programação dinâmica seria uma abordagem muito melhor para Fibonacci, apenas a usei como um exemplo fácil aqui)

(se alguém pudesse compartilhar um exemplo de código em C \ C ++ \ C #, isso seria o ideal)

Isso é possível, mas é uma péssima idéia; calcule o número de threads que você gerará ao calcular fib (16), digamos, e depois multiplique pelo custo de um thread. Threads são incrivelmente caros; fazer isso para a tarefa que você descreve é ​​como contratar um datilógrafo diferente para digitar cada personagem de um romance.

Dito isso, os algoritmos recursivos geralmente são bons candidatos à paralelização, principalmente se eles dividirem o trabalho em dois trabalhos menores que podem ser executados independentemente. O truque é saber quando parar de paralelizar.

Em geral, você deseja paralelizar apenas tarefas "embaraçosamente paralelas". Ou seja, tarefas que são computacionalmente caras e podem ser computadas independentemente . Muitas pessoas esquecem a primeira parte. Os encadeamentos são tão caros que só faz sentido criar um quando você tem uma enorme quantidade de trabalho para eles e, além disso, pode dedicar um processador inteiro ao encadeamento . Se você tiver 8 processadores, a criação de 80 threads os forçará a compartilhar o processador, diminuindo tremendamente cada um deles. É melhor fazer apenas 8 threads e permitir que cada um tenha 100% de acesso ao processador quando tiver uma tarefa paralela embaraçosa para executar.

Bibliotecas como a Task Parallel Library no .NET são projetadas para descobrir automaticamente quanto paralelismo é eficiente; considere pesquisar seu design se esse assunto lhe interessar.

A pergunta tem duas respostas, na verdade.

A recursão pode ser feita em paralelo? Isso faria sentido?

Sim, claro. Na maioria dos casos (todos?), Um algoritmo recursivo pode ser reescrito de uma maneira sem recursão, levando a um algoritmo que muitas vezes é facilmente paralelizável. Nem sempre, mas frequentemente.

Pense no Quicksort ou na iteração através de uma árvore de diretórios. Em ambos os casos, uma fila pode ser usada para armazenar todos os resultados intermediários, respectivamente. subdiretórios encontrados. A fila pode ser processada em paralelo, eventualmente criando mais entradas até que a tarefa seja concluída com êxito.

E o fib()exemplo?

Infelizmente, a função Fibonacci é uma má escolha, porque os valores de entrada dependem completamente dos resultados calculados anteriormente. Essa dependência dificulta a execução paralela se você iniciar sempre com 1e 1.

No entanto, se você precisar fazer cálculos de Fibonacci com mais frequência, pode ser uma boa idéia armazenar (ou armazenar em cache) resultados pré-calculados para evitar todos os cálculos até esse ponto. O conceito por trás é bastante semelhante às tabelas do arco-íris.

Digamos que você armazene em cache todos os 10 pares de números Fibo até 10.000. Inicie esta rotina de inicialização em um encadeamento em segundo plano. Agora, se alguém pedir o número Fibo 5246, o algoritmo simplesmente seleciona o par de 5240 e inicia o cálculo a partir desse ponto. Se o par 5240 ainda não estiver lá, aguarde.

Dessa forma, o cálculo de muitos números de fibo escolhidos aleatoriamente poderia ser feito de maneira muito eficiente e paralela, porque é muito improvável que dois threads precisem calcular os mesmos números - e mesmo assim, isso não seria um grande problema.

É claro que é possível, mas para um exemplo tão pequeno (e, de fato, para muitos que são muito maiores), a quantidade de código de controle de encanamento / simultaneidade que você precisaria escrever obscureceria o código comercial a tal ponto que não seja uma boa idéia, a menos que você realmente, realmente, precise realmente de números de Fibonacci calculados muito rapidamente.

É quase sempre mais legível e sustentável formular seu algoritmo normalmente e, em seguida, permitir que uma extensão de biblioteca / linguagem de concorrência, como TBB ou GCD, cuide de como realmente distribuir as etapas em threads.

No seu exemplo, você está calculando fib (3) duas vezes, o que leva à dupla execução de toda a fib (1) e fib (2); para números mais altos, é ainda pior.

Você provavelmente ganhará velocidade com a solução não-recursiva, mas custará muito mais recursos (processadores) do que vale a pena.

Sim pode! Meu exemplo mais simples que posso dar é imaginar uma árvore binária de números. Por alguma razão, você deseja somar todos os números em uma árvore binária. Bem, para fazer isso, você precisa adicionar valor do nó raiz ao valor do nó esquerdo / direito .... mas o próprio nó pode ser a raiz de outra árvore (uma subárvore na árvore original)
Em vez de calcular o soma da subárvore esquerda e, em seguida, a soma da direita ... adicione-as ao valor da raiz ... você pode calcular a soma da subárvore esquerda e direita em paralelo.

Um problema é que o algoritmo recursivo padrão para a função fibonacci é péssimo, pois o número de chamadas para calcular fib (n) é igual a fib (n), que é um crescimento muito rápido. Então, eu realmente me recusaria a discutir esse assunto.

Vejamos um algoritmo recursivo mais razoável, o Quicksort. Ele classifica uma matriz da seguinte maneira: Se a matriz for pequena, classifique-a usando Bubblesort, Classificação de inserção ou o que for. Caso contrário: Escolha um elemento da matriz. Coloque todos os elementos menores de um lado, todos os elementos maiores do outro lado. Classifique o lado com os elementos menores. Classifique o lado com os elementos maiores.

Para evitar recursões arbitrariamente profundas, o método usual é que a função de classificação rápida faça uma chamada recursiva para o menor dos dois lados (aquele com menos elementos) e lide com o próprio lado maior.

Agora você tem uma maneira muito simples de usar vários threads: em vez de fazer uma chamada recursiva para classificar o lado menor, inicie um thread; classifique a metade maior e aguarde o término da discussão. Mas iniciar threads é caro. Portanto, você mede quanto tempo leva para classificar n elementos, em comparação com o tempo para criar um encadeamento. A partir daí, você encontra o menor n de modo que vale a pena criar um novo encadeamento. Portanto, se o lado menor que precisa ser classificado estiver abaixo desse tamanho, você fará uma chamada recursiva. Caso contrário, você classificará a metade em um novo segmento.