6

並列化を使用して、階層的に順序付けられたオブジェクトを使用して3Dシーンを描画するためのリフレッシュレートを改善しようとしています。シーン描画アルゴリズムは、最初にオブジェクトのツリーを再帰的にトラバースし、そこから、シーンを描画するために必要な重要なデータの順序付けられた配列を構築します。次に、その配列を複数回トラバースしてオブジェクト/オーバーレイなどを描画します。私が読んだことから、OpenGLはスレッドセーフなAPIではないため、配列トラバーサル/描画コードはメインスレッドで実行する必要があると思いますが、配列を満たす再帰関数を並列化できるかもしれないと思っています。重要な点は、シーン内でオブジェクトが発生する順序で配列にデータを入力する必要があるため、特定のオブジェクトを配列インデックスに関連付けるすべての機能を適切な順序で実行する必要があることです。ただし、配列インデックスが割り当てられると、ワーカースレッドを使用して、その配列要素のデータを入力できます（これは必ずしも簡単な操作ではありません）。これが私が取得しようとしている擬似コードです。xml風のスレッド構文を理解していただければ幸いです。

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

それで、OpenMPを使用してこれを行うことは可能ですか？もしそうなら、どのように？これをより適切に処理する他の並列化ライブラリはありますか？

補遺：ダビデのさらなる説明の要請に応えて、もう少し詳しく説明させてください。シーンが次のように順序付けられているとしましょう。

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

現在、これらの各オブジェクトには、場所、回転、サイズ、さまざまな描画パラメータなど、多くのデータが関連付けられています。さらに、適切に描画するには、このシーンを複数回パスする必要があります。1つのパスはオブジェクトの形状を描画し、別のパスはオブジェクトを説明するテキストを描画し、別のパスはオブジェクト間の接続/関連付けを描画します（存在する場合）。とにかく、これらの異なるオブジェクトからすべての描画データを取得するのは、複数回アクセスする必要がある場合はかなり遅いので、1つのパスを使用して、すべてのデータを1次元配列にキャッシュし、次にすべての実際のオブジェクトをキャッシュすることにしました。描画パスは、配列を見るだけです。問題は、OpenGLのプッシュ/ポップを正しい順序で実行する必要があるため、配列はツリー階層を表す適切な深さ優先探索順序である必要があるということです。上記の例では、

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

したがって、配列の順序は適切にシリアル化する必要がありますが、その順序を適切に割り当てると、配列の入力を並列化できます。たとえば、自転車フレームをインデックス0に割り当て、ハンドルバーをインデックス1に割り当てると、1つのスレッドが自転車フレームの配列要素の入力を取得し、別のスレッドがハンドルバーの配列要素の入力を取得できます。

OK、これを明確にすることで、私は自分の質問に答えたと思うので、Davideに感謝します。だから私は自分の答えを投稿しました。

4

4 に答える 4

1

私はあなたがあなたの質問をよりよく明確にするべきだと思います（例えば、正確に何を連続して行わなければならないのか、そしてその理由）

OpenMP（他の多くの並列化ライブラリと同様）は、さまざまな並列セクションが実行される順序を保証しません。また、それらは（マルチコアマシン上で）真に並列であるため、異なるセクションが同じデータを書き込む場合、競合状態が発生する可能性があります。それで問題がなければ、きっと使用できます。

于 2009-05-07T17:24:16.387 に答える
1

gbjbaanbが述べたように、これは簡単に実行できます。これを並列化するには、プラグマステートメントが必要です。

ただし、注意すべき点がいくつかあります。

まず、ここでは順序が重要であるとおっしゃっています。階層構造をフラット化する際に順序を維持する必要がある場合、（このレベルでの）並列化は問題になります。注文が完全に失われる可能性があります。

また、再帰関数の並列化には多くの問題があります。極端な場合を考えてみましょう。たとえば、デュアルコアマシンがあり、各「親」ノードに4つの子があるツリーがあるとします。ツリーが深い場合は、問題を非常に迅速に「過剰並列化」し、通常、パフォーマンスを向上させるのではなく、悪化させます。

これを行う場合は、おそらくレベルパラメータを設定し、最初の2つのレベルのみを並列化する必要があります。私の4つの親ごとの子の例を見てください。最初の2つのレベルを並列化すると、これはすでに16の並列チャンク（4つの並列チャンクから呼び出されます）に分割されています。

あなたが言ったことから、私はこの部分をシリアルのままにして、あなたが言及する2番目の部分の代わりに焦点を合わせます：

「次に、その配列を複数回トラバースして、オブジェクト/オーバーレイなどを描画します。」

それは並列化するのに理想的な場所のように聞こえます。

于 2009-05-07T17:30:57.353 に答える
0

子スレッドを並列化するには、ループの前にプラグマを置くだけです。

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

仕事は終わりました。

さて、あなたはまったく正しいです。完全に並列な方法でスレッドライブラリを次々と実行することはできません（明らかに！）。openMPには「ロック」または「待機」機能がありません（「すべてが終了するのを待つ'キーワード-バリア）、スレッドライブラリをエミュレートするようには設計されていませんが、並列セクションの「外側」に値を格納し、特定のセクションを「シングルスレッドのみ」としてマークすることができます（順序付きキーワード）したがって、これは、他のスレッドが要素を割り当てている間に、並列ループでインデックスを割り当てるのに役立つ場合があります。

スタートガイドをご覧ください。

Visual C ++を使用している場合は、コンパイラのビルド設定で/ompフラグも設定する必要があります。

于 2009-05-07T17:17:42.347 に答える
0

これは、機能するはずの疑似コードの変更された部分です。

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)
  }
}
于 2009-05-07T19:49:06.380 に答える