OpenMP並列forループの中断処理

OpenMPによる並列forループにおいて、該当ループの処理途中で中断する方法について。

OpenMPでは並列forループ内からの break は禁止されるため、フラグ変数を用いたループ内処理スキップで代用する。並列リージョンでのフラグ変数アクセスは、全てクリティカルセクションで保護する必要がある。下記コードでは critical コンストラクトを利用しているが、omp_lock_tを用いた明示的ロック／アンロック操作でも良い。

int break_loop = 0;  // ループ中断フラグ

#pragma omp parallel for
for (int i = 0; i < N; i++) {
  int local;
  // break_loopフラグ設定値を読み取り
  #pragma omp critical(access_flag)
  local = break_loop;
  if (local) continue;

  // 処理本体
  int stop = process(i);

  if (stop) {
    // break_loopフラグをセット
    #pragma omp critical(access_flag)
    break_loop = 1;
  }
}

OpenMPベース言語のC/C++処理系においてint型のatomic性が保証される場合は、flush コンストラクトを利用した軽量実装も可能ではある。*1（→id:yohhoy:20140214）

// intのatomic性を前提とした非ポータブル実装
int break_loop = 0;

#pragma omp parallel for
for (int i = 0; i < N; i++) {
  #pragma omp flush(break_loop)
  if (break_loop) continue;

  // 処理本体
  int stop = process(i);

  if (stop) {
    break_loop = 1;
    #pragma omp flush(break_loop)
  }
}

OpenMP 3.1以降

OpenMP 3.1から atomic 指示文にオプションが追加され（→id:yohhoy:20140212）、atomic 更新操作ではない通常の atomic 読取／書出操作がサポートされた。前述クリティカルセクションよりも軽量で、処理系に依存しないポータブルな実装が可能となる。

int break_loop = 0;  // ループ中断フラグ

#pragma omp parallel for
for (int i = 0; i < N; i++) {
  int local;
  #pragma omp atomic read
  local = break_loop;
  if (local) continue;

  // 処理本体
  int stop = process(i);

  if (stop) {
    #pragma omp atomic write
    break_loop = 1;
  }
}

OpenMP 4.0以降

OpenMP 4.0から cancel コンストラクトが追加され、最内並列処理へのキャンセル通知がサポートされた。ただし、キャンセルサポートは既定で無効化されているため、環境変数OMP_CANCELLATIONを用いた明示的な有効化が必要となる。プログラム内部から設定有効化する方法は存在しない（設定値取得のみ可能）。

#pragma omp parallel
#pragma omp for
for (int i = 0; i < N; i++) {
  int stop = process(i);
  // stopが真ならば並列forループ中断
  #pragma omp cancel for if (stop)
}

$ gcc source.c -fopenmp
$ OMP_CANCELLATION=true ./a.out

関連URL

• Breaking Out of Loops in OpenMP
• c++ - Why is openMP cancellation construct not cancelling the worksharing region? - Stack Overflow
• volatile変数とOpenMP flush操作の短い関係 - yohhoyの日記

*1:flush 指示文無しでも概ね期待通り動作する可能性はあるが、OpenMPメモリモデル定義上はここに flush 指示文配置が必要とされる。OpenMP 2.5以前の仕様に "厳密" 準拠する処理系なら volatile int 型利用で flush 操作が暗黙に発行される（→id:yohhoy:20140216）が、最新OpenMPでは廃止済みの動作仕様に依存することになる。