Msieve 1.50 feedback - Page 2

poily · 2012-03-30, 16:22

Ok, I agreed to help jrk investigate this problem.

Meanwhile I found another bug in r715: msieve segfaults in NFS sieving (-ns) mode. I was able to patch the bug out by adding two mpz_poly_init in read_factor_base just before read_poly is called. Not sure if the patch is correct but it works.

WraithX · 2012-04-06, 02:30

Is there any way to limit the polynomials that are generated during polynomial selection? For example, I'm running a search on a C181 and the log stated:

expecting poly E from 5.93e-014 to 6.82e-014

And eventually it found poly's with E values up to 7e-014 and even 8e-014. However, it found a LOT with E values around 4,5,6e-014. I was wondering if an option could be added to msieve that would "not save poly's with E value less than x". Maybe call it -minE x and it could be used like:

msieve -np 1,100000 -minE 6.5e-014 <etc>

And then it wouldn't save any polynomials that had an E score < 6.5e-014. Does this sound reasonable? I was only able to determine this lower bound for my own run after it had been running for a day or two. But, with this addition it would greatly reduce the number of poly's saved to file. Here is an example of the number of poly's it found during my recent search:

Code:

$ grep -c "e 4" *.p
msieve.dat1.p:25295
msieve.dat2.p:26790
msieve.dat3.p:25862
msieve.dat4.p:28362

$ grep -c "e 5" *.p
msieve.dat1.p:6053
msieve.dat2.p:9107
msieve.dat3.p:7664
msieve.dat4.p:8016

$ grep -c "e 6" *.p
msieve.dat1.p:214
msieve.dat2.p:839
msieve.dat3.p:248
msieve.dat4.p:355

$ grep -c "e 7" *.p
msieve.dat1.p:6
msieve.dat2.p:18
msieve.dat3.p:3
msieve.dat4.p:27

$ grep -c "e 8" *.p
msieve.dat1.p:0
msieve.dat2.p:1
msieve.dat3.p:0
msieve.dat4.p:1

xilman · 2012-04-06, 06:38

Quote:

Originally Posted by WraithX

Is there any way to limit the polynomials that are generated during polynomial selection? For example, I'm running a search on a C181 and the log stated:

expecting poly E from 5.93e-014 to 6.82e-014

And eventually it found poly's with E values up to 7e-014 and even 8e-014. However, it found a LOT with E values around 4,5,6e-014. I was wondering if an option could be added to msieve that would "not save poly's with E value less than x". Maybe call it -minE x and it could be used like:

msieve -np 1,100000 -minE 6.5e-014 <etc>

And then it wouldn't save any polynomials that had an E score < 6.5e-014. Does this sound reasonable? I was only able to determine this lower bound for my own run after it had been running for a day or two. But, with this addition it would greatly reduce the number of poly's saved to file. Here is an example of the number of poly's it found during my recent search:

Code:

$ grep -c "e 4" *.p
msieve.dat1.p:25295
msieve.dat2.p:26790
msieve.dat3.p:25862
msieve.dat4.p:28362

$ grep -c "e 5" *.p
msieve.dat1.p:6053
msieve.dat2.p:9107
msieve.dat3.p:7664
msieve.dat4.p:8016

$ grep -c "e 6" *.p
msieve.dat1.p:214
msieve.dat2.p:839
msieve.dat3.p:248
msieve.dat4.p:355

$ grep -c "e 7" *.p
msieve.dat1.p:6
msieve.dat2.p:18
msieve.dat3.p:3
msieve.dat4.p:27

$ grep -c "e 8" *.p
msieve.dat1.p:0
msieve.dat2.p:1
msieve.dat3.p:0
msieve.dat4.p:1

Another approach, and one which wouldn't need human intervention after some period of running, would be for the program to keep a list of the top-N (perhaps N=10 or 20 is appropriate) values found so far. Newly found polynomials would be printed, and stored in the list, only if they are eligible for storing in an updated list.

fivemack · 2012-04-06, 07:53

Quote:

Originally Posted by WraithX

Is there any way to limit the polynomials that are generated during polynomial selection? For example, I'm running a search on a C181 and the log stated:

Yes; you change numbers in the big table in gnfs/poly/poly_skew.c .

Setting these numbers is easiest if you've done an actually-large polynomial selection job to see where the thresholds turn out to be; so thanks for running the large job and telling us that the thresholds currently are wrong. The actual values used are obtained by an exponential interpolation.

