Now what (V)

fivemack · 2009-11-22, 22:01

2^941-1 reservations are closed, and it will soon enter the two-month linear algebra phase, so it's time to start figuring out what to do next.

I'm not sure there's much point manually organising any more sieving, given that NFS@home exists. So I've set my computers over to doing sieving for NFS@home for the moment.

I'm doing a polynomial search with msieve_gpu for the 180-digit EM43 number; my aim is to get a decent polynomial (two GeForce 275-weeks ought to suffice) and then present it to frmky as a candidate for 'first NFS@home GNFS'.

I'm tempted to organise manually a polynomial search, using msieve_gpu, for some local-record-size GNFS, probably the C188 from 7^347+1 - I have checked that the polynomial for RSA200 is too hard to sieve with 32-bit large primes and gnfs-lasieve4I16e, and that I don't have the resources to run a matrix job with 33-bit large primes, but I'm hoping that the polynomial for that C188 might be on the edge of practicality.

I don't know whether a new msieve release might use 96-bit arithmetic on CPU for polynomial search at this level, it's in one sense a complete waste of time to implement since the GPU code is so much faster. But I find that msieve_gpu leaves the machine it's running on pretty much interactively unusable - you get random five-second pauses every fifteen seconds during which the mouse doesn't move and windows don't refresh - and I expect most people have their biggest GPU in their main desktop and wouldn't be willing to use it under those conditions.

Any comments?

Batalov · 2009-11-22, 23:09

For another gnfs-180 (2,2254L), msieve144_gpu bailed after half a day of a run. The pol51 poly for the same number has
# norm 1.16e+25 alpha -6.20 Murphy_E 6.31e-14

It could be the card of course. Is your search producing "save"s?

fivemack · 2009-11-22, 23:28

Yes, I'm getting saves, though it took eight hours to get the first one.

# norm 4.644635e-18 alpha -6.486823 e 3.759e-14

is the best polynomial I've got after twelve hours, but twelve hours into a GNFS-180 polynomial search really isn't very far.

I'm getting to the point of believing that a) the card I have is actually reasonably reliable and b) as soon as you have written outside the bounds of an array in CUDA code running on the GPU, your card has entered a wobbly state and will fall over for no clear reason within the next two minutes to 48 hours, almost surely making you think that some other bit of code is to blame.

Which means I probably should buy an absolute-minimal computer, with a processor so slow that I don't run sieving on it, install the GTX275 in it, and count on rebooting it after each CUDA segfault, if I plan to do any CUDA development at all.

frmky · 2009-11-23, 01:13

Quote:

Originally Posted by fivemack

I'm not sure there's much point manually organising any more sieving, given that NFS@home exists. So I've set my computers over to doing sieving for NFS@home for the moment.

I'm not sure NFS@Home is appropriate for those few with large clusters who wish to participate in a group effort. There may still be a place for manual organization. Comments from Andi47, bsquared, JF?

Quote:

Originally Posted by fivemack

I'm doing a polynomial search with msieve_gpu for the 180-digit EM43 number; my aim is to get a decent polynomial (two GeForce 275-weeks ought to suffice) and then present it to frmky as a candidate for 'first NFS@home GNFS'.

What would be reasonable parameters for this size GNFS? Approximately equivalent to a 270-digit SNFS? I want to hold off for a while getting into anything larger than 2,941-.

jasonp · 2009-11-23, 04:43

Serge has asked before that the 96-bit poly selection code be moved into a CPU version, and it wouldn't be that hard. I estimate that a single modern GPU would be around 35x faster than one core of a comparable CPU when doing poly selection, but Bruce has hundreds of such CPUs available and is not afraid to let them run for a while.

I've noticed the unresponsiveness and there's not much I can do about it, short of using the card in smaller bites and sacrificing some time for extra overhead. At least in windows the refresh rate on the monitor goes way down (a single GPU kernel lasts about 1.2 seconds) but at least background processes do not get stuck.

If 2,941 is almost too large for the postprocessing, how much larger can we go before hitting a postprocessing limit? With NFS@home, enormous sieving jobs can take a few weeks, so it won't be enough to rely on Moore's law making memory cheap by the time we need more of it. The obvous solutions are parallel Lanczos and parallel Wiedemann, and while the second is out of the question given my time budget, the first is doable with a concentrated effort. Otherwise my preference is to continue with the stage 2 root sieve for degree 6; it would be kind of cool to see what a good degree 6 polynomial for RSA >= 200 digits would look like.

