Parallel Kahan summation

[williamshipman]

Hi PF,

I am working on a parallel reduction code to sum up approximately 1 million 32-bit floating point numbers. The serial part running on each processor uses Kahan summation, no problems there. My problem is that this produces several sum/compensation pairs that now need to be added together. How should this be handled, as I am unable to find helpful literature in the databases my library subscribes to? At the moment I am just adding the two compensation values and treating that as the new compensation value for one of the two numbers to be added.

Secondly, what is the correct way to handle a situation where the two sums must be weighted before summing them? At the moment if I have two Kahan summation results (sum1,compensation1) and (sum2,compensation2) I would proceed as follows: (sum,compensation) = kahan((sum1*w1,compensation1*w1), (sum2*w2,compensation2*w2)) where w1 and w2 are the weights and kahan() is the kahan summation from the paragraph above.

Any advice would be greatly appreciated.

 

[AlephZero]

With the notation of http://en.wikipedia.org/wiki/Kahan_summation_algorithm , I guess the best method would be to return both "sum" and "c" from each parallel branch, and then in the final step add all the sum's and c's using Kahan summation.

The second question depends whether you are happy with the floating point approximation $w(a+b) = (wa) + (wb)$. In general that is not true (for example you can easily invent examples where one result gives an overflow or underflow, but the other does not) but whether it matters to you depends on much more information than is in your OP.

 

[williamshipman]

Hi AlephZero,

If I understand you properly, you're suggesting that I do the following for question 1:

1. Kahan summation of sum1, sum2 up to sumN, giving an $s$ and $c$ value.
2. Kahan summation of compensation1 up to compensationN, giving an $s$ and $c$ value.

At the end of this, I would come out with a sum of all the sums and its compensation term, a sum of all the previous compensation values, and its compensation term. Did I follow that correctly?

Regarding question 2, I think you misunderstood me. I am trying to calculate $w_1 a + w_2 b$, i.e. two different weights and $a$ and $b$ are both results from previous Kahan summations.

 

[williamshipman]

To answer my original question, the correct way to handle my problem seems to be to use what is known as double-single precision math. See http://crd-legacy.lbl.gov/~dhbailey/mpdist/ for Fortran code for a double-single and double-double precision libraries. Unfortunately, once one gets to multiplication and division operations, which I need a lot of, the amount of operations becomes quite large, making it pointless for me to pursue double-single precision in place of plain double precision.