OpenMPと共有メモリ並列

共有メモリ並列という前提

1ノードの中に数十コアが載るのが当たり前になった今、ノード内の並列化を担うのが共有メモリ並列であり、その事実上の標準がOpenMPです。ノードをまたぐ並列化を担うMPIと集団通信がプロセス間で明示的にメッセージを送り合うのに対し、OpenMPは同一アドレス空間を複数スレッドが共有し、変数を直接読み書きすることで協調します。通信を書かなくてよい代わりに、どの変数が共有され、どのスレッドがどのメモリに触るかを意識しないと、データ競合や帯域律速で性能が出ません。本稿はこの共有構造に起因する原理を扱います。

横にスクロール

OpenMPはコンパイラ指示文（#pragma omp ...）としてコードに注釈を付ける形をとります。逐次コードに指示文を足していく増分的な並列化ができる一方、指示文が指定するのは「並列にしてよい」という許可であって、正しさ（競合の不在）はプログラマが保証する責任を負います。

fork-joinモデルとスレッドプール

OpenMPの実行モデルはfork-joinです。プログラムは1本のマスタースレッドで始まり、parallel構築子に到達するとスレッドのチーム（team）が生成（fork）されて領域内を並行実行し、構築子の終端で全スレッドが合流（join）してマスターだけが残ります。

fork-joinの流れ

  master ──┬─ thread0 ─┐
           ├─ thread1 ─┤ parallel領域（全スレッドが領域を実行）
           ├─ thread2 ─┤
           └─ thread3 ─┘
                       │ ← 暗黙バリア（全員そろうまで待つ）
  master ─────────────  以降は再び逐次

重要なのは、parallelのたびにOSスレッドを生成・破棄しているわけではない点です。多くの実装はスレッドをプールとして保持し、parallelのたびに休眠中のスレッドを起こしてチームに割り当て、領域を抜けたら再び休眠させます。これによりスレッド生成の高コストが繰り返し発生するのを避けています。とはいえ、細粒度のparallelを高頻度で入退出すればプールの起動・同期のオーバーヘッドが無視できなくなるため、並列領域はできるだけ大きく取り、内側で仕事を分ける設計が原則です。

parallel領域の終端には暗黙バリアがあり、全スレッドがそろうまで先へ進みません。バリアはロードバランスの崩れをそのまま待ち時間に変えるため、もっとも遅いスレッドが全体の律速になります。この構造は強スケーリングと弱スケーリングで述べたAmdahlの法則の逐次区間として効き、並列化できない部分やバリア待ちがスレッド数を増やしても消えない上限を作ります。

ワークシェアリングとscheduleによる反復分配

ループ並列の中核がワークシェアリング、すなわちループの反復空間をチームのスレッドへ分配する仕組みです。schedule句は、この「どの反復をどのスレッドに割り当てるか」を制御します。

#pragma omp parallel for schedule(dynamic, 16)
for (int i = 0; i < N; i++) {
    result[i] = heavy_work(i);   // 反復ごとの計算量が違いうる
}

代表的な方針は次の3つで、反復ごとの計算量が均一か偏るかで選びます。

staticは割り当てを実行前に決めてしまうので実行時のオーバーヘッドが最小ですが、反復ごとに計算量が違うと担当の重いスレッドだけが遅れ、バリアで全体を待たせます。dynamicは速く終わったスレッドが次のchunkを取りに行くため負荷の偏りに強い反面、chunkを取得するたびに共有カウンタへの同期が発生し、chunkを小さくしすぎるとその同期コストが支配的になります。適応格子や粒子法のように反復ごとの負荷が動的に偏る問題では、科学シミュレーションの負荷分散と同じ設計判断が、ノード内でもscheduleの選択として現れます。

reductionとデータ競合

複数スレッドが同じ変数を更新する典型が総和などの縮約です。素朴に共有変数sumへ全スレッドがsum += ...すると、読み出し・加算・書き戻しが不可分でないため更新が失われるデータ競合（レースコンディション）になり、結果が実行のたびに変わります。

これを安全かつ高速に行うのがreduction句です。各スレッドに縮約変数のプライベートな部分コピーを持たせて競合なく部分結果を積み上げ、領域の終端でそれらを指定した演算子（+、*、maxなど）で1つに併合します。

