Trial Factoring vs. LL-testing

[aketilander]

Here follows some statistics from my last days work.

I have been doing trial factoring ^68 --> ^69 for 906 exponents in the range 53 400 000 to 55 200 000. The total factoring costs have been 979.86 GHz-Days and among the 906 exponents have 12 factors been found.

Doing first trial LL-test would have costed 12 * 110 Ghz-Days = 1320 GHz-Days. And the doublecheck as much. That is a total of 2640 GHz-Days.

Roughly speaking, trial factoring the same number of 906 exponets ^69 --> ^70 would cost more or less twice as much = 1960 GHz-Days. But most probably we would find another 12 factors of these exponents, but the saving would be as large. Roughly 2650 GHz-Days.

So, the question is: Why don't we do it?

I gather there is something I don't understand here?

[TimSorbet]

FYI for everyone: Prime95 will TF to 2^69 for exponents this size.
It's possible that the TF limits need to be adjusted, but here's something to consider: P-1 is usually run before the last bit of TF. P-1 can find some factors that might have otherwise been discovered via TF, so the probability of TF finding a factor after P-1 has been run is lower.

Let's say you're looking at a group of 1000 exponents, average p=54,300,000 that have been TF'd to 2^69 and have P-1 searches whose probabilities of finding factors averaged 0.07 (7%), and you want to know if TFing to 2^70 should save time.
For each TF, you can expect to find 0.0145988 factors, so for 1000 TFs, you can expect to find 14.5988. But about 7% (I doubt this is precisely accurate, probably a bit more, but it should be close enough for this estimation) of those were already found by P-1, so you can expect to find 13.5767 new factors. This will take about 2.2019 GHz-days for each one, or 2201.91 GHz-days total.
One LL test takes 115.09 Ghz-days, and you can expect to run a little over 2 LLs per exponent due to DCing and non-matching residues, say 2.1. That's 241.68 GHz-days saved if you can find a factor. With the factors we expect, that's 3281.26 GHz-days.
This means you can expect to save 1079.35 GHz-days by TFing.

