Parallélisation OpenMP sur une fonction récursive

Question

J'essaie d'utiliser la parallélisation pour améliorer le taux de rafraîchissement pour dessiner une scène 3D avec des objets ordonnés de manière hiérarchique. L'algorithme de dessin de scène parcourt d'abord de manière récursive l'arborescence des objets, puis construit un tableau ordonné de données essentielles nécessaires pour dessiner la scène. Ensuite, il parcourt ce tableau plusieurs fois pour dessiner des objets / des superpositions, etc. Depuis ce que j'ai lu, OpenGL n'est pas une API thread-safe, je suppose que le code de traversée de tableau / dessin doit être effectué sur le thread principal, mais je 'pense que je pourrais être capable de paralléliser la fonction récursive qui remplit le tableau. La clé réside dans le fait que le tableau doit être rempli dans l'ordre dans lequel les objets se produisent dans la scène. Par conséquent, toutes les fonctionnalités associant un objet donné à un index de tableau doivent être exécutées dans le bon ordre, mais une fois l'attribut attribué, Je peux remplir les données de cet élément de tableau (ce qui n'est pas nécessairement une opération triviale) à l'aide de threads de travail. Alors voici le pseudo code que je cherche à obtenir. J'espère que vous aurez l'idée de la syntaxe des threads 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>
}

Alors, est-il possible de faire cela en utilisant OpenMP, et si oui, comment? Existe-t-il d'autres bibliothèques de parallélisation qui gèrent mieux cela?

Addendum: en réponse à la Davide's Pour plus de précisions , permettez-moi de vous expliquer un peu plus en détail. Disons que la scène est ordonnée comme suit:

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

Maintenant, chacun de ces objets est associé à de nombreuses données, à savoir l'emplacement, la rotation, la taille, différents paramètres de dessin, etc. De plus, je dois effectuer plusieurs passages sur cette scène pour la dessiner correctement. Une passe dessine les formes des objets, une autre passe dessine le texte décrivant les objets, une autre passe dessine les connexions / associations entre les objets, le cas échéant. Quoi qu'il en soit, extraire toutes les données de dessin de ces différents objets est assez lent si je dois y accéder plusieurs fois. J'ai donc décidé d'utiliser un seul passage pour mettre en cache toutes ces données dans un tableau unidimensionnel, puis toutes les données réelles. les passes de dessin ne font que regarder le tableau. Le problème est que, parce que je dois effectuer des push / pop OpenGL dans le bon ordre, le tableau doit être dans le bon ordre de recherche en profondeur d'abord, qui est représentatif de la hiérarchie des arbres. Dans l'exemple ci-dessus, le tableau doit être commandé comme suit:

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

Donc, l'ordre du tableau doit être sérialisé correctement, mais une fois que j'ai assigné cet ordre correctement, je peux paralléliser le remplissage du tableau. Par exemple, une fois que j'ai assigné Bicycle Frame à l'index 0 et les guidons à l'index 1, un thread peut effectuer le remplissage de l'élément de tableau pour le cadre de bicyclette, tandis qu'un autre prend en charge le remplissage de l'élément de tableau pour les guidons.

D'accord, je pense qu'en clarifiant cela, j'ai répondu à ma propre question, alors merci Davide. J'ai donc posté ma propre answer .

Answer 1

Voici un morceau de pseudo-code modifié qui devrait fonctionner.

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

Je pense que vous devriez mieux préciser votre question (par exemple, que faut-il exactement faire en série et pourquoi)

OpenMP (comme de nombreuses autres bibliothèques de parallélisation) ne garantit pas l'ordre dans lequel les différentes sections parallèles seront exécutées - et comme elles sont réellement parallèles (sur une machine multicœur), il peut exister des conditions de concurrence critique. si différentes sections écrivent les mêmes données. Si cela vous convient, vous pouvez certainement l’utiliser.

Answer 3

Comme le mentionné ci-dessus , vous pouvez le faire facilement - il suffit d’une déclaration pragma pour mettre cela en parallèle.

Cependant, il y a quelques points à surveiller:

Tout d’abord, vous mentionnez que l’ordre est essentiel ici. Si vous devez conserver l'ordre lors de l'aplatissement d'une structure hiérarchique, la parallélisation (à ce niveau) sera problématique. Vous risquez de perdre complètement votre commande.

De plus, la parallélisation des fonctions récursives pose de nombreux problèmes. Prenons un cas extrême - disons que vous avez une machine à double cœur et que vous avez un arbre dans lequel chaque "parent" Le noeud a 4 enfants. Si l’arbre est profond, vous allez très, très vite "sur-paralléliser" le problème, généralement aggraver les choses, pas mieux, performance sage.

Si vous voulez faire cela, vous devriez probablement mettre un paramètre de niveau et ne paralléliser que les deux premiers niveaux. Prenons mon exemple de 4 enfants par parent, si vous parallélisez les 2 premiers niveaux, vous le divisez déjà en 16 morceaux parallèles (appelés à partir de 4 morceaux parallèles).

D'après ce que vous avez mentionné, j'aimerais laisser cette partie en série et me concentrer au lieu de la seconde où vous mentionnez:

"Il parcourt ensuite ce tableau plusieurs fois pour dessiner des objets / des superpositions, etc."

Cela ressemble à un endroit idéal pour la parallélisation.

Answer 4

pour paralléliser le thread enfant, mettez simplement un pragma avant la boucle:

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

Travail terminé.

Maintenant, vous avez tout à fait raison, aucune librairie de threading ne peut être exécutée de manière totalement parallèle (évidemment!), et openMP ne dispose pas de fonctionnalité de 'verrouillage' ou 'd'attente' avoir un mot clé 'attendre que tout se termine' - Barrier), il n'est pas conçu pour émuler une bibliothèque de threads, mais il vous permet de stocker des valeurs "en dehors" et la section parallèle, et de marquer certaines sections comme "mono-thread uniquement" (mot-clé commandé). Cela peut donc vous aider à affecter les index dans une boucle parallèle pendant que d'autres threads affectent des éléments.

Consultez le guide de démarrage .

Si vous utilisez Visual C ++, vous devez également définir l'indicateur / omp dans les paramètres de construction de votre compilateur.