OpenMPと並列処理の順序付け

　並列処理を行うと、実行順序は不定になります。しかしながら、並列ループ内の一部コードを、順番に処理したい場合があります。その場合は、ordered構文（#pragma omp ordered ）と、ループ構文もしくは、パラレルループ構文を組み合わせて使用します。
　分かりやすいように、サンプルプログラム（C言語を使用）を掲載します。

#include <stdio.h>

int main()
{
    int i;

    //並列的に数字を表示
    printf( "これから並列的に数字を表示します・・・\n" );
    #pragma omp parallel for num_threads( 10 )
    for ( i = 0; i < 100; i++ ) {
        printf( " %d", i );
    }
    printf( "\n\n" );

    //順番に数字を表示
    printf( "これから順番に数字を表示します・・・\n" );
    #pragma omp parallel for num_threads( 10 ) ordered
    for ( i = 0; i < 100; i++ ) {
        #pragma omp ordered 
        {
            printf( " %d", i );
        }
    }
    printf( "\n\n" );
    return 0;
}

　サンプルを実行すると、ordered構文を指定したプログラムは、数値が順番に表示されます。これにより、指定された部分のコードが、逐次的に実行されている事が確認できます。
　ordered構文を使用するには、ループ構文で必ずordered指示句を指定します。そして、順番に指定したいコードを ordered構文で指定します。ordered構文で指定されていないコードは、並列に処理されます。
　これで、ordered構文内のコードが、順番に処理されるのがなんとなく分かったと思います。ですが、具体的に、どのように実行されるのかが気になると思いましたので、もうひとつサンプルを用意しました。

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

int main()
{
    int i, count;
    count = 4;
    #pragma omp parallel for num_threads( count ) ordered
    for ( i = 0; i < count; i++ ) {
        printf( "スレッド%dがorderedよりも前の処理をしました。\n", 
            omp_get_thread_num() );
        #pragma omp ordered 
        {
            printf( "スレッド%dがordered内の処理をしました。\n", 
                omp_get_thread_num() );
        }
        printf( "スレッド%dがorderedよりも後の処理をしました。\n", 
            omp_get_thread_num() );
    }
    printf( "\n\n" );
    return 0;
}

　このサンプルを何度か実行し、どの部分のコードがいつ実行されるのかを確認すると、ordered構文の働きが良く分かると思います。
　ordered構文で指定された範囲のコードは、必ずスレッドのID昇順で実行されています。一方、ordered構文よりも前のコードは、順番に関係なく実行されています。ordered構文よりも後のコードについても、短いサンプルなので確認し難いですが、ordered構文で指定された範囲のコードが順番に実行された後、並列的に実行されています。
　以上の様に、ordered構文は、指定したコードブロック内のコードを、逐次化する事により順番に実行します。プログラムを逐次化すると、パフォーマンスが低下するので、ordered構文は極力使用せず、使用する際も指定するコードの範囲を絞るのが得策です。


【参考資料】

• MSDN
• OpenMP公式ホームページ
• OpenMP入門―マルチコアCPU時代の並列プログラミング

OpenMPと非同期処理

　OpenMPとバリアでOpenMPには暗黙のバリアがある事について触れました。では、暗黙のバリアを取り除くにはどうしたらいいのかを気にする人が居ると思いますので、今回は暗黙のバリアを取り除き、非同期に処理をする方法について書きます。
　暗黙のバリアを取り除くには、nowait指示句を使用します。nowait指示句を使用すると、ループ構文等の暗黙のバリアがなくなり、指定されたコードブロック内の処理が非同期に処理がされるようになり、処理速度がアップします。
　暗黙のバリアを使用した同期処理と、暗黙のバリアがない非同期処理の処理スピードを測定するプログラムを使って、この事実を確認します。

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

int main()
{
    int i, a, b, max;
    double start, end;
    double diff, diff1;
    max = 50000000;

    /* 同期処理 */
    a = b = 0;
    start = omp_get_wtime();
    #pragma omp parallel shared( a, b )
    {
        #pragma omp for
        for ( i = 0; i < max; i++ ) {
            #pragma omp atomic
            ++a;
        }

        #pragma omp for
        for ( i = 0; i < max; i++ ) {
            #pragma omp atomic
            ++b;
        }
    }
    end = omp_get_wtime();
    diff = ( end - start );
    printf( "同期処理時の処理時間は%f秒です。\n", diff );

    /* 非同期処理 */
    a = b = 0;
    start = omp_get_wtime();
    #pragma omp parallel shared( a, b )
    {
        #pragma omp for nowait
        for ( i = 0; i < max; i++ ) {
            #pragma omp atomic
            ++a;
        }

        #pragma omp for nowait
        for ( i = 0; i < max; i++ ) {
            #pragma omp atomic
            ++b;
        }
    }
    end = omp_get_wtime();
    diff1 = ( end - start );
    printf( "非同期処理時の処理時間は%f秒です。\n", diff1 );

    //差を表示
    printf( "処理時間の差は%f秒です。\n\n", diff - diff1 );
    return 0;
}

