再帰関数でのOpenMP並列化

StackOverflow https://stackoverflow.com/questions/835893

  •  08-07-2019
  •  | 
  •  

質問

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

では、OpenMPを使用してこれを実行できますか？これをより適切に処理する他の並列化ライブラリはありますか？

補遺： Davideのより明確にするためのリクエスト、もう少し詳しく説明させてください。シーンが次のように順序付けられているとしましょう：

-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つのスレッドが自転車フレームの配列要素を埋め、もう1つのスレッドがハンドルバーの配列要素を埋めることができます。

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

>
役に立ちましたか？

解決 4

これは、動作するはずの修正された擬似コードです。

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

他のヒント

質問をより明確にする必要があると思います（たとえば、連続して実行する必要がある正確な理由と理由）

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

gbjbaanb言及のように、これを簡単に行うことができます-これを並列化するにはプラグマステートメントが必要です。

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

最初に、ここで順序が重要であることに言及します。階層構造をフラット化する際に順序を保持する必要がある場合、（このレベルでの）並列化には問題が生じます。注文を完全に失う可能性があります。

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

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

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

＆quot;次に、その配列を複数回走査して、オブジェクト/オーバーレイなどを描画します。＆quot;

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

子スレッドを並列化するには、単にループの前にプラグマを置きます：

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

ジョブ完了。

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

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

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

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top