I think probably we want to change the last number in the line starting 180 to 7.0e-14 and the last number in the line starting 185 to something like 2.0e-14.

(also the parameter for log=152 is larger than for log=151 at present; looking through the logs of quite a few polynomial selections, I think the commented-out Emax values for 148..151 are more realistic than the currently-active ones)

jasonp · 2012-04-06, 11:52

Thanks everybody, changes are in place now. The ironic thing about saving polynomials is that the current stage 2 of the polynomial selector already keeps a list of the top 200 polynomials found, and it would be easy to move the printing out there, but I currently don't have the time for it.

RichD · 2012-04-08, 01:27

I recently completed a C142 for OPN and currently working on a C138 for HoC. The E scores I got through the first 15000 coefficients beat the expected, so I was good to go sieving (or I thought).

Code:

factoring 4721020176826283942234245210199913451732185614015690866453727141832938312023177626734217364080574415711515119038239236965497177815852334193491 (142 digits)
searching for 15-digit factors
commencing number field sieve (142-digit input)
commencing number field sieve polynomial selection
expecting poly E from 1.41e-11 to 1.63e-11
searching leading coefficients from 2 to 15000
polynomial selection complete
R0: -3169494027445352246332733890
R1: 209449181853581
A0: -9118597704530372603270572314768849
A1: 149885132942924726323262335056
A2: 334954146828597710282668
A3: 8056001457167852
A4: -97510856151
A5: 14760
skew 1733724.27, size 1.149e-13, alpha -6.449, combined = 1.768e-11 rroots = 5

And this one handsomely beat the expected.

Code:

factoring 722563270434339023062704681861783863695892145034250463125043296061508723835492703569922420139832463000361566788159909417823393533888735957 (138 digits)
searching for 15-digit factors
commencing number field sieve (138-digit input)
commencing number field sieve polynomial selection
expecting poly E from 2.41e-11 to 2.77e-11
searching leading coefficients from 10000 to 15000
polynomial selection complete
R0: -557507281822603815271627199
R1: 213903879187097
A0: 613819631110716910616472604373400
A1: -8659415425378762346003145510
A2: 10910174388116480254505
A3: 17040308449026062
A4: 8917368348
A5: 13416
skew 735740.92, size 3.173e-13, alpha -6.543, combined = 3.226e-11 rroots = 3

Did I bail too quickly?

Batalov · 2012-04-08, 02:41

The question when to bail everyone decides for themselves - there are too many parameters (how many sievers will be used, how many poly select threads are used, etc). Or leave it up to the built-in timeout.

