OpenMPによるfor文の並列化
  • Date:木曜日 21 9月 2017 (PM 03:45:59)
  • Tags:C C++
  • Category:Programming

OpenMPには、forの並列化とsectionによる並列化がありますが、forの並列化のみを扱います。

OpenMPに関する仕様に関しては、kosyu-openmp_c.pdfを読んで勉強します、よくまとまっているのであとあとリファレンスとしても使えます。

以下、C++ 開発者が陥りやすい OpenMP* の 32 の罠 | iSUSを参考に情報をまとめます。

書き方とコンパイル

簡単なOpenMPを使用したコードで説明します。

#include <stdio.h>
#ifdef _OPENMP
#include <omp.h>
#endif

int main() {
#ifdef _OPENMP
  #pragma omp parallel for
#endif
  for (int i = 0; i < 5; ++i) {
#ifdef _OPENMP
    #pragma omp critical
#endif
    {
      printf("Thread No: %d\n");
    }
  }
}

まず、OpenMPを使用するために"omp.h"というヘッダファイルを使用します。"omp.h"はコンパイル時にOpenMPが有効になっていない場合、コンパイルエラーになるのでOpenMPが有効な場合に使用できるマクロ"_OPENMP"がある時のみ読み込むようにします。後述する"#pragma omp"の部分はOpenMPが有効でない場合は無視されるので"_OPENMP"による#ifdefガードは必須ではありません。静的解析ツールなどを使用するとWarningが出る場合があるので、場合によってはOpenMPコード部分にはすべて#ifdefガードを付け足ほうが良いかもしれません。

main関数内でfor文を並列化しています。記法は"#pragma omp"から始まる指示句(指示句と言った場合OpenMPの命令を指すことにします)を使用します。for文を並列化する場合はfor文の直前に"#pragma omp parallel for"をつけるだけで並列化されます。

このコードの場合、出力は並列化されているので順番は保証されません。

Thread No: 0
Thread No: 3
Thread No: 1
Thread No: 4
Thread No: 2

"#pragma omp critical"はprintfで使用する共有のリソース(標準出力)で競合が起こらないためにつけています。

以下のコード例では見やすさのためifdefの記述を省略します。


OpenMPはVisual Studio 2005以降、gcc 4.2以降、intel compiler 12.1以降で使えます(使用可能なバージョンについてここでは説明しません)。

  • Visual Studio: [Projects (プロジェクト)] > [Properties (プロパティ)] > [Configuration Properties (構成プロパティ)] > [C/C++] > [Language (言語)] から有効にする
  • gcc: -fopenmpをつける
  • intel compiler: -openmpをつける

競合状態

競合状態が発生すると同じ入力を与えても同じ出力が保証できなくなります。これは簡単に起こせます、以下のコードは同じ結果を返すとは限りません。

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

int main() {
  double global = 0.0;
  #pragma omp parallel for
  for (int i = 0; i < 5; ++i) {
    if (i != 0) global += 2.0 / (double)(i * i);
  }
  printf("global val: %f\n", global);
}

これはすべての変数に目が行き届くシンプルな例なので競合状態が起こるのは明白ですが、実際の関心事ではforループ内で複雑なデータ構造を扱う場合もあるため意図せず競合状態が発生するケースがあります。

競合状態の回避

