情報科学 › 研究のための計算の実務 › 並列化と GPU

部分和に分けた和の差の上界と、分割の固定による再現

定理 6.1(「並列化と GPU」§6) ・ ✓公理まで証明済み

x1,…,xnx_1, \ldots, x_n(n≥2n \ge 2)を浮動小数点数、uu を単位丸めとし、(n−1)u<1(n-1)u \lt 1、γn−1=(n−1)u/(1−(n−1)u)\gamma_{n-1} = (n-1)u/(1 - (n-1)u) とする。添字の集合 {1,…,n}\{1, \ldots, n\} を空でない pp 個の組に分け、各組の和を浮動小数の加算で(任意の順序・任意の括弧づけで)計算し、得られた pp 個の部分和を浮動小数の加算で(任意の順序・任意の括弧づけで)足した結果を s^par\hat s_{\mathrm{par}} とする。逐次和の結果を s^seq\hat s_{\mathrm{seq}} とする。どの計算でもオーバーフローとアンダーフローが起きないならば、次が成り立つ。

  1. ∣s^par−s^seq∣≤2γn−1∑i=1n∣xi∣|\hat s_{\mathrm{par}} - \hat s_{\mathrm{seq}}| \le 2\gamma_{n-1}\displaystyle\sum_{i=1}^n|x_i|。
  2. 組への分け方、各組の中の加算の順序と括弧づけ、部分和を足す順序と括弧づけがすべて同じ 2 回の実行は、加算が同じ丸めの方向で正しく丸められる限り、どの加算をどのスレッドがいつ実行したかによらず、同じ浮動小数点数を返す。

本文で読む(証明と前後の説明)→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を 前提 としてたどると、Rikai の中の証明だけで定義・公理(物理では基本仮定)までつながっています(前提の定理類 7 件、定義なども含めて 9 件)。

印の意味: ✓公理まで証明済み ・ △証明あり(閉包未完)・ ※主張のみ。テーマごとの集計は 閉包の状況。

前提をたどる 証明が使う定理・定義(直接 3 件)

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

これを使っている定理

証明で明示的に参照している定理は、まだありません。