1

このループを並列化する必要があります。使用するのは良いアイデアだと思いましたが、これまでにそれらを研究したことはありませんでした。 

 #pragma omp parallel for

for(std::set<size_t>::const_iterator it=mesh->NEList[vid].begin();
        it!=mesh->NEList[vid].end(); ++it){

    worst_q = std::min(worst_q, mesh->element_quality(*it));
}

この場合、ループは反復子を使用し、コンパイラーはそれを分割する方法を理解できないため、並列化されません。

手伝って頂けますか？

4

2 に答える 2

1

OpenMPでは、並列ループの制御述語に、、、、またはのいずれかforの関係演算子が必要です。ランダムアクセスイテレータのみがこれらの演算子を提供するため、OpenMP並列ループはランダムアクセスイテレータを提供するコンテナでのみ機能します。双方向イテレータのみを提供します。明示的なタスクを使用して、この制限を克服できます。削減は、最初に各スレッド変数に対してプライベートを部分的に削減し、次に部分的な値をグローバルに削減することによって実行できます。<<=>>=std::set

double *t_worst_q;
// Cache size on x86/x64 in number of t_worst_q[] elements
const int cb = 64 / sizeof(*t_worst_q);

#pragma omp parallel
{
   #pragma omp single
   {
      t_worst_q = new double[omp_get_num_threads() * cb];
      for (int i = 0; i < omp_get_num_threads(); i++)
         t_worst_q[i * cb] = worst_q;
   }

   // Perform partial min reduction using tasks
   #pragma omp single
   {
      for(std::set<size_t>::const_iterator it=mesh->NEList[vid].begin();
          it!=mesh->NEList[vid].end(); ++it) {
         size_t elem = *it;
         #pragma omp task
         {
            int tid = omp_get_thread_num();
            t_worst_q[tid * cb] = std::min(t_worst_q[tid * cb],
                                           mesh->element_quality(elem));
         }
      }
   }

   // Perform global reduction
   #pragma omp critical
   {
      int tid = omp_get_thread_num();
      worst_q = std::min(worst_q, t_worst_q[tid * cb]);
   }
}

delete [] t_worst_q;

（私はそれmesh->element_quality()が戻ると思いますdouble）

いくつかの重要なポイント：

  • ループは1つのスレッドによってのみシリアルに実行されますが、反復ごとに新しいタスクが作成されます。これらは、アイドル状態のスレッドによる実行のためにキューに入れられる可能性があります。
  • コンストラクトの暗黙のバリアで待機しているアイドルスレッドは、single作成されるとすぐにタスクの消費を開始します。
  • が指す値はit、タスク本体の前で逆参照されます。タスク本体内で逆参照された場合は、タスクitごとfirstprivateに（つまり、反復ごとに）イテレータのコピーが作成されます。これはあなたが望むものではありません。
  • 各スレッドは、のプライベート部分で部分的な削減を実行しt_worst_q[]ます。
  • 偽共有によるパフォーマンスの低下を防ぐためにt_worst_q[]、各スレッドがアクセスする要素は、別々のキャッシュラインになるように間隔が空けられています。x86 / x64では、キャッシュラインは64バイトであるため、スレッド番号に。が掛けられcb = 64 / sizeof(double)ます。
  • グローバル最小削減は、一度に複数のスレッドからアクセスされないcriticalように保護するために、構成内で実行されます。worst_qこれは、並列領域の後のメインスレッドのループによっても削減を実行できるため、説明のみを目的としています。

明示的なタスクには、OpenMP3.0または3.1をサポートするコンパイラーが必要であることに注意してください。これにより、Microsoft C / C ++コンパイラのすべてのバージョンが除外されます（OpenMP 2.0のみをサポートします）。

于 2013-03-04T23:13:02.527 に答える
0

ランダム アクセス コンテナ

最も簡単な解決策は、すべてをランダム アクセス コンテナー ( などstd::vector) に入れ、OpenMP で好まれるインデックス ベースのループを使用することです。

// Copy elements
std::vector<size_t> neListVector(mesh->NEList[vid].begin(), mesh->NEList[vid].end());

// Process in a standard OpenMP index-based for loop
#pragma omp parallel for reduction(min : worst_q)
for (int i = 0; i < neListVector.size(); i++) {
    worst_q = std::min(worst_q, complexCalc(neListVector[i]));
}

あなたの状況（size_t簡単にコピーできるタイプの小さな要素）では、信じられないほど単純であることに加えて、これは最高のパフォーマンスとスケーラビリティを備えたソリューションでもあります。

コピーの回避

ただし、あなたの状況とは異なる状況では、要素が簡単にコピーされない (より大きな要素) か、まったくコピーできない場合があります。この場合、対応するポインターをランダム アクセス コンテナーにスローするだけです。

// Collect pointers
std::vector<const nonCopiableObjectType *> neListVector;
for (const auto &entry : mesh->NEList[vid]) {
    neListVector.push_back(&entry);
}

// Process in a standard OpenMP index-based for loop
#pragma omp parallel for reduction(min : worst_q)
for (int i = 0; i < neListVector.size(); i++) {
    worst_q = std::min(worst_q, mesh->element_quality(*neListVector[i]));
}

これは最初のソリューションよりも少し複雑ですが、小さな要素では同じように良好なパフォーマンスが得られ、大きな要素ではパフォーマンスが向上します。

タスクと動的スケジューリング

他の誰かが彼の回答で OpenMP タスクを取り上げたので、それについてコメントしたいと思います。タスクは非常に強力な構成要素ですが、オーバーヘッドが非常に大きく (スレッドの数が増えるとさらに増加し​​ます)、この場合は物事がより複雑になります。

メインスレッドでのタスクの作成は、それ自体を行うよりもはるかにコストがかかるため、min削減のためにタスクの使用は決して正当化されません!std::min

より複雑な操作では、 の実行時間が反復間で大きく異なり、それを均等にするのに十分な反復がないmesh->element_quality場合に、タスクの動的な性質が負荷分散の問題に役立つと考えるかもしれません。mesh->element_qualityしかし、その場合でも、より簡単な解決策があります。以前の解決策の 1 つで、行にschedule(dynamic)ディレクティブを追加して動的スケジューリングを使用するだけです。parallel forオーバーヘッドがはるかに少ない同じ動作を実現します。

于 2015-06-06T15:16:33.877 に答える