　このサンプルを実行すると、暗黙のバリアが存在する同期処理よりも、バリアがない非同期処理の方が速い事が確認できます。このサンプルは実行するプログラムが少ないので、処理時間に殆ど差がありません。ですが、もっと大量のプログラムと、暗黙のバリアが存在する場合、処理時間に差が出てくるでしょう。
　nowait指示句を使用すると、より並列にプログラムを実行する事が出来ますが、発見が困難なバグが発生する可能性が高まります。使用する際には、慎重にプログラミングを行って下さい。
　先ずは、nowait指示句を使用しないプログラムを作成し、それが正しく動作する事を確認します。そして、処理スピードが問題になった時、改めてnowait指示句を使用し、意図どおりに動作しているのか再度確認するとよいでしょう。


【参考資料】

• MSDN
• OpenMP公式ホームページ
• OpenMP入門―マルチコアCPU時代の並列プログラミング

OpenMPとバリア

　処理に複数の段階があり、各段階が前の段階の結果を待たねばならない場合があります。例えば、前処理と後処理で分かれている、一連の処理を並列化したい場合、全てのスレッドが前処理を完了しないと、後処理を始めてはなりません。この場合、バリアを使用します。
　OpenMPでバリアを実現するには、barrier構文（#pragma omp barrier）を使用します。バリアの効果は、サンプルを実行すれば直ぐに分かると思います。

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

int main()
{
    //バリア未使用
    printf("バリアを使用せずに、並列処理を実行します。\n");
    #pragma omp parallel num_threads( 4 )
    {
        printf( "スレッド番号%dの前処理\n", omp_get_thread_num() );
        printf( "スレッド番号%dの後処理\n", omp_get_thread_num() );
    }
    printf( "\n" );

    //バリアを使用
    printf("バリアを使用して、並列処理を実行します。\n");
    #pragma omp parallel num_threads( 4 )
    {
        printf( "スレッド番号%dの前処理\n", omp_get_thread_num() );
        #pragma omp barrier
        printf( "スレッド番号%dの後処理\n", omp_get_thread_num() );
    }
    printf( "\n" );
    return 0;
}

　このサンプルを実行すると、前処理と後処理が綺麗に分かれます。
　バリア機能を初めて知った人は、あまり使い道がない機能だと感じるかもしれません。しかし、実のところOpenMPでは暗黙のバリアとして、随所で使用されている有用な機能です。暗黙のバリアがあるお陰で、タイミングに関する並列処理特有のバグが発生する事を避けられています。
　具体的には、parallel構文（#pragma omp parallel）、ループ構文（#pragma omp for）、single構文（#pragma omp single）の終わりには、暗黙のバリアが存在します。暗黙のバリアを消すには、nowait指示句を使用します。


【参考資料】

• MSDN
• OpenMP公式ホームページ
• OpenMP入門―マルチコアCPU時代の並列プログラミング

OpenMPとクリティカルセクション

　atomic構文は、単一の単純なプログラムのみ適用できます。しかし、関係がある複数のプログラムを、不可分に処理したい場合があります。不可分とは、複数のスレッドが、共有するリソースを同時に操作しない事です。
　並列プログラミングでは、共有リソースは不可分に処理しないと、正常な結果を得られません。この場合は、クリティカルセクションを使用します。OpenMPを使って、クリティカルセクションを実現したい場合、critical構文（#pragma omp critical）を使用します。
　文章だけでは分かりにくいと思いますので、サンプル（C言語使用）を元に解説を続けます。

#include <stdio.h>

