直列加算と並列加算でdoubleの足し算の結果が変わる話

Javaに限った話ではないのだけど、Javaで並列加算が気軽にできるようになったので、気に留めておいたほうがいい話。

まず、次のようなコードを動かしてみます。

public static void main(String[] args){
    double[] data = {
        1.234E80, -1.234E80, 
        2, 3};
    System.out.println(Arrays.stream(data).sum());
    System.out.println(Arrays.stream(data).parallel().sum());
}

1.234×10^80と-1.234×10^80という、桁が大きくて符号の違う数を並べて、そのあとに2と3という1桁の数値を置いています。
これらを加算すると、1.234×10^80と-1.234×10^80は符号が違うだけなので、当然結果は0になります。そして、2と3を足すので、答えは5ですね。

ここでは、配列をDoubleStreamに変換して、.sum()メソッドで加算しています。それから、DoubleStreamを.parallel()で並列ストリームにして.sum()での加算を行っています。
実行すると、両方5.0が表示されます。正しいですね。

5.0
5.0

ここで、データをひとつ追加してみます。

    double[] data = {
        0,
        1.234E80, -1.234E80, 
        2, 3};

先頭に0を追加しただけです。

これで試してみると、次のような結果になります。

5.0
0.0

並列版のほうは、0になってしまってますね。

もちろん、並列版だから正しく計算できないという話ではありません。
次のようなデータでは直列版で0になります。

    double[] data = {
        2, 3,
        1.234E80, -1.234E80};

結果は次のように。

0.0
5.0

直列版と並列版で答えが変わる、というところが問題です。

これは、浮動小数点実数の加算で結合則がなりたたないことによるものです。

1.234×10^80+(-1.234×10^80)+2

という計算があるとき、

(1.234×10^80+(-1.234×10^80))+2

のように計算を行うと、同じ桁で同じ仮数の符号が違う数同士の足し算が行われて０になり、そのあとで2が足されるので、答えは2になります。
一方で、

1.234×10^80+((-1.234×10^80)+2)

のように計算を行うと、(-1.234×10^80)+2という計算で桁が違いすぎるので2のほうが切り捨てられて、答えが-1.234×10^80になります。その後1.234×10^80と足し算を行うので、答えが０になります。

並列加算の場合は、そのときに使えるコアの数によって足し算の順序が変わるので、実行する環境や同時に動いているアプリケーションなどの条件によって答えが変わる可能性があります。
浮動小数点実数の計算では、そもそも正確な答えを期待してはいけないのですが、同じデータでの計算で答えが変わっていいかどうかは、並列加算を行うときに考えておく必要があります。

詳しくはパタヘネで。

コンピュータの構成と設計 第4版 上 (Computer Organization and Design: The Hardware/Software Interface, Fourth Edition)

※今回は、JDK1.8 Early Access b113で動作確認しています。