mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-05-02, 21:49   #56
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

18110 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
My 2 centavos is that any overhead that is not error checking related, should not be more than 0.5%. The loss vs. gain doesn't make sense.
I'm the only person working on this and I haven't focused on optimizing code, that can happen after people have been convinced this is worth doing, which has proved to be an uphill struggle.

Quote:
Originally Posted by Uncwilly View Post
What is the potential gain (speed-wise) to the project? Based upon the examination of "expected number of factors", we don't have systematic cheating. We have had a few idiots. Total loss due to them nearly nil.
Loss comes in many forms, it can be ghz-days, it can be human hours, it can be trust in the project.
You are correct that this won't change the overall speed in any significant way today.
It is my belief that this would increase the reproducibility and overall trust in the project.
My goal would be that TJAOI stops finding bad results, and that no one reruns TF results because the don't trust old results.

Quote:
Originally Posted by Uncwilly View Post
Is this an actual residual of the calculation, or is it just a manufactured calculation? It is not a natural byproduct of the calculation like the LL residual.
It is a natural byproduct of the calculation.
It feels strange for you to not understand this, so maybe your claim is that keeping track of the smallest residual is not a natural byproduct?

Quote:
Originally Posted by Uncwilly View Post
This is my very naive concept.
It doesn't feel good to spend time and effort working on something then have someone call it bad. The use of very feels unrestrained.

Quote:
Originally Posted by Uncwilly View Post
Why can't the program take the result to the mod operation at certain select k values and do a rolling operation on them like a CRC? Or certain classes. The k values to be selected could be calculated based upon the exponent. Doing the operation every 10000 k's tested should not put an undue burden on operation and would prove that the at least those items were done in sequence.
I think this comes back to what we are worried about.

I'm worried about them in this order

