Msieve 1.51 feedback - Page 5

LangerJan · 2013-02-21, 12:11

Quote:

Originally Posted by jasonp

Thanks for the first fix to the QS code in 6 years :)

I'm glad I could help

I'm doing this for my master thesis, I can fill a section or two about bugfixing ;)

Quote:

Originally Posted by jasonp

I committed the change to avoid the double-free. The first bug you found is a lot more subtle; you get a crash because the values of root1 and/or root2 are not correct, and the prime in the loop does not actually divide the sieve value. Unfortunately any checks for something wrong in the sieve would take time, so I don't yet know why it's wrong, and it could be literally anything.

I made a (rather dirty) hotfix for that one, which at least lets me continue working: I think it's safe to assume that when mp_is_zero(&res) is true within the loop, something went horribly wrong. I break then and try to return with an error-code.

Dubslow · 2013-02-26, 19:28

Are there plans for adding LangerJan's error-handling patch to trunk? (And, to be extra annoying, what about the stuff I put in post 38? yafu uses analyze_one_poly(), by parsing the output file which is a rather ugly kludge

)

LangerJan · 2013-03-02, 01:01

You know what would be really great? A configure script! :) I might try writing one, but I can't test it all alone.

WraithX · 2013-03-17, 02:49

Okay, I've finally downloaded svn 863 (on my new Linux system) and did "make all CUDA=1 NO_ZLIB=1". It looks like I've finally gotten everything to compile. I'd like to ask for some advice on running the polynomial selection on a C210 (GNFS) that I'll be working on here shortly. Can someone confirm if my following notes are correct for poly select?

Code:

msieve -v -i worktodo.ini -np1 "stage1_norm=5e33 X,Y" -s <something_unique>
(this will create a something_unique.m file)

./msieve -v -i worktodo.ini -nps "stage2_norm=1e100" -s <something_unique>
(this looks for something_unique.m and will create something_unique.ms)
(the .ms file will end up about 4 times bigger than the .m file)

./msieve -v -i worktodo.ini -npr -s <something_unique>
(this looks for something_unique.ms and will create something_unique.p)
(the .p file will end up about 250 times bigger than the .ms file)

./msieve -v -i worktodo.ini -npr "stage2_norm=1e100" -s <something_unique>
(this looks for something_unique.ms and will create something_unique.p)
(the .p file will end up about 250 times bigger than the .ms file)

grep alpha *.p | sort -g -k 7 | tail
(this will list the 10 best poly's found)

For -np1:
1) Is there a preferred format for X and Y? ie, Can I do 1.0e8,2.0e8? Or should it be 100000000,200000000?
2) Would it hurt to search smaller X and Y? ie 1 to 1.0e8, or should I start at some large value, like 1e10?
3) Is there a preferred stage1_norm for a C210?
4) Is it better to have two computers searching the same X,Y range, or should I have them work on two different X,Y ranges?

For -nps/-npr:
1) Is there a preferred stage2_norm for a C210?

jasonp · 2013-03-17, 03:28

1) you have to write out X and Y, floating point will not work
2) searching smaller X and Y will probably hurt; experiments by several people have shown that polynomial quality is not really improved by searching through X and Y too small, but the rate that hits are found goes way down
3) we tend to determine stage 1 and 2 norms experimentally; start off with the norm quite permissive, then dial it back until hits occur with acceptable frequency. This makes them a moving target, better code and/or hardware allow a smaller bound
4) having two computers search the same range admits a small probability they will duplicate each other's work, but that's usually an acceptable price to avoid having to ensure multiple machines search disjoint ranges

Dubslow · 2013-03-17, 03:41

Please please please do not run -npr on all your -nps hits. It will take ten times as long, and it's likely that the best polys will come out of the top 1% of the -nps hits anyways. If you want to be as thorough as possible, -npr'ing the top 5% would be more than enough.

