【c/c++】OpenMPの基礎的な使い方+並列処理で意識すべきこと【OpenMP】

c/c++ プログラミング OpenMP

OpenMPの基礎的な使い方を通して並列処理で意識すべきことを書きます。
ここではコンパイル方法や詳細な内容については触れませんが、OpenMPのより詳細な使い方については参考文献を参照してください。
記事の内容をざっくりとまとめると、並列化の上で知っておかなければならないことは大まかに以下の3点です。

  • その処理は並列化可能か
  • 負荷の分散は十分考えられているか
  • 共有変数への不正なアクセスは発生しないか

並列化の基本

並列化の可否

そもそもコードを並列化するためには、行われる処理がそれぞれ独立している必要が有ります。
例えば以下のようなコードではa = 1;とb = a + 1;は並列化することはできません。a = 1;の結果を得なければb = a + 1;を計算できないからです。

int a, b;

a = 1;
b = a + 1;

並列化可能なコードとは、並列実行したいそれぞれの処理が別の処理に対して影響を与えないようなコードです。

セクションごとの並列化

ここでは、並列化するコードの単位をセクションと呼びます。
処理Aをやっている間に並行して処理Bを行う（ex.サーバーからファイルを落とす間に別の処理を行うなど）ということができれば、場合によっては大きな高速化が期待できます。

OpenMPを用いたセクションでの並列化

以下はOpenMPを用いた2つのセクションでの並列化の例です。（OpenMP - PukiWiki for PBCG Lab より引用）

#pragma omp parallel sections num_threads(2)
{
    #pragma omp section
    {
        /* セクション1 */
    }
    #pragma omp section
    {
        /* セクション2 */
    }
}
セクションごとの処理コストの均等化の必要性

処理の並列化は、上手くやればコア数分（ハイパースレッディングなどが有ればそれ以上）の高速化が期待できます。一方、セクションに分割して並列化を行ったとしても、セクションごとの処理コストの均等化を行わなければ、最終的には一番コストの重いコードの実行時間までしか高速化できない点には注意が必要でしょう。
例として処理A, B, C, D（処理コスト：A ＞ B ＞ C ＞ D）が有ったとき、セクション1が処理A, B、セクション2がC, Dとして並列化を行ってしまうと、全体ではセクション1の実行時間が足を引っ張るため思ったほど高速化しない、ということになります。これは後述するループの並列化においても同様で、例えばループ中の処理コストがどこかに偏っている場合、分割手法によってはあまり高速化できません。
このように、並列化によって高速化したい場合、それぞれのセクションの処理コストをできるだけ均一にすることが重要となります。

ループの並列化

特に並列化で触れる機会が多いのは、ループの並列化でしょう。
ループの並列化は『一番外側の(iに関する)ループをプロセス/スレッドに分割して並列化し、一番内側のループ（kに関するループ）をSIMD命令で並列化する*1』というやり方が基本です。
「分割すればした分だけ早くなるのでは？」と感じるかもしれませんが、プロセス/スレッドの作成やプロセス間通信などにもコストが掛かることから、コア数以上の並列化を行っても実行速度は低下する場合が多いです。一般的な環境では一番外側のループを並列化した時点でコア数を使い切ってしまうため、分割は一番外側だけにするというのがベターとしました。
特殊な例として、スーパーコンピュータのようにコア数が物凄く多い環境では、コア数を使い切るための分割の最適化が必要となります。要はコア数とスレッド分割数をできるだけ近づけた方がいいということです。

OpenMPを使ったループの並列化

OpenMPでは、特に設定しなければ利用する論理コア数に合わせて自動でスレッドの分割数を決定してくれます。
単純に書くと以下のようになります。OpenMPでは更に自由度の高い（＝複雑な）並列化の指定も可能ですが、ここでは省略します。

#pragma omp parallel for
for(int i = 0; i < ... ; i++){
    for(int j = 0; j < ... ; j++){
        for(int k = 0; k < ... ; k++){
            /* 何らかの処理 */
        }
    }
}
schedule指示句によるループスケジューリング

前述のとおり、ループ中に処理コストの偏りが有ればループを均等に分割しても十分に高速化しないことが考えられます。このようなループはschedule指示句を追加することで簡単に高速化できる場合が有ります。
schedule指示句はparallel for構文の後ろに付けることで、ループを大まかにどのように分割するかを指定できます。
勉強不足で挙動について理解できていないので詳しく書けませんが、自分で確認したところ、計算量がインデックスiの2乗に比例するようなプログラムでschedule(guided)を指定したところ、20%の高速化が確認できました。
以下のページが参考になると思います。
OpenMP* ループ・スケジュール | iSUS

共有メモリへのアクセス

並列処理では複数のプロセスやスレッドが同時に処理を行うため、スレッド間で共有される変数が予期せぬタイミングで書き換えられ、結果が不正となる場合があります。
共有メモリへのアクセスは並列化の上で意識すべき最も重要な内容であるため、1章を割いて説明します。