1. Having any verifiable result associated with each TF submission.
1a. Result(s) should be quickly verifiable by the server (e.g. not requiring a 2nd DC)
1b. Result(s) should cover a large percent of work done.
2. Detect when the GPU/Program is not working quickly (e.g. after 10 submissions not 200)
3. Prevent Malicious/Prank submissions (I'd wager I can easily submit 10000 results at the cost of zero compute and have none of the be detected as fake)

Your method provides 1, 1a, and helps with 2, 3
My method provides stronger guarantees on 1b, 2 and 3.
SethTro is offline   Reply With Quote
Old 2020-05-03, 07:48   #57
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

181 Posts
Default

I cleaned up some debug code and measured impact over the last 24 hours (13 DC TF)

Impact is ~0.4% for adding my new code on DC exponents evaluated with kernel barrett76_mul32_gs

https://colab.research.google.com/dr...o=HMlzwXBlejHb

Last fiddled with by SethTro on 2020-05-03 at 07:52
SethTro is offline   Reply With Quote
Old 2020-05-03, 08:17   #58
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

132338 Posts
Default Finding the needles in the haystack

The server creates a set of secret random prime-k values and computes the remainders.
Send the remainders to the client.
The clients task is to find the k values that generate the remainders.
Client sends the found k values to the server for verification.

How would that affect the client code if it needs to find some specific remainder values instead of just a remainder of zero, or the smallest remainder?

If you had one remainder then on average the client needs to run 50% of the work before finding the k value.
If you had two remainders then on average the client needs to run 75% of the work before finding both k values.
etc.

Considerations: The set of k values might not exactly match each other when two k values generate the same remainder, so just send one of them and the server can still verify the remainder is correct. The server doesn't need to remember the k values it chooses, just the remainders it sends.

Last fiddled with by retina on 2020-05-03 at 08:17
retina is online now   Reply With Quote
Old 2020-05-03, 08:23   #59
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

181 Posts
Default

Quote:
Originally Posted by retina View Post
The server creates a set of secret random prime-k values and computes the remainders.
Send the remainders to the client.
The clients task is to find the k values that generate the remainders.
Client sends the found k values to the server for verification.

How would that affect the client code if it needs to find some specific remainder values instead of just a remainder of zero, or the smallest remainder?

If you had one remainder then on average the client needs to run 50% of the work before finding the k value.
If you had two remainders then on average the client needs to run 75% of the work before finding both k values.
etc.

Considerations: The set of k values might not exactly match each other when two k values generate the same remainder, so just send one of them and the server can still verify the remainder is correct. The server doesn't need to remember the k values it chooses, just the remainders it sends.
This assumes that mfaktc always computes the residual. which it does not; mfaktc notices when the lower bits of the residual are not zero and doesn't calculate the upper bits so 90%+ of the time the full residual is never calculated.
SethTro is offline   Reply With Quote
Old 2020-05-03, 08:26   #60
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

32×643 Posts
Default

Quote:
Originally Posted by SethTro View Post
This assumes that mfaktc always computes the residual. which it does not; mfaktc notices when the lower bits of the residual are not zero and doesn't calculate the upper bits so 90%+ of the time the full residual is never calculated.
Oh.

Then how do you find the smallest remainder? Doesn't that require computing the upper bits to check if they are zeros?
retina is online now   Reply With Quote
Old 2020-05-03, 10:17   #61
SethTro
 
SethTro's Avatar
 
"Seth"
Apr 2019

181 Posts
Default

Quote:
Originally Posted by retina View Post
Oh.

Then how do you find the smallest remainder? Doesn't that require computing the upper bits to check if they are zeros?
I change the definition of "smallest" to be the most trailing zeros and only compute the full residual when the low word is all zero (rare but still happens several times per ghz-day).

I like you're idea otherwise. It can be reworked to return a lower residual to look for.
The downside is depending on which kernel is used different intermediate values are available this would require the server to make guesses about what kernel mfaktc will use.
SethTro is offline   Reply With Quote
Old 2020-05-04, 16:21   #62
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

23×1,087 Posts
Default

Quote:
Originally Posted by SethTro View Post
It is a natural byproduct of the calculation.
It feels strange for you to not understand this, so maybe your claim is that keeping track of the smallest residual is not a natural byproduct?
I think I was remembering Bob's suggestion. Sorry for the confusion.
Quote:
It doesn't feel good to spend time and effort working on something then have someone call it bad. The use of very feels unrestrained.
I did not say bad. Again, I am concerned about cost vs benefit. You have brought the cost down. I don't like Retina's idea of the server sending some secret info (more than the AID) to the factoring program.

Quote:
I'm worried about them in this order

1. Having any verifiable result associated with each TF submission.
1a. Result(s) should be quickly verifiable by the server (e.g. not requiring a 2nd DC)
1b. Result(s) should cover a large percent of work done.
2. Detect when the GPU/Program is not working quickly (e.g. after 10 submissions not 200)
3. Prevent Malicious/Prank submissions (I'd wager I can easily submit 10000 results at the cost of zero compute and have none of the be detected as fake)

Your method provides 1, 1a, and helps with 2, 3
My method provides stronger guarantees on 1b, 2 and 3.
I did say mine was naive. I have no GPU programming experience.
And sorry for the delay responding. It has been a busy few days.
Uncwilly is offline   Reply With Quote
Old 2020-05-04, 22:16   #63
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

32×643 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
I don't like Retina's idea of the server sending some secret info (more than the AID) to the factoring program.
Just to be clear. The server doesn't need to retain or send any secrets. The remainders can be public information. The initial k-values can be deleted after the remainders have been generated.
retina is online now   Reply With Quote
Old 2020-05-05, 19:17   #64
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

2·4,643 Posts
Default

Quote:
Originally Posted by SethTro View Post
It doesn't feel good to spend time and effort working on something then have someone call it bad. The use of very feels unrestrained.
Juggling some things at the moment, but...

Please never take offense from feedback here. It's never personal -- we're just trying to come to convergence.

At the end of the day, having a "Proof of Work" code-path is going to be a hard sell if it adds more than, let's say, 1% to the compute cost. The reason is we /believe/ there's almost no cheating going on.

Also, it's not the end of the world if a factor is missed. It just means that a P-1 run and then (likely, eventually) two LL tests will be done on the candidate, proving it's composite.

However, I personally feel that /some/ would value having some sort of sanity check on the GPU hardware. As said before, some of us these things for more than just TF'ing (where determinism (or, at least, sanity) is coveted). There would be value in being able to determine if our "kit" was sane while running mfakt[c|o] (as opposed to a GPU based DC test).

Lastly, it would be trivial for the servers to deal with this additional data stream. The heavy-lifting is all in the client (and, thus, the authors of same).
chalsall is offline   Reply With Quote
Old 2020-05-05, 19:38   #65
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

107278 Posts
Default

Quote:
Originally Posted by chalsall View Post
/some/ would value having some sort of sanity check on the GPU hardware. As said before, some of us [use] these things for more than just TF'ing (where determinism (or, at least, sanity) is coveted). There would be value in being able to determine if our "kit" was sane while running mfakt[c|o] (as opposed to a GPU based DC test).
Especially since issues can reside within specific circuitry or microcode that affects one computation type and not another, or for speed and low user involvement. Issues can be very localized, yet significant.

Remember the pentium fdiv bug; wrong output only for specific instruction and operand combinations. Various software workarounds were developed. The initial mass produced chips were wrong by design. https://en.wikipedia.org/wiki/Pentium_FDIV_bug
kriesel is offline   Reply With Quote
Old 2020-05-05, 22:23   #66
greg
 
May 2020

416 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
My 2 centavos is that any overhead that is not error checking related, should not be more than 0.5%. The loss vs. gain doesn't make sense.

If TF and/or P-1 became verifiable (even if only a subset of clients) then there is the potential to reward that work with a portion of the prime prize award (even if only a $2.56 check).
greg is offline   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 06:59.

Tue Oct 20 06:59:31 UTC 2020 up 40 days, 4:10, 0 users, load averages: 1.60, 1.58, 1.57

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.