mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2020-04-28, 10:52   #34
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×577 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
So if two different machines trial divide with two different sets of trial factors how do you know whether a true factor was actually tested??? You might be missing some.
It's my understanding that the leading gpu TF applications use not too few but too many candidate factors. Incomplete sieving of trial factoring candidates is accepted because it is higher performance, without excluding any candidate prime factors. It's faster in practice to sieve the Mersenne number with an occasional composite factor candidate also included, than to perfectly sieve the factor candidates. All the primes of the proper form in 2b to 2b+1 are in the set of trial factors when doing TF from b to b+1, plus a varied set of composites. Assuming the hardware and software are operating to spec, that is, or sufficiently near it.

That's covered in points 8 and 9 of https://www.mersenneforum.org/showpo...23&postcount=6 (my attempt to document all the concepts of mfaktc trial factoring I could identify, which had been reviewed by the author of mfaktc)

But suppose one in 106 primes were omitted somehow from the TF candidate factors. We would still get nearly all the benefits of a perfect TF process, with all or nearly all the run time of a perfect TF process, over the same bit size interval.
A usable proof of work algorithm needs to be tolerant of both some level of expected software imperfection and speed optimizations.

Last fiddled with by kriesel on 2020-04-28 at 11:01
kriesel is online now   Reply With Quote
Old 2020-04-28, 13:33   #35
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2×43×83 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
So if two different machines trial divide with two different sets of trial factors how
do you know whether a true factor was actually tested??? You might be missing some.
All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.
Prime95 is offline   Reply With Quote
Old 2020-04-28, 13:52   #36
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

100100010001102 Posts
Default

Quote:
Originally Posted by Prime95 View Post
All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.
Please forgive my ignorance, but would it be expensive to somehow sum/hash the vector of dividing candidates, post sieve? Or are they spread over too many vectors?

Edit: Sorry, I just realized this would be useless. Different for every run. Never mind...

