並列計算時の数値演算の再現性問題 計算機で浮動小数点演算を行う場合，一般にその結果は数学的な演算とは一致しない。たとえば，一般に計算機の加算のような浮動小数演算では次式のように結合法則が成立しない。 \[ (x + y) + z \stackrel{?}{=} x + (y + z)\] 10 進数で有限桁数な数でも 2 進数表記では有限桁数で正確に表現できない場合などもある。数学的に正確ではない例として，以下のように $0.1 + 0.01 - 0.1 - 0.01$ を計算すると $0$ にならない。(Python 3.8.5) >>> 0.1 + 0.01 - 0.1 - 0.01 -5.204170427930421e-18 しかし，$0.1 - 0.1 + 0.01 - 0.01$ の結果は $0$ である。 >>> 0.1 - 0.1 + 0.01 - 0.01 0.0 また，絶対値の極端に違う数値の加減算で絶対値の小さな値が値に反映されないアンダーフロー問題などもある。これは丸めの演算が演算順序に依存する(Order dependent rounding) 問題である。大きな数に極端な小さな数を複数たす場合，丸めによって小さな数が皆無視される場合でも，小さな数を先にたすことで，無視されなくなる場合がある。 しかし，アルゴリズムの多くはある演算結果の等値性に依存する。そのためにこの数値演算の再現性は重要な問題となる。演算結果が等しくないという場合でもその差は最初の数値演算の例のようにかなり小さいことが普通なので，これをある範囲の上限と下限を記録する interval algorithm を使うことができる場合がある。ただし interval algorithm は今回の Tips では用いない。 今回の Tips では演算順序の違いによる問題を避けるために並列演算の各スレッドやプロセスで演算が同じ順序になるようにする方法例を述べる。 具体的問題例 具体例として以下の 2 つの幾何学問題を用いる。 空間分割型の ray-object intersection 3 角形メッシュにおける plane-triangle intersection 空間分割型の Ray-object