So my calculations agree with yours, assuming GHz-days are accurate whether TFing or LLing: exponents that size should be tested to 2^70. (take my calculations with a large grain of salt - assumptions, too many significant digits shown, possible mistakes, etc. mean it's anything but precise - but I think the conclusion is quite possibly valid)
Keep in mind that's only 1.079 GHz-days saved per exponent. That's on the order of half a percent more efficient. A little LL efficiency improvement ups the speed of the project way more than this. Still, on the scale of GIMPS, no point having any waste.
(p.s. for reference, many of the figures came from the very handy tools at http://mersenne-aries.sili.net/credit.php)

[Prime95]

The trial factoring vs. LL testing breakeven points were last calculated for a 2.0 GHz Pentium 4.

I'll play around using a Core 2 machine to see if the breakeven points need to change much.

[Christenson]

The problem I see with this is that we now have a sufficiently heterogeneous population (GPUs versus CPUs), and GPUs are sufficently more efficient than CPUs at TF that the *cost* of a GHz-day of TF on a GPU is significantly less than on a CPU. I don't see my single CPU core catching up with a reasonable GPU, designed for parallelism, any time soon.

I even have a (cheap) GPU that doesn't have the ability to do LL!

[Prime95]

Originally Posted by aketilander

Doing first trial LL-test would have costed 12 * 110 Ghz-Days = 1320 GHz-Days. And the doublecheck as much. That is a total of 2640 GHz-Days.

Roughly speaking, trial factoring the same number of 906 exponets ^69 --> ^70 would cost more or less twice as much = 1960 GHz-Days. But most probably we would find another 12 factors of these exponents, but the saving would be as large. Roughly 2650 GHz-Days.

I gather there is something I don't understand here?

The key concept you are missing is that of the 12 new factors you expect to find doing the next TF level, P-1 factoring would likely have found 4 of those. Thus your actual savings is 4 P-1 tests (about 24 GHz-days) plus 8 LL tests and double checks (8 * 110 * 2 = 1760 GHz-days).

[Prime95]

Originally Posted by Prime95

I'll play around using a Core 2 machine to see if the breakeven points need to change much.

The new breakeven points for version 26 need to be a little higher (i.e. do less TF)!! The table below shows that in v25 exponents above 58.52M are factored to 2^70. In v26, exponents above 60.94M are factored to 2^70. We no longer need to TF exponents between 58.52M to 60.94M from 2^69 to 2^70. The big reason for this is LL tests are now faster than the last time breakeven points were calculated.

New breakevens:

#define FAC79 516800000L
#define FAC78 408400000L
#define FAC77 322100000L
#define FAC76 253500000L
#define FAC75 199500000L
#define FAC74 153400000L
#define FAC73 120000000L
#define FAC72 96830000L
#define FAC71 77910000L
#define FAC70 60940000L
#define FAC69 48800000L
#define FAC68 38300000L
#define FAC67 29690000L

Old breakevens:

//#define FAC80 516000000L
//#define FAC79 420400000L
//#define FAC78 337400000L
//#define FAC77 264600000L
//#define FAC76 227300000L
//#define FAC75 186400000L
//#define FAC74 147500000L
//#define FAC73 115300000L
//#define FAC72 96830000L
//#define FAC71 75670000L
//#define FAC70 58520000L
//#define FAC69 47450000L
//#define FAC68 37800000L
//#define FAC67 29690000L

I'll modify version 26.6 to reflect the new Core 2 breakeven points (which will have virtually no effect as most LL assignments have already had all necessary TF completed). For now, I'll not change the server. In fact, we have so much excess TF capacity, there has been serious thought given to having the server assign an extra bit of TF.

[petrw1]

Originally Posted by Prime95

Core 2 breakeven points (which will have virtually no effect as most LL assignments have already had all necessary TF completed). For now, I'll not change the server. In fact, we have so much excess TF capacity, there has been serious thought given to having the server assign an extra bit of TF.

To echo a few others...does the Server know if a TF assignment is being requested for a GPU? If so it seems to make sense to let them have another bit or even two.

If you can't tell could it be an option to have another work type of TF-GPU? Mind you, it would have to be on the honor system. i.e. If I ask for TF-GPU and don't have a GPU or don't run it ona GPU that would be MY problem.

[ckdo]

Originally Posted by Prime95

The new breakeven points for version 26 need to be a little higher (i.e. do less TF)!! The table below shows that in v25 exponents above 58.52M are factored to 2^70. In v26, exponents above 60.94M are factored to 2^70. We no longer need to TF exponents between 58.52M to 60.94M from 2^69 to 2^70. The big reason for this is LL tests are now faster than the last time breakeven points were calculated.

FAC72 did not change, contrary to the others? Seems unlikely.

[Christenson]

Originally Posted by Prime95

<snip>
In fact, we have so much excess TF capacity, there has been serious thought given to having the server assign an extra bit of TF.

If the objective to be minimized is GHz days per Mersenne number checked, then this makes sense. However, if there are so many extra GHz days of TF available through the GPUs that they overwhelm the CPUs, then the TF GHz-day needs to be devalued. At the very least, CPUs shouldn't be doing TF right now.

That is, minimizing GHz days is a stand-in for the real objective (roughly, finding the most Mersenne Primes at the least cost in time and other factors, such as electrical energy) works until we have machines like the GPUs that run circles around our original CPU machines, but only for some kinds of work.

I suggest that we make it easier in lots of ways to put GPUs to other kinds of useful work. This includes NFS@home, making sure normal folks can find the latest LL for CUDA, and thinking seriously (RDS: Flame off please, I am ignorant here and we might already know these aren't good ideas) about P-1 and ECM on CUDA.

****
If this is a bit hard to visualize, re-calculate the balance of TF and LL to get the optimum cost in calendar time if your favorite high-end CUDA-enabled GPU is assigned both the TF and the first-time and double-check LL for your favorite candidate for mersenne prime #48.
******

[petrw1]

Originally Posted by Prime95

In fact, we have so much excess TF capacity, there has been serious thought given to having the server assign an extra bit of TF.

Makes sense...IMHO better to do an extra bit of TF at the LL wavefront to save some LL/DC work than to do TF work at what is now probably dozens of years ahead of LL; even if this extra bit is above the work breakeven point. GPUs being much faster at TF makes it even a better idea.

That is until GPU-LL and/or Quantum computing turbo-charges LL testing.

[Christenson]

Originally Posted by petrw1

<snip>
That is until GPU-LL and/or Quantum computing turbo-charges LL testing.

That is, until that "Dozens of Years into the Future" is blown completely out of the water!