Parallelizzazione OpenMP su una funzione ricorsiva

Question

Sto provando a utilizzare la parallelizzazione per migliorare la frequenza di aggiornamento per disegnare una scena 3D con oggetti ordinati gerarchicamente. L'algoritmo di disegno della scena attraversa prima in modo ricorsivo l'albero degli oggetti, e da ciò costruisce una serie ordinata di dati essenziali necessari per disegnare la scena. Quindi attraversa quell'array più volte per disegnare oggetti/sovrapposizioni, ecc. Poiché da quello che ho letto OpenGL non è un'API thread-safe, presumo che il codice di attraversamento/disegno dell'array debba essere fatto sul thread principale, ma io Sto pensando che potrei essere in grado di parallelizzare la funzione ricorsiva che riempie l'array. Il problema è che l'array deve essere popolato nell'ordine in cui gli oggetti si verificano nella scena, quindi tutte le funzionalità che associano un determinato oggetto con un indice di matrice devono essere eseguite nell'ordine corretto, ma una volta che l'indice dell'array è stato assegnato, Posso riempire i dati di quell'elemento dell'array (che non è necessariamente un'operazione banale) usando i thread worker. Quindi ecco lo pseudo-codice che sto cercando di ottenere. Spero che tu abbia l'idea della 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 utilizzando OpenMP e, in caso affermativo, come? Ci sono altre librerie di parallelizzazione che gestiscono meglio questo?

Addendum: In risposta a Davide's request for more clarification, vorrei spiegarmi un po 'più in dettaglio. Diciamo che la scena è ordinato 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, ognuno di questi oggetti ha un sacco di dati ad esso associati, vale a dire i parametri di posizione, rotazione, dimensioni, disegno diverso, 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. In ogni caso, 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 una matrice unidimensionale, e quindi tutti i dati effettivi il disegno passa solo guardando l'array. Il problema è che, poiché ho bisogno di fare push/pop OpenGL nell'ordine corretto, l'array deve essere nell'ordine di ricerca profondità-primo appropriato che è rappresentativo della gerarchia dell'albero. Nell'esempio sopra, la matrice 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 della matrice deve essere serializzata correttamente, ma una volta che ho assegnato quello ordinare correttamente, posso parallelizzare il riempimento della matrice. Ad esempio, dopo aver assegnato Frame bicicletta all'indice 0 e Handle Bars all'indice 1, un thread può occupare il riempimento dell'elemento array per il Bicycle Frame, mentre un altro prende il riempimento dell'elemento array per Handle Bars.

OK, penso che nel chiarire questo, ho risposto alla mia stessa domanda, quindi grazie Davide. Quindi ho pubblicato il mio answer.

Answer 1

Ecco un 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

per parallelizzare il thread figlio, è sufficiente mettere un pragma prima del ciclo: fatto

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

lavoro.

Ora, hai perfettamente ragione, non è possibile ottenere una libreria di threading prima di un altro in un modo completamente parallelo (ovviamente!), E openMP non ha una funzione 'lock' o 'wait' ha una parola chiave 'wait for all to finish' - Barrier), non è progettato per emulare una libreria di thread, ma consente di memorizzare valori "al di fuori" della sezione parallela e di contrassegnare alcune sezioni come 'single threaded only' (Parola chiave ordinata) in modo che questo possa aiutare a assegnare gli indici in un ciclo parallelo mentre altri thread stanno assegnando gli elementi.

Dai un'occhiata a getting started guide.

Se si utilizza Visual C++, è inoltre necessario impostare il flag/omp nelle impostazioni di compilazione del compilatore.

Answer 3

penso che si dovrebbe chiarire meglio la tua domanda (ad esempio, che cosa esattamente deve essere fatto in serie e perché)

OpenMP (come molte altre librerie di parallelizzazione) fa non garantisce l'ordine in cui le varie sezioni parallele sarà eseguiti, e poiché sono veramente paralleli (su una macchina multicore) ci potrebbero essere condizioni di gara se diverse sezioni scrivono gli stessi dati. Se questo è ok per il tuo problema, sicuramente puoi usarlo.

Answer 4

Come gbjbaanb mentioned, è possibile farlo facilmente - richiede solo un'istruzione pragma per parallelizzare questo.

Tuttavia, ci sono alcune cose da guardare fuori per:

In primo luogo, si parla che l'ordine è crutial qui. Se è necessario mantenere gli ordini per appiattire una struttura gerarchica, la parallelizzazione (a questo livello) sarà problematica. Probabilmente perderai completamente il tuo ordine.

Inoltre, la parallelizzazione delle funzioni ricorsive presenta molti problemi. Prendiamo un caso estremo - diciamo che hai una macchina dual core, e hai un albero in cui ogni nodo "genitore" ha 4 figli. Se l'albero è profondo, molto rapidamente "sovrapponi" il problema, in genere peggiorando le cose, non migliorando le prestazioni.

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

Da quello che lei ha citato, avrei lasciato questa porzione di serie, e concentrarsi invece del secondo in cui si parla:

"Allora attraversa tale matrice più volte per disegnare oggetti/sovrapposizioni, ecc"

Sembra un luogo ideale per il parallelismo.