mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Hardware > GPU Computing

Reply
 
Thread Tools
Old 2020-11-01, 19:33   #1
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

13×109 Posts
Default Better error correction

With a probably restarted computation the task is to compute base^(2^n) mod N, so here we can have that base is "big". As usual the standard setup, let:

x[t]=base^(2^(t*L)) mod N
y[t]=x[0]*x[1]*..*x[t] mod N

then:
we compute the y[] sequence with y[t]=y[t-1]*x[t]
the error check: y[t]=base*y[t-1]^(2^L) mod N should hold.

If we have a detected error for t=m, but we have stored in memory (x[t],y[t-1],y[t]) earlier residues for 0<t<m then we can find the largest t where we have an error checked residue with a binary search [it can be t=0 if we have no positive t], and continue the work with that stored x[u],y[u] that is passing the error check.

Ofcourse with no failure it gives no speedup but quicker regain when we have error(s), because
you can save some iterations where we're almost absolutely sure that the work was correct.
Assuming there was a single error we'll save on average (at most) half of the residues.
It would be worth to use say 8 (or more) such stored (x[t],y[t-1],y[t]) residues if the cpu/gpu memory still allows [with equally spaced t=m/8*i for i=1..8, note that for t=0 we have an error checked residue], probably less if we are still in the P-1 1st phase's iterations since that is also a memory hungry job.

Notice that it is really worth because one (strong) error check takes L multiplications so a full binary search takes only extra log2(8)*L=3*L multiplications [for 8 stored triplets], but we can save up to L*m iterations. Storing too many triplets is pointless, even if memory allows that since copying residues takes time.

ps. It is not need to store the intermediate x[t], because for a strong checked point: x[t]=y[t]/y[t-1] mod N.

Last fiddled with by R. Gerbicz on 2020-11-01 at 19:41 Reason: trivial typo
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pointwise error correction of convolution outputs ewmayer Math 1 2019-12-05 00:16
Mersenne software error detection or correction opportunities kriesel Software 6 2018-08-06 21:15
@ Supermods: Error Correction please Raman Forum Feedback 72 2013-06-22 07:24
Prime Density Correction Terms? wblipp Math 20 2011-09-07 21:45
Error 5 causes userid change and error 17 updates for exponents Old man PrimeNet PrimeNet 0 2006-02-05 02:27

All times are UTC. The time now is 00:12.

Fri Nov 27 00:12:02 UTC 2020 up 77 days, 21:23, 4 users, load averages: 1.40, 1.51, 1.47

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.