如何使用可并行化的方法来聚合浮点数组并获得精确的结果？

为了得到浮点数组的精确和，我只需要对它们进行排序并添加每一对，然后再添加对（这些对的和）直到我只有一个元素。（正确吗？）如何使用可并行化的方法来聚合浮点数组并获得精确的结果？

当我想找到多重总和时，我该怎么做。（正确的单词？）

我假设乘以两个浮动点号的作用：（？是不是太）

// sign -> -1 or 1 
// mantissa -> 0.5 ... <1.0 (Never actual 1.0) 

new_sign = x_sign * y_sign 
new_exponent = x_exponent + y_exponent 
new_mantissa = x_mantissa * y_mantissa 

if (new_mantissa < 0.5) { 
    new_mantissa *= 2.0 
    new_exponent-- 
}

有与new_sign也不new_exponent没有精度问题，我不应该给予重视他们。我应该看到与new_mantissa准确输了。那么我应该按浮点数排序浮点数，然后呢？说什么是正确的？

如果我不在正确的方向，那么达到这种效果的正确方向是什么？

来源

2015-05-13 LyingOnTheSky

为了获得尽可能准确的总和，我会使用[Kahan summation]（http://en.wikipedia.org/wiki/Kahan_summation_algorithm）。如果您假设IEEE 754二进制浮点，则乘法码不正确。 –

我也不明白为什么你需要进入乘法的远比你想象的更复杂的细节。重要的是你的处理器将两个数字乘以产生最接近的可表示价值的产品。 –

@PatriciaShanahan它不是可并行的，或者它是？乘以太多的数字（数十亿）将会有很大的错误，并且我有足够的力量对这些数字进行排序，所以为什么不呢？ – LyingOnTheSky

乘以数十亿双倍的主要问题是指数溢出和下溢。假设double为IEEE 754 64位二进制浮点数，那么最大有限双倍的十亿分之一大约为1.0000007097829648。最小正数的十亿分之一大约是0.9999992555602052。将每个大于1.0000007097829648的十亿个数乘以将产生无穷的结果。将每个小于0.9999992555602052的十亿数字乘以下降为零。

最简单的解决方案是添加输入的对数来获得其产品的对数。对数计算非常好并行。

为了准确性，应使用Kahan summation来计算对数的总和以获得O（1）误差增长。为了表现，应该同时进行，建议pairwise summation。

这可能是值得尝试妥协的。让每个处理器做一个输入子集的Kahan求和，然后有一个处理器做这些和的Kahan求和。

或者，让一个线程完成一个完整的Kahan求和，但是会为它提供对数块，因为它们是由所有其他线程生成的。

来源

2015-05-15 11:54:14

我正在使用GPU，在GPU内部运行循环有点困难，我会尝试一些。 – LyingOnTheSky

如何使用可并行化的方法来聚合浮点数组并获得精确的结果？

回答

相关问题