Seti@Home optimized science apps and information

Optimized Seti@Home apps => Discussion Forum => Topic started by: sunu on 09 Jun 2011, 04:21:45 pm

Title: Difference?
Post by: sunu on 09 Jun 2011, 04:21:45 pm
Lets say we have some Credit and Runtime data from a few tasks and want to calculate Credit/sec. I see three possibilities:

1) sum(Credit) / sum(Runtime)
2) avg(Credit) / avg(Runtime)
3) avg(Credit / Runtime)

In the 3rd we calculate Credit/sec for each task and then we take the average of those.

1 and 2 give me the same result but not 3. What is the difference?
Title: Re: Difference?
Post by: Miep on 09 Jun 2011, 04:34:39 pm
You mean, apart from the random number generator called 'Credit new'?

I'll look inti the maths tomorrow.

[edit]1 and 2 are identical because avarage is sum divided  by number of elements. as number of elements is identical they cancel each other out.

I need pen and paper for 3.
Title: Re: Difference?
Post by: sunu on 09 Jun 2011, 04:45:32 pm
Yes, don't think about that stuff. Let's say we have x and y. Why sum(x) / sum(y) or avg(x) / avg(y) is different from avg(x / y)?
Title: Re: Difference?
Post by: Miep on 09 Jun 2011, 04:54:06 pm
yes, sorry I did understand it as a purely mathematical question of formulas and why they produce different results.
probably to do with the way the sums are done and in what order the errr. operations are performed. but I'll have to write it out on paper and have a close look.
Title: Re: Difference?
Post by: Jason G on 09 Jun 2011, 04:55:54 pm
Yes, don't think about that stuff. Let's say we have x and y. Why sum(x) / sum(y) or avg(x) / avg(y) is different from avg(x / y)?

How much different ? with just a few numbers is it closer than if there are a lot ?  If it's a fractional difference there are several opportunities for accumulated sum and rounding errors, which can look like random results, and changing the order of computation like that can make a big difference. 

Keeping the division to a single operation at the last step will be far more accurate if you have many results, and there are ways to further improve the result accuracy by not summing long strings of numbers in a line too.  summing in blocks of SQRT(N), then summing those block results, minimises accumulated roundoff error in the sums (one way).

[Edit:] Looking at the third equation with that in mind, it would basically maximise the accumulated summing error by adding smaller values, so the error has more effect on the average, Also having  applied truncation to every element during the divisions ... So yeah, yuck

If you have trouble sleeping sometime you can read this:

What Every Computer Scientist Should Know about Floating Point Arithmetic, by David Goldberg  (http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=86013D0FEFFA6CD1A626176C5D4EF9E2?doi=10.1.1.102.244&rep=rep1&type=pdf)
Title: Re: Difference?
Post by: sunu on 09 Jun 2011, 05:23:03 pm
I first found out about it looking at thousands of results and thought about rounding errors. But then I took data from ten tasks to look closely.

With 10 decimal points accuracy for the separate credit / runtime operations the difference is already 0.0014 between the two methods for only 10 tasks. I don't think it could be a rounding error.

Edit: Thanks for the link!
Title: Re: Difference?
Post by: Jason G on 09 Jun 2011, 05:38:09 pm
Have a look at the section on summing error & see which answer you get if you use your first equation using Kahan Summation or similar, minimising the division to the one final one.  That would be the 'most right' answer, though there isn't any 'right' answer in floating point... They're all wrong!  :o  :D
Title: Re: Difference?
Post by: sunu on 09 Jun 2011, 05:49:35 pm
Ok, I took 3400 tasks. Difference is 0.0017 almost equal with the 0.0014 from 10 tasks. This can't be a rounding error.

I'll look at Kahan Summation.
Title: Re: Difference?
Post by: sunu on 09 Jun 2011, 07:17:27 pm
I think an equivalent everyday example would be:

You drive from A to B and you want to know  your average km/h. This is elementary school stuff:  distance / time

The next time you drive from A to B you make 4-5 stops in between for coffee. How do you calculate your average speed now? Do you add the distance and the time and divide them ( sumx / sumy ) or do you calculate your average speed from each segment and then calculate the average as a whole ( avg (x / y))?

The last method now seems goofy but why is it right or wrong? And is the difference just a rounding error or avg (x / y) calculates something different?
Title: Re: Difference?
Post by: perryjay on 09 Jun 2011, 07:59:37 pm
On that second drive do you also have to figure in the restroom stops?   ::)
Title: Re: Difference?
Post by: Josef W. Segur on 09 Jun 2011, 09:04:51 pm
Yes, don't think about that stuff. Let's say we have x and y. Why sum(x) / sum(y) or avg(x) / avg(y) is different from avg(x / y)?

Methods 1 and 2 give more weight to long-running tasks. Take two tasks, one which runs in 6 hours and gives 100 credits, another which runs in 2 hours and gives 40 credits. The six hours of the first task makes the 2 hours of the second task only 1/4 of the total time. So you get 17.5 credits/hour which is closer to the 16.7 c/h of the first task than the 20 c/h of the second.

But method 3 gives equal weight to the tasks no matter how quickly or slowly they run. So you get 18.333 c/h.

BOINC uses method 3 for its server-side averages, a 100 hour task is weighted the same as a 1 minute task...
                                                                       Joe
Title: Re: Difference?
Post by: Jason G on 10 Jun 2011, 01:54:25 am
The last method now seems goofy but why is it right or wrong? And is the difference just a rounding error or avg (x / y) calculates something different?
Yes, don't think about that stuff. Let's say we have x and y. Why sum(x) / sum(y) or avg(x) / avg(y) is different from avg(x / y)?
But method 3 gives equal weight to the tasks no matter how quickly or slowly they run. So you get 18.333 c/h.

That's right they are different, nothing is goofy (except maybe me), because the order is important.   so it's a different calculation with or without precision issues.

#1:  sum(x) / sum(y) simplifies to the same as #2 by n/n,
#2: avg(x) / avg(y) is the ratio of two averages, which will weight by large x,
#3: avg(x / y), is the arithmetic mean of x/y , so likely the one you want,

but depending on what you want to achieve, if you want a more robust statistic you could possibly use the medians instead, or even truncated means to chuck out outliers.

Title: Re: Difference?
Post by: sunu on 10 Jun 2011, 06:50:30 am
Yes, "weight" seems the magic word here. After Josef's post I looked at various weighted means but still avg(x / y) doesn't look anything like them.

but depending on what you want to achieve, if you want a more robust statistic you could possibly use the medians instead, or even truncated means to chuck out outliers.

I just wanted to calculate the credit / sec output of my machine broken down to CPU, GPU, AP, MB etc. :)

As for the problem with the car above, the answer isn't as simple as I thought http://en.wikipedia.org/wiki/Harmonic_mean#In_physics

Well, I guess we need a professional statistician  :D
Title: Re: Difference?
Post by: Jason G on 10 Jun 2011, 06:57:01 am
As for the problem with the car above, the answer isn't as simple as I thought http://en.wikipedia.org/wiki/Harmonic_mean#In_physics

Well, I guess we need a professional statistician  :D

Hahaha, Yep, Don't know about Joe but my statistics is certainly rusty.  If you intend to process a lot of results, do work with a general idea of the golden rules in mind with floating point as well, since anything that could compound tiny error in unexpected ways will change the result as well.

Jason
Title: Re: Difference?
Post by: Miep on 10 Jun 2011, 09:54:01 am
I do plain linear regression. mainly to prove that credit new is not linear ;D
0.188 credit/second on beta with some flavour of x37.

Title: Re: Difference?
Post by: sunu on 10 Jun 2011, 10:23:33 am
I do plain linear regression. mainly to prove that credit new is not linear ;D
0.188 credit/second on beta with some flavour of x37.

