Current status

[R.D. Silverman]

Originally Posted by xilman

I've been vaguely assuming that the last base-3 number should be done next. At least, that was the purpose of discussion with Alex a few months back.

However, I'm not really in a position to contribute much sieving effort these days.


Paul

Doing 3,499+ is terrific, but given the current progress on 3,479+, one might
ask whether you want to spend a whole year (or more) sieving one number?

Perhaps NFSNET might solicit for more sievers on sci.crypt/sci.math
etc?

Perhaps those spending (wasting IMO) time chasing billion digit primes
or OPN might be convinced to switch to a project that can and will
succeed with a large-but-doable effort?

I've squeezed another several percent out of my lattice sieve via
improved parameter choices. Perhaps NFSNET might want to switch
to a lattice siever? Mine will fit in less than 1/2 Gbyte. It would
probably need some minor changes to run under NFSNET, but I know
how and where to make those changes. My lattice siever really is at
least 5 times faster than my line siever for numbers in the 200+ digit range.

How much machine time did NFSNET require for 2,1466L? I did 2,1454L
in only 17 days with about 16 machines running nights/weekends only and
another 10 machines running about 90% of the time. 2,1462L should
take me about ~3 weeks. AFAIR, 2,1466L took NFSNET more than a month
with ~100 machines????

NFSNET really should change sievers.

[akruppa]

> NFSNET really should change sievers.

I agree. I'm using only Franke's siever atm, when I compare the rate of relations found between Franke's lattice siever and the CWI line siever, Franke's usually is several times faster (how many times exactly depending on the project size.)

I'm aware of how hard Franke's siever is to port, although afaik the ggnfs project has done some work to improve portability.

As an alternative, NFSNET could maybe use Bob's siever. I don't know how fast it is compared to Franke's, but it supports lattice sieving and so should beat CWI's handily.

Btw, I don't know how much longer I'll have access to any University computers, but if I do when sieving for 3,499+ starts, I'd happily join in. I may also polish the 31 bit hacks I did for the CWI tools some more so they can be used for 3,499+. Using 31 bit large primes should help for a project of this size.

Alex

[Wacky]

I see two problems related to changing sievers.

First, the added memory required for a lattice siever will eliminate some of our participating machines.
However, the bigger problem is code stability. Although I have gotten a number of different sievers to run on one machine or another, only the CWI siever seems to be reliable across the range of different machine/OS configurations of our participants.
And the biggest problem is that all of this keeps falling on my shoulders. Not only am I having to handle the day-to-day administration, I'm also the only one that seems to have time to work on the code. And I don't really have that much time to devote to it.

[xilman]

Originally Posted by Wacky

I see two problems related to changing sievers.

First, the added memory required for a lattice siever will eliminate some of our participating machines.
However, the bigger problem is code stability. Although I have gotten a number of different sievers to run on one machine or another, only the CWI siever seems to be reliable across the range of different machine/OS configurations of our participants.
And the biggest problem is that all of this keeps falling on my shoulders. Not only am I having to handle the day-to-day administration, I'm also the only one that seems to have time to work on the code. And I don't really have that much time to devote to it.

I just don't have time to work on the code either.

I'm frequently able to run sieving in an off-line mode but I am not able to satisfy the conditions required to run classical NFSNET clients. There is just too much admin overhead, from my point of view, to set up a slave server and yet if I were to run a purely client site I can fairly confidently predict that the clients would spend much of their time blacklisted and/or trying to contact a server to acquire more work to do. Sorry, but a maximum timeslice of two hours between client/server contacts is much too small --- by a factor of at least ten and possibly fifty to a hundred.

Unless someone can find the time to port different sievers and find the time to re-implement the administrative software, NFSNET will continue to run at suboptimal efficiency. As I say, I do not have the time.


Paul

[R.D. Silverman]

Originally Posted by xilman

I just don't have time to work on the code either.

I'm frequently able to run sieving in an off-line mode but I am not able to satisfy the conditions required to run classical NFSNET clients. There is just too much admin overhead, from my point of view, to set up a slave server and yet if I were to run a purely client site I can fairly confidently predict that the clients would spend much of their time blacklisted and/or trying to contact a server to acquire more work to do. Sorry, but a maximum timeslice of two hours between client/server contacts is much too small --- by a factor of at least ten and possibly fifty to a hundred.