double sum = 0.0;
#pragma omp parallel for reduction(+:sum)
for (int i = 0; i < N; i++) {
    sum += a[i] * b[i];   // 各スレッドは自分の部分和に加算
}
// 領域終端で全スレッドの部分和が + で併合され sum に入る

reductionが優れているのは、critical（排他区間）やatomic（不可分更新）でループ内の更新を毎回直列化する方式と違い、併合をループの外に1回だけ押し出す点です。ループ内は各スレッドが独立に部分和を積むため直列化されず、スケールします。なお浮動小数点の加算は結合則が厳密には成り立たないため、部分和の併合順序が実行ごとに変わると最終結果の丸めが微妙に変わりうる点は、reductionを使う上での既知の性質です。

false sharingとNUMA意識の配置

データ競合を消しても、共有メモリ特有の性能問題が2つ残ります。false sharingとNUMA配置です。どちらも「正しさ」ではなく「速度」の問題であり、コードは正しく動くのに帯域やコヒーレンスで律速されます。

false sharingは、異なるスレッドが更新する別々の変数が、たまたま同一キャッシュライン（多くは64バイト）に同居しているときに起きます。ライン内のどこか1バイトでも書き込むと、キャッシュコヒーレンスプロトコルはそのライン全体を他コアのキャッシュから無効化します。各スレッドが自分専用のカウンタを更新しているつもりでも、それらが同じライン上にあると、更新のたびに他コアのラインを無効化し合い、DRAM往復に近いコストが繰り返し発生します。

false sharing（配列を隣接インデックスで書くと起きやすい）

  counter[0] counter[1] counter[2] counter[3]  ← 同一64Bライン
     ↑thread0  ↑thread1  ↑thread2  ↑thread3
  各スレッドは別要素を書いているのにラインを共有 → 相互に無効化

  対策: 各スレッドの書き込み先をラインサイズ以上に離す（パディング）
        あるいは局所変数に集計し、最後に1回だけ共有配列へ書く

もう1つがNUMA（Non-Uniform Memory Access）です。複数ソケット構成では各ソケットに接続されたメモリへのアクセスが速く、他ソケットのメモリは相互接続を経由するため遅くなります。多くのOSはファーストタッチ方針を採り、確保した領域に最初に書き込んだスレッドのソケットにその物理ページを配置します。したがって配列を1スレッドでまとめて初期化してから並列計算に入ると、全ページが1ソケットに寄り、他ソケットのスレッドは常に遠いメモリを叩いて帯域が律速されます。

// 初期化を計算と同じ並列パターンで行い、ページを各ソケットに分散させる
#pragma omp parallel for schedule(static)
for (int i = 0; i < N; i++) a[i] = 0.0;   // ファーストタッチで配置が決まる

#pragma omp parallel for schedule(static)
for (int i = 0; i < N; i++) a[i] = f(i);  // 各スレッドは自ソケットのページに触る

対策の要点は、初期化のスレッド配置を計算のスレッド配置と一致させることと、スレッドをコアに固定して移動を防ぐこと（アフィニティ設定）です。メモリバウンドなカーネルではこの配置の良し悪しが実効帯域を直接決めるため、Roofline性能モデルで言う斜めの屋根（メモリ帯域の天井）そのものが、NUMA配置の失敗によって下方向にずれてしまいます。

まとめ

• OpenMPはfork-joinモデルの共有メモリ並列で、parallel構築子でスレッドチームを起こし終端の暗黙バリアで合流する。スレッドはプール再利用で生成コストを隠すが、細粒度な並列領域の高頻度な入退出やバリア待ちは逐次区間として上限を作る。
• ワークシェアリングのscheduleは反復のスレッドへの割り当て方の選択で、計算量が均一ならstatic、偏るならdynamic/guidedを選び、chunkサイズで同期コストと負荷分散の粒度を調整する。
• reductionは各スレッドのプライベート部分結果を終端で1回だけ併合する機構で、共有変数への直接更新（データ競合）やcritical/atomicによる毎回の直列化を避けてスケールさせる。
• false sharing（同一キャッシュラインの相互無効化）とNUMA配置（ファーストタッチによるページの偏り）は、正しさではなく性能の問題であり、パディングやスレッド局所化、初期化と計算のスレッド配置の一致・アフィニティ固定で実効帯域を確保するのがノード内性能の要点となる。