mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2011-01-25, 21:11   #1
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

CAE16 Posts
Default QS/NFS crossover points

I finally got cado-nfs-1.0 built for x86_64 linux, and decided to run some experiments to determine the crossover points for switching between QS and NFS using different software packages. Posting the results here in case anyone else is interested.

QS packages tested:
* msieve-1.48
* yafu-1.23

NFS packages tested:
* factMsieve.pl (msieve-1.48 poly/postproc, ggnfs sieving)
* yafu-nfs (msieve-1.48 poly/postproc, ggnfs sieving)
* cado-nfs-1.0

build/test environment:
Code:
% uname -r
2.6.18-128.4.1.el5

% gcc -v
Using built-in specs.
Target: x86_64-redhat-linux
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --enable-checking=release --with-system-zlib --enable-__cxa_atexit --disable-libunwind-exceptions --enable-libgcj-multifile --enable-languages=c,c++,objc,obj-c++,java,fortran,ada --enable-java-awt=gtk --disable-dssi --enable-plugin --with-java-home=/usr/lib/jvm/java-1.4.2-gcj-1.4.2.0/jre --with-cpu=generic --host=x86_64-redhat-linux
Thread model: posix
gcc version 4.1.2 20080704 (Red Hat 4.1.2-44)

% cat /proc/cpuinfo
<snip>
vendor_id       : GenuineIntel
cpu family      : 6
model           : 23
model name      : Intel(R) Xeon(R) CPU           X5460  @ 3.16GHz
stepping        : 6
cpu MHz         : 3166.000
<snip>
Results:
Attached Thumbnails
Click image for larger version

Name:	bench_and_xover.jpg
Views:	1367
Size:	178.8 KB
ID:	6126  
bsquared is offline   Reply With Quote
Old 2011-01-25, 21:33   #2
bchaffin
 
Sep 2010
Portland, OR

32×41 Posts
Default

Nice work Ben, this is great data. Two things stand out to me:

1) YAFU's QS is really, really fast at the low end -- more than 2x faster than any other. Wow.

2) YAFU-NFS is slightly but consistently slower than factMsieve. I haven't looked at your new NFS code yet but I would have expected it to be doing basically the same thing as factMsieve -- any idea what causes that difference?
bchaffin is offline   Reply With Quote
Old 2011-01-25, 21:41   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1100101011102 Posts
Default

Quote:
Originally Posted by bchaffin View Post
Nice work Ben, this is great data. Two things stand out to me:

1) YAFU's QS is really, really fast at the low end -- more than 2x faster than any other. Wow.

2) YAFU-NFS is slightly but consistently slower than factMsieve. I haven't looked at your new NFS code yet but I would have expected it to be doing basically the same thing as factMsieve -- any idea what causes that difference?
Thanks!

The major difference between factMsieve and yafu-nfs is that factMsieve implements a minimum relations threshold whereas yafu-nfs doesn't. factMsieve waits until approximately enough relations have been collected before first calling msieve for postprocessing, so filtering is performed quite a few less times compared to yafu-nfs.

That's one source of the difference that I can easily fix. There might also be differences in the job parameters used. I haven't compared that yet.
bsquared is offline   Reply With Quote
Old 2011-01-25, 21:54   #4
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·3·541 Posts
Default

Perhaps also of interest is the polynomial score achieved with the two different NFS packages. Unfortunately I didn't keep the time needed in polyselect for the cado jobs. Cado polyselect definitely didn't take as long.
Attached Thumbnails
Click image for larger version

Name:	poly_compare.jpg
Views:	442
Size:	59.8 KB
ID:	6128  
bsquared is offline   Reply With Quote
Old 2015-05-12, 14:07   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

62568 Posts
Default crossover data

This topic came up recently and I've been meaning to update this comparison from several years ago anyway.

QS packages tested:
* msieve-1.53
* yafu-1.34.5

