10

私は OpenMp を使ったプログラミングの初心者です。行列をベクトルで乗算する簡単な C プログラムを作成しました。残念ながら、実行時間を比較すると、OpenMP はシーケンシャル方式よりもはるかに遅いことがわかりました。

これが私のコードです（ここでは、行列はN * N int、ベクトルはN int、結果はN long longです）：

#pragma omp parallel for private(i,j) shared(matrix,vector,result,m_size)
for(i=0;i<m_size;i++)
{  
  for(j=0;j<m_size;j++)
  {  
    result[i]+=matrix[i][j]*vector[j];
  }
}

そして、これはシーケンシャルな方法のコードです:

for (i=0;i<m_size;i++)
        for(j=0;j<m_size;j++)
            result[i] += matrix[i][j] * vector[j];

999x999 の行列と 999 のベクトルでこれら 2 つの実装を試したところ、実行時間は次のようになりました。

シーケンシャル: 5439 ミリ秒 パラレル: 11120 ミリ秒

OpenMP がシーケンシャル アルゴよりもはるかに遅い理由を本当に理解できません (2 倍以上遅い!) 私の問題を解決できる人はいますか?

4

3 に答える 3

19

あなたのコードは、すべてのキャッシュ コヒーレント システムに典型的な、いわゆる偽共有の影響を部分的に受けています。result[]つまり、配列の多くの要素が同じキャッシュ ラインに収まります。スレッドが演算子の結果としてi書き込みを行うと、その部分を保持しているキャッシュ ラインがダーティになります。次に、キャッシュ コヒーレンシ プロトコルは、他のコア内のそのキャッシュ ラインのすべてのコピーを無効にし、上位レベルのキャッシュまたはメイン メモリからコピーを更新する必要があります。の配列と同様に、1 つのキャッシュ ライン (x86 では 64 バイト) が 8 つの要素を保持し、さらにresult[i]+=result[]resultlong longresult[i]同じキャッシュ ラインには他に 7 つの配列要素があります。したがって、2 つの「隣接する」スレッドが常にキャッシュ ラインの所有権をめぐって争う可能性があります (各スレッドが別々のコアで実行されていると仮定します)。

あなたのケースで誤った共有を軽減するための最も簡単な方法は、各スレッドが反復ブロックを取得することです。そのサイズは、キャッシュ ライン内の要素の数で割り切れます。たとえば、繰り返しスペースが断片化されすぎないように十分に大きくする必要があるschedule(static,something*8)場所を適用できますが、同時に、各スレッドがブロックを取得できるように十分に小さくする必要があります。somethingたとえば、m_size999 と 4 つのスレッドに等しい場合、schedule(static,256)節をparallel for構文に適用します。

コードの実行が遅くなるもう 1 つの部分的な理由は、OpenMP が有効になっている場合、共有変数が割り当てられているときにコンパイラがコードの最適化を適用するのをためらう可能性があることです。OpenMP は、いわゆるリラックス メモリ モデルを提供します。このモデルでは、各スレッドで共有変数のローカル メモリ ビューが異なることが許可flushされ、ビューを同期するために構造が提供されます。volatileしかし、コンパイラは通常、他のスレッドが非同期化された共有変数にアクセスする必要がないことを証明できない場合、共有変数を暗黙的に認識します。result[i]のみに割り当てられ、の値であるため、あなたのケースはそれらの1つですresult[i]他のスレッドによって使用されることはありません。シリアルの場合、コンパイラはおそらく内部ループからの結果を保持する一時変数を作成しresult[i]、内部ループが終了した後にのみ割り当てます。並列のケースでは、これにより一時的に非同期のビューがresult[i]他のスレッドに作成されると判断し、最適化を適用しないことを決定する場合があります。記録のために、GCC 4.7.1-O3 -ftree-vectorizeでは、OpenMP が有効な場合と無効な場合の両方で一時変数のトリックを行います。

于 2013-05-05T02:45:57.367 に答える
0

Hristoのコメントを参照してこれを行いました。schedule(static, 256) を使ってみました。私にとっては、デフォルトのチャンクサイズを変更しても役に立ちません。たぶんそれはそれをさらに悪化させます。スケジュールを設定した場合と設定しない場合のスレッド番号とそのインデックスを出力しました。OpenMP が既にスレッド インデックスを互いに遠く離れた場所に選択していることは明らかで、偽共有が問題にならないように見えます。私にとって、このコードはすでに OpenMP で優れた効果を発揮しています。

#include "stdio.h"
#include <omp.h>

void loop_parallel(const int *matrix, const int ld, const int*vector, long long* result, const int m_size) {
    #pragma omp parallel for schedule(static, 250)
    //#pragma omp parallel for
    for (int i=0;i<m_size;i++) {
        //printf("%d %d\n", omp_get_thread_num(), i);
        long long sum = 0;
        for(int j=0;j<m_size;j++) {
            sum += matrix[i*ld +j] * vector[j];
        }
        result[i] = sum;
    }
}

void loop(const int *matrix, const int ld, const int*vector, long long* result, const int m_size) {
    for (int i=0;i<m_size;i++) {
        long long sum = 0;
        for(int j=0;j<m_size;j++) {
            sum += matrix[i*ld +j] * vector[j];
        }
        result[i] = sum;
    }
}

int main() {
    const int m_size = 1000;
    int *matrix = new int[m_size*m_size];
    int *vector = new int[m_size];
    long long*result = new long long[m_size];
    double dtime;

    dtime = omp_get_wtime();
    loop(matrix, m_size, vector, result, m_size);
    dtime = omp_get_wtime() - dtime;
    printf("time %f\n", dtime);

    dtime = omp_get_wtime();
    loop_parallel(matrix, m_size, vector, result, m_size);
    dtime = omp_get_wtime() - dtime;
    printf("time %f\n", dtime);

}
于 2013-05-05T18:58:21.680 に答える