Edit2: What about a sum/hash of the vector of candidates /before/ the sieve? Is that deterministic and reproducable? (Sorry... Haven't had my second cup of coffee yet...)

Last fiddled with by chalsall on 2020-04-28 at 13:55
chalsall is offline   Reply With Quote
Old 2020-04-28, 15:55   #37
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×577 Posts
Default

Quote:
Originally Posted by Prime95 View Post
All prime factors will be tested. A small non-deterministic set of composite factors will also be tested.
Hmm.
Is this non-deterministic set of composite factors a problem for Gerbicz' TF proof of work method? https://www.mersenneforum.org/showpo...7&postcount=30 If for the set of q=2kp+1 that are composite but are not sieved out, one or more of (Mp mod q) mod 2t is 1, it would seem so. Testing in that case that a candidate k for the proof list gives a prime q (finishing the sieving of only those that are candidates to go into the verification list) should handle that. Maybe that's best done on the cpu. The value of the list formed, as a proof of work, is that it is hard to produce, and easy to verify, rather like a found factor. Also it is usable in the most common TF case, no factor found. And depends on doing most of the actual TF work. And can be made reliable yet somewhat compact in size. And does not depend on keeping secrets such as encryption codes secret.

One of the reasons I like the Gerbicz double mod method is something analogous might be usable for P-1 verification of work, which is also not currently present. Some fraction of the code could be reused.

Last fiddled with by kriesel on 2020-04-28 at 16:25
kriesel is online now   Reply With Quote
Old 2020-04-28, 18:03   #38
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·4,643 Posts
Default

Quote:
Originally Posted by axn View Post
Because of variable SoE sieve depth (and the inherent nondeterminism in GPU sieve), the exact sequence of candidate factors produced can vary and so the server can't validate the residue.
Please forgive another possibly stupid question (I understand mfaktc largely as a black box)... But if the SieveP is constant during a run, does that make anything more usefully deterministic?

Probably wouldn't help determine sanity during runtime, but it would open the option of random DCs (for kit sanity checks, for example, if the user wanted to check and monitor their own kit).
chalsall is offline   Reply With Quote
Old 2020-04-28, 18:28   #39
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

2·7·13 Posts
Default

Quote:
Originally Posted by axn View Post
You have clearly not done any GPU programming. What sounds like a simple operation in CPU land will have a large impact on GPU performance (not like 2x hit, but easily 20-30%). But for the sake of argument, let's say this is acceptable
Luckily there are some GPU programmers here! I coded up my proposal and see less than a 5% performance impact (I measured 2-3% over 4 hours of work but with some margin of error)


Quote:
Originally Posted by axn View Post
The problem is that all of these have different authors. Any many people have their own scripts. Some people just manually get assignment from server and launch using command line. This isn't just code change -- it is a complex "system" change. The problem is that the whole "GPU TF" thing isn't very streamlined. Anyway, for the sake of argument, let's assume that this can somehow be coordinated.
I asked about distribution somewhere and was told that mfaktc is ~30% of GPU factoring so starting there would be a good idea.
SethTro is offline   Reply With Quote
Old 2020-04-28, 18:52   #40
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×577 Posts
Default

Quote:
Originally Posted by SethTro View Post
I asked about distribution somewhere and was told that mfaktc is ~30% of GPU factoring so starting there would be a good idea.
Wow, I thought mfaktc was more than that, closer to 70%. As far as I know, there's only mfaktc, mfakto, and perhaps TJAOI. Mfakto competes for AMD gpus and their higher DP throughput relative to TF throughput with primality testing and P-1 with gpuowl. What are the other gpu TF apps for GIMPS? (I'm always looking for more for the "available software" list http://www.mersenneforum.org/showpos...91&postcount=2)
kriesel is online now   Reply With Quote
Old 2020-04-28, 23:57   #41
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

2×7×13 Posts
Default

Quote:
Originally Posted by kriesel View Post
Wow, I thought mfaktc was more than that, closer to 70%. As far as I know, there's only mfaktc, mfakto, and perhaps TJAOI. Mfakto competes for AMD gpus and their higher DP throughput relative to TF throughput with primality testing and P-1 with gpuowl. What are the other gpu TF apps for GIMPS? (I'm always looking for more for the "available software" list http://www.mersenneforum.org/showpos...91&postcount=2)
I looked up the post that I had basing that number on and I have incorrectly recalled it as having a percentage which it doesn't.
https://www.mersenneforum.org/showthread.php?t=24994
SethTro is offline   Reply With Quote
Old 2020-04-29, 00:05   #42
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

2·7·13 Posts
Default

Quote:
Originally Posted by axn View Post
Perhaps we should do some threat modeling before evaluating proposed solutions.

What is the current problem? Someone can fake a "no factor" result by manually typing up the result line and submitting to the server.

A simple checksum that can only be generated by the client should prevent that. It should have the property that different exponent/bit level should give unique value. Presumably, the client should have enough safeguards that it can't be tricked into computing the checksum without doing the actual work. This would mean encrypting the checkpoint files written to the disk.

I don't think for the problem as stated, we need proof of work. Provided the server trusts the client, the checksum is basically the client vouching for the work done -- that should be good enough.
I think this is a good line of reasoning.

A suspect some small percent of TF results were never run because manually created NO_FACTOR results including a larger bitrange were submitted (e.g. a NF result for bitrange 1-80). Making that harder (via a checksum for the line even) seems like a good starting place. If you want to do more to verify the calculating (to prevent against overclocking / math errors) we should look at my proof-of-work proposal.
SethTro is offline   Reply With Quote
Old 2020-04-29, 16:39   #43
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·4,643 Posts
Default

Quote:
Originally Posted by retina View Post
Revised "kit": ALL of it. Everything that is required to run a test. Including the power cable, the OS, the drivers, and the ability to keep the kitty off the keyboard.
My problem is keeping the kittens off the bed...
Attached Thumbnails
Click image for larger version

Name:	cats_on_bed_scaled.jpg
Views:	54
Size:	170.0 KB
ID:	22187  
chalsall is offline   Reply With Quote
Old 2020-04-29, 16:42   #44
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23×577 Posts
Default

Quote:
Originally Posted by chalsall View Post
My problem is keeping the kittens off the bed...
I find doors work well. Although if it's the bedroom door, they'll hook it at the bottom with a paw and rattle it in the frame until "he who feeds cats" wakes up, so a more distant door is better.
kriesel is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GPU Trial Factoring FAQ garo GPU Computing 100 2019-04-22 10:58
mfaktc for dummies NBtarheel_33 GPU Computing 10 2011-10-13 00:04
How much Trial Factoring to do? odin Software 4 2010-08-08 20:23
How far to do trial factoring S485122 PrimeNet 1 2007-09-06 00:52
trial factoring and P-1 jocelynl Math 8 2006-02-01 14:12

All times are UTC. The time now is 21:29.

Mon Oct 26 21:29:36 UTC 2020 up 46 days, 18:40, 0 users, load averages: 1.96, 1.98, 1.91

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.