1

OpenMP を使用して、バランスの取れていないネストされた for ループを使用してアルゴリズムを並列化しようとしています。前代未聞の政府の秘密のプロジェクトであるため、元のコードを投稿することはできませんが、おもちゃの例を次に示します。

for (i = 0; i < 100; i++) {
    #pragma omp parallel for private(j, k)
    for (j = 0; j < 1000000; j++) {
        for (k = 0; k < 2; k++) {
            temp = i * j * k;      /* dummy operation (don't mind the race) */
        }
        if (i % 2 == 0) temp = 0;  /* so I can't use openmp collapse */
    }
}

現在、この例は複数のスレッドで動作が遅くなります (シングル スレッドで~1 秒、2 スレッドで~2.4 秒など)。

注意事項:

  • 外側の for ループは順番に実行する必要があります (前のステップに応じて) (私の知る限り、OpenMP は内側のループを適切に処理するため、各ステップでスレッドが作成/破棄されませんよね?)

  • 典型的なインデックス番号が例に示されています(100, 1000000, 2)

  • ダミー操作はわずかな操作で構成されています

  • 最も内側のループの外側にいくつかの条件付き操作があるため、折りたたみはオプションではありません (とにかくパフォーマンスが向上するようには見えません)

恥ずかしいほど並列アルゴリズムのように見えますが、過去 2 日間はスピードアップしていないようです。ここでの最善の戦略は何でしょうか?

4

2 に答える 2

5

残念ながら、この恥ずかしい並列アルゴリズムは、パフォーマンスの高い並列処理を実装する方法の恥ずかしいほど悪い例です。そして、私のクリスタルボールは、 以外iにtempも共有自動変数であることを教えてくれるので、このテキストの残りの部分ではそれを仮定します. また、Nehalem より前の CPU を使用していることもわかります...

ここには、コード変換とキャッシュの一貫性という 2 つの速度低下の原因があります。

並列領域が実装される方法は、それらのコードが個別の関数で抽出されることです。共有ローカル変数は構造体に抽出され、並列領域を実行するチーム内のスレッド間で共有されます。OpenMP 変換の下では、コード サンプルは次のようになります。

typedef struct {
    int i;
    int temp;
} main_omp_fn_0_shared_vars;

void main_omp_fn_0 (void *data) {
    main_omp_fn_0_shared_vars *vars = data;

    // compute values of j_min and j_max for this thread

    for (j = j_min; j < j_max; j++) {
        for (k = 0; k < 2; k++) {
            vars->temp = vars->i * j * k;
        if (vars->i % 2 == 0) vars->temp = 0;
    }
}

int main (void) {
    int i, temp;
    main_omp_fn_0_shared_vars vars;

    for (i = 0; i < 100; i++)
    {
        vars.i = i;
        vars.temp = temp;

        // This is how GCC implements parallel regions with libgomp

        // Start main_omp_fn_0 in the other threads
        GOMP_parallel_start(main_omp_fn_0, &vars, 0);

        // Start main_omp_fn_0 in the main thread
        main_omp_fn_0(&vars);

        // Wait for other threads to finish (implicit barrier)
        GOMP_parallel_end();

        i = vars.i;
        temp = vars.temp;
    }
}

中間値はレジスタに格納できず、毎回ロードおよび格納されるため、この方法でアクセスするtempと、わずかなペナルティが発生します。i

低下のもう 1 つの原因は、キャッシュ コヒーレンシ プロトコルです。複数の CPU コアで実行されている複数のスレッドから同じメモリ位置にアクセスすると、多くのキャッシュ無効化イベントが発生します。さらに悪いことにvars.i、vars.temp同じキャッシュ ラインで終了する可能性が高く、vars.i読み取りのみと書き込みvars.tempのみが行われますが、内部ループの反復ごとに完全なキャッシュ無効化が発生する可能性があります。

通常、共有変数へのアクセスは、アトミック ステートメントやクリティカル セクションなどの明示的な同期構造によって保護されており、その場合、パフォーマンスの低下が十分に予想されます。

于 2012-06-29T09:28:51.857 に答える
2

オーバーヘッドについて考えてみてください。

内側のループで作業を実行するためにx個のスレッドを作成し、それらを破棄してから再度作成するためには、外側のループが必要なので...などを100回繰り返します。

内側のループ内の最長のタスクがその作業を完了するまで待ってから、外側のループの次のステップを実行する必要があるため、基本的にこれは同期のオーバーヘッドです。タスクは不規則に見えませんが、実行する作業が小さい場合は、これから抜け出すことができるスピードアップはそれほど多くありません。

ここでスレッドを作成し、プライベート変数を割り当てるコストがかかります。

内側のループ内の作業が小さい場合、このループを並列化することの利点は、上記の並列化のオーバーヘッドのコストを必ずしも上回るとは限らないため、速度が低下することになります。

于 2012-06-29T00:28:26.507 に答える