bsquared · 2009-11-23, 04:59

Quote:

Originally Posted by frmky

I'm not sure NFS@Home is appropriate for those few with large clusters who wish to participate in a group effort. There may still be a place for manual organization. Comments from Andi47, bsquared, JF?

I'm fairly consistently plagued by guilt for using the university cluster (or machines at work) as much as I do for what I still consider to be hobby activity. I don't like to get in the way of people doing real research.

That, and the job submission queue the clusters use, are barriers to NFS@Home... I'll only be using it manually.

Andi47 · 2009-11-23, 06:34

Quote:

Originally Posted by frmky

I'm not sure NFS@Home is appropriate for those few with large clusters who wish to participate in a group effort. There may still be a place for manual organization. Comments from Andi47, bsquared, JF?

I have used a C2D with 1 GB RAM and Windoze XP for sieving so far (no cluster available), and I have seen that 16e jobs are definitely too large to run in the background (a 1M-sized sieving job at the low end of the range took me several weeks of running it just overnight, stopping it every morning and "-R'ing" it in the evening, with the second thread left idle), so I will not participate in record-sized NFSes any more. I plan to shift this cpu to either ECM or to one of the aliqueit subprojects or to the aliqueit-4788-team-sieves.

frmky · 2009-11-23, 07:05

Quote:

Originally Posted by Andi47

I have used a C2D with 1 GB RAM and Windoze XP for sieving so far (no cluster available), and I have seen that 16e jobs are definitely too large to run in the background (a 1M-sized sieving job at the low end of the range took me several weeks of running it just overnight, stopping it every morning and "-R'ing" it in the evening, with the second thread left idle), so I will not participate in record-sized NFSes any more. I plan to shift this cpu to either ECM or to one of the aliqueit subprojects or to the aliqueit-4788-team-sieves.

This is the setup that is perfect for NFS@Home, but I understand the wish to be more involved in the computations than simply installing the BOINC client and connecting to the project. However, if you change your mind, BOINC has options to automatically pause computations whenever the computer is in use, or will allow you to suspend and resume computations with a single button click.

frmky · 2009-11-23, 07:49

Quote:

Originally Posted by jasonp

I estimate that a single modern GPU would be around 35x faster than one core of a comparable CPU when doing poly selection, but Bruce has hundreds of such CPUs available and is not afraid to let them run for a while.

Since most computers are quad core right now, this means that one GPU can do the work of about 9 computers. Although at first glance it seems like a waste, I suspect that there are significantly more than 9 times more computers than GPUs available to do poly selection. I have a test of CUDA MacLucasFFTW running right now, but once that's done in a few days, I can run poly selection ranges on three GPUs.

Quote:

Originally Posted by jasonp

If 2,941 is almost too large for the postprocessing, how much larger can we go before hitting a postprocessing limit? With NFS@home, enormous sieving jobs can take a few weeks, so it won't be enough to rely on Moore's law making memory cheap by the time we need more of it. The obvous solutions are parallel Lanczos and parallel Wiedemann, and while the second is out of the question given my time budget, the first is doable with a concentrated effort. Otherwise my preference is to continue with the stage 2 root sieve for degree 6; it would be kind of cool to see what a good degree 6 polynomial for RSA >= 200 digits would look like.

Actually, the sieving of 2,941- almost uses too much memory for NFS@Home. There was a large malloc error rate, especially on Windows machines. I can increase the minimum memory required to run the work unit, but this excludes additional machines (esp. Linux) that otherwise would be able to run it. I haven't tried it, but perhaps using 33-bit large primes and a smaller factor base will reduce the memory used by the 16e siever and allow NFS@Home to go to larger numbers.

After spending about 2 1/2 months administering NFS@Home, I'm beginning to think that sieving a 250-digit SNFS in a few days is normal. It's a strange feeling, actually.

J.F. · 2009-11-23, 08:45

Quote:

Originally Posted by bsquared

I'm fairly consistently plagued by guilt for using the university cluster (or machines at work) as much as I do for what I still consider to be hobby activity. I don't like to get in the way of people doing real research.

That, and the job submission queue the clusters use, are barriers to NFS@Home... I'll only be using it manually.

This applies to me also. But I'm ramping down anyway due to other hobby-related activities, so feel free to ignore me in the decision making process.

fivemack · 2009-11-23, 10:16

Quote:

Originally Posted by frmky

