5

並列コード (OpenMP を使用) で使用される C++ データ構造 (グラフ用) を設計しています。

すべての要素 (ノード) の反復を可能にするメソッドが必要だとします。もちろん、この反復は並列化されます。

この目的でイテレータを使用することは可能ですか? 並列アクセスを可能にする反復子はどのように見えるべきですか? この場合、イテレータの使用に賛成ですか、反対ですか?

4

5 に答える 5

6

OpenMP の並列ループは、反復子ではうまく機能しません。operator[]グラフ クラスに (整数の引数を取る)インデックス作成メカニズムを実装する必要があります。

OpenMP 3.0 反復子サポートを使用する場合は、ランダム アクセス反復子があることを確認してください。ノードまたはエッジへのポインターとして実装するのが最も簡単な選択です。

于 2012-11-05T13:42:10.443 に答える
3

私のコメントを拡張させてください。クロスプラットフォームの互換性をターゲットにしており、コードをコンパイルして MS Visual C++ で動作させたい場合を除き、明示的な OpenMP タスクを使用することで、グラフ オブジェクトに "線形" イテレータを提供する複雑さを相殺できます。明示的なタスキングは OpenMP 3.0 で導入されました (したがって、2012 年になってもずっと以前の仕様にしか準拠していない MSVC ではサポートされていません)。タスクは、並行して実行できるコードのブロックです。それらは次のtask構成によって作成されます。

... other code ...
#pragma omp task
{
   ... task code ...
}
... other code ...

実行フローがマークされた領域に到達するたびに、新しいタスク オブジェクトが作成され、タスク キューに入れられます。その後、特定の時点で、アイドル状態のスレッドがキューから 1 つのタスクを取得して実行を開始します。タスクは、環境を継承し、シリアル バージョンのコードとは異なる順序で実行できるという点で、OpenMP* セクションによく似ています。

タスクを使用すると、再帰アルゴリズムを実装でき、ランダム イテレータを提供しない C++ コンテナーを簡単に操作できます。たとえば、バイナリ ツリーのトラバーサルは、次のようにタスクで実行できます。

// Helper routine to traverse a tree and create one task for each node
void traverse_and_make_tasks(tree_node *tn)
{
   if (tn == NULL)
      return;

   // Create a task to process the node
   #pragma omp task
   {
      very_long_computation(tn->value);
   }

   traverse_and_make_tasks(tn->left);
   traverse_and_make_tasks(tn->right);
}

... main code ...

// Disable dynamic teams
omp_set_dynamic(0);

#pragma omp parallel
{
   #pragma omp single nowait
   {
      traverse_and_make_tasks(tree->root_node);
   }
}

(OpenMP ランタイムがスマートになりすぎてparallel領域をシングルスレッドで実行するのを防ぐために、動的チームを無効にする必要があります)

これは、シングル/シリアル プロデューサーとして知られる非常に一般的なタスク パターンです。実行が領域に入るたびにparallel、単一のスレッドがsingle構造内のコードを実行します。traverse_and_make_tasks3つのルートノードで呼び出します。traverse_and_make_tasks3 つをウォークし、ノードごとに 1 つのタスクを作成します。taskコンストラクトは、領域内で使用される場合parallel(静的スコープ)、またはparallel領域内から (直接的または間接的に) 呼び出されるコードで使用される場合 (動的スコープ) にのみ機能します。traverse_and_make_tasksツリーをたどると、キューに入れられるタスクが生成されます。最後にparallelこれは、すべてのタスクが実行されるまで、リージョンの最後を超えて実行が再開されないことを大まかに意味します。を使用して、並列領域内に明示的なポイントを配置することもでき#pragma omp taskwaitます。barrier- すべてのタスクが処理されるまで実行を「ブロック」します。

もう 1 つの一般的なパターンは、タスクが並列で生成される並列プロデューサーです。上記のサンプル コードは、次のように簡単に変更するだけで、簡単に並列プロデューサーに変換できますtraverse_and_make_tasks。

void traverse_and_make_tasks(tree_node *tn)
{
   if (tn == NULL)
      return;

   #pragma omp task
   traverse_and_make_tasks(tn->left);
   #pragma omp task
   traverse_and_make_tasks(tn->right);

   // Create a task to process the node
   very_long_computation(tn->value);
}

このバージョンのコードは、各ノードに 2 つのタスクを作成します。1 つは左側の子孫を処理するタスクで、もう 1 つは右側の子孫を処理するタスクです。これがシリアルコードの場合、ツリーを下から上にトラバースします。ただし、並列ケースでは、タスクのキューイングにより、多かれ少なかれ上から下へのトラバーサルが発生します。

タスクを使用するシナリオは他にも多数あります。非再帰的なケースでそれらを使用して、ワークシェアリング コンストラクトで必要なランダム イテレータを提供しないコンテナを処理することもできますfor。

typedef container_type::iterator citer;

container_type container;
... push some values in the container ...

#pragma omp parallel
{
   #pragma omp single nowait
   {
      for (citer it = container.begin(); it != container.end(); it++)
         #pragma omp task
         process(*it);
   }

   #pragma omp taskwait

   // process more
   #pragma omp single nowait
   {
      for (citer it = container.begin(); it != container.end(); it++)
         #pragma omp task
         process_more(*it);
   }
}

parallelこの例は、リージョン内での明示的なタスク同期の使用も示しています。

于 2012-11-06T09:24:11.607 に答える
1

それらがツリーである場合、おそらく「反復子」よりもオイラー ツアー トラバーサルのスキャンの観点から考えたいと思うでしょう。http://en.wikipedia.org/wiki/Euler_tour_technique

ステパノフの本が目の前にあればいいのに。彼がそれに簡単に触れたのを覚えています。

于 2012-11-15T21:17:01.453 に答える
1

これは、リーダー/ライターの問題のバリエーションです。

その構造が変更可能かどうかによって異なります。そうでない場合は、好きなだけ並行して読んでください。

しかし、変更可能である場合、イテレータは構造に加えられた変更と衝突する可能性があります。たとえば、現在削除中の要素に反復子が到達する場合があります。1 つの解決策は、反復子ごとに構造体の読み取り専用で不変のコピーを作成することですが、その反復子は、反復子の作成後に構造体に加えられた変更を登録しません。2 番目の解決策は、コピー オン ライトの実装を作成することです。これにより、構造体へのすべての書き込みで新しいオブジェクトが作成され、現在実行中のイテレーターが古いオブジェクトで動作します。

その構造体への書き込みがプログラムにとってアルゴリズム的に何を意味するかを決定し、読み取り/書き込みロックを適切に実装する必要があります。

于 2012-11-05T13:46:26.520 に答える
0

私はJavaでまったく同じ問題を抱えていました。私が実装したソリューションでは、「ハッシュマップのハッシュマップ」を使用しています。標準ライブラリでマルチスレッド イテレータを使用できない理由をまだ理解できません...ここで私の質問と私の回答 (Java コードへのリンク付き) を読むことができます。

ConcurrentHashMap<Element, Boolean> のすべての要素に 1 回だけアクセスするスケーラブルな方法

于 2013-11-23T15:38:04.460 に答える