Unless someone can find the time to port different sievers and find the time to re-implement the administrative software, NFSNET will continue to run at suboptimal efficiency. As I say, I do not have the time.


Paul

I would be happy to modify my lattice siever, but I don't know how
to make it fit in with the current NFSNET admin tools; how are
assignments made? how are unfinished assignments determined and
reassigned? How is data collected?

I see no reason why sievers need to be in constant contact with
the servers. Grab an assignment that will take (maybe) 4-5 days,
and return data files once a day, for example. This would allow
"semi" off-line work.

My home Pentium IV PC does (for numbers in the (say) 700-750 bit
range) a single special Q in about 18-20 seconds. This is about 10000
special Q's every 2 days. [or 4 nights]. My current number will require
about 2.6 million special Q's (+/- 15%). This is ~520 machine days.

I can provide my PC based siever for off-line work to NFSNET.
I am working on a port to SUN-Solaris and HP-UX, but these
machines will be quite a bit slower than the PCs. I have encountered
bugs and have not had the time to track them down.

I personally would be willing to run an off-line network based sieve
effort, but I have no way to collect the data owing to security restrictions.
An automated server to receive data is impossible for me.
There is no way that I could collect 8-10Gbytes of data via email. (Our
admins would be justifiably annoyed with the data traffic coming to me
and I don't have time to manually extract email data.)

Perhaps a compromise would be the following:

I provide code, input data and assignments, MANUALLY in big chunks.
[say 10 machine days worth at a time].

Then people periodically (say every 10 days) send the relation data to a
central NFSNET site and send reports (automatically generated) of which
Q's were run to me. [so I can reassign Q's that were not run]

I am in violent agreement that the assignment granularity should
be coarse.

Once upon a time I had the time for such efforts. Now I have a real job.
[as Xilman and Wacky know all too well.................]

[Wacky]

OK, I'll try to give you some insight into the reasons that we are doing things in the manner that we are:

First, I will assure you that the administrative load in handling assignments quickly becomes unmanagable when you are dealing with a group that is more than just a few highly motivated, responsible participants. Automated procedures for tracking assignments, etc. are almost essential.

Second, and this was not my suggestion or preference, it was chosen to use an HTTP server to send assignments and receive results. Particularly because of proxy servers, this has caused some difficulty in receiving response packets that contain a large number of relations. Sometimes, I even have difficulty receiving (much larger) files by sftp from the Bristol server. The 2 hour reporting interval is a compromise. It would be very easy to run a server that gave out significantly larger assignments if we could get the results back. In that respect, the original NFSNet that I set up and ran a decade ago using SMTP as a transport mechanism had a significant advantage over the current implementation. In particular, it had a queue of work to be done. Each "assignment" was of a reasonable size, but we kept a number of assignments in each participant's pipeline. And, unlike the current implementation, the transport ran in parallel with the sieving in an entirely separate program.

For the last year, or so, I have been attempting to design and implement a new system. I'll describe it in more detail in the next posting.

Richard

[xilman]

Originally Posted by Wacky

Sometimes, I even have difficulty receiving (much larger) files by sftp from the Bristol server. The 2 hour reporting interval is a compromise. It would be very easy to run a server that gave out

I can very, very easily write a Perl script (or most any other kind of script for that matter) which will chop up a large chunk of relations into portions of any size you wish and then upload them individually by sftp, http, ftp, rcp, scp, smtp, airmail, or most any transport you wish to name. What I can't guarantee is that my machines will remain permanently connected to the internet, or even with periods of disconnection insignificant in comparison to 2 hours. If my ADSL line goes down, which it does distressingly often, it can, and frequently does, remain down for several hours. I had to reboot the router between sending my previous posting in another thread about how to run ECM from the command line and composing this response. If the ADSL link had gone down after I went to bed, it would remain down until at least the next morning.

If I can run my sievers for days or weeks at a time and upload the results (in bite-size chunks if desired) when I feel like it then I can contribute. I can not contribute if I'm required to be on-line essentially continuously. Neither can I set up a NFSNET slave server on my employer's systems, though I can very probably run sievers at idle priority --- as long as I am neither required to shutdown cleanly nor to complete any particular assignment. I am capable of writing scripts to determine the extent of any work not completed and to resubmit that work to fresh instances of the sievers.


Paul

[Wacky]