What would be reasonable parameters for this size (180-digit) GNFS? Approximately equivalent to a 270-digit SNFS? I want to hold off for a while getting into anything larger than 2,941-.

It's nearer 260- than 270-digit SNFS, I think. On the borderline between the 15e and 16e sievers, so for nfs@home I'd use 15e to save on memory. Algebraic side only, 32A31R large primes, something like alim=2e8 rlim=1e8, and you do need quite a bit of oversieving to get the matrix feasible so I'd go for 4e8 raw relations.

See http://www.mersenneforum.org/showthread.php?t=10495 for the last 180-digit GNFS I had a hand in.

2009-11-22, 22:01	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	Now what (V) 2^941-1 reservations are closed, and it will soon enter the two-month linear algebra phase, so it's time to start figuring out what to do next. I'm not sure there's much point manually organising any more sieving, given that NFS@home exists. So I've set my computers over to doing sieving for NFS@home for the moment. I'm doing a polynomial search with msieve_gpu for the 180-digit EM43 number; my aim is to get a decent polynomial (two GeForce 275-weeks ought to suffice) and then present it to frmky as a candidate for 'first NFS@home GNFS'. I'm tempted to organise manually a polynomial search, using msieve_gpu, for some local-record-size GNFS, probably the C188 from 7^347+1 - I have checked that the polynomial for RSA200 is too hard to sieve with 32-bit large primes and gnfs-lasieve4I16e, and that I don't have the resources to run a matrix job with 33-bit large primes, but I'm hoping that the polynomial for that C188 might be on the edge of practicality. I don't know whether a new msieve release might use 96-bit arithmetic on CPU for polynomial search at this level, it's in one sense a complete waste of time to implement since the GPU code is so much faster. But I find that msieve_gpu leaves the machine it's running on pretty much interactively unusable - you get random five-second pauses every fifteen seconds during which the mouse doesn't move and windows don't refresh - and I expect most people have their biggest GPU in their main desktop and wouldn't be willing to use it under those conditions. Any comments? Last fiddled with by fivemack on 2009-11-22 at 22:02

2009-11-23, 04:43	#5
jasonp Tribal Bullet Oct 2004 3,541 Posts	Serge has asked before that the 96-bit poly selection code be moved into a CPU version, and it wouldn't be that hard. I estimate that a single modern GPU would be around 35x faster than one core of a comparable CPU when doing poly selection, but Bruce has hundreds of such CPUs available and is not afraid to let them run for a while. I've noticed the unresponsiveness and there's not much I can do about it, short of using the card in smaller bites and sacrificing some time for extra overhead. At least in windows the refresh rate on the monitor goes way down (a single GPU kernel lasts about 1.2 seconds) but at least background processes do not get stuck. If 2,941 is almost too large for the postprocessing, how much larger can we go before hitting a postprocessing limit? With NFS@home, enormous sieving jobs can take a few weeks, so it won't be enough to rely on Moore's law making memory cheap by the time we need more of it. The obvous solutions are parallel Lanczos and parallel Wiedemann, and while the second is out of the question given my time budget, the first is doable with a concentrated effort. Otherwise my preference is to continue with the stage 2 root sieve for degree 6; it would be kind of cool to see what a good degree 6 polynomial for RSA >= 200 digits would look like. Last fiddled with by jasonp on 2009-11-23 at 05:04

2009-11-22, 23:09	#2
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	For another gnfs-180 (2,2254L), msieve144_gpu bailed after half a day of a run. The pol51 poly for the same number has # norm 1.16e+25 alpha -6.20 Murphy_E 6.31e-14 It could be the card of course. Is your search producing "save"s?

2009-11-22, 23:28	#3
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6419₁₀ Posts	Yes, I'm getting saves, though it took eight hours to get the first one. # norm 4.644635e-18 alpha -6.486823 e 3.759e-14 is the best polynomial I've got after twelve hours, but twelve hours into a GNFS-180 polynomial search really isn't very far. I'm getting to the point of believing that a) the card I have is actually reasonably reliable and b) as soon as you have written outside the bounds of an array in CUDA code running on the GPU, your card has entered a wobbly state and will fall over for no clear reason within the next two minutes to 48 hours, almost surely making you think that some other bit of code is to blame. Which means I probably should buy an absolute-minimal computer, with a processor so slow that I don't run sieving on it, install the GTX275 in it, and count on rebooting it after each CUDA segfault, if I plan to do any CUDA development at all.