See page 2 or 3 of the RSA 896 thread to see a recipe for sorting the -nps hits (it's just sorting on the last column, IIRC).

(All wisdom in this post is more or less a repeat of jasonp wisdom found in the afore-mentioned RSA 896 thread.

)

WraithX · 2013-03-17, 04:29

Thank you Jason and Dubslow. I currently have -np1 running, and on a GTX570 on this C210 at 1e8,2e8, stage1_norm=5e29 gives me about 1-20 hits per coeff. Is this a good goal? Or might it be too strict?

Also, I can tell that np1 is running on the video card, but does either nps or npr use the video card?

Dubslow · 2013-03-17, 05:34

Quote:

Originally Posted by WraithX

Also, I can tell that np1 is running on the video card, but does either nps or npr use the video card?

Nope.

As for your speed, I can say that with a 460 on RSA 896, I saw on the order of 10 hits per minute (very rough!). So for the lower difficulty and faster card, you should perhaps be seeing 20-50 hits a minute? (These estimates could be wrong entirely, that thread has more details!)

PhilF · 2013-03-17, 12:34

From the info gathered by a lot of reading, I can't get a clear picture as to whether msieve or pol51* is best for poly selection. Some info seems to indicate that msieve is better up to a certain size number, after that pol51 is probably better.

Is msieve now considered the best poly selection tool?

debrouxl · 2013-03-17, 12:47

Quote:

Is msieve now considered the best poly selection tool?

Yup, msieve is now far better than pol51*

msieve has a Nvidia CUDA implementation of stage 1 of polynomial selection, which is much faster than the CPU implementation. My lower-end laptop GT540M handily beats the sum of all 8 hyperthreads of the accompanying Core i7-2670QM, and a GTX580 does an order of magnitude better yet than a GT540M.
Several months ago, msieve produced in several dozens of minutes (IIRC) a polynomial which beat CPU-days of pol51*. Had I left msieve running for longer, it could have found better polynomials.

Dubslow · 2013-03-17, 21:06

Arguably CADO is better than Msieve -- but (AFAIK) no one knows why.

2013-03-17, 02:49	#48
WraithX Mar 2006 111011111₂ Posts	Okay, I've finally downloaded svn 863 (on my new Linux system) and did "make all CUDA=1 NO_ZLIB=1". It looks like I've finally gotten everything to compile. I'd like to ask for some advice on running the polynomial selection on a C210 (GNFS) that I'll be working on here shortly. Can someone confirm if my following notes are correct for poly select? Code: msieve -v -i worktodo.ini -np1 "stage1_norm=5e33 X,Y" -s <something_unique> (this will create a something_unique.m file) ./msieve -v -i worktodo.ini -nps "stage2_norm=1e100" -s <something_unique> (this looks for something_unique.m and will create something_unique.ms) (the .ms file will end up about 4 times bigger than the .m file) ./msieve -v -i worktodo.ini -npr -s <something_unique> (this looks for something_unique.ms and will create something_unique.p) (the .p file will end up about 250 times bigger than the .ms file) ./msieve -v -i worktodo.ini -npr "stage2_norm=1e100" -s <something_unique> (this looks for something_unique.ms and will create something_unique.p) (the .p file will end up about 250 times bigger than the .ms file) grep alpha *.p \| sort -g -k 7 \| tail (this will list the 10 best poly's found) For -np1: 1) Is there a preferred format for X and Y? ie, Can I do 1.0e8,2.0e8? Or should it be 100000000,200000000? 2) Would it hurt to search smaller X and Y? ie 1 to 1.0e8, or should I start at some large value, like 1e10? 3) Is there a preferred stage1_norm for a C210? 4) Is it better to have two computers searching the same X,Y range, or should I have them work on two different X,Y ranges? For -nps/-npr: 1) Is there a preferred stage2_norm for a C210?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Msieve 1.53 feedback	xilman	Msieve	149	2018-11-12 06:37
Msieve 1.50 feedback	firejuggler	Msieve	99	2013-02-17 11:53
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

2013-02-26, 19:28	#46
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	Are there plans for adding LangerJan's error-handling patch to trunk? (And, to be extra annoying, what about the stuff I put in post 38? yafu uses analyze_one_poly(), by parsing the output file which is a rather ugly kludge )

2013-03-02, 01:01	#47
LangerJan Feb 2013 F₁₆ Posts	You know what would be really great? A configure script! :) I might try writing one, but I can't test it all alone.

2013-03-17, 03:28	#49
jasonp Tribal Bullet Oct 2004 3,541 Posts	1) you have to write out X and Y, floating point will not work 2) searching smaller X and Y will probably hurt; experiments by several people have shown that polynomial quality is not really improved by searching through X and Y too small, but the rate that hits are found goes way down 3) we tend to determine stage 1 and 2 norms experimentally; start off with the norm quite permissive, then dial it back until hits occur with acceptable frequency. This makes them a moving target, better code and/or hardware allow a smaller bound 4) having two computers search the same range admits a small probability they will duplicate each other's work, but that's usually an acceptable price to avoid having to ensure multiple machines search disjoint ranges

2013-03-17, 03:41	#50
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 1C35₁₆ Posts	Please please please do not run -npr on all your -nps hits. It will take ten times as long, and it's likely that the best polys will come out of the top 1% of the -nps hits anyways. If you want to be as thorough as possible, -npr'ing the top 5% would be more than enough. See page 2 or 3 of the RSA 896 thread to see a recipe for sorting the -nps hits (it's just sorting on the last column, IIRC). (All wisdom in this post is more or less a repeat of jasonp wisdom found in the afore-mentioned RSA 896 thread. )

2013-03-17, 04:29	#51
WraithX Mar 2006 479 Posts	Thank you Jason and Dubslow. I currently have -np1 running, and on a GTX570 on this C210 at 1e8,2e8, stage1_norm=5e29 gives me about 1-20 hits per coeff. Is this a good goal? Or might it be too strict? Also, I can tell that np1 is running on the video card, but does either nps or npr use the video card?

2013-03-17, 12:34	#53
PhilF Feb 2005 Colorado 284₁₆ Posts	From the info gathered by a lot of reading, I can't get a clear picture as to whether msieve or pol51* is best for poly selection. Some info seems to indicate that msieve is better up to a certain size number, after that pol51 is probably better. Is msieve now considered the best poly selection tool?

2013-03-17, 21:06	#55
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3×29×83 Posts	Arguably CADO is better than Msieve -- but (AFAIK) no one knows why.