OpenMPプログラミング - 並列実行の競合対策

いちごパック > OpenMPの解説 > OpenMPプログラミング - 並列実行の競合対策

競合対策の方法

並列実行中に同じリソースを変更する可能性がある場合には、競合対策が必要になります。 基本的な競合対策として、バリアとクリティカルセクションを説明してきました。 これら2つの競合対策を使えばどのようなソースコードでも競合の対策は可能ですが、 OpenMPは他にも次のomp atomicやomp for reductionという競合対策を提供しています。
OpenMPの機能内容
omp atomic排他制御つき演算を提供する。
omp for reductionリダクションと呼ばれる特別な演算を提供する。
これらを順に説明していきます。

排他制御つき演算

opm parallelの対象範囲でforやセクションを使う場合は、 排他制御が必要になります。 例えば、sectionsを使い、 第1セクションではichigovalに1から10までの数値を加え、 第2セクションではichigovalに11から20までの数値を加える次のソースコードを考えてみます。 
#include <iostream>

int main()
{
    int ichigoval = 0;

    #pragma omp parallel
    {
        #pragma omp sections
        {
            #pragma omp section
            {
                int l_val = ichigoval;
                for ( int ichigoloop = 1; ichigoloop <= 10; ichigoloop++ ) {
                    l_val += ichigoloop;
                    #pragma omp critical(crit_cout)
                    {
                        std::cout << ".";
                    }
                }
                ichigoval = l_val;
            }
            #pragma omp section
            {
                int l_val = ichigoval;
                for ( int ichigoloop = 11; ichigoloop <= 20; ichigoloop++ ) {
                    l_val += ichigoloop;
                    #pragma omp critical(crit_cout)
                    {
                        std::cout << ".";
                    }
                }
                ichigoval = l_val;
            }
        }
        #pragma omp barrier

        #pragma omp master
        {
            #pragma omp critical(crit_cout)
            {
                std::cout << std::endl;
                std::cout << "ichigoval = " << ichigoval << std::endl;
            }
        }
        #pragma omp barrier
    }

    return 0;
}
各セクションは、はじめにichigovalを読み込み、その値に数値を加えてからichigovalに計算結果を書き戻しています。 複数のスレッドで同一の変数ichigovalを更新しますので、排他制御をしないとこのソースコードは期待通り動きません。 この出力は例えば次のようになります。 
....................
ichigoval = 155
この出力例では、ichigovalが更新される前に2つのスレッドでそれぞれichigovalを読み込んだため、 いずれのスレッドでもichigovalの値として0を読み込みました。 各スレッドで数値を加えて書き戻した結果、先にichigovalを更新したスレッドの結果は、 後にichigovalを更新したスレッドの結果で上書きされ、期待とは違った結果が得られました。
クリティカルセクションを入れれば、この問題を避けることができます。 
#include <iostream>

int main()
{
    int ichigoval = 0;

    #pragma omp parallel
    {
        #pragma omp sections
        {
            #pragma omp section
            {
                #pragma omp critical(crit_val)
                {
                    int l_val = ichigoval;
                    for ( int ichigoloop = 1; ichigoloop <= 10; ichigoloop++ ) {
                        l_val += ichigoloop;
                        #pragma omp critical(crit_cout)
                        {
                            std::cout << ".";
                        }
                    }
                    ichigoval = l_val;
                }
            }
            #pragma omp section
            {
                #pragma omp critical(crit_val)
                {
                    int l_val = ichigoval;
                    for ( int ichigoloop = 11; ichigoloop <= 20; ichigoloop++ ) {
                        l_val += ichigoloop;
                        #pragma omp critical(crit_cout)
                        {
                            std::cout << ".";
                        }
                    }
                    ichigoval = l_val;
                }
            }
        }
        #pragma omp barrier

        #pragma omp master
        {
            #pragma omp critical(crit_cout)
            {
                std::cout << std::endl;
                std::cout << "ichigoval = " << ichigoval << std::endl;
            }
        }
        #pragma omp barrier
    }

    return 0;
}
ichigovalに対し排他制御が行われるため、期待通りの結果が得られます。 
....................
ichigoval = 210
しかし、このソースコードは演算部分全体をクリティカルセクションで保護しているため、 先にクリティカルセクションを得たスレッドがichigoloopの値を加えている間、 もう1つのスレッドは待機しています。その結果、CPUの利用率は下がってしまいます。
クリティカルセクションによる保護領域を最小限にすれば、 CPUの利用率を上げることができます。 この例では、最初にichigovalの値を読み込むのではなく、 0から加算した値を求め、最後にichigovalに加算するように変更すれば、 クリティカルセクションは最後のichigovalに加算する部分だけですみます。 
#include <iostream>

