10

É possível trabalhar com recursividade de forma paralela quando se trabalha com tecnologias exclusivas para parelelismo (Multithread) usando a placa de vídeo como instrumento CUDA e OpenCL? se sim como é feito a sincronia e a passagem de valores, se não qual a forma de simularmos esta recursividade já que muitas operações em estruturas de dados como Árvores de todos os tipos usam de recursão para se obter os dados.

Cuda é uma extensão para a linguagem de programação C/C++.

OpenCL é uma arquitetura para escrever programas que funcionam em plataformas heterogêneas, inclui uma linguagem (baseada em C99) para escrever kernels (funções executadas em dispositivos OpenCL)

4
  • 3
    Qual o motivo do downvote?
    – Ricardo
    Commented 15/07/2015 às 15:08
  • Infelizmente este não é o meu forte e não sei exatamente o que queres dizer com "parelelismo" e "recursividade". No entanto me parece algo mais baixo nivel, seria C/C++?
    – Syzoth
    Commented 15/07/2015 às 18:43
  • @GuilhermeNascimento Sim, paralelismo seria multithread.
    – Ricardo
    Commented 15/07/2015 às 18:44
  • as vezes os termos em português podem soar confusos para as pessoas, a pergunta me parece boa, mas poderia revisar estes detalhes, tente não alterar muito além disto. :) +1 por me explicar os termos.
    – Syzoth
    Commented 15/07/2015 às 18:46

2 Respostas 2

4

Tecnologias SIMD (single instruction source, multiple data sources) normalmente não tem capacidade de realização assíncrona de tarefas, como no caso de funções recursivas.

Processadores típicos possuem uma quantidade razoável de memória de trabalho (registradores e CACHE) para uma quantidade pequena de CPUs (1, 2, 4 ou 8), sendo que estas CPUs atuam de forma independente, executando instruções distintas simultaneamente (MIMD - Multiple instruction sources, multiple data sources). Processadores típicos conseguem montar altas stacks de dados de instruções executadas, permitindo diversas iterações recursivas da mesma função. Pra isso, precisam de ponteiros de instrução complexos e inteligentes para guardar múltiplos pontos de retorno.

Co-Processadores SIMD, como GPGPUs, abrem mão de tais complexidades e sofisticações em prol da quantidade de unidades lógicas e aritméticas. Imagine um dispositivo que permitisse uma única pessoa apertar o mesmo botão de operação em diversas calculadoras, mesmo que pudesse digitar valores diferentes em cada uma. A mesma operação é realizada simultaneamente em diversos valores. O custo de tal aceleração é a sofisticação do sistema de leitura e interpretação das instruções, que não tem a capacidade de gerenciar diversos ponteiros de retorno necessários para o uso de recursão.

Contudo, é possível trabalhar de forma paralela em GPGPUs em funções recursivas, no caso em que a identificação de término (IF clause) e demais operações da função recursiva sejam executadas em CPU, sendo cálculos internos de cada iteração da função realizados em GPGPU, completamente alienada da origem das instruções do programa principal. Como exemplo, o pseudo-código abaixo.

function calcularDados( var dados, var localidade[])    //GPGPU
    return calcular(localidade, dados)                  //GPGPU

function souRecursiva(var dados)            //CPU
    if dados != condição_final then         //CPU
        GPGPU <<dados, calcularDados>> dadosResposta    //GPGPU
        return souRecursiva(dadosResposta)  //CPU
    else                                    //CPU
        return dados                        //CPU
-1

CUDA em suas versões mais modernas aceita recursividade de forma bem limitada. Basicamente, um kernel marcado como __global__ pode chamar outro kernel __global__, que vai ser executado em outro bloco, e esperar até que termine, mas com limite de mais ou menos 24 níveis de recursão. A memória fica coerente somente em níveis adjacentes, mas isso pode ser contornado passando a parte desejada como parâmetro. Aqui um slide da NVIDIA a respeito. Vale lembrar que, dependendo do problema ser resolvido, a recursão pode ser substituída por um loop e regras de como passar de um elemento para outro.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .