Paralelización OpenMP en una función recursiva

Question

Estoy tratando de usar la paralelización para mejorar la frecuencia de actualización para dibujar una escena 3D con objetos ordenados jerárquicamente. El algoritmo de dibujo de escenas primero recorre recursivamente el árbol de objetos y, a partir de ahí, crea una matriz ordenada de datos esenciales que se necesitan para dibujar la escena. Luego atraviesa esa matriz varias veces para dibujar objetos/superposiciones, etc. Dado que, por lo que he leído, OpenGL no es una API segura para subprocesos, supongo que el código de cruce/dibujo de la matriz debe hacerse en el hilo principal, pero Estoy pensando que podría paralelizar la función recursiva que llena la matriz. La clave es que la matriz debe rellenarse en el orden en que los objetos se encuentran en la escena, por lo que todas las funciones que asocian un objeto determinado con un índice de matriz deben realizarse en el orden correcto, pero una vez que se haya asignado el índice de matriz, Puedo completar los datos de ese elemento de matriz (que no es necesariamente una operación trivial) utilizando subprocesos de trabajo. Así que aquí está el pseudo código que estoy tratando de obtener. Espero que entiendas la sintaxis del hilo 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> 
} 

Entonces, ¿es posible hacer esto usando OpenMP, y si es así, cómo? ¿Hay otras bibliotecas de paralelización que puedan manejar esto mejor?

Adición: En respuesta a Davide's request for more clarification, permítanme explicarles un poco más en detalle. Digamos que la escena se ordena así:

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

Ahora, cada uno de estos objetos tiene una gran cantidad de datos asociados con él, es decir, los parámetros de ubicación, rotación, tamaño, dibujo diferente, etc. Además, tengo que hacer Pases múltiples sobre esta escena para dibujarla correctamente. Un pase dibuja las formas de los objetos, otro pasa dibuja texto que describe los objetos, otro pase dibuja conexiones/asociaciones entre los objetos si hay alguno. De todos modos, obtener todos los datos de dibujo de estos diferentes objetos es bastante lento si tengo que acceder a él varias veces, así que he decidido usar una pasada para almacenar todos esos datos en una matriz unidimensional, y luego toda la información real dibujando pases solo mira la matriz. El problema es que, debido a que tengo que hacer que OpenGL presione/haga pops en el orden correcto, la matriz debe estar en el orden de búsqueda de profundidad apropiado que sea representativo de la jerarquía de árbol. En el ejemplo anterior, la matriz debe ser ordenado de la siguiente manera:

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 

Por lo tanto, el orden de la matriz debe ser serializado correctamente, pero una vez que he asignado que ordenar adecuadamente, puedo paralelizar el llenado de la matriz. Por ejemplo, una vez que he asignado Bicycle Frame al índice 0 y Handle Bars al índice 1, un hilo puede tomar el relleno del elemento del array para Bicycle Frame, mientras que otro toma el relleno del elemento del array para Handle Bars.

Bien, creo que al aclarar esto, he respondido mi propia pregunta, así que gracias a Davide. Así que publiqué mi propio answer.

Answer 1

Aquí hay una pieza modificada de pseudocódigo que debería 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

a paralelizar el hilo hijo, sólo tiene que poner un pragma antes del bucle: hace

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

de empleo.

Ahora, tiene toda la razón de que no se puede hacer que una biblioteca de subprocesos haga un bit antes que otro de forma totalmente paralela (¡obviamente!), Y openMP no tiene una función 'bloquear' o 'esperar' (tiene una palabra clave 'esperar a que todos terminen' - Barrera), no está diseñada para emular una biblioteca de hilos, pero le permite almacenar valores "fuera" de la sección paralela y marcar ciertas secciones como 'solo un hilo' (Palabra clave ordenada) por lo que esto puede ayudarlo a asignar los índices en un bucle paralelo, mientras que otros hilos están asignando elementos.

Eche un vistazo a getting started guide.

Si está usando Visual C++, también deberá establecer el indicador/omp en la configuración de compilación del compilador.

Answer 3

creo que debería aclarar mejor su pregunta (por ejemplo, qué es exactamente lo que debe hacerse en serie y por qué)

OpenMP (al igual que muchas otras bibliotecas de paralelización) no no garantizar el orden en el que las diversas secciones paralelas habrá ejecutados, y dado que son verdaderamente paralelos (en una máquina multinúcleo), puede haber condiciones de carrera si diferentes secciones escriben los mismos datos. Si eso está bien para su problema, seguramente puede usarlo.

Answer 4

Como gbjbaanb mentioned, puede hacerlo fácilmente, solo se necesita una declaración pragma para paralelizar esto.

Sin embargo, hay algunas cosas a tener en cuenta:

En primer lugar, se menciona que el orden es crutial aquí. Si necesita conservar el orden al allanar una estructura jerárquica, la paralelización (en este nivel) va a ser problemática. Es probable que pierda por completo su pedido.

Además, la paralelización de funciones recursivas tiene muchos problemas. Tomemos un caso extremo, digamos que tiene una máquina de doble núcleo, y tiene un árbol donde cada nodo "padre" tiene 4 hijos. Si el árbol es profundo, usted muy, muy rápidamente "sobre-paraleliza" el problema, por lo general empeorando las cosas, no mejor, en cuanto al rendimiento.

Si va a hacer esto, probablemente deba poner un parámetro de nivel y solo paralelizar los primeros dos niveles. Tome mi ejemplo de 4 hijos por padre, si paraleliza los primeros 2 niveles, ya está dividiendo esto en 16 trozos paralelos (llamados desde 4 trozos paralelos).

De lo que usted ha mencionado, me gustaría dejar esta parte en serie, y se centran en lugar del segundo, donde se menciona:

"Luego se atraviesa esa matriz varias veces para dibujar objetos/superposiciones, etc."

Suena como un lugar ideal para paralelizar.