mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > PrimeNet

Reply
 
Thread Tools
Old 2011-04-03, 17:06   #1
aketilander
 
aketilander's Avatar
 
"Åke Tilander"
Apr 2011
Sandviken, Sweden

2·283 Posts
Smile Trial Factoring vs. LL-testing

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?
aketilander is offline   Reply With Quote
Old 2011-04-03, 18:15   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

427810 Posts
Default

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)

Last fiddled with by Mini-Geek on 2011-04-03 at 18:25
Mini-Geek is offline   Reply With Quote
Old 2011-04-04, 01:47   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

5×37×43 Posts
Default

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.
Prime95 is offline   Reply With Quote
Old 2011-04-04, 03:04   #4
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

34038 Posts
Default

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!
Christenson is offline   Reply With Quote
Old 2011-04-04, 03:18   #5
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

174238 Posts
Default

Quote:
Originally Posted by aketilander View Post
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 is offline   Reply With Quote
Old 2011-04-04, 03:33   #6
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

5·37·43 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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.
Prime95 is offline   Reply With Quote
Old 2011-04-04, 04:44   #7
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

3·37·47 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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.
petrw1 is offline   Reply With Quote
Old 2011-04-04, 07:00   #8
ckdo
 
ckdo's Avatar
 
Dec 2007
Cleves, Germany

53010 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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.
ckdo is offline   Reply With Quote
Old 2011-04-05, 01:39   #9
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Default

Quote:
Originally Posted by Prime95 View Post
<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.
******
Christenson is offline   Reply With Quote
Old 2011-04-05, 23:05   #10
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

521710 Posts
Default

Quote:
Originally Posted by Prime95 View Post
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.
petrw1 is offline   Reply With Quote
Old 2011-04-06, 02:14   #11
Christenson
 
Christenson's Avatar
 
Dec 2010
Monticello

5·359 Posts
Default

Quote:
Originally Posted by petrw1 View Post
<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!
Christenson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
What is Trial Factoring? Unregistered Information & Answers 5 2012-08-02 03:47
How far to do trial factoring S485122 PrimeNet 1 2007-09-06 00:52
Speed of P-1 testing vs. Trial Factoring testing eepiccolo Math 6 2006-03-28 20:53
How to only do Trial Factoring? michael Software 23 2004-01-06 08:54
About trial factoring gbvalor Math 4 2003-05-22 02:04

All times are UTC. The time now is 22:28.


Sun Aug 14 22:28:40 UTC 2022 up 38 days, 17:15, 2 users, load averages: 2.10, 1.62, 1.28

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