5

私は C で OpenMP を使用する方法を学習中であり、HelloWorld の演習として、素数を数えるプログラムを作成しています。次に、これを次のように並列化します。

int numprimes = 0;
#pragma omp parallel for reduction (+:numprimes)
for (i = 1; i <= n; i++)
{
    if (is_prime(i) == true)
        numprimes ++;
}

gcc -g -Wall -fopenmp -o primes primes.c -lmこのコードを(使用-lmしているmath.h関数に対して) を使用してコンパイルします。次に、このコードを で実行するIntel® Core™2 Duo CPU E8400 @ 3.00GHz × 2と、予想どおり、パフォーマンスはシリアル プログラムよりも優れています。

ただし、これをはるかに強力なマシンで実行しようとすると、問題が発生します。( で使用するスレッド数を手動で設定しようとしましたnum_threadsが、何も変わりませんでした。) までのすべての素数を数えると、 ( を使用して)10 000 000次の時間が得られます。time

8 コア マシン:

real    0m8.230s
user    0m50.425s
sys     0m0.004s

デュアルコアマシン: 

real    0m10.846s
user    0m17.233s
sys     0m0.004s

このパターンは、より多くの素数をカウントするために続きます。より多くのコアを備えたマシンは、わずかなパフォーマンスの向上を示していますが、より多くのコアを使用できる場合に期待するほどではありません。(コアが 4 倍多いということは、実行時間がほぼ 4 分の 1 になることを意味すると思いますか?)

まで素数を数え50 000 000ます:

8 コア マシン:

real    1m29.056s
user    8m11.695s
sys     0m0.017s

デュアルコアマシン:

real    1m51.119s
user    2m50.519s
sys     0m0.060s

誰かが私のためにこれを明確にすることができれば、それは大歓迎です。

編集

これが私の素数チェック関数です。

static int is_prime(int n)
{
  /* handle special cases */
  if      (n == 0) return 0;
  else if (n == 1) return 0;
  else if (n == 2) return 1;

  int i;
  for(i=2;i<=(int)(sqrt((double) n));i++)
    if (n%i==0) return 0;

  return 1;
}
4

3 に答える 3

6

このパフォーマンスは、次の理由で発生しています。

  1. is_prime(i)高くなるほど時間がかかりi、
  2. OpenMP の実装では、デフォルトで句parallel forのない構造に対して静的スケジューリングが使用されますschedule。つまり、for ループが同じサイズの連続したチャンクに分割されます。

つまり、番号が最も大きいスレッドが、最も困難な操作をすべて実行しています。

句を使用してより適切なスケジューリング タイプを明示的に選択すると、schedule作業をスレッド間で公平に分割できます。

このバージョンでは、作業がより適切に分割されます。

int numprimes = 0;
#pragma omp parallel for schedule(dynamic, 1) reduction(+:numprimes) 
for (i = 1; i <= n; i++)
{
    if (is_prime(i) == true)
        numprimes ++;
}

スケジューリング構文に関する情報は、 MSDNおよびWikipediaから入手できます。

schedule(dynamic, 1)ハイパフォーマンスマークが彼の答えで指摘しているように、最適ではないかもしれません。このOpenMP wihtepaperには、スケジューリングの粒度に関するより詳細な説明があります。

この回答に貢献してくれたJens GustedtとMahmoud Fayezにも感謝します。

于 2013-03-17T16:30:16.733 に答える
3

プログラムのスケーリングが明らかに不十分である理由は、@ naroomが示唆しているように、is_prime関数への各呼び出しの実行時間の変動性です。実行時間は、の値とともに単純に増加するわけではありませんi。あなたのコードは、の最初の因子iが見つかるとすぐにテストが終了することを示しているので、最も長い実行時間は、素数自体を含む、因子が少ない（そして大きい）数の場合になります。

すでに説明したように、並列化のデフォルトのスケジュールでは、マスターループの反復が、使用可能なスレッドに対して一度に1チャンクずつ分割されます。テストする整数と使用する8コアの場合、最初のスレッドがテスト5*10^7する整数を取得し、2番目のスレッドが取得します。もちろん、素数が均一に分散されていないため、これによりスレッド間で負荷が大幅に不均衡になります。1..62500006250001..12500000

デフォルトのスケジューリングを使用するのではなく、動的スケジューリングを試してみてください。m次のステートメントは、マスターループの反復の反復を計算のスレッドに一度に分割するようにランタイムに指示します。

#pragma omp parallel for schedule(dynamic,m)

スレッドがm反復を終了すると、mさらに作業が許可されます。あなたにとっての秘訣は、forを見つけることsweet spotですm。小さすぎると、実行時に反復をパーセル化する作業が計算に支配され、大きすぎると、計算は、すでに見た不均衡な負荷に戻ります。

ただし、これらすべてを実行することで、並列計算のコストと利点に関するいくつかの有用な教訓を学ぶことができます。

于 2013-03-17T17:39:00.127 に答える
1

コードは動的に使用する必要があると思います。これにより、反復の作業負荷が異なるため、スレッドごとに異なる反復回数を消費できるため、現在のコードのバランスが取れているため、あなたのケースでは役に立ちません。これを試してください:

int numprimes = 0;
#pragma omp parallel for reduction (+:numprimes) schedule(dynamic,1)
for (i = 1; i <= n; i++){
    if (is_prime(i) == true)
    ++numprimes;
}
于 2013-03-17T17:27:03.107 に答える