OpenMP Parallelisierung auf einer rekursiven Funktion

Question

Ich versuche, Parallelisierung zu verwenden, um die Aktualisierungsrate zu verbessern, für eine 3D-Szene Zeichnung mit heirarchically Objekten geordnet. Die Szene Zeichnung Algorithmus zuerst quert rekursiv den Baum von Objekten, und von diesem baut sich eine geordnete Anordnung von wesentlichen Daten, die benötigt wird, um die Szene zu zeichnen. Dann durchläuft es, dass Array mehr Male Objekte / Overlays zu ziehen usw. Da von dem, was ich habe gelesen, OpenGL ist kein Thread-sichere API, gehe ich davon aus dem Array-Traversal / code Zeichnung auf dem Haupt-Thread getan werden muss, aber ich ist zu denken, dass ich in der Lage sein könnte, die rekursive Funktion parallelisieren, die das Array füllt. Der Schlüssel Haken ist, dass das Array muss in der Reihenfolge benutzt werden, dass die Objekte in der Szene auftreten, so dass alle Funktionen, die ein bestimmtes Objekt mit einem Array-Index ordnet müssen in der richtigen Reihenfolge durchgeführt werden, aber sobald der Array-Index zugewiesen wurde, ich kann die Daten dieses Array-Elements füllen (die nicht notwendigerweise eine triviale Operation) unter Verwendung von Arbeitsthreads. Also hier ist der Pseudo-Code, den ich versuche zu bekommen. Ich hoffe, dass Sie die Idee der xml-ish Thread Syntax erhalten.

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>
}

So ist es möglich, dies mit OpenMP zu tun, und wenn ja, wie? Gibt es weitere Parallelisierung Bibliotheken, die diesen besser wäre umgehen?

Nachtrag: In Reaktion auf Davides Bitte um weitere Klärung , lassen Sie mich ein wenig mehr im Detail erklären. Lassen Sie uns sagen, dass die Szene wie folgt bestellt:

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

Nun, jedes dieser Objekte hat viele Daten zugeordnet, das heißt Position, Rotation, Größe, unterschiedliche Zeichenparameter usw. Außerdem habe ich mehrere Durchgänge über diese Szene zu zeichnen, es richtig zu machen brauchen. Ein Durchgang zieht die Formen der Objekte, ein weiterer Pass zieht Text die Objekte beschreiben, ein weiterer Pass zieht Verbindungen / Assoziationen zwischen den Objekten, wenn es welche gibt. Wie auch immer, die alle Zeichnungsdaten immer aus diesen verschiedenen Objekten ist ziemlich langsam, wenn ich es mehrmals zugreifen müssen, so habe ich beschlossen, einen Pass zu verwenden, um alle diese Daten in einem eindimensionalen Array zwischenzuspeichern, und dann all die tatsächlichen Zeichnung Ausweise nur Blick auf das Array. Der Haken ist, dass, weil ich brauche OpenGL schiebt / Pop in der richtigen Reihenfolge zu tun, wobei die Anordnung in dem richtigen Tiefensuchauftrag, den Vertreter der Baumes Hierarchie ist sein muss. In dem obigen Beispiel muss das Array wie folgt bestellt werden:

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

Die Reihenfolge der Anordnung muss also richtig serialisiert werden, aber sobald ich zugewiesen haben, dass die Bestellung richtig, ich habe die Füllung des Arrays parallelisieren können. Zum Beispiel, wenn I Fahrradrahmen Index 0 und Lenker auf dem Index 1, ein Thread kann die Füllung des Array-Elements für den Fahrradrahmen nimmt zugewiesen haben, während ein anderes die die Füllung des Array-Elements für Lenker nimmt.

OK, ich denke, das bei der Klärung, ich habe meine eigene Frage beantwortet, so dank Davide. Also ich habe meine eigene beantworten .

Answer 1

Hier ist ein modifizierte Stück Pseudo-Code, sollte funktionieren.

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

Ich denke, Sie sollten besser auf Ihre Frage klären (z was genau seriell getan werden muss, und warum)

OpenMP (wie viele andere Parallelisierung Bibliotheken) hat nicht garantieren die Reihenfolge, in der die verschiedenen parallelen Abschnitten ausgeführt wird, und da sie wirklich parallel sind (auf einer Multi-Core-Maschine) könnte es Rennbedingungen sein wenn verschiedene Abschnitte schreiben die gleichen Daten. Wenn das für Ihr Problem ist ok, sicher können Sie es verwenden.

Answer 3

Wie gbjbaanb erwähnt , können Sie dies ganz einfach -. es erfordert nur eine Pragma-Anweisung, dies parallelisieren

Allerdings gibt es ein paar Dinge zu achten gilt:

Als erstes erwähnen Sie, dass um crutial hier. Wenn Sie Bestellung erhalten benötigen eine hierarchische Struktur in Abflachung, Parallelisierung (auf dieser Ebene) wird problematisch. Du wirst wahrscheinlich vollständig Ihre Bestellung verlieren.

Auch hat rekursiven Funktionen Parallelisierung viele Probleme. Nehmen Sie einen extremen Fall - sagen Sie einen Dual-Core-Maschine haben, und Sie haben einen Baum, wo jeder „Eltern“ Knoten 4 Kinder hat. Wenn der Baum tief ist, können Sie sehr, sehr schnell „over-parallelize“ das Problem, in der Regel die Dinge noch schlimmer, nicht besser, Leistung klug.

Wenn Sie vorhaben, dies zu tun, sollten Sie vielleicht einen Level-Parameter setzen, und parallelisieren nur die ersten paar Stufen. Nehmen Sie meine 4 Kind-pro-parent Beispiel, wenn Sie die ersten 2 Ebenen parallelisieren, haben Sie bereits brechen diese in 16 parallele Chunks (genannt von 4 parallel chunks).

Von dem, was Sie erwähnt haben, würde ich diesen Teil seriell, verlassen und anstelle des zweiten konzentrieren, wo Sie erwähnen:

"Dann durchläuft es, dass Array mehrere Male Objekte / Overlays zu ziehen, etc."

Das klingt wie ein idealer Ort, um parallelisieren.

Answer 4

das Kind Thread parallelisieren, einfach ausgedrückt eine Pragma vor der Schleife:

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

Job gemacht.

Sie jetzt sind, ganz richtig können Sie keine Threading-Bibliothek erhalten, bevor ein anderer etwas zu tun in einer vollständig parallelen Art und Weise (natürlich!) Und OpenMP nicht über eine ‚Sperre‘ oder ‚warten‘ -Funktion (es tut habe ein ‚für alle wartet bis zum Ende‘ Schlüsselwort - Barrier), es ist nicht entworfen, um eine Thread-Bibliothek zu emulieren, aber es ermöglicht es Ihnen, Werte zu speichern „außerhalb“ des parallelen Abschnitt und bestimmte Abschnitte als ‚einzigen Gewinde nur‘ zu markieren ( Bestellen keyword) so dabei helfen können Ihnen die Indizes in einer parallelen Schleife zuzuordnen, während andere Threads Elemente zuweisen.

Werfen Sie einen Blick auf eine Erste Schritte .

Wenn Sie Visual C ++ verwenden, müssen Sie auch den / omp-Flag in Ihren Compiler Build-Einstellungen setzen.