再現性と決定的並列リダクション

なぜ「同じ計算」の答えがブレるのか

同一のバイナリを同一のノードで動かしても、スレッド数を変えたりGPUで実行したりすると、総和やノルムの最下位ビットが実行ごとに変わることがあります。バグではありません。原因は浮動小数点加算が結合則(associativity)を満たさない、という数学的事実にあります。

実数の加算では (a + b) + c と a + (b + c) は等しいですが、IEEE 754浮動小数点では各加算のたびに結果が最近接の表現可能値へ丸められるため、途中結果の丸め位置が違えば最終値も違い得ます。典型例として、大きな値 A に対して非常に小さな値 e を足すと、A + e が丸めで A に戻ってしまう「吸収(absorption)」が起きます。

結合則が崩れる最小例（10進で仮数3桁の丸めを仮定）

  A = 1.00e+3,  b = 1.00e+0,  c = -1.00e+3

  (A + b) + c = (1001 → 丸め 1.00e+3) + (-1.00e+3) = 0.00
  A + (b + c) = 1.00e+3 + (1.00e+0 - 1.00e+3)      = 1.00e+0

  同じ3つの数でも、足す順序で答えが 0 と 1 に割れる

つまり総和の値は集合 {A,b,c} だけでは決まらず、加算の順序に依存します。逐次実行では順序が一意なので毎回同じ答えになりますが、並列化すると順序が実装・スケジューリング任せになり、ここに非再現性が入り込みます。この丸め自体の性質は「数値安定性と浮動小数点誤差」で扱った蓄積誤差と同根ですが、本稿の主題は誤差の大小ではなく結果が一意に定まるかという別軸です。

並列リダクションで順序が変わる仕組み

n 要素の総和を並列化する典型は、部分和を各スレッドが計算し、それらを木状に集約するツリー型リダクションです。逐次加算が深さ n の直鎖であるのに対し、ツリー型は深さ log2(n) で集約するため、加算のグルーピング(結合の入れ方)が根本的に異なります。

横にスクロール

問題は、そのグルーピングが実行環境で変わる点です。スレッド数を変えれば1スレッドが担当する要素範囲が変わり、部分和の切れ目がずれます。GPUではブロック数・ワープ数・占有率で分割が決まります。さらに、集約の最終段でしばしば使われるアトミック加算(atomicAdd)は、各スレッドの部分和が到着した順にグローバル変数へ足し込むため、到着順そのものがハードウェアのスケジューリングに左右され、実行ごとに変わります。

非決定性が混入する主なポイント

  1. スレッド/ブロック数の変化 → 部分和の区切りが変わる（結合の入れ方が変わる）
  2. atomicAdd による集約     → 部分和の到着順で加算順が変わる（実行ごとに非決定）
  3. 動的スケジューリング       → どのスレッドがどの範囲を取るかが可変
  4. FMA(融合積和)の有無       → a*b+c を1回で丸めるか2回で丸めるかで結果が変わる

このうちアトミック加算は再現性にとって最も厄介です。atomicAdd 自体は競合を排他して値の破壊は防ぎますが、順序は保証しません。同じ数の集合をランダムな順で足すのだから、結果は毎回変わり得ます。この種の集約は分散学習の勾配同期やモンテカルロ積分の集計でも現れ、「モンテカルロ法(HPC・科学計算)」で扱うサンプル総和や、CG法の内積計算(「反復法による連立一次方程式の求解」)でも同じ非決定性が問題になります。

ビット再現性を得るための決定的手法

ビット再現性(bitwise reproducibility)とは、入力が同じなら実行環境(スレッド数・ハードウェア)が変わっても結果がビット単位で一致することを指します。これを満たす基本方針は「加算のグルーピングを実行環境から切り離して固定する」ことです。代表的な手法を整理します。

鍵となる洞察は、整数加算は結合則を満たすという点です。浮動小数点の非再現性は「途中で丸めること」に由来するので、丸めが起きないほど広いビット幅で足し込めば順序に依存しなくなります。長蓄積器(Kulischアキュムレータ)は倍精度の全指数域を丸めなしに収容できる固定小数点レジスタで、どの順で足しても同じビット列になります。再現可能BLASはこの発想を軽量化し、指数の範囲をいくつかのビンに分け、各ビン内では丸めが起きないように部分和を積んでから最後に合算することで、順序非依存かつ現実的なコストを実現します。

Kahan補償加算は「再現性」ではなく「精度」の道具

総和の誤差対策として知られるKahanの補償加算(compensated summation)は、各加算で切り捨てられた下位ビットを補正項 c に退避し次の加算で足し戻すことで、総和の誤差を O(n・ε) から O(ε) 程度へ抑えます。ここで注意すべきは、Kahan補償加算は精度を上げるが順序非依存にはしないという点です。

Kahan補償加算（擬似コード）── 精度は上がるが順序は依然として意味を持つ

  sum = 0.0
  c   = 0.0                 // 切り捨てられた誤差を保持
  for x in 配列:            // ← この for の巡回順が変われば結果も変わり得る
      y = x - c
      t = sum + y
      c = (t - sum) - y     // 今回失われた下位ビットを回収
      sum = t
  戻り値: sum

補償加算はあくまで逐次的な誤差回収の仕組みで、要素を足す順序が変われば補正項 c の履歴も変わり、最終ビットは一致しません。したがって並列環境で各スレッドがKahan補償加算した部分和を、さらにアトミックに集約すれば、部分和の到着順で答えは揺れます。補償加算と再現性を混同すると「精度は上げたのに実行ごとに答えが違う」という状態に陥ります。

実務では両者を組み合わせるのが定石です。すなわち(1)集約の順序を固定して再現性を確保し、その固定順序の各段で(2)Kahan補償加算や長蓄積器を使って精度を確保する、という二段構えです。順序の固定が再現性を、補償・広ビット化が精度を担うと役割を分けて考えると設計が明快になります。

まとめ

• 浮動小数点加算は丸めのため結合則を満たさず、並列リダクションのスレッド数・集約順序が変わると総和の最下位ビットが変化する。
• 非決定性の主因は、部分和の区切りの変化・アトミック加算の到着順依存・動的スケジューリング・FMAの有無であり、なかでも atomicAdd は高速だが再現しない。
• ビット再現性は加算のグルーピングを環境から切り離して固定することで得られ、固定順序リダクション・長蓄積器・再現可能BLAS・整数化が決定的手法となる。
• Kahan補償加算は誤差を O(ε) に抑える精度の道具であって順序非依存ではないため、順序固定(再現性)と補償・広ビット化(精度)は役割を分けて二段構えで設計する。