Devo usar threading e recursão juntos?

Question

I foram mexer com árvores BSP para um tempo e agora estou jogando também com threads. Ao adicionar um triângulo a uma árvore BSP, surja uma oportunidade de criar um novo segmento para fins de processamento de dados em paralelo.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = plane_split(triangle, bspnode)

    insert(frontpiece, bspnode.front)
    insert(backpiece, bspnode.back)
  }
  ....
}

As duas operações de inserção acima poderia ser executado por dois threads, e desde que não modifique os mesmos dados, sincronização barato pode ser usado.

insert(triangle, bspnode)
{
  ....
  else if(triangle spans bspnode)
  {
    (frontpiece, backpiece) = split(triangle, bspnode)

    handle = beginthread(insert(backpiece, bspnode.front))
    insert(frontpiece, bspnode.back)
    if(handle)
    {
      waitforthread(handle)
    }
    else
    {
      insert(backpiece, bspnode.front)
    }
  }
  ....
}

Este método novas tentativas de criar um thread para concluir a operação em paralelo, mas não deve falhar se o segmento não pode ser criado (ele vai simplesmente reverter para o algoritmo original).

Esta é uma prática de programação de som, ou estou usando segmentos de forma inadequada? Eu não tenho sido capaz de encontrar qualquer literatura sobre esta técnica. Eu gosto que ele tende a usar o meu CPU para a sua plenitude (2 núcleos), e, teoricamente, se adaptar a todos número de processadores disponíveis. Eu não gosto que poderia ser terrivelmente desperdício na CPU e memória.

Answer 1

Threads são grandes, se alguma parte do processamento está à espera de algo externo (entrada do usuário, I / O, algum outro processamento) - o segmento que está esperando pode continuar a esperar, enquanto um segmento que não está esperando forjas adiante .

No entanto, para tarefas de processamento intensivo, mais tópicos do que os processadores realmente cria sobrecarga. Parece que seus tópicos estão fazendo todo o "trabalho CPU", então eu ficar com um thread por core -. Teste para descobrir o número ideal, embora

A maior sobrecarga criado é de troca de contexto (congelamento uma thread e carregar o contexto de execução do próximo), bem como erros de cache quando tópicos estão fazendo tarefas com memória diferente (se o thread pode usar o cache da CPU de forma eficaz) .

Answer 2

a sua melhor aposta seria a criação de um pool de threads e, em seguida, usá-lo 'transparente' para adicionar nós.

por exemplo, criar 2 linhas no início do programa, tê-los esperar em um semáforo ou evento. Quando você tem os nós para adicionar, você estourar os dados em uma fila, em seguida, acionar o semáforo. Este acorda um dos fios que aparece os dados da fila e executa o processamento. (Certifique-se o acesso à fila é threadsafe - totalmente sincronizado com uma seção crítica é melhor)

.

O desempenho global do seu aplicativo é mais lento do que você tem mais sobrecarga, em copiar os dados para a fila e executar os fios extras, mas se você usou para executar em um único núcleo, agora será executado em 2. Ele funciona melhor se o processamento de rosca é caro.

Answer 3

Claro, por exemplo, Quicksort podem ser programados vários segmentos com bastante facilidade e obter algumas grandes ganhos de desempenho em sistemas multi-core, e algumas pequenas perdas de desempenho em matéria de não-multithreaded. Basta lembrar que você está adicionando sobrecarga duas vezes agora - uma vez para a pilha de economia na recursão e uma vez no segmento, por isso, se você está fazendo um grande número de recursions então ele poderia sobrecarregar um sistema mais rápido do que uma abordagem não-multithreaded.