int main()
{
    int ichigoval = 0;

    #pragma omp parallel
    {
        #pragma omp sections
        {
            #pragma omp section
            {
                int l_val = 0;
                for ( int ichigoloop = 1; ichigoloop <= 10; ichigoloop++ ) {
                    l_val += ichigoloop;
                    #pragma omp critical(crit_cout)
                    {
                        std::cout << ".";
                    }
                }
                #pragma omp critical(crit_val)
                {
                    ichigoval += l_val;
                }
            }
            #pragma omp section
            {
                int l_val = 0;
                for ( int ichigoloop = 11; ichigoloop <= 20; ichigoloop++ ) {
                    l_val += ichigoloop;
                    #pragma omp critical(crit_cout)
                    {
                        std::cout << ".";
                    }
                }
                #pragma omp critical(crit_val)
                {
                    ichigoval += l_val;
                }
            }
        }
        #pragma omp barrier

        #pragma omp master
        {
            #pragma omp critical(crit_cout)
            {
                std::cout << std::endl;
                std::cout << "ichigoval = " << ichigoval << std::endl;
            }
        }
        #pragma omp barrier
    }

    return 0;
}
このソースコードでも排他制御は期待通り行われますので、同じ結果が得られます。 
....................
ichigoval = 210
ここで得られたソースコードでは、 変数に値を加える部分だけがクリティカルセクションで保護されています。
OpenMPでは、変数に特定の演算をするだけといった単純な演算に限り、 クリティカルセクションやバリアを使わずに排他制御できる、 omp atomicと呼ぶ機能が提供されています。 omp atomicによる更新中にほかのスレッドがその変数にアクセスする場合、そのスレッドは変数の更新が終わるまで待ってから変数にアクセスします。 omp atomicの対象は次の1演算のみであり、omp atomicを適用できる主な演算は++、--、+=、-=、*=、/=、&=、^=、|=、<<=、>>=です。
この機能を使うと、先ほどのソースコードは次のように書くこともできます。 
#include <iostream>

int main()
{
    int ichigoval = 0;

    #pragma omp parallel
    {
        #pragma omp sections
        {
            #pragma omp section
            {
                int l_val = 0;
                for ( int ichigoloop = 1; ichigoloop <= 10; ichigoloop++ ) {
                    l_val += ichigoloop;
                    #pragma omp critical(crit_cout)
                    {
                        std::cout << ".";
                    }
                }
                #pragma omp atomic
                    ichigoval += l_val;
            }
            #pragma omp section
            {
                int l_val = 0;
                for ( int ichigoloop = 11; ichigoloop <= 20; ichigoloop++ ) {
                    l_val += ichigoloop;
                    #pragma omp critical(crit_cout)
                    {
                        std::cout << ".";
                    }
                }
                #pragma omp atomic
                    ichigoval += l_val;
            }
        }
        #pragma omp barrier

        #pragma omp master
        {
            #pragma omp critical(crit_cout)
            {
                std::cout << std::endl;
                std::cout << "ichigoval = " << ichigoval << std::endl;
            }
        }
        #pragma omp barrier
    }

    return 0;
}
omp atomicにより排他制御が行われますので、期待通りの結果が得られます。 
....................
ichigoval = 210

