4

OpenMP（C ++で）の使用について簡単な質問があります。誰かが私を助けてくれることを望んでいました。私の問題を説明するために、以下に小さな例を含めました。

#include<iostream>
#include<vector>
#include<ctime>
#include<omp.h>

using namespace std;

int main(){
  srand(time(NULL));//Seed random number generator                                                                               

  vector<int>v;//Create vector to hold random numbers in interval [0,9]                                                                                   
  vector<int>d(10,0);//Vector to hold counts of each integer initialized to 0                                                                    

  for(int i=0;i<1e9;++i)
    v.push_back(rand()%10);//Push back random numbers [0,9]                                                                      

  clock_t c=clock();

  #pragma omp parallel for
  for(int i=0;i<v.size();++i)
    d[v[i]]+=1;//Count number stored at v[i]                                                                                     

  cout<<"Seconds: "<<(clock()-c)/CLOCKS_PER_SEC<<endl;

  for(vector<int>::iterator i=d.begin();i!=d.end();++i)
  cout<<*i<<endl;

  return 0;
}

上記のコードはv、範囲内に10億個のランダムな整数を含むベクトルを作成します[0,9]。次に、コードvは、それぞれの異なる整数のインスタンスの数をカウントすることでループします（つまり、vで見つかったインスタンスの数、2の数など）。

特定の整数が検出されるたびに、ベクトルの適切な要素をインクリメントすることによってカウントされますd。したがって、d[0]ゼロの数、6の数などd[6]をカウントします。これまでのところ意味がありますか？

私の問題は、カウントループを並列にしようとしたときです。ステートメントがない#pragma OpenMP場合、私のコードは20秒かかりますが、ステートメントがある場合は60秒pragma以上かかります。

明らかに、私はOpenMPに関連するいくつかの概念を誤解しました（おそらくデータの共有/アクセス方法は？）。誰かが私のエラーを説明してくれませんか、または私の検索に役立つ適切なキーワードを含む洞察に満ちた文献の方向に私を向けてもらえますか？

4

2 に答える 2

6

あなたのコードは次のとおりです。

  • 共有変数への非同期アクセスによる競合状態
  • false および true 共有キャッシュの問題
  • 実行時間の間違った測定

d複数のスレッドで vector の同じ要素を同時に更新しているため、競合状態が発生します。行をコメントアウトしsrand()、同じ数のスレッド (ただし複数のスレッド) でコードを数回実行します。異なる実行からの出力を比較します。

偽共有は、2 つのスレッドが互いに近いメモリ位置に書き込み、結果として同じキャッシュ ラインになる場合に発生します。これにより、マルチソケット システムでキャッシュ ラインがコアからコアへ、または CPU から CPU へと絶えずバウンスし、過剰なキャッシュ コヒーレンス メッセージが発生します。キャッシュ ラインあたり 32 バイトの場合、ベクトルの 8 つの要素が 1 つのキャッシュ ラインに収まります。キャッシュ ラインあたり 64 バイトの場合、ベクトル全体dが 1 つのキャッシュ ラインに収まります。これにより、Core 2 プロセッサではコードが遅くなり、Nehalem および Nehalem 以降 (Sandy Bridge など) のプロセッサでは少し遅くなります (ただし、Core 2 ほど遅くはありません)。真の共有は、2 つ以上のスレッドが同時にアクセスする要素で発生します。インクリメントを OpenMPatomicコンストラクト (低速) に配置するか、OpenMP ロックの配列を使用して要素へのアクセスを保護する必要があります。d(OpenMP ランタイムに応じて、より高速または低速) またはローカル値を蓄積してから、最終的な同期リダクションを実行します (最速)。最初のものは次のように実装されます。

#pragma omp parallel for
for(int i=0;i<v.size();++i)
  #pragma omp atomic
  d[v[i]]+=1;//Count number stored at v[i]

2 つ目は次のように実装されます。

omp_lock_t locks[10];
for (int i = 0; i < 10; i++)
  omp_init_lock(&locks[i]);

#pragma omp parallel for
for(int i=0;i<v.size();++i)
{
  int vv = v[i];
  omp_set_lock(&locks[vv]);
  d[vv]+=1;//Count number stored at v[i]
  omp_unset_lock(&locks[vv]);
}

for (int i = 0; i < 10; i++)
  omp_destroy_lock(&locks[i]);

(関数omp.hへのアクセスを取得するために含めomp_*ます)

3 番目のオプションの実装を考え出すのはあなた次第です。

clock()を使用して経過時間を測定していますが、ランタイムではなくCPU時間を測定しています。1 つのスレッドが 1 秒間 100% の CPU 使用率で実行されている場合clock()、CPU 時間が 1 秒間増加したことを示します。8 つのスレッドが 1 秒間 100% の CPU 使用率で実行されている場合clock()、8 秒の CPU 時間の increate を示します (つまり、スレッドごとに 8 スレッド x 1 CPU 秒)。代わりにomp_get_wtime()or gettimeofday()(またはその他の高解像度タイマー API) を使用してください。

于 2012-07-25T17:39:29.367 に答える
1

編集 競合状態が正しい同期によって解決されると、次の段落が適用されます。その前に、残念ながらデータ競合状態によって速度比較がミュートされます。

プラグマ セクションでランダムにアクセスされる可能性のある出力が 10 個あるため、プログラムの速度が低下しています。その結果、OpenMP はロック (同期を介して提供する必要があります) なしではこれらの要素のいずれにもアクセスできず、ロックにより、並列でカウントすることから得られるよりも高いオーバーヘッドがスレッドに発生します。

この速度を上げるための解決策は、代わりに、特定のスレッドが認識した 0 から 10 の値をすべてカウントする各 OpenMP スレッドのローカル変数を作成することです。次に、マスター カウント ベクトルでそれらを合計します。スレッドが共有書き込みベクトルをロックする必要がないため、これは簡単に並列化され、はるかに高速になります。必要なロックが非常に限られているため、N は OpenMP からのスレッドの数である Nx に近いスピードアップが期待されます。このソリューションは、現在コード内にある多くの競合状態も回避します。

スレッド ローカル OpenMP の詳細については、http://software.intel.com/en-us/articles/use-thread-local-storage-to-reduce-synchronization/を参照してください。

于 2012-07-25T16:57:32.350 に答える