mersenneforum.org QS/NFS crossover points
 Register FAQ Search Today's Posts Mark Forums Read

 2011-01-25, 21:11 #1 bsquared     "Ben" Feb 2007 7·11·47 Posts 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 vendor_id : GenuineIntel cpu family : 6 model : 23 model name : Intel(R) Xeon(R) CPU X5460 @ 3.16GHz stepping : 6 cpu MHz : 3166.000  Results: Attached Thumbnails
 2011-01-25, 21:33 #2 bchaffin   Sep 2010 Portland, OR 22×3×31 Posts 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?
2011-01-25, 21:41   #3
bsquared

"Ben"
Feb 2007

7·11·47 Posts

Quote:
 Originally Posted by bchaffin 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.

 2011-01-25, 21:54 #4 bsquared     "Ben" Feb 2007 70438 Posts 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
 2015-05-12, 14:07 #5 bsquared     "Ben" Feb 2007 7·11·47 Posts 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
 2015-05-12, 15:09 #6 axn     Jun 2003 28·3·7 Posts 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.
2015-05-12, 15:35   #7
bsquared

"Ben"
Feb 2007

1110001000112 Posts

Quote:
 Originally Posted by axn 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 * 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 * 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 * 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 * 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
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.

 2015-05-14, 18:31 #8 chris2be8     Sep 2009 22·587 Posts 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
 2016-01-20, 16:05 #9 bsquared     "Ben" Feb 2007 7×11×47 Posts 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
 2016-01-21, 02:12 #10 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 9,973 Posts 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?
 2016-01-21, 02:50 #11 bsquared     "Ben" Feb 2007 7·11·47 Posts 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...

 Similar Threads Thread Thread Starter Forum Replies Last Post VBCurtis Factoring 11 2015-03-09 07:01 fivemack Factoring 7 2009-04-21 07:59 Mystwalker Prime Sierpinski Project 6 2006-01-03 23:32 crash893 Software 9 2002-09-18 20:45 svempasnake Software 2 2002-09-09 21:32

All times are UTC. The time now is 15:18.

Wed Jun 29 15:18:50 UTC 2022 up 76 days, 13:20, 2 users, load averages: 1.45, 1.49, 1.44