When NFSNet" was organized, we wanted to quickly get something operational so that we could be doing useful work while we developed the supporting infrastructure. To accomplish this, we were fortunate enough to have been granted a source license to the CWI line siever. We quickly designed a scheme to augment the normal output with some additional tracking information that can be used to drive our administrative processes.

The code to do this was "hacked" into the siever and we were quickly generating output files based on manual assignments and manual delivery of the results. This was fine because there were only three of us involved at the time. Soon, we had developed a "wrapper" program that communicated with a server and automated the "last mile" delivery. At least in theory, another "wrapper" could be implemented and we could still utilize the same siever code. This is one of the things that IMHO we did "right".

Our development effort has always been hampered by a shortage of "human resources". Those individuals who have the skills, don't seem to have the time and visa-versa.

One of the biggest drawbacks is related to the siever code. There are a few excellent developers out there who have written some very good sieving code. Unfortunately, none of them seem to write code that is very portable, either between platforms or even compilers. The CWI siever has been, in my experience, the most dependable across platforms. Unfortunately, because of licensing restrictions, our group has very few members who are authorized to access that source code.

To get around this problem, and to further allow flexibility across platforms (choose, by platform, the best implementation of the functionality, even if the choices are different), I am attempting to abstract the "computation" from the "control". If we view any loosely coupled distributed computation, it can be reduced to performing a specific task for each of a large number of distinct lattice points. Often it is significantly more efficient to perform a number of "consecutive" tasks on the same processor because of initialization "expense".

This code for this "control" can be made common to many distributed efforts by reducing the hard-to-code computational part as a subroutine to a common control interface. Similarly, for each class of conputations (a lattice siever and a line siever both produce "relations") having a common output routine gives us the flexibility to format and handle the output as we see fit.

This also gives us the ability to separate the "meta-data" from the siever. By supplying an interface into the common control section, additional meta-data can be incorporated in the output stream without the siever having any need to understand its meaning.

My whole purpose in this approach is to attempt to partition the system into components that can be developed independently. Even the most ineffieient siever is adequate to provide data to a developer working on the infrastructure. Simply writing to a file is adequate for a siever developer to "tune" his code.

[Wacky]

Paul,

Yes, I recognize that you can do so. If you would like for me to assign you a million "lines", I would have no problem doing so. In fact, I have plenty of them available for our current project. I both know that you would attempt to fulfill that "obligation" and, within a reasonable time frame, keep the project coordinator apprised of your progress.

However, please recognize that such a solution does not "scale".

Also note that this is somewhat independent of the "line" vs. "lattice" siever question. From our previous experience, it is unclear just how we can efficiently mix the two. -- And then there is also the question of a "stable" lattice siever for an adequate number of platforms.

Perhaps we need to bifurcate the effort. I'm sure that there are some "easy" factorizations still around (perhaps not "Cunningham") that we could allow a subset of the participants to pursue while those of us who are fortunate enough to have enough memory use a lattice siever to attack a much harder problem.

[Wacky]

Originally Posted by fivemack

OK, so NFSNET is managing 12% a month, at which rate the sieving won't be done until the end of the year

A month later and we are at 69%. That's 20% in the last month. And at the present rate, we should finish this one at the end of the month.

Our progress is highly dependent on the level of participation of a few key individuals. Unfortunately, we should expect the rate to drop in the Fall as some of those resources are directed to other projects. Unless there is a significant increase due to people returning from Summer, I fear that we should not attempt anything "hard" at this time.

Does anyone have any "easy" suggestions?

[R.D. Silverman]

Originally Posted by Wacky

A month later and we are at 69%. That's 20% in the last month. And at the present rate, we should finish this one at the end of the month.

Our progress is highly dependent on the level of participation of a few key individuals. Unfortunately, we should expect the rate to drop in the Fall as some of those resources are directed to other projects. Unless there is a significant increase due to people returning from Summer, I fear that we should not attempt anything "hard" at this time.

Does anyone have any "easy" suggestions?

Sure! 5,311-, 5,311+ , 5,313- and 5,313+ are ~730 bits and
are the 1st/2nd holes in the base 5 tables. 7,263- is quite doable.
The base 5 numbers are the oldest unfactored numbers among the
first 5 holes in all the Cunningham tables......

We need to encourage more participants! Why is it that GIMPS
can attract 10's of thousands (or more)?

I am about 50% done with 2,1462L and will then do 2,1478L, 1490L, and
1526L. The last two are easy. This will finish 2LM to 768 bits.