クリティカルセッション(#pragma omp critical)とアトミック操作(#pragma omp atomic)、リダクション(記法は後述)を使用することで上記のような競合状態の回避ができます。

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

void critical_session() {
  double global = 0.0;
  #pragma omp parallel for
  for (int i = 0; i < 5; ++i) {
    #pragma omp critical
    {
      if (i != 0) global += 2.0 / (double)(i * i);
    }
  }
  printf("global val: %f\n", global);
}

void atomic() {
  double global = 0.0;
  #pragma omp parallel for
  for (int i = 0; i < 5; ++i) {
    if (i != 0) {
      #pragma omp atomic
      global += 2.0 / (double)(i * i);
    }
  }
  printf("global val: %f\n", global);
}

void reduction() {
  double global = 0.0;
  #pragma omp parallel for reduction(+:global)
  for (int i = 0; i < 5; ++i) {
    if (i != 0) global += 2.0 / (double)(i * i);
  }
  printf("global val: %f\n", global);
}

int main() {
  critical_session();
  atomic();
  reduction();
}

クリティカルセッションとアトミック

OpenMPでは"#pragma omp critical"と"#pragma omp atomic"がクリティカルセッションとアトミック操作になります。

クリティカルセッションは、処理を1スレッドに制限します。アトミック操作は直後の一文を競合を起こさないで安全に変数の値を更新することを保証します。

変数の値を更新する場合はアトミックを使用するほうが効率が良いです。標準出力などの利用や関数呼び出しを使用する場合はアトミックで保証できないのでクリティカルセッションを利用します。

他にロックを利用することもできますが特別な理由がない限りは使いません。この理由にはロックを使うことによるコードの複雑性の回避、ロックを使うことによるバグ(デッドロックなど)の回避、速度(アトミック>クリティカルセッション>ロックの順でアトミックが一番高速)の問題があります。

アトミックとリダクション

演算処理と直後の一文にしか使えませんが、アトミックやクリティカルセクションと置き換えることができます。

リダクションは各スレッドでの計算結果をループ終了後にマージします。

つまり、アトミックの場合はスレッド間で共有されたメモリに対して更新を行いますが、リダクションの場合はスレッドごとにメモリを作成します。

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

int atomic() {
  double global = 0.0;
  #pragma omp parallel for
  for (int i = 0; i < 5; ++i) {
    int ithread = omp_get_thread_num();
    printf("atomic[%d]: %p\n", ithread, &global);
    if (i != 0) {
      #pragma omp atomic
      global += 2.0 / (double)(i * i);
    }
  }
  printf("global val: %f\n", global);
}

int reduction() {
  double global = 0.0;
  #pragma omp parallel for reduction(+:global)
  for (int i = 0; i < 5; ++i) {
    int ithread = omp_get_thread_num();
    printf("reduction[%d]: %p\n", ithread, &global);
    if (i != 0) global += 2.0 / (double)(i * i);
  }
  printf("global val: %f\n", global);
}

int main() {
  atomic();
  reduction();
}
atomic[0]: 0x7fff8a6c9500
atomic[0]: 0x7fff8a6c9500
atomic[1]: 0x7fff8a6c9500
atomic[2]: 0x7fff8a6c9500
atomic[3]: 0x7fff8a6c9500
global val: 2.847222
reduction[0]: 0x7fff8a6c90b8
reduction[0]: 0x7fff8a6c90b8
reduction[3]: 0x7f115bd8e938
reduction[1]: 0x7f115c18f938
reduction[2]: 0x7f1153ffe938
global val: 2.847222

reductionのほうが変数のメモリ領域を必要としますが、途中でスレッドをとめることがないためatomicより高速に思えます。実際に簡単な例で測定してみます。

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

#define LOOP_NUM 1000

void atomic() {
  double global = 0.0;
  #pragma omp parallel for
  for (int i = 0; i < LOOP_NUM; ++i) {
    if (i != 0) {
      #pragma omp atomic
      global += 2.0 / (double)(i * i);
    }
  }
  printf("global val: %f\n", global);
}

void reduction() {
  double global = 0.0;
  #pragma omp parallel for reduction(+:global)
  for (int i = 0; i < LOOP_NUM; ++i) {
    if (i != 0) global += 2.0 / (double)(i * i);
  }
  printf("global val: %f\n", global);
}

void measure_and_print_time(const char* message, void (*func)()) {
  double start_time = omp_get_wtime();
  func();
  double end_time = omp_get_wtime();
  printf("%s: TIME %f(sec)\n", message, end_time - start_time);
}

int main() {
  measure_and_print_time("atomic", atomic);
  measure_and_print_time("reduction", reduction);
}
global val: 3.287867
atomic: TIME 0.010829(sec)
global val: 3.287867
reduction: TIME 0.001302(sec)

このケースではreductionを使用するほうが高速に動作しています。場合によっては差は埋まるかもしれませんが、reductionのほうが高速と思っていて良さそうです。ただしこの例だけでは必ずしもredutionが高速とは保証できません。

変数の取り扱い

競合状態とその回避について説明しましたが、アトミック、クリティカルセクション、リダイレクションのどれを使ってもパフォーマンスは落ちるためほんとうに必要なとき以外は使用を控えたほうが良いです。

for並列化セクション内で使う変数はスレッドごとにメモリを割り当てることができます。

基本的にはfor文内のローカル変数として宣言すると良いのですが、private,fastprivate,lastprivate指示節を使って今まで使っていた変数もスレッド内ローカルで使うこともできます。

ちなみにforで使用するインデックス変数はforの外で宣言する場合もfor内で宣言する場合もどちらもスレッドごとにメモリが割り当てられます。

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

int main() {
  int private_v= 0;
  int global = 0;

  omp_set_num_threads(4);
  #pragma omp parallel for private(private_v)
  for (int i = 0; i < 10; ++i) {
    int local = 0;
    #pragma omp critical
    {
      printf("Thread No: %d | global: %p | private: %p | local: %p\n", omp_get_thread_num(), &global, &private_v, &local);
    }
  }
}
Thread No: 0 | global: 0x7fff5c389600 | private: 0x7fff5c3891bc | local: 0x7fff5c3891b8
Thread No: 2 | global: 0x7fff5c389600 | private: 0x7f651fa6b93c | local: 0x7f651fa6b938
Thread No: 1 | global: 0x7fff5c389600 | private: 0x7f651fe6c93c | local: 0x7f651fe6c938
Thread No: 0 | global: 0x7fff5c389600 | private: 0x7fff5c3891bc | local: 0x7fff5c3891b8
Thread No: 2 | global: 0x7fff5c389600 | private: 0x7f651fa6b93c | local: 0x7f651fa6b938
Thread No: 1 | global: 0x7fff5c389600 | private: 0x7f651fe6c93c | local: 0x7f651fe6c938
Thread No: 0 | global: 0x7fff5c389600 | private: 0x7fff5c3891bc | local: 0x7fff5c3891b8
Thread No: 1 | global: 0x7fff5c389600 | private: 0x7f651fe6c93c | local: 0x7f651fe6c938
Thread No: 3 | global: 0x7fff5c389600 | private: 0x7f651f66a93c | local: 0x7f651f66a938
Thread No: 3 | global: 0x7fff5c389600 | private: 0x7f651f66a93c | local: 0x7f651f66a938

ただし、private,fastprivate,lastprivateの使用にはいくつか注意点があります。

共通の注意点

  1. 指定する変数は参照型であってはならない
  2. インスタンスを指定する場合はコピーコンストラクタの定義が必要
  3. オブジェクトのメンバーを指定することはできない

privateの注意点

privateで指定した変数は初期化されていません。必ずfor文内で初期化して使います。

privateで使用する変数は、for並列化セクションに入る前で使用されていない値であればfor内のローカル変数として宣言するほうが読みやすさの観点から良いと考えます。

fastprivateとlastprivate

fastprivateは並列化処理開始時の値が各スレッドの値にコピーされます。for並列化セクションに入る前の値を使いたいときに有効です。

lastprivateは並列化の最後のスレッドの持つ値が元の変数に代入されます。for並列化ではどのスレッドの値が入ってくるか実行されるまでわからないので値が自明な場合ではない限りあまり使用しないほうが良いでしょう。

紹介していないOpenMPの機能

atomic, critical, reduction, privateを紹介しましたが、OpenMPにはほかにもいろいろな機能があります。

これらはfor文に関するいくつかの機能です、sectionsによる並列化などほかにも機能があるので紹介していない機能を以下に列挙します。

  • sections
  • single
  • master
  • barrier
  • ordered
  • flush
  • threadprivate
  • schedule
  • nowait
  • if

あとAPIについてもあまり触れていません。ロックの使用はOpenMPのAPI経由になります。

OpenMPは使い方に熟知していないとうまく使いこなせないだけでなくバグを生み出しがちでパフォーマンスを引き出すこともできなくなります。

本記事はfor並列化に絞ってあえて少ない機能でまとめてあります、OpenMPは不用意に特定の難しいバグを埋め込んでしまう可能性が高いので気を付けて使うと良いでしょう。

参考

kosyu-openmp_c.pdf

  • 日本語記事の中では一番詳しいと思われる
  • 仕様を網羅しているので読むのは必須

C++ 開発者が陥りやすい OpenMP* の 32 の罠 | iSUS

  • アンチパターンとその解決について丁寧に書かれている
  • OpenMPのAPIについて一通り知っていないと内容を正確には理解できない

OpenMP - Tech Note

  • そこそこまとまった記事

OpenMPの使い方:tech.ckme.co.jp

  • セクションについて
  • スケジューリングについて
  • API(omp_get_max_threadsなど)について

OpenMP - Wikipedia

  • 基本的な内容(紹介に近い)

01_OpenMP_osx.indd - 525J-001.pdf

  • OpenMP 4.5の公式ドキュメント

openmp-examples-4.5.0.pdf

  • OpenMP topic 2: Loop parallelism

OpenMP topic 2: Loop parallelism

Show comments

Adsense

Share

  • このエントリーをはてなブックマークに追加

About

どこにでもいる平凡なプログラムを書く人間のログ。

Tags

-->