Best way to scale polynomial selection

pastcow · 2013-04-28, 07:56

If I want to scale polynomial selection (over multiple cores / computers) is the best way to have each CPU check a different range of coefficients (like below):

./msieve -v -s test1 -l test1 -nf test1 -np "min_coeff=0 max_coeff=1000" -m 18482358805813848044952912904056328155022481776091991120664052047908519720614998988214854943918675611393700936203073

Currently I'm doing it this way and it seems to work, is there a better way I should be doing it?

Thanks :)

P.

fivemack · 2013-04-28, 09:03

That's how I do it, though it's worth remembering that small leading-coefficients complete much more slowly than large ones (it's about proportional to 1/sqrt(C5), but not precisely). I never managed to split it up statically in a way I was happy with, so I tend to use a makefile distributing lots of 1k ranges to the set of available cores.

xilman · 2013-04-28, 11:56

Quote:

Originally Posted by fivemack

That's how I do it, though it's worth remembering that small leading-coefficients complete much more slowly than large ones (it's about proportional to 1/sqrt(C5), but not precisely). I never managed to split it up statically in a way I was happy with, so I tend to use a makefile distributing lots of 1k ranges to the set of available cores.

As a side effect of investigation cado-nfs I discovered that their polynomial selection is rather good in that it generates high quality results quickly and naturally over multiple cores and multiple hosts. Their siever and LA aren't yet competitive with msieve so I've used cado-nfs for polynomial selection and msieve for the rest.

debrouxl · 2013-04-28, 13:30

There's a patch for MPI polynomial selection with msieve

pastcow · 2013-05-07, 10:58

Thanks for the replies :) they've been a great help.

I'm now trying to scale ggnfs sieving up - I've noticed that factmsieve.py starts sieving at q=13550000 e.g. the output shows

making sieve job for q = 13550000 in 13550000 .. 13562500 as file ./outputf.m.job.T0

Is there any particular reason for this? wouldn't it be just as good to start at q = 0? or is this an effort to get each block to process in a similar time frame?

Thanks

P.

debrouxl · 2013-05-07, 20:37

Did you get around to polishing the scripts you mentioned at http://www.mersenneforum.org/showthread.php?t=17847 ? Or maybe this is still part of the feature / polishing work

Starting at overly low q values tends to produce higher duplicate rates, which will be filtered later anyway. Therefore, "low" q values are not much (if at all) more productive than higher q values.

pastcow · 2013-05-08, 09:01

I sure did :) I got distracted by another project for a while but i'm now back working on it - I've built a light weight standalone python + sqlite3 job server and a client that can be started on Amazon EC2 spot instances.

Polynomial selection is working pretty well - for a recent C155 I found a polynomial with a score of 3.212e-12 in < 1 hr (If anyone needs help finding a good polynomial quickly let me know)

I'm going to work on the sieving distribution this weekend - now the server + client is written it shouldn't require too much work to finish off. Once I'm happy with it i'll make the code and a fully configured Amazon AMI available.

One of the issues I've had is getting ggnfs to compile properly on 64 bit linux. I've ended up using some pre-compiled binaries I found online - I could get it to compile but it just kept giving me a Error -11 when it was doing some of the sieving :S

2013-04-28, 07:56	#1
pastcow Feb 2013 111₂ Posts	Best way to scale polynomial selection If I want to scale polynomial selection (over multiple cores / computers) is the best way to have each CPU check a different range of coefficients (like below): ./msieve -v -s test1 -l test1 -nf test1 -np "min_coeff=0 max_coeff=1000" -m 18482358805813848044952912904056328155022481776091991120664052047908519720614998988214854943918675611393700936203073 Currently I'm doing it this way and it seems to work, is there a better way I should be doing it? Thanks :) P.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial selection	Max0526	NFS@Home	9	2017-05-20 08:57
msieve 1.52 with GPU polynomial selection	cgy606	Msieve	16	2016-10-06 14:16
SNFS Polynomial selection help?	mhill12	Factoring	59	2013-09-09 22:40
2^877-1 polynomial selection	fivemack	Factoring	47	2009-06-16 00:24
Polynomial selection	CRGreathouse	Factoring	2	2009-05-25 07:55

2013-04-28, 09:03	#2
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 14356₈ Posts	That's how I do it, though it's worth remembering that small leading-coefficients complete much more slowly than large ones (it's about proportional to 1/sqrt(C5), but not precisely). I never managed to split it up statically in a way I was happy with, so I tend to use a makefile distributing lots of 1k ranges to the set of available cores.

2013-04-28, 13:30	#4
debrouxl Sep 2009 977 Posts	There's a patch for MPI polynomial selection with msieve

2013-05-07, 10:58	#5
pastcow Feb 2013 7 Posts	Thanks for the replies :) they've been a great help. I'm now trying to scale ggnfs sieving up - I've noticed that factmsieve.py starts sieving at q=13550000 e.g. the output shows making sieve job for q = 13550000 in 13550000 .. 13562500 as file ./outputf.m.job.T0 Is there any particular reason for this? wouldn't it be just as good to start at q = 0? or is this an effort to get each block to process in a similar time frame? Thanks P.

2013-05-07, 20:37	#6
debrouxl Sep 2009 1111010001₂ Posts	Did you get around to polishing the scripts you mentioned at http://www.mersenneforum.org/showthread.php?t=17847 ? Or maybe this is still part of the feature / polishing work Starting at overly low q values tends to produce higher duplicate rates, which will be filtered later anyway. Therefore, "low" q values are not much (if at all) more productive than higher q values.

2013-05-08, 09:01	#7
pastcow Feb 2013 111₂ Posts	I sure did :) I got distracted by another project for a while but i'm now back working on it - I've built a light weight standalone python + sqlite3 job server and a client that can be started on Amazon EC2 spot instances. Polynomial selection is working pretty well - for a recent C155 I found a polynomial with a score of 3.212e-12 in < 1 hr (If anyone needs help finding a good polynomial quickly let me know) I'm going to work on the sieving distribution this weekend - now the server + client is written it shouldn't require too much work to finish off. Once I'm happy with it i'll make the code and a fully configured Amazon AMI available. One of the issues I've had is getting ggnfs to compile properly on 64 bit linux. I've ended up using some pre-compiled binaries I found online - I could get it to compile but it just kept giving me a Error -11 when it was doing some of the sieving :S