共有メモリの不正な読み書き

以下のコードを実行すると、本来であれば5050が出力されますが、実際はそうならない場合があります。

omp_set_num_threads(100); //変数の不正な上書きを誘発するために実行スレッド数を多めに設定

int count = 0, factor;
int i;

#pragma omp parallel for
for(i = 1; i <= 100; i++) {
    factor = i -1;
    count += factor;
    count++;
}

printf("%d", count);
なぜこうなったのか

CPUは以下のような手順で命令を実行します。

  1. 変数をメモリから読み出す
  2. 処理を行う
  3. メモリへ結果を書き戻す

一方並列化して実行を行うと、タイミングによっては、以下のように共有メモリ上の演算結果が破壊されてしまいます。

  1. 変数をスレッド1が読み出す
  2. 変数をスレッド2が読み出す ← スレッド1による処理の結果は反映されていない！
  3. スレッド1, 2が処理を行う
  4. スレッド1がメモリへ書き戻す
  5. スレッド2がメモリへ書き戻す ← スレッド1による処理の結果が上書きされる！

つまり、上の例では変数factorが複数スレッドから同時に書き換えられたり、countが同時に複数のスレッドから読み出されるといった事態が発生すると結果が不正になるということです。

不正なアクセスを防ぐためには

このような不正なアクセスは、複数のスレッドから呼び出される変数に対して大まかに3通つの手段を講じることで防げます。

  1. スレッドごとにローカル（プライベート）な変数にする
  2. 変数へのアクセスをロックする
  3. 個別の書き込みスペースを用意する
スレッドごとにローカル（プライベート）な変数にする

例では、変数factorは毎回ループの先頭で初期化されています。このような変数は各スレッドごとにローカルな変数とすることで、別スレッドからの操作が起こらないようにできます。
具体的な方法として、c/c++のバージョンが高ければ変数factorをループの先頭で宣言するように変更するのが最も単純な方法です。
OpenMPの機能としては、以下のようにprivate([変数名])指示句を追加することで、指定した変数をプライベートなものとして扱うことができます。

#pragma omp parallel for private(factor) 
for(i = 1; i <= 100; i++) {
    factor = i -1;
    count += factor;
    count++;
}
変数へのアクセスをロックする

例では、変数countへのアクセスをロックすることで不正な読み書きを防ぐことができます。OpenMPではatomic指示句やcritical指示句を用いる、ロックを行うといった手法が有ります*2。
実行速度は『atomic指示句 ＞ critical指示句 ＞ ロック』の順で高速です。ただしatomic指示句は利用可能な命令に制限があるため、注意が必要です。
以下はcritical指示句を利用した例です。この例ではatomic指示句が使えなかったので、critical指示句を利用しています。

#pragma omp parallel for private(factor)
for(i = 1; i <= 100; i++) {
    factor = i -1;
    #pragma omp critical
    {
        count += factor;
        count++;
    }
}
個別の書き込みスペースを用意する

例では一々変数countへの書き込みを行っていることが原因で不正なアクセスが発生しています。
先ほどは変数へのアクセスをロックすることでこの問題を回避していましたが、答えを書き込むための配列int temp[100]を用意しておき、あるiに対する計算結果をtemp[ i-1 ]に格納し、最後に総和を計算することによっても回避することができると考えられます。
OpenMPではreduction指示句を用いることで、自動的に『個別の書き込みスペースの確保→集計』までを行ってくれます。
以下の例では、critical指示句の代わりにreduction指示句に総和を指定することでこの問題を回避しています。

#pragma omp parallel for private(factor) reduction(+:count)
for(i = 1; i <= 100; i++) {
    factor = i -1;
    count += factor;
    count++;
}

reduction指示句に指定可能な演算子の一覧はこちらをご覧ください。

参考文献

C++ 開発者が陥りやすい OpenMP* の 32 の罠 | iSUS
OpenMP - PukiWiki for PBCG Lab
OpenMP超入門 その1 - Qiita
OpenMPによるfor文の並列化
Reduction Clause
OpenMP* ループ・スケジュール | iSUS

オマケ1（OpenMPを利用する際のCMake）

cmake_minimum_required(VERSION 3.10)
project([プロジェクト名] C)

find_package( OpenMP )

set(CMAKE_C_STANDARD 11)
set (CMAKE_C_FLAGS "${CMAKE_C_FLAGS} ${OpenMP_C_FLAGS}")

add_executable([プロジェクト名] [ソースコード].c)

オマケ2（SIMD命令に関する記事を作成しました）

wrongwrong163377.hatenablog.com

*1:この記事ではSIMD命令には触れません。

*2:これらは厳密には処理の内容が異なりますが、得られる結果は同じなのでまとめて取り扱います。