GPU TF work and its impact on P-1

[Prime95]

Originally Posted by axn

But, half-sized exponent also takes twice the effort to get to the same sieve depth. So it should be 4 bit levels?

Good point!

[davieddy]

Originally Posted by axn

But, half-sized exponent also takes twice the effort to get to the same sieve depth. So it should be 4 bit levels?

Beat me to it, although I said just that in an earlier post.

But then again "all math discussions are irrelevant..."


Back in 2005 I wrote my own TF and LL programs, and verified
everything up to and including M29 (discovered 1988).
Since I was using "grammar school" squaring, the time for a
LL test went as exponent^3.
With time for TF going as 1/exponent, doubling the exponent
upped the optimum TF level by 4. (I didn't DC, but then again,
I wrote bug-free integer arithmetic code).

To put this one to bed, time for an FFT iteration goes as
exponent*log(exponent) so going from exponent 2^25 to 2^26
also involves a factor of 26/25. This manifests itself in the
time for a 4096K FFT being more than double that of a 2048K one.

David

[davieddy]

Originally Posted by axn

sieve depth

I'm open to correction, but my interpretation of "sieve depth",
at least in the context of TF, refers to "how big a prime do you
want to check doesn't divide your potential TF candidate?".
c.f. Eratosthenes.

I think "TF bit-level" is the appropriate term you wanted.
When I say "appropriate", I mean "as has evolved into common usage
in Mersenneforum.org"

David

Edit: I see that you meant "sieve" in the sense that
TF "sieves" potential Mersenne prime candidates.

[davieddy]

Originally Posted by davieddy

doubling the exponent
upped the optimum TF level by 4

This was slightly messed up because at 32,48,64 bits, the division
involved in TF got harder.

But in our case (how does 70 bits of TF compare with 74 bits?)
this hiccup doesn't really arise.

David

[davieddy]

Originally Posted by davieddy

It ain't Number Theory, but...
<snip>
In post #1 I emphatically agreed with Tom that GPUs = TF and
CPUs = everything but TF. I don't think there are many dissenters
from this view.

Roughly quoting GH Hardy (in "A Mathematician's Apology" or it maybe
CP Snow's preface):

"What made you do mathematics?"

Hardy: There are a few people in this world who can do one thing well.
The number of those who can do two things well is negligible.

David

[davieddy]

TF from 2^(69+x) to 2^(70+x) takes
119.566*2^x/(exponent/10^6) GHz-days.
LL takes ~ .036*(exponent/10^6)^2 Ghz-days.

I'll take the probability of a finding a factor to be 1/100 to take
account of past or future P-1 work.

The "break-even point" for TF on a CPU is given by:

119.566*2^x/(exponent/10^6) = .00072*(exponent/10^6)^2
(assuming finding a factor saves 2 LL tests)

exponent/10^6 = 55 * 1.26^x

So TF (by CPU) to:
68 bits for exponent < 43M
69 bits for exponent < 55M
70 bits for exponent < 69M
71 bits for exponent < 87M

For the DC range,
simply halve the exponent and subtract 4 from the bit level.

David

[davieddy]

I guess that the unchanging hard core of exponents left in the
"available for P-1" column, after the daily assignments have reached 53M,
are exponents which have been LL tested once, but have not been P-1ed.
IMO they should be disceetly moved to the "available for DC" column.

That would make a much more important consideration easier to recognize:
exponents <53M constitute about 80% of daily LL assignments. Yesterday
they didn't even get to 53M.
I have a hunch that George is on the case already, but returned/expired
exponents should be TFed to 72 bits (by GPU of course) before being
deemed "available for LL".

David

[KingKurly]

Originally Posted by davieddy

I guess that the unchanging hard core of exponents left in the
"available for P-1" column, after the daily assignments have reached 53M,
are exponents which have been LL tested once, but have not been P-1ed.
IMO they should be disceetly moved to the "available for DC" column.

I occasionally do P-1 work on exponents that were LL'd once but never P-1'd. (Almost all of them are by curtisc.) You would propose that I cease such activities?

[davieddy]

Originally Posted by KingKurly

I occasionally do P-1 work on exponents that were LL'd once but never P-1'd. (Almost all of them are by curtisc.) You would propose that I cease such activities?

No. But since a factor saves only one LL instead of two, its value
is diminished. We are short on P-1 before 1st time tests.
But if that activity really floats your boat, you can still seek out such
exponents. But they won't get DCed for ages, so there is absolutely
no urgency.

I would guess that there are similar candidates in the 30-40M range which
are in the "available for DC" column, and they will get DCed before
the 40-50M range.

David

[S485122]

Originally Posted by davieddy

We are short on P-1 before 1st tine tests.

I should not say it aloud, but the throughput figures that I posted a few days ago say differently : the PrimeNet P-1 work is, at the moment, a little bit more than enough to keep up with the LL tests. That being said perhaps a lot of P-1 is done on "other" exponents and more important, and in agreement with your post, PrimeNet is lacking a cushion of P-1'ed exponents before the LL wave-front.

Jacob

[davieddy]

Originally Posted by S485122

perhaps a lot of P-1 is done on "other" exponents

Comparing the number of P-1 assignments for exponents < 10M with
the number of others, I think "perhaps" may be understating it

David