I have thousands of data if you want help.

What method do you use for credit/sec?
Title: Re: Difference?
Post by: Miep on 10 Jun 2011, 10:41:16 am
I do plain linear regression. mainly to prove that credit new is not linear ;D
0.188 credit/second on beta with some flavour of x37.

I have thousands of data if you want help.

What method do you use for credit/sec?

not something that's suitable for large amount of data - unless it is in some form that can be read by excel.

As I said - linear regression. Stuff the data into Excel, make a scatter graph and tell excel to 'add trendline, linear, with equation and r value showing'

Should be fairly simple to code, but my Fortran is rusty and I don't have access to a compiler or NAG libraries anyway. Not to mention my 15 year old scripts on how to manually calculate the smallest sum of squared errors and the precise formula for linear regression...
Title: Re: Difference?
Post by: sunu on 10 Jun 2011, 12:07:54 pm
Computer is http://setiathome.berkeley.edu/show_host_detail.php?hostid=3281360

If a task is made from more than 1 GPUs (boinc restart, preemption) it goes to the GPU that finishes it.

                              Sample
Device0 = GTX295 Core1         1254
Device1 = GTX295 Core2         1242
Device2 = GTX285               1490

Title: Re: Difference?
Post by: Miep on 10 Jun 2011, 12:18:46 pm
hmm. Runtime to AR may be scattering too much and credit to runtime scatters, so I wouldn't expect credit/sec to AR to follow a linear dependency.

Anyway we know that runtime to AR is not linear over the whole AR range, but only over shorter AR stretches. There is a very old plot of runtime/AR with lines across somewhere in NC.

Try plotting credit to runtime and linear regression on that.
Title: Re: Difference?
Post by: sunu on 10 Jun 2011, 12:48:21 pm
Data same as above

Title: Re: Difference?
Post by: Claggy on 10 Jun 2011, 12:51:21 pm
Remember the runtime and credit awarded might be from your wingman's result, and not yours

Claggy
Title: Re: Difference?
Post by: sunu on 10 Jun 2011, 12:53:11 pm
Remember the runtime and credit awarded might be from your wingman's result, and not your's,
Claggy

? ? ? ? ? ? ? ? ? ?
Title: Re: Difference?
Post by: Claggy on 10 Jun 2011, 12:56:08 pm
Remember the runtime and credit awarded might be from your wingman's result, and not your's,
Claggy

? ? ? ? ? ? ? ? ? ?
Aspecially if you're running anonymous platform,

Claggy
Title: Re: Difference?
Post by: sunu on 10 Jun 2011, 01:01:49 pm
What do you mean? That credit is decided with accordance to your wingman? Everyone knows and accepts that.
Title: Re: Difference?
Post by: Claggy on 10 Jun 2011, 01:19:14 pm
What do you mean? That credit is decided with accordance to your wingman? Everyone knows and accepts that.
You'll have to have a read of NewCredit (http://boinc.berkeley.edu/trac/wiki/CreditNew) and try and understand it, i don't fully understand it myself, let alone anyone else,
but from watching the amount of Credit awarded on Astropulse tasks, we used to get 700 to 800 credits with the old credit way,
with new credit my anonymous platform hosts get 700 to 800 Credit when matched to hosts app_versions that have more than 10 validations using the Stock app,
and 500 to 600 Credits when matched to hosts that haven't done 10 validations on that app_version using the Stock app,
and 500 to 600 Credits when matched to other hosts that are running anonymous platform,

Claggy
Title: Re: Difference?
Post by: Miep on 10 Jun 2011, 04:27:45 pm
I haven't been bored enough to try and go through the finer maths of it and then go through the code...

anyway, his runtime should be his ;)

dependency on wingmate is deliberate, I just don't believe the statistics used are sound - or the code. Rs of .85  and lower are linear only to a biologist...