浮動小数点の宿命
浮動小数点数は、有限のビットで実数を表すために丸め誤差(rounding error)が発生する。
このため、足し算の順番が変わるだけで結果が変わる:
この非結合性は、非決定性(nondeterminismの根源でもある。
GPU上で並列計算を行うと、スレッドの実行順序が変わるたびに加算結果が微妙に変化する。
カハンの加算アルゴリズムとは
カハンの加算アルゴリズム は、 この丸め誤差を補正するための古典的手法である。
アルゴリズム
補正項 ( c ) に失われた桁を記録し、次回の計算で取り戻す。
ただし演算回数が増えるため、速度は遅く、GPUの並列演算には向かない。