NFS packages tested:
* factmsieve.py (msieve-1.53 poly/postproc, ggnfs sieving)
* yafu-nfs (msieve-1.53 poly/postproc, ggnfs sieving)
* cado-nfs-2.1.1

build/test environment:
Code:
% uname -r
2.6.32-358.6.2.el6.x86_64

% gcc -v
gcc version 4.4.7 20120313 (Red Hat 4.4.7-3) (GCC)

% cat /proc/cpuinfo
vendor_id       : GenuineIntel
cpu family      : 6
model           : 45
model name      : Intel(R) Xeon(R) CPU E5-2687W 0 @ 3.10GHz
stepping        : 7
cpu MHz         : 3099.837
cache size      : 20480 KB
When I get time I will try out the git version of Cado-NFS. Paul Z. has indicated it might have improved parameter selection for these smaller inputs. (Note: don't extrapolate performance here to performance at large digit sizes).

Also, I need to update yafu to use the superblocksize parameter of msieve for LA. It is lots faster for this cpu (factmsieve uses it, yafu currently does not).

Looks like the QS/NFS crossover ranges from 86 digits to 100+ digits, depending on your choice of tools. Using yafu for both it is about 93 digits on this CPU.
Attached Thumbnails
Click image for larger version

Name:	crossover_data.PNG
Views:	539
Size:	106.9 KB
ID:	12608  
bsquared is offline   Reply With Quote
Old 2015-05-12, 15:09   #6
axn
 
axn's Avatar
 
Jun 2003

459110 Posts
Default

Random observations:
* CADO-NFS Murphy-E and msieve Murphy-E are not comparable (IIRC). Have you normalized the score by computing the Murphy-E using the same tool for all polys?
* Time spent in poly selection is just way too much in this range. Even the CADO-NFS ones, which is the more frugal of the lot. Honestly, just search only the leading coefficients 6-120, and you should be good to go.
* There is a _big_ difference in LA time between yafu-nfs and factmsieve. Since both are using msieve, that indicates that yafu's job parameters are on the high side, generating much more relations?
* Did you use the liux64 sievers (or, if on Windows, did you use the ones which are as fast as the linux ones?)
* If everything is carefully tuned (including poly select), the msieve+GGNFS route probably will have crossover at or below 90 digits.
axn is offline   Reply With Quote
Old 2015-05-12, 15:35   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×3×541 Posts
Default

Quote:
Originally Posted by axn View Post
Random observations:


* CADO-NFS Murphy-E and msieve Murphy-E are not comparable (IIRC). Have you normalized the score by computing the Murphy-E using the same tool for all polys?
No, forgot that fact. And I can't seem to find a log file of any kind so the poly's CADO used are lost as far as I can see. If I test the git version I will try to capture them and re-compute their score with msieve.

Quote:
Originally Posted by axn View Post
* Time spent in poly selection is just way too much in this range. Even the CADO-NFS ones, which is the more frugal of the lot. Honestly, just search only the leading coefficients 6-120, and you should be good to go.
Just capturing the current behavior of the tools. For the yafu and factmsieve tools, the best leading coefficients were found at:

Code:
digit size    best leading coefficient
85              60
90              1980
95              180
100            1680
I don't know how much these "best" ones improved on the best one found in your proposed range.

Quote:
Originally Posted by axn View Post
* There is a _big_ difference in LA time between yafu-nfs and factmsieve. Since both are using msieve, that indicates that yafu's job parameters are on the high side, generating much more relations?
No, the parameters were the same. The difference is due to the use of superblocksizes. factmsieve uses them, yafu doesn't (it requires a command line option to specify the superblocksize). Apparently the 20 MB L3 cache in this CPU helps a bunch.


Quote:
Originally Posted by axn View Post
* Did you use the liux64 sievers (or, if on Windows, did you use the ones which are as fast as the linux ones?)
Yes, 64 bit linux sievers.

Quote:
Originally Posted by axn View Post
* If everything is carefully tuned (including poly select), the msieve+GGNFS route probably will have crossover at or below 90 digits.
Maybe... but seems unlikely. Here is the raw data:

Code:
	          total time			
	           digit size			
tool                85           90         95        100
yafu-qs             386          1473     4082     8809
msieve-qs           873          2454     7184     17236
yafu-nfs            1054        1973     4215     6787
cado-nfs            1271        2283    5659     11066.2
factmsieve.py       1080        2160    3600     6929
Subtracting a few hundred seconds from poly time (likely increasing sieving time some amount) would not bring NFS times down that far. But it is kinda splitting hairs - use your personal preference anywhere between 90-95 digits and you will be pretty close to optimal.
bsquared is offline   Reply With Quote
Old 2015-05-14, 18:31   #8
chris2be8
 
chris2be8's Avatar
 
Sep 2009

2·17·53 Posts
Default

I've found a crossover berween yafu's QS and gnfs at about 90 digits when using my GPU for msieve polynomial selection and the 64 bit Linux sievers.

Chris
chris2be8 is offline   Reply With Quote
Old 2016-01-20, 16:05   #9
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

62568 Posts
Default

Time for another update: Paul Z. asked me to check out CADO-2.2.0

QS packages tested:
* yafu (1.34.5)

NFS packages tested:
* yafu-nfs (yafu-1.34.5/msieve-svn-991/ggnfs-asm64)
* cado-nfs-2.2.0

Run on a Xeon Haswell system (linux); all tests single threaded.

Here is the total time data:

Code:
input digits	yafu-1.34.5 qs	yafu-1.34.5/msieve-svn-991/ggnfs-asm64	cado-nfs-2.2.0
60	           2.2		                                                44.42
65	           6.6		                                                64.24
70	           13.8		                                                112.65
75	           50.8		                                                256.5
80	           104.3	                                                470
85	           276	                 747.7	                                738
90	           1077	                 1488	                                1457
95	           3069	                 3390	                                3306
100	           6689	                 5377	                                6431
105	           22155	         10743	                                12986
110		                         21773	                                27662
Generally, CADO poly select is faster while yafu/msieve/ggnfs has faster sieving/LA. CADO has good parameter selection down to at least c60 (it does feel weird running NFS on a c60). Between the NFS implementations, CADO wins up to 100 digits. The QS/NFS crossover is about 96-97 digits in both cases.
Attached Thumbnails
Click image for larger version

Name:	Screen Shot 01-20-16 at 09.58 AM.PNG
Views:	392
Size:	33.8 KB
ID:	13748  
bsquared is offline   Reply With Quote
Old 2016-01-21, 02:12   #10
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

23·11·97 Posts
Default

Are you sure the 22k for SIQS C105 is the right one? It seems that 12k-15k or (max) 18k should be more correct one. Some systems have crossovers over 105 digits.

If indeed the 22k is the correct one, then why? What the explanation can be?

Did you run single/few composite tests or you tested a bunch of them for each size?
LaurV is online now   Reply With Quote
Old 2016-01-21, 02:50   #11
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×3×541 Posts
Default

That's the correct time, yes. It fits well on the trendline, and fits compared to the few previous times (roughly factor 3 increase for each 5 digits). I just ran one number... running several c105 would provide a better estimate of performance, sure, but I'm lazy.

Single-threaded c105 by QS in 6 hours doesn't seem too bad to me...
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
29 to 30 bit large prime SNFS crossover VBCurtis Factoring 11 2015-03-09 07:01
32/33 and 15e/16e crossover point fivemack Factoring 7 2009-04-21 07:59
More points for PRP? Mystwalker Prime Sierpinski Project 6 2006-01-03 23:32
any body play with the soft fft crossover yes? crash893 Software 9 2002-09-18 20:45
Can I move an exponent near a FFT crossover to my P III? svempasnake Software 2 2002-09-09 21:32

All times are UTC. The time now is 13:56.

Fri May 29 13:56:47 UTC 2020 up 65 days, 11:29, 1 user, load averages: 2.25, 2.36, 2.40

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.