如何使用可並行化的方法來聚合浮點數組並獲得精確的結果？

爲了得到浮點數組的精確和，我只需要對它們進行排序並添加每一對，然後再添加對（這些對的和）直到我只有一個元素。（正確嗎？）如何使用可並行化的方法來聚合浮點數組並獲得精確的結果？

當我想找到多重總和時，我該怎麼做。（正確的單詞？）

我假設乘以兩個浮動點號的作用：（？是不是太）

// 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

如何使用可並行化的方法來聚合浮點數組並獲得精確的結果？

回答

相關問題