That line is all that it says: an expectation interval (the two ballpark values are in the ratio of 1.15 which is the cost of one less effective gnfs digit; it is not unusual to beat the upper estimate by "another digit" or even "two"; you usually don't want to stop without achieving at least the lower estimate). The longer one selects, the better poly one will find.

I guess a phrase "or more" can be easily added to the end of that message. The phrase "or less" is also implied (there are some ranges where the historical fit is not so good and there was no desire to make the function more complicated).

poily · 2012-04-10, 15:17

Quote:

Originally Posted by poily

Meanwhile I found another bug in r715: msieve segfaults in NFS sieving (-ns) mode. I was able to patch the bug out by adding two mpz_poly_init in read_factor_base just before read_poly is called. Not sure if the patch is correct but it works.

The patch in r717 for the problem I described is incorrect: when there's no .fb file with the full factor base in it but instead just an .fb with the polynomial the mpz_poly_free at the end of the read_factor_base kills the allocated polynomials which makes subsequent create_factor_base to fail.

Btw, I've made a patch to enable MPI polynomial search in msieve. It hasn't been tested with GPU but I'm planning to make it work, so here's a question - is the GPU polynomial search in msieve thread safe? I heard CUDA is but the kernel may be not. On the other hand I could probably make a dedicated task on the node to run in GPU mode and all the others in CPU mode.

jasonp · 2012-04-11, 12:49

The whole library should be thread safe, there are no writable global variables used anywhere. The poly search code puts all the CUDA state in local structures, so that should work out okay as well. A CUDA context is thread-local (I hope), the assumption is that one thread uses one GPU, and if there are several GPUs then threads have to switch between different contexts.

Edit: upon reflection, there aren't any globals but one instance of the library does write to files and print to the screen while poly selection is in progress. With MPI any log output writes to a per-MPI-process logfile, but all processes will currently write polynomials found to the same output file.

Also, I haven't tested the line sieve much after converting it to use GMP, so I don't trust it at all right now. Do you have a suggestion for a working alternative to the patch in r717?

xilman · 2012-04-12, 09:59

Thought I'd update my systems to the latest msieve version from a variety of older ones. Since the last iteration of this exercise one system has had OpenBSD 5.0 installed. Msieve doesn't build from the standard tarball on this machine.

The symptoms are:

Code:

-bash-4.2$ make -n
"Makefile", line 23: Missing dependency operator
"Makefile", line 25: Need an operator
"Makefile", line 33: Missing dependency operator
"Makefile", line 36: Need an operator
"Makefile", line 37: Missing dependency operator
"Makefile", line 39: Need an operator
"Makefile", line 40: Missing dependency operator
"Makefile", line 42: Need an operator
"Makefile", line 43: Missing dependency operator
"Makefile", line 61: Need an operator
"Makefile", line 62: Missing dependency operator
"Makefile", line 65: Need an operator
"Makefile", line 66: Missing dependency operator
"Makefile", line 68: Need an operator
"Makefile", line 70: Need an operator
"Makefile", line 245: Missing dependency operator
"Makefile", line 249: Need an operator
"Makefile", line 254: Need an operator
Fatal errors encountered -- cannot continue
-bash-4.2$

I know exactly what's wrong, so this post is partly to get the information into the public domain and partly to ask whether anyone else has tried building it without the GNU enhancments to make(1) --- and I don't mean using Visual Studio!

This particular installation will be put on hold for the moment while the other systems are upgraded and enhanced. I want to install MPI on the significantly multicored machines for instance. If after that a fire&forget solution hasn't arrived I'll think about creating BSDmakefile with BSD-standard conditional operators .if ... .endif , for example, instead of the GNU-like ifeq ... endif.

Paul

poily · 2012-04-12, 10:06

I already dealt with the same polynomial file, so MPI implementation is fully working at least in CPU mode. Except for the Ctrl-C interruption - my home MPI implementations don't give the program enough time to respond to any signal, so msieve couldn't syncronize the results b/ the nodes and select the best.

I'll play with the GPU mode later after jrk sends me the patches he promised.

I see two ways to solve the problem with .fb. The first one is to move mpz_poly_free from the end of read_factor_base to the free_factor_base. The second and I think better one is to pass the polynomials directly from factor_gnfs to the do_line_sieving and later to the read_factor_base/create_factor_base.

2012-04-06, 02:30	#13
WraithX Mar 2006 479 Posts	Is there any way to limit the polynomials that are generated during polynomial selection? For example, I'm running a search on a C181 and the log stated: expecting poly E from 5.93e-014 to 6.82e-014 And eventually it found poly's with E values up to 7e-014 and even 8e-014. However, it found a LOT with E values around 4,5,6e-014. I was wondering if an option could be added to msieve that would "not save poly's with E value less than x". Maybe call it -minE x and it could be used like: msieve -np 1,100000 -minE 6.5e-014 <etc> And then it wouldn't save any polynomials that had an E score < 6.5e-014. Does this sound reasonable? I was only able to determine this lower bound for my own run after it had been running for a day or two. But, with this addition it would greatly reduce the number of poly's saved to file. Here is an example of the number of poly's it found during my recent search: Code: $ grep -c "e 4" .p msieve.dat1.p:25295 msieve.dat2.p:26790 msieve.dat3.p:25862 msieve.dat4.p:28362 $ grep -c "e 5" .p msieve.dat1.p:6053 msieve.dat2.p:9107 msieve.dat3.p:7664 msieve.dat4.p:8016 $ grep -c "e 6" .p msieve.dat1.p:214 msieve.dat2.p:839 msieve.dat3.p:248 msieve.dat4.p:355 $ grep -c "e 7" .p msieve.dat1.p:6 msieve.dat2.p:18 msieve.dat3.p:3 msieve.dat4.p:27 $ grep -c "e 8" *.p msieve.dat1.p:0 msieve.dat2.p:1 msieve.dat3.p:0 msieve.dat4.p:1

2012-04-11, 12:49	#20
jasonp Tribal Bullet Oct 2004 3,541 Posts	The whole library should be thread safe, there are no writable global variables used anywhere. The poly search code puts all the CUDA state in local structures, so that should work out okay as well. A CUDA context is thread-local (I hope), the assumption is that one thread uses one GPU, and if there are several GPUs then threads have to switch between different contexts. Edit: upon reflection, there aren't any globals but one instance of the library does write to files and print to the screen while poly selection is in progress. With MPI any log output writes to a per-MPI-process logfile, but all processes will currently write polynomials found to the same output file. Also, I haven't tested the line sieve much after converting it to use GMP, so I don't trust it at all right now. Do you have a suggestion for a working alternative to the patch in r717? Last fiddled with by jasonp on 2012-04-11 at 12:53

2012-04-12, 09:59	#21
xilman Bamboozled! "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 10,753 Posts	msieve fails to build under BSD Thought I'd update my systems to the latest msieve version from a variety of older ones. Since the last iteration of this exercise one system has had OpenBSD 5.0 installed. Msieve doesn't build from the standard tarball on this machine. The symptoms are: Code: -bash-4.2$ make -n "Makefile", line 23: Missing dependency operator "Makefile", line 25: Need an operator "Makefile", line 33: Missing dependency operator "Makefile", line 36: Need an operator "Makefile", line 37: Missing dependency operator "Makefile", line 39: Need an operator "Makefile", line 40: Missing dependency operator "Makefile", line 42: Need an operator "Makefile", line 43: Missing dependency operator "Makefile", line 61: Need an operator "Makefile", line 62: Missing dependency operator "Makefile", line 65: Need an operator "Makefile", line 66: Missing dependency operator "Makefile", line 68: Need an operator "Makefile", line 70: Need an operator "Makefile", line 245: Missing dependency operator "Makefile", line 249: Need an operator "Makefile", line 254: Need an operator Fatal errors encountered -- cannot continue -bash-4.2$ I know exactly what's wrong, so this post is partly to get the information into the public domain and partly to ask whether anyone else has tried building it without the GNU enhancments to make(1) --- and I don't mean using Visual Studio! This particular installation will be put on hold for the moment while the other systems are upgraded and enhanced. I want to install MPI on the significantly multicored machines for instance. If after that a fire&forget solution hasn't arrived I'll think about creating BSDmakefile with BSD-standard conditional operators .if ... .endif , for example, instead of the GNU-like ifeq ... endif. Paul

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.53 feedback	xilman	Msieve	149	2018-11-12 06:37
Msieve v1.48 feedback	Jeff Gilchrist	Msieve	48	2011-06-10 18:18
Msieve 1.43 feedback	Jeff Gilchrist	Msieve	47	2009-11-24 15:53
Msieve 1.42 feedback	Andi47	Msieve	167	2009-10-18 19:37
Msieve 1.41 Feedback	Batalov	Msieve	130	2009-06-09 16:01

2012-03-30, 16:22	#12
poily Nov 2010 2×5² Posts	Ok, I agreed to help jrk investigate this problem. Meanwhile I found another bug in r715: msieve segfaults in NFS sieving (-ns) mode. I was able to patch the bug out by adding two mpz_poly_init in read_factor_base just before read_poly is called. Not sure if the patch is correct but it works.

2012-04-06, 11:52	#16
jasonp Tribal Bullet Oct 2004 110111010101₂ Posts	Thanks everybody, changes are in place now. The ironic thing about saving polynomials is that the current stage 2 of the polynomial selector already keeps a list of the top 200 polynomials found, and it would be easy to move the printing out there, but I currently don't have the time for it.

2012-04-08, 02:41	#18
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9477₁₀ Posts	The question when to bail everyone decides for themselves - there are too many parameters (how many sievers will be used, how many poly select threads are used, etc). Or leave it up to the built-in timeout. That line is all that it says: an expectation interval (the two ballpark values are in the ratio of 1.15 which is the cost of one less effective gnfs digit; it is not unusual to beat the upper estimate by "another digit" or even "two"; you usually don't want to stop without achieving at least the lower estimate). The longer one selects, the better poly one will find. I guess a phrase "or more" can be easily added to the end of that message. The phrase "or less" is also implied (there are some ranges where the historical fit is not so good and there was no desire to make the function more complicated).

2012-04-12, 10:06	#22
poily Nov 2010 2×5² Posts	I already dealt with the same polynomial file, so MPI implementation is fully working at least in CPU mode. Except for the Ctrl-C interruption - my home MPI implementations don't give the program enough time to respond to any signal, so msieve couldn't syncronize the results b/ the nodes and select the best. I'll play with the GPU mode later after jrk sends me the patches he promised. I see two ways to solve the problem with .fb. The first one is to move mpz_poly_free from the end of read_factor_base to the free_factor_base. The second and I think better one is to pass the polynomials directly from factor_gnfs to the do_line_sieving and later to the read_factor_base/create_factor_base.