msieve 1.52 with GPU polynomial selection

[VBCurtis]

Originally Posted by cgy606

Thank you Carlos, the one with CUDA7 works (at least is seems to generate a ton of number triplets on the screen which I think is stage 1). Now, without asking a ton of questions, is there something I can read that will tell me how to configure the parameters of stage 1 poly search given a particular input size (the readme isn't too informative in this regard). What I mean is, what should the bounds be for the stage 1/2 norms, min E-Value, leading coeffs, poly search ranges and time limits per coeff and for the entire process. Also, can gpu do anything other than a degree 5 poly? Thanks...

Within this forum, you'll find a one-post thread on stage1norm selection, as well as quite a lot of discussion about using the various poly-select flags throughout the poly request thread. The poly request thread includes actual invocations of msieve flags, which may help you figure out how to generate a full polynomial.

A super-abridged version:
Run -np1 once for a few seconds to see what the log file says are msieve's choices for stage1norm and stage2 norm.
Then, run msieve -np1 -nps -stage1_norm={default norm divided by 8 to 10, depending on how fast your GPU is; experiment) -stage2_norm={default norm divided by 25 to 30, depending on how big the project is} -s output

This will create an output file "output.ms" with a few dozen size-optimized hits, ready for the root-opt phase. Setting the norms as I suggest should produce a couple hits per hour, though of course that varies with GPU and CPU speed. I try to collect 80 to 150 before bothering to run -npr.

When you have a batch you wish to run, msieve -npr -s output tells msieve to look in output.ms for the polys to run root-opt on. This step takes something like an hour per 100 hits, give or take a factor of two. If you want less output, you can use -min_evalue={something bigger than default but less than the log's hoped-for poly score}.

Let it finish, and the best-scoring poly will be written to (I think) msieve.fb (or maybe msieve.poly, or output.fb).

I allocate GPU time based on a guess of 3% of total project run time. A GNFS-155 will take about 35 core-days, so a full GPU-day of -np1 -nps sounds about right.

[RichD]

by VBCurtis

[jasonp]

When you run stage 1 combined with size optimization, and use a GPU, the GPU handles stage 1 and each hit is immediately forwarded to the size optimization which runs in a separate CPU thread. I designed it that way so the two stages combine to produce a small output file of decent hits, rather than a huge stage 1 file that is manually boiled down to a small output file.

You only want to run the root optimization on a few hits; it runs 100x slower than the size optimization, and if you ran the root optimization on everything most of that effort will be wasted. Root optimization improves the sieving performance of the polynomial, but the best polynomials have both very good size and very good root scores. Polynomials which have mediocre size scores score but excellent root scores cannot compete with them.

Polynomial selection is a lottery; you will get winners at random and get better winners the longer you play.

[VBCurtis]

Originally Posted by cgy606

I produced 760K stage 1 hits in 970 seconds which subsequently lead to a polynomial being found after the other two stages in a little less than 2 hours (20 min for size and 95 min for root opt). Do you think this is enough effort for a c155 gnfs? What benefit would I get if I were to let it spend more time doing polynomial search.

No, 16 minutes of GPU is not enough, by about a factor of 20 (50?). As Jason mentioned, running -np1 and -nps at the same time allocates the GPU to stage 1 and one CPU thread to size-opt at the same time. You discovered that for the norms you selected in your trial run, the two tasks take about the same amount of time; this is the joy of running them together.
How many stage1 hits you get depends entirely on the stage1 norm you choose- I might get 10 hits per second while you get 800/sec, but mine produce 80% of the good polys that yours produce, so my list of 50000 will produce a better poly than your list of 800,000 (note my 50000 would take me 90 min or so, while yours took 16 minutes). There is no "right" number of stage1 hits, they're raw material.
I think the "right" number of stage 2 hits is around 100, assuming the stage2norm is set tightly enough to produce polys worth running root-opt on. As you discovered, msieve's default settings produce a lot of size-opt hits, requiring a LOT of root-opt time; some folks leave stage2norm alone, sort the output file by score (the last column), and root-opt only the best 100 or 1000. I prefer to set stage2norm tightly enough that I can root-opt the entire output file without worrying about sorting or truncating.

To get a sense of what a better poly would get you, compare your poly's E-score to the listing of the best found for your input size in the "best msieve poly scores" thread. If you're very close to the best anyone has found for 155 digits, you are unlikely to improve your performance with more poly search. Score roughly predicts job time: if your poly's score is 20% worse than the best ever found, your job will take roughly 25% longer to run. (20% worse = 0.8; time would be proportional to reciprocal of score, so 1/0.8 = 1.25 = 25% longer).

As a wild guess, your poly might have a score around 3.0e-12. That's about 8% lower than the best ever found, so your job can be expected to take 8-9% longer than the fastest-ever gnfs155 job. Earlier I estimated 35 core-days for a gnfs155, so 8% more is an additional ~3 core-days your job will take from your brief poly search. If you invest a full GPU-day, you might get a poly with a score 2-3% worse than the best ever, knocking 2 core-days off the job length. You might get luckier, or less lucky, but the 3% of project length is a good rule of thumb for the inexperienced.

On bigger projects, relatively more GPU time is often spent, as GPU time is cheap while matrix-solving time is very very processor intensive, so there is incentive to hope to reduce it via a lucky/better poly. I think I gave 3 GPU-days to my first GNFS155 task, 'cause I was nervous I might get a sieve setting wrong and have a job take twice as long as an experienced person might so I wanted a really good poly. Also, there are many knobs to turn in poly select, with quick results ("hey, those norm settings found my best poly yet, in a run that only lasted 8 hrs. Neat!"). Playing with factor-base bounds and large-prime settings and which siever to use are also lots of knobs, but they can be chosen once per job, so playing with them requires running lots and lots of jobs. So, poly select is the most fun to tinker with as it has the quickest feedback.

Good luck!

[cgy606]

I think this is the relevant information on the poly I found:

Wed Oct 05 15:11:47 2016 Msieve v. 1.53 (SVN unknown)
Wed Oct 05 15:11:47 2016 random seeds: ee730bb0 795f1996
Wed Oct 05 15:11:47 2016 factoring 14983833053669267073388859640749386761592128691535474632716887403740027331275486495085918514582693799340373342068801035123016311177538173489337402480577483 (155 digits)
Wed Oct 05 15:11:48 2016 searching for 15-digit factors
Wed Oct 05 15:11:48 2016 commencing number field sieve (155-digit input)
Wed Oct 05 15:11:48 2016 commencing number field sieve polynomial selection
Wed Oct 05 15:11:48 2016 polynomial degree: 5
Wed Oct 05 15:11:48 2016 max stage 1 norm: 8.32e+023
Wed Oct 05 15:11:48 2016 max stage 2 norm: 5.19e+021
Wed Oct 05 15:11:48 2016 min E-value: 2.32e-012
Wed Oct 05 15:11:48 2016 poly select deadline: 1020287
Wed Oct 05 16:47:50 2016 polynomial selection complete
Wed Oct 05 16:47:50 2016 R0: -2625948045755411549827597579873
Wed Oct 05 16:47:50 2016 R1: 99141267303762143
Wed Oct 05 16:47:50 2016 A0: 4597278842096467715676618600553505696486400
Wed Oct 05 16:47:50 2016 A1: 51642863204603531030334712983127200
Wed Oct 05 16:47:50 2016 A2: -1640579774019376000685179714
Wed Oct 05 16:47:50 2016 A3: -2856460253758201969
Wed Oct 05 16:47:50 2016 A4: 80746006334
Wed Oct 05 16:47:50 2016 A5: 120
Wed Oct 05 16:47:50 2016 skew 151147435.61, size 4.912e-015, alpha -8.501, combined = 2.819e-012 rroots = 5
Wed Oct 05 16:47:50 2016 elapsed time 01:36:03

The best according to another post on this forum is for a c155:

155 3.23e-12 Firejuggler 08-13 3408:1311

So I'm about 12.7% off. Not bad for a 16 min GPU job with no fine tuning. Maybe I'll give it another run to see if I can do better...

[VBCurtis]

2.82 is quite close to the best reported for GNFS156, so that poly would make your job almost one digit harder than it should be. That's quite bad, actually; difficulty doubles every 5 digits.

You'll almost surely find 3e-12 or better in a couple hours, and 3.1 or better with an overnight or longer run.