OpenMPパラレルforループでパフォーマンスが少し向上する

Question

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

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

私は（私が使用していmath.h機能のための-lm）gcc -g -Wall -fopenmp -o primes primes.c -lmを使用してこのコードをコンパイル。次に、私は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分の走行時間を意味することを期待する？）

カウントが50 000 000までの素数：

8コアマシン：

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

デュアルコアマシン：

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

誰でも私のためにこれを明確にすることができれば、非常に感謝しています。

EDIT

これは私のプライム・チェック機能です。

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

Answer 1

ので、このパフォーマンスが起こっている：

1. is_prime(i)がi高いが取得し、それはチョップすなわち
2. あなたのOpenMPの実装は、schedule句なしparallel for構築物について、デフォルトでは静的スケジューリングを使用して時間がかかります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)が最適ではない可能性があります。回答はHigh Performance Markです。このOpenMP wihtepaperには、粒度のスケジューリングに関する詳細な説明があります。

この回答に寄せられたJens GustedtとMahmoud Fayezにも感謝します。

Answer 2

あなたのコードは動的である必要があると思うので、スレッドごとに異なる繰り返し回数を消費するので、現在のコードはバランスがとれていますので、あなたのケースでは役に立ちません。

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

Answer 3

あなたのプログラムのスケーリングが明らかに悪い理由は、あなたがis_prime関数を呼び出すたびに実行時間のばらつきがあります。実行時間は単にiの値で増加するわけではありません。あなたのコードは、最初のファクタがiであるとすぐにテストが終了することを示しているので、最長実行時間は、素数自体を含めたいくつかの（そして大きな）要因を持つ数字になります。

すでに説明したように、並列化のデフォルトスケジュールでは、一度に1つのチャンクであるマスターループの繰り返しを利用可能なスレッドに分割します。あなたのケースでは、テストする整数とテストする整数と8コアを使用する場合、最初のスレッドは1..6250000の数値を取得し、2番目の数値は6250001..12500000となります。これは、もちろん、素数が一様に分布していないため、スレッド間で重大な不均衡な負荷につながります。

デフォルトスケジューリングを使用するのではなく、動的スケジューリングを試す必要があります。次の文は、あなたの計算の内のスレッドまでの時間であなたのマスターループm反復の反復を区分けするために、実行時に指示します：

#pragma omp parallel for schedule(dynamic,m) 

スレッドがm多くを与えられますそのm繰り返しを終了したら作業する。あなたのための秘訣はmのsweet spotです。小さすぎると、実行時間が反復処理に費やされる作業が支配的になりすぎます。計算が、すでに見た不均衡な負荷に戻ってしまいます。

しかし、このすべてを処理することで、並列計算のコストと利点についての有用な教訓を学ぶことができます。