omp atomicにはいくつかの制約がありますので、 特に必要がなければクリティカルセクションを使ったほうが良いでしょう。 omp atomicは、後述のomp for reductionの中で使うことはできません。 また、omp atomicを使う場合は、対象とする変数をreinterpret_castなどで別の型としてアクセスしてはいけません。

リダクション

1から1000までの合計(答えは500500)を求めるプログラムの並列化を考えます。 omp forを使えばスレッド分割してくれますので、 omp paralellの対象領域内で、 各スレッドで初期値が0の変数を用意し、各スレッドで分割された部分の合計値を求めたうえで、 最後にその結果を全スレッドぶん加えれば答えが得られます。 ソースコードは次のようになります。 
#include <iostream>

int main()
{
    int ichigoval = 0;

    #pragma omp parallel
    {
        int l_val = 0;
        #pragma omp for nowait
        for ( int ichigoloop = 1; ichigoloop <= 1000; ichigoloop++ ) {
            l_val += ichigoloop;
        }
        #pragma omp critical(crit_cout)
        {
            std::cout << "l_val = " << l_val << std::endl;
        }
        #pragma omp atomic
            ichigoval += l_val;

        #pragma omp barrier

        #pragma omp single nowait
        {
            #pragma omp critical(crit_cout)
            {
                std::cout << "ichigoval = " << ichigoval << std::endl;
            }
        }
        #pragma omp barrier
    }

    return 0;
}
ソースコード中、ichigovalは全スレッド共通の変数、l_valは各スレッドで別々の変数になります。 ichigovalはomp atomicにより排他制御されますので、このソースコードにより正しい結果が得られます。 
l_val = 31375
l_val = 218875
l_val = 156375
l_val = 93875
ichigoval = 500500
この例のように、複数のスレッドの結果を束ねて1つの結果を得る操作はリダクションと呼ばれます。 リダクションは並列化の際によく使われますので、OpenMPではomp forの追加機能としてreduction(操作:変数名)を提供しています。
リダクション機能は、reduction(+:ichigoval)のように、 操作(この例では+)と、全スレッド共通の変数名(この例ではichigoval)を指定して利用します。 reductionは、次の2つの機能を組み合わせたものです。
  • 指定された全スレッド共通の変数とは別に、スレッドごとに変数を準備し、操作ごとに決められた初期値をセットします。
  • バリアのタイミングで、各スレッドの変数値をまとめて全スレッド共通の変数に反映させます。forにnowait指定がない場合は、forが終わるタイミングでバリアが自動的に挿入されますので、このタイミングで反映されます。

    • リダクションで指定できる操作は、+、-、*、&、&&、|、||、^です。 ほとんどの操作ではスレッド変数の初期値は0になりますが、

    と&の初期値は1、&の初期値は全ビットを1とした数値になります。

    1つのomp forに対してreductionを複数指定することも可能です。
    reductionは得られた結果の統合にバリアを必要としますので、 reductionを使うのであればomp forにnowait指定はしないほうが良いでしょう。
    reductionを使って先のソースコードを書き換えると次のようになります。 
    #include <iostream>

int main()
{
    int ichigoval = 0;

    #pragma omp parallel
    {
        #pragma omp for reduction(+:ichigoval)
        for ( int ichigoloop = 1; ichigoloop <= 1000; ichigoloop++ ) {
            ichigoval += ichigoloop;
        }

        #pragma omp single nowait
        {
            #pragma omp critical(crit_cout)
            {
                std::cout << "ichigoval = " << ichigoval << std::endl;
            }
        }
        #pragma omp barrier
    }

    return 0;
}
    得られる結果は次のようになります。 
    ichigoval = 500500

    関連ページ

  • OpenMPの解説 目次
  • 前の項目: 複数のソースコードの並列実行
  • 次の項目: 変数のスレッドコピー