Re: Mersenne: idea for a new prime95 version, QA, primenet etc
> >> Nothing built by human hands is perfect, so, sure, the program could > >> be improved! Personally I'd like to see an optimization for Athlon; > >> at the expense of having to load different versions for different > >> processor types, I'd like to see seperate "streamlined" versions of > >> the code optimized for different processor types rather than one > >> monolithic program with everything embedded in it; Optimizations for Athlon would be very welcome :) Using a modularized version of the program (sort of like dll's) would keep the simlicity in using the program AND keep it resource-efficient. The added download time shouldn't be a problem since it is a one-time download and for example SETI@Home requires daily downloads on a fast machine. (That project isn't going all to bad :)) just my two cents... /Lars _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
On 3 Feb 2001, at 17:03, Jeff Woods wrote: > > >With increasing exponent size (and therefore run time), I'd like to > > >see PrimeNet evolve to track intermediate residues & also to be able > > >to coordinate parallel LL testing & double-checking, so that runs > > >which are going wrong can be stopped for investigation without having > > >to be run through to the end. > > I think this is an EXCELLENT idea, but remember that the "s" values (i.e. > the intermediate residue/modulus) for such numbers is quite simply > enormous. One couldn't (and shouldn't) check the entire intermediate > value, but merely the last "x" bits, where "x" is enough to be reasonably > certain that a match isn't random chance -- say, the final 1024 bits. 64 bits is enough to be pretty confident! We need a recovery procedure anyway, to cope with any systematic bugs which may exist. > > PrimeNet would thus also have to carefully assign the exponents to similar > machines with similar runtimes and performance, as it would do little good > to assign the primary test to an Athlon-800 and the "real-time" > double-check to a much slower machine, as the Athlon would quickly outpace > the second check. > > If a discrepancy was found in a real-time double-check, a ternary run on a > different machine could determine which (if either) of the two intermediate > residuals was correct, and the tests could proceed from there, with both > original machines assuming the same correct residue. > My reply to Ken Kriesel's message on this topic shows how the need for paired systems to be evenly matched could be avoided - though it is certainly preferable that gross mismatches are avoided. However, there shouldn't be much problem providing reasonable matches, since the PrimeNet server knows each participating system's CPU type & clock speed. > Also, if this did evolve, I'd suggest that the "double-checker" be given > equal credit with the primary machine, for purposes of credit in history > books as discoverers, and/or EFF monies. This question obviously needs to be addressed, if only to keep lawyers out of our hair. I agree with Jeff on this one. > > Note that there's a point of futility, at which a "tie-breaker" ought to > merely be a triple-check, run to conclusion. Let's say on a 14-month co-op > effort, 13.6 months into it a discrepancy was found. Both machines ought > to finish, and just have it triple-checked, rather than suspending both, > awaiting a tiebreaker. While I'm sure someone could solve for the optimum > cutoff point where tiebreakers are not useful, my guess would be that it is > around 85% of the way to completion. With the suggestions in my reply to Ken, having "late" checkpoints doesn't do much to slow down completion - the leading system proceeds unless or until the trailing system finds a discrepancy. However, I certainly agree that there's not much point in having a checkpoint at iteration 14 million if you're testing e.g. exponent 1403. I'd suggest "missing out" the last checkpoint if the number of iterations remaining at that point is less than half the iterations between checkpoints. Regards Brian Beesley _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
Jeff Woods wrote: > Then why is SETI@home so popular, when it shows little in the way of daily > statistics, either? Because Space/Aliens/E.T./Sci-Fi/etc is popular and SETI lets you participate, not just watch NASA/movies/others... That busy colorful SETI screensaver is also pretty neat to watch. Cheers... Russ _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
Ken Kriesel wrote: > At 09:23 AM 2/3/2001 -, "Brian J. Beesley" <[EMAIL PROTECTED]> wrote: > >> George has announced the development of new FFT code optimised for >> Pentium 4. The FFT code is the true heart of the program: it's really >> hard for me to put into words just how much we all owe to George for >> his unstinting efforts to make the program as efficient as it is. >> Suffice it to say that, without George's input, we would probably be >> two or three Mersenne primes short of where we actually are. > > > Possibly 4 primes. That would obviously depend on how fast David Slowinski was progressing at the time. Remember that much of George's contribution was organizing the project itself, though he certainly has put a huge amount of effort into developing the x86 software. > > I've been lobbying a bit for a dual-processor optimized version for Intel. > I have little technical basis on which to judge the potential gains, but > speculate that memory bus contention and caching efficiency would > be improved if both processors were working on the same large exponent. IIRC, Slowinski usually ran one exponent on each processor, except when verifying a prime. > > Well before learning of GIMPS and George's program in 1996, I had > coded a program to do limited trial division followed by a Lucas-Lehmer > test. Having done that, and then seeing the efficiency of George's > program, gave me a better appreciation for how much work and skill > went into prime95. It's highly optimized, using the counters built into > the cpus for the purpose, and using virtually everything known about > properties of potential factors and the best algorithms to speed things up > both in the factoring attempts and the Lucas Lehmer test. > > Our best hopes for future speed improvements are > 1) the steady march to faster computers in greater numbers (& more > multi-cpu systems running multiple instances of the program 1 per cpu) > 2) possible future discoveries of better algorithms by mathematicians. > Last I heard, there was still some space between the upper and lower > bounds to the limit on number of operations required to perform a > long multiplication or squaring. > 3) modest increments due to optimizations to specific architectures, > additional factoring methods, implementation of additional FFT runlengths etc. > The easy large gains were implemented long ago, and medium difficulty > & moderate gains also, leaving diminishing returns requiring significant > effort. Obviously, something else we can all do is encourage our friends to run the program. I am a member of a website known as everything2, and have written articles for that site regarding GIMPS. Feedback is welcome. I am aware that my article is now extremely brief, but it's hard to see what more can be said in a non-technical way. http://www.everything2.com/index.pl?node_id=877902 I have also mentioned GIMPS on my homepage, http://www.acsu.buffalo.edu/~nrussell/ > >> Nothing built by human hands is perfect, so, sure, the program could >> be improved! Personally I'd like to see an optimization for Athlon; >> at the expense of having to load different versions for different >> processor types, I'd like to see seperate "streamlined" versions of >> the code optimized for different processor types rather than one >> monolithic program with everything embedded in it; and I'd like to >> see the client/server security code somehow "opened", to facilitate >> the integration of non-Intel clients into PrimeNet, but without >> sacrificing the trust we have that results have really been computed. > > > Let's keep it simple; disk space is cheap (including space for paging > out unused code). > I think the current situation where the program detects cpu model > and reacts accordingly is a good one; you can still take control > by editing the ini file if need be. It keeps it simple for both the novice > end user wanting to download a program and get going, and for the > program developers. If cpu-specific programs were made > instead, the number of distinct programs gets large because the > combinations of cpu type and OS is large. Agreed there! There is nothing wrong with monolithic programs. Compared with, eg, Netscape or even Winamp, Prime95 requires a very small amount of resources. (snip) > > Perhaps some GIMPS participants could offer George & Scott > nonprivileged account access on some other architectures, so they > could do the required development. Certainly not a bad idea. I think an Amiga client in particular would attract a fair amount of interest, as would a version specially designed for NetBSD or OpenBSD > >> With increasing exponent size (and therefore run time), I'd like to >> see PrimeNet evolve to track intermediate residues & also to be able >> to coordinate parallel LL testing & double-checking, so that runs >> which are going wrong can be stopped for investigation without having >>
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
Jeff Woods wrote: > At 04:48 PM 2/3/01 -0500, you wrote: > >> After hanging around the Anandtech DC forum for awhile, I'm convinced >> that this completion time "problem" might be GIMPS biggest hurdle to >> getting more participation. Very few "loonies" like us are willing >> to wait 14 months for the calculation of one result. Those folks at >> Anand's are interested in visible changes in daily statistics, >> something GIMPS doesn't provide when doing LL testing. > > > Then why is SETI@home so popular, when it shows little in the way of > daily statistics, either? I recently invested a few CPU days in SETI. On my P3-600, I was completing a work unit about every 7-8 hours. Most people's primary machines could certainly complete one work unit per day quite easily. I might point out, though, that now that SETI is producing a new client version which does more testing, and requires roughly twice as long to do each work unit, some folks were complaining on their IRC channel about the time needed to finish each work unit. Nathan _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
At 17:04 02/03/2001 -0500, Jeff Woods wrote: >At 04:48 PM 2/3/01 -0500, you wrote: > >>After hanging around the Anandtech DC forum for awhile, I'm convinced that >>this completion time "problem" might be GIMPS biggest hurdle to getting >>more participation. Very few "loonies" like us are willing to wait 14 >>months for the calculation of one result. Those folks at Anand's are >>interested in visible changes in daily statistics, something GIMPS doesn't >>provide when doing LL testing. > >Then why is SETI@home so popular, when it shows little in the way of daily >statistics, either? My understanding is that it is possible to have a significant change in daily statistics with SETI@home. A fast machine can complete a SETI work unit in 8 to 10 hours, I believe. Additionally, I believe that SETI@home is "sexier" for the general public and has done a much more thorough job of selling itself via the general media. BTW, I do participate in GIMPS (and have since around 1996 or so), so it's not as if I think it's a bad thing. I just think it will be tough to attract significant membership numbers (say two hundred thousand users, just to throw out a number) when an exponent takes 14 months to complete. Kel _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
At 04:48 PM 2/3/01 -0500, you wrote: >After hanging around the Anandtech DC forum for awhile, I'm convinced that >this completion time "problem" might be GIMPS biggest hurdle to getting >more participation. Very few "loonies" like us are willing to wait 14 >months for the calculation of one result. Those folks at Anand's are >interested in visible changes in daily statistics, something GIMPS doesn't >provide when doing LL testing. Then why is SETI@home so popular, when it shows little in the way of daily statistics, either? _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
At 02:57 PM 2/3/01 -0600, you wrote: > >With increasing exponent size (and therefore run time), I'd like to > >see PrimeNet evolve to track intermediate residues & also to be able > >to coordinate parallel LL testing & double-checking, so that runs > >which are going wrong can be stopped for investigation without having > >to be run through to the end. > >In the QA effort, we've seen a few instances already of errors caught >midway by doing a manual/email version of this. Brian Beesley had an error >detected this way in his run of a double-check of a 10-megadigit exponent. >This exponent takes a PII-400 428 days (yes 14 months) to complete, >so detecting the one error and restarting early saves about 10.5 PII-400 >months. I think this is an EXCELLENT idea, but remember that the "s" values (i.e. the intermediate residue/modulus) for such numbers is quite simply enormous. One couldn't (and shouldn't) check the entire intermediate value, but merely the last "x" bits, where "x" is enough to be reasonably certain that a match isn't random chance -- say, the final 1024 bits. PrimeNet would thus also have to carefully assign the exponents to similar machines with similar runtimes and performance, as it would do little good to assign the primary test to an Athlon-800 and the "real-time" double-check to a much slower machine, as the Athlon would quickly outpace the second check. If a discrepancy was found in a real-time double-check, a ternary run on a different machine could determine which (if either) of the two intermediate residuals was correct, and the tests could proceed from there, with both original machines assuming the same correct residue. Also, if this did evolve, I'd suggest that the "double-checker" be given equal credit with the primary machine, for purposes of credit in history books as discoverers, and/or EFF monies. >I assume that Brian means sending intermediate 64-bit residues to Primenet >for comparison. (The intermediate save files are too big to send with any >frequency and would require a lot of storage.) > >To automate checking via interim residues would require significant longterm >storage at primenet, of quadruples containing exponent, iteration, 64-bit >residue, and the source of the information (person or machine ID). When >two with matching exponent and iteration but different source were available a >comparison would be made; if a discrepancy was found, both runs should be >halted while a tiebreaker run was made via a different source, to avoid >wasting cpu time of one or both original sources. Since the most likely >cause of a discrepancy is error in one run not both, a resume capability >as well as a discard capability would be needed. I feel exponents halted >for a tiebreaker run should not be expired. I'd agree. Machines awaiting a tie-breaker could move on to factoring, or another smaller double-check. I would not want to see such machines begin another 14-month effort, as once the tiebreaker concluded, that work would be suspended while the first test was concluded. Note that there's a point of futility, at which a "tie-breaker" ought to merely be a triple-check, run to conclusion. Let's say on a 14-month co-op effort, 13.6 months into it a discrepancy was found. Both machines ought to finish, and just have it triple-checked, rather than suspending both, awaiting a tiebreaker. While I'm sure someone could solve for the optimum cutoff point where tiebreakers are not useful, my guess would be that it is around 85% of the way to completion. _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
At 14:57 02/03/2001 -0600, Ken Kriesel wrote: >In the QA effort, we've seen a few instances already of errors caught >midway by doing a manual/email version of this. Brian Beesley had an error >detected this way in his run of a double-check of a 10-megadigit exponent. >This exponent takes a PII-400 428 days (yes 14 months) to complete, >so detecting the one error and restarting early saves about 10.5 PII-400 >months. After hanging around the Anandtech DC forum for awhile, I'm convinced that this completion time "problem" might be GIMPS biggest hurdle to getting more participation. Very few "loonies" like us are willing to wait 14 months for the calculation of one result. Those folks at Anand's are interested in visible changes in daily statistics, something GIMPS doesn't provide when doing LL testing. Kel U. _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: idea for a new prime95 version, QA, primenet etc
At 09:23 AM 2/3/2001 -, "Brian J. Beesley" <[EMAIL PROTECTED]> wrote: >George has announced the development of new FFT code optimised for >Pentium 4. The FFT code is the true heart of the program: it's really >hard for me to put into words just how much we all owe to George for >his unstinting efforts to make the program as efficient as it is. >Suffice it to say that, without George's input, we would probably be >two or three Mersenne primes short of where we actually are. Possibly 4 primes. I've been lobbying a bit for a dual-processor optimized version for Intel. I have little technical basis on which to judge the potential gains, but speculate that memory bus contention and caching efficiency would be improved if both processors were working on the same large exponent. Well before learning of GIMPS and George's program in 1996, I had coded a program to do limited trial division followed by a Lucas-Lehmer test. Having done that, and then seeing the efficiency of George's program, gave me a better appreciation for how much work and skill went into prime95. It's highly optimized, using the counters built into the cpus for the purpose, and using virtually everything known about properties of potential factors and the best algorithms to speed things up both in the factoring attempts and the Lucas Lehmer test. Our best hopes for future speed improvements are 1) the steady march to faster computers in greater numbers (& more multi-cpu systems running multiple instances of the program 1 per cpu) 2) possible future discoveries of better algorithms by mathematicians. Last I heard, there was still some space between the upper and lower bounds to the limit on number of operations required to perform a long multiplication or squaring. 3) modest increments due to optimizations to specific architectures, additional factoring methods, implementation of additional FFT runlengths etc. The easy large gains were implemented long ago, and medium difficulty & moderate gains also, leaving diminishing returns requiring significant effort. >Nothing built by human hands is perfect, so, sure, the program could >be improved! Personally I'd like to see an optimization for Athlon; >at the expense of having to load different versions for different >processor types, I'd like to see seperate "streamlined" versions of >the code optimized for different processor types rather than one >monolithic program with everything embedded in it; and I'd like to >see the client/server security code somehow "opened", to facilitate >the integration of non-Intel clients into PrimeNet, but without >sacrificing the trust we have that results have really been computed. Let's keep it simple; disk space is cheap (including space for paging out unused code). I think the current situation where the program detects cpu model and reacts accordingly is a good one; you can still take control by editing the ini file if need be. It keeps it simple for both the novice end user wanting to download a program and get going, and for the program developers. If cpu-specific programs were made instead, the number of distinct programs gets large because the combinations of cpu type and OS is large. Prime95 supports or supported something like 11 cpu type codes. Regarding OS, there are at least 6 types (currently maintained at V20): Win95/NT interactive NT service linux statically linked linux freebsd statically linked bsd Setting CPU type in prime95 V20.4.1 and then examining local.ini, CPUType=3 is a Cyrix 6x86 CPUType=4 is a 486 CPUType=5 is a Pentium CPUType=6 is a Pentium Pro CPUType=7 is an AMD K6 CPUType=8 is a Celeron CPUType=9 is a PentiumII CPUType=10 is a PentiumIII CPUType=11 is an AMD Athlon P-4 code adds another type. (Is there another AMD type?) Presumably cputype 386 and below have been retired (yes 386's were supported, in v13.2 or so) Perhaps some GIMPS participants could offer George & Scott nonprivileged account access on some other architectures, so they could do the required development. >With increasing exponent size (and therefore run time), I'd like to >see PrimeNet evolve to track intermediate residues & also to be able >to coordinate parallel LL testing & double-checking, so that runs >which are going wrong can be stopped for investigation without having >to be run through to the end. In the QA effort, we've seen a few instances already of errors caught midway by doing a manual/email version of this. Brian Beesley had an error detected this way in his run of a double-check of a 10-megadigit exponent. This exponent takes a PII-400 428 days (yes 14 months) to complete, so detecting the one error and restarting early saves about 10.5 PII-400 months. (Thanks to Rick Pali for providing interim residues to make this savings possible.) Another exponent, 20295631 showed similar results; both Paul Victor Novarese's run and mine produced errors while Brian Beesley's run matched Gordon Spence's. I assume that B
