Parallelizzazione OpenMP su una funzione ricorsiva

Question

Sto cercando di usare la parallelizzazione per migliorare la frequenza di aggiornamento per disegnare una scena 3D con oggetti ordinati gerarchicamente. L'algoritmo di disegno di scena attraversa in modo ricorsivo l'albero degli oggetti e da ciò crea una serie ordinata di dati essenziali necessari per disegnare la scena. Quindi attraversa l'array più volte per disegnare oggetti / overlay, ecc. Dal momento che ho letto OpenGL non è un'API thread-safe, presumo che il codice di attraversamento / disegno dell'array debba essere eseguito sul thread principale, ma io sto pensando che potrei essere in grado di parallelizzare la funzione ricorsiva che riempie l'array. La chiave è che l'array deve essere popolato nell'ordine in cui si verificano gli oggetti nella scena, quindi tutte le funzionalità che associano un determinato oggetto a un indice dell'array devono essere eseguite nell'ordine corretto, ma una volta assegnato l'indice dell'array, Posso riempire i dati di quell'elemento dell'array (che non è necessariamente un'operazione banale) usando i thread di lavoro. Quindi ecco lo pseudo codice che sto cercando di ottenere. Spero che ti venga in mente la sintassi del thread 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>
}

Quindi, è possibile farlo usando OpenMP, e se sì, come? Esistono altre librerie di parallelizzazione che gestiranno meglio questo?

Addendum: in risposta a di Davide richiesta di ulteriori chiarimenti , lasciatemi spiegare un po 'più in dettaglio. Diciamo che la scena è ordinata in questo modo:

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

Ora, a ciascuno di questi oggetti sono associati molti dati, ad esempio posizione, rotazione, dimensioni, parametri di disegno diversi, ecc. Inoltre, ho bisogno di fare più passaggi su questa scena per disegnarlo correttamente. Un passaggio disegna le forme degli oggetti, un altro passaggio disegna il testo che descrive gli oggetti, un altro passaggio disegna connessioni / associazioni tra gli oggetti se ce ne sono. Ad ogni modo, ottenere tutti i dati di disegno da questi diversi oggetti è piuttosto lento se devo accedervi più volte, quindi ho deciso di utilizzare un passaggio per memorizzare tutti i dati in un array unidimensionale e quindi tutti gli effettivi passaggi di disegno basta guardare l'array. Il problema è che, poiché ho bisogno di eseguire push / pop OpenGL nell'ordine giusto, l'array deve trovarsi nell'ordine di ricerca primo in profondità appropriato, che è rappresentativo dell'erarchia dell'albero. Nell'esempio sopra, l'array deve essere ordinato come 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

Quindi, l'ordinamento dell'array deve essere serializzato correttamente, ma una volta assegnato correttamente l'ordinamento, posso parallelizzare il riempimento dell'array. Ad esempio, una volta assegnato il telaio della bicicletta all'indice 0 e i manubri all'indice 1, un thread può occupare il riempimento dell'elemento array per il telaio della bicicletta, mentre un altro prende il riempimento dell'elemento array per i manubri.

OK, nel chiarire questo, ho risposto alla mia domanda, quindi grazie Davide. Quindi ho pubblicato la mia risposta .

Answer 1

Ecco un pezzo di pseudo-codice modificato che dovrebbe funzionare.

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

Penso che dovresti chiarire meglio la tua domanda (ad es. cosa si deve fare esattamente in serie e perché)

OpenMP (come molte altre librerie di parallelizzazione) non garantisce l'ordine in cui verranno eseguite le varie sezioni parallele e poiché sono veramente parallele (su una macchina multicore) potrebbero esserci condizioni di gara se sezioni diverse scrivono gli stessi dati. Se va bene per il tuo problema, sicuramente puoi usarlo.

Answer 3

Come citato da gbjbaanb , puoi farlo facilmente - richiede solo un'istruzione pragma per parallelizzare questo.

Tuttavia, ci sono alcune cose a cui fare attenzione:

Per prima cosa, dici che qui l'ordine è cruciale. Se è necessario preservare l'ordine nell'appiattimento di una struttura gerarchica, il parallelismo (a questo livello) sarà problematico. Probabilmente perderai completamente il tuo ordine.

Inoltre, parallelizzare le funzioni ricorsive ha molti problemi. Prendi un caso estremo: supponi di avere una macchina dual core e di avere un albero in cui ogni "genitore" il nodo ha 4 figli. Se l'albero è profondo, molto, molto rapidamente "sovra parallelizzi". il problema, in genere peggiorando le cose, non meglio, dal punto di vista delle prestazioni.

Se hai intenzione di farlo, dovresti probabilmente mettere un parametro di livello e parallelizzare solo il primo paio di livelli. Prendi il mio esempio di 4 figli per genitore, se parallelizzi i primi 2 livelli, lo stai già suddividendo in 16 blocchi paralleli (chiamati da 4 blocchi paralleli).

Da quello che hai menzionato, lascerei questa parte seriale e mi concentrerò invece della seconda in cui menzioni:

" Quindi attraversa l'array più volte per disegnare oggetti / sovrapposizioni, ecc. "

Sembra un posto ideale per parallelizzare.

Answer 4

per parallelizzare il thread figlio, inserisci semplicemente un pragma prima del ciclo:

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

Lavoro svolto.

Ora, hai ragione, non puoi fare in modo che nessuna libreria di threading faccia un po 'prima dell'altra in modo completamente parallelo (ovviamente!), e openMP non ha una funzione' lock 'o' wait '(lo fa ha una parola chiave 'wait for all to finish' - Barrier), non è progettata per emulare una libreria di thread, ma ti consente di memorizzare valori " outside " la sezione parallela e per contrassegnare alcune sezioni come "solo thread singolo" (parola chiave ordinata) in modo che ciò possa aiutarti ad assegnare gli indici in un ciclo parallelo mentre altri thread assegnano elementi.

Dai un'occhiata a una guida introduttiva .

Se stai usando Visual C ++, dovrai anche impostare il flag / omp nelle impostazioni di compilazione del compilatore.