paralelização OpenMP em uma função recursiva

Question

Eu estou tentando usar paralelização para melhorar a taxa de atualização para desenhar uma cena 3D com objetos heirarchically encomendados. O algoritmo de desenho primeira cena de forma recursiva percorre a árvore de objetos e, a partir disso, cria uma matriz ordenada de dados essenciais que é necessário para desenhar a cena. Em seguida, ele atravessa essa matriz várias vezes para desenhar objetos / sobreposições, etc. Desde de que eu li OpenGL não é uma API thread-safe, eu assumo a matriz transversal / código de desenho deve ser feito no segmento principal, mas eu 'm pensando que eu poderia ser capaz de paralelizar a função recursiva que preenche o array. O problema principal é que a matriz deve ser preenchida na ordem em que os objectos ocorrer na cena, de modo que todas as funcionalidades que associa um dado objecto com um índice de matriz deve ser feita na ordem adequada, mas uma vez que o índice de matriz tem sido atribuído, eu pode preencher os dados daquele elemento de matriz (que não é necessariamente uma operação trivial) utilizando segmentos de trabalho. Então, aqui está o código pseudo que eu estou tentando chegar. Eu espero que você começa a idéia da sintaxe fio xml-ish.

recursivepopulatearray(theobject)
{
  <main thread>
  for each child of theobject
  {
     assign array index
     <child thread(s)>
       populate array element for child object
     </child thread(s)>
     recursivepopulatearray(childobject)
  }
  </main thread>
}

Assim, é possível fazer isso usando OpenMP, e se sim, como? Existem outras bibliotecas de paralelização que iria lidar com isso melhor?

Adenda: Em resposta a Davide pedido de mais esclarecimentos , deixe-me explicar um pouco mais em detalhe. Vamos dizer que a cena é ordenado como este:

-Bicycle Frame
  - Handle Bars 
  - Front Wheel
  - Back Wheel
-Car Frame
  - Front Left Wheel
  - Front Right Wheel
  - Back Left Wheel
  - Back Right Wheel

Agora, cada um desses objetos tem muitos dados associados a ele, ou seja, localização, rotação, tamanho, diferentes parâmetros de desenho, etc. Além disso, eu preciso fazer várias passagens sobre esta cena para desenhá-lo corretamente. Uma passagem desenha as formas dos objetos, uma outra passagem desenha texto que descreve os objetos, uma outra passagem chama conexões / associações entre os objetos, se houver algum. De qualquer forma, obter todos os dados de desenho fora destes objetos diferentes é bastante lento se eu tiver para acessá-lo várias vezes, então eu decidi usar uma passagem para armazenar em cache todos os dados em uma matriz unidimensional, e depois todas as reais desenho passes basta olhar para a matriz. O problema é que, porque eu preciso fazer empurra OpenGL / pops na ordem certa, a matriz deve ser na ordem de pesquisa em profundidade adequada, que é representante da hierarquia árvore. No exemplo acima, a matriz deve ser ordenados como se segue:

index 0: Bicycle Frame
index 1: Handle Bars 
index 2: Front Wheel
index 3: Back Wheel
index 4: Car Frame
index 5: Front Left Wheel
index 6: Front Right Wheel
index 7: Back Left Wheel
index 8: Back Right Wheel

Assim, a ordem da matriz deve ser serializado corretamente, mas uma vez eu ter atribuído que encomendar corretamente, eu posso paralelizar o preenchimento da matriz. Por exemplo, uma vez eu atribuído Armação de Bicicleta para indexar 0 e guidão para o índice 1, um thread pode tomar o enchimento do elemento da matriz para o quadro de bicicleta enquanto outro leva o enchimento do elemento de matriz para guidão.

OK, eu acho que em esclarecer isso, eu respondi minha própria pergunta, por isso obrigado Davide. Então, eu postei minha própria resposta .

Answer 1

Aqui está uma peça modificada do pseudo-código que deve funcionar.

populatearray(thescene)
{
  recursivepopulatearray(thescene)

  #pragma omp parallel for
  for each element in array
    populate array element based on associated object
}

recursivepopulatearray(theobject)
{
  for each childobject in theobject
  {
     assign array index and associate element with childobject
     recursivepopulatearray(childobject)
  }
}

Answer 2

Eu acho que você deve esclarecer melhor a sua pergunta (por exemplo, o que exatamente deve ser feito em série e por que)

OpenMP (como muitas outras bibliotecas de paralelização) faz não garantir a ordem em que as várias seções paralelas será executado, e uma vez que eles são verdadeiramente paralelos (em uma máquina multicore) pode haver condições de corrida se diferentes seções escrever os mesmos dados. Se isso é ok para o seu problema, certamente você pode usá-lo.

Answer 3

Como gbjbaanb mencionado , você pode fazer isso facilmente - requer apenas uma declaração pragma para paralelizar este

.

No entanto, existem algumas coisas que atente para:

Primeiro, você menciona que a ordem é crutial aqui. Se você precisar preservar ordenação em achatamento uma estrutura hierárquica, paralelização (a este nível) vai ser problemático. É provável que você vai perder completamente a sua ordenação.

Além disso, paralelização funções recursivas tem muitos problemas. Tome um caso extremo - dizer que você tem uma máquina dual core, e você tem uma árvore onde cada nó "pai" tem 4 filhos. Se a árvore é profunda, você muito, muito rapidamente "over-parallelize" o problema, normalmente tornando as coisas piores, não melhores, desempenho sábio.

Se você estiver indo para fazer isso, você provavelmente deve colocar um parâmetro de nível, e só paralelizar o primeiro par de níveis. Pegue a minha 4 exemplo filho por pai, se você paralelizar os 2 primeiros níveis, você já está quebrando isso em 16 pedaços paralelos (chamados a partir de 4 pedaços paralelas).

Do que você mencionou, eu deixaria esta parte de série, e concentrar-se em vez do segundo, onde você menciona:

"Em seguida, ele atravessa essa matriz várias vezes para desenhar objetos / sobreposições, etc."

Isso soa como um lugar ideal para paralelizar.

Answer 4

a complementar o segmento infantil, basta colocar um pragma antes do loop:

#pragma omp parallel for
for (i=0; i < elements; i++) 
{
}

feito Job.

Agora, você está certo você não pode obter qualquer biblioteca de threading para fazer um pouco antes de outro de uma forma totalmente paralela (obviamente!), E não OpenMP não tem um 'lock' ou recurso 'espera' (que faz ter um 'esperar para que todos possam finish' palavra-chave - Barreira), não é projetado para emular uma biblioteca de threads, mas permite que você armazene valores "fora" da seção paralela, e para marcar determinadas seções como 'única rosca única' ( palavra-chave ordenada) então isso pode ajudá-lo para atribuir os índices em um loop paralelo, enquanto outros segmentos estão atribuindo elementos.

Dê uma olhada em um guia de iniciação .

Se você estiver usando Visual C ++, você também precisa definir o sinalizador / omp em suas configurações de compilação do compilador.