int main()
{
    int i, x, y, max;
    max = 10000;

    /* クリティカルセクションなしで計算 */
    x = y = 0;
    #pragma omp parallel for shared( x, y )
    for ( i = 0; i < max; i++ ) {
        ++x;
        y += x;
    }
    printf( "critical構文を、指定していない場合の値は[x:%d][y:%d]です。\n", x, y );

    /* クリティカルセクション内で計算 */
    x = y = 0;
    #pragma omp parallel for shared( x, y )
    for ( i = 0; i < max; i++ ) {
        #pragma omp critical
        {
            ++x;
            y += x;
        }
    }
    printf( "critical構文を、指定した場合の値は[x:%d][y:%d]です。\n\n", x, y );
    return 0;
}

　このサンプルは、共有変数xとyの値を計算しています。変数xとyは、互いに関係が深いと仮定して下さい。サンプルを実行すれば、critical構文を使用しないと、更新の喪失が起こる事が確認できます。
　atomic構文を複数使えばいいと思う方もいるでしょうが、変数xとyの関係が深い場合、それぞれの変数がアトミックに更新されても、処理結果は予想外のものになり、正常な処理ではなくなる可能性があります。
　何故ならば、並列処理では、同時に複数の処理が実行されますので、他のスレッドが処理した結果が混ざってしまう場合があるからです。処理A内で、処理Bが更新したyの値を使用してしまった場合、処理結果は予想もつかないものになるでしょう。まとまった処理は、クリティカルセクションで一度に指定しましょう。
　critical構文は#pragma omp critical( name )のように、クリティカルセクションに名前を付ける事が出来ます。名前を付ける事により、同時に実行できる処理を増やす事が出来ます。
例えば、#pragma omp critical( critical0 )と#pragma omp critical( critical1 )を指定したとします。この場合、名前を付けなかった時とは違い、クリティカルセクション0とクリティカルセクション1内のプログラムが同時に実行されます。一方、名前を付けなかった場合、未指定の名前（unspecified name）と看做され、同時に一つのクリティカルセクション内のプログラムしか処理する事が出来ません。
　ただし、複数のクリティカルセクションは、互いに関係がない処理に指定して下さい。関係がある処理に対して、複数のクリティカルセクションを使用すると、正常な処理結果を得られません。
　最後に、critical構文を使用するにあたって、一つ注意するべきことを述べます。critical構文を多用しないでください。クリティカルセクションは、共有リソースを単一スレッドのみ処理できるようにする技術なので、並列処理のパフォーマンスを下げます。本当に必要な時だけ使用するようにして下さい。


【参考資料】

• MSDN
• OpenMP公式ホームページ
• OpenMP入門―マルチコアCPU時代の並列プログラミング

OpenMPのアトミック命令

同じデータを対象に並列処理を行うと、データの整合性が保てなくなります。
文章ではイメージし難いですので、サンプルプログラム（C言語を使用）を用いて解説します。

#include <stdio.h>

int main()
{
    int i, count, max;
    max = 100000;

    /* アトミック構文を指定していないカウント処理 */
    count = 0;
    #pragma omp parallel for shared( count )
    for ( i = 0; i < max; i++ ) {
        ++count;
    }
    printf( "atomic構文指定なし：処理回数%d\n", count );

    /* アトミック構文を指定したカウント処理 */
    count = 0;
    #pragma omp parallel for shared( count )
    for ( i = 0; i < max; i++ ) {
        #pragma omp atomic
        ++count;
    }
    printf( "atomic構文指定あり：処理回数%d\n\n", count );
    return 0;
}

　このサンプルの内容は、処理回数をカウントする単純なものです。一見何の問題もありません。しかし、何度か実行すると、atomic構文を指定していない方のプログラムは、正常にカウントされない時があります。この現象を、更新の喪失と呼びます。
　更新の喪失が起こる原因は、一つの操作に見える++countが実は三つの操作だからです。++countは、現在値を取り出し、それに1を加え、新しい値を書き戻しています。この様な三つの操作をリード・モディファイ・ライト（read-modify-write）操作と呼びます。
　更新の喪失を防ぐ方法は、リード・モディファイ・ライト操作をアトミック操作（単一不可分操作）へ変更する事です。OpenMPでは、atomic構文（#pragma omp atomic）を指定する事により、これを実現します。
　++x、x++、--x、x--、x += 1、x -= 1の様なプログラムが、リード・モディファイ・ライト操作です。一見単純なこれらのプログラムも、並列処理時に変数を共有すると、更新の喪失などの問題が発生するので十分に注意しましょう。


【参考資料】

• MSDN
• OpenMP公式ホームページ
• OpenMP入門―マルチコアCPU時代の並列プログラミング