Msieve v1.46 feedback

em99010pepe · 2010-07-31, 19:37

jasonp,

I have a stupid question, will msieve scale better on one socket quad machines?

jasonp · 2010-07-31, 19:45

Multithreading has been added to the vector-vector operations, so you should see a 5-10% speedup when using multiple threads, even without using MPI. Compiling with MPI and running on only one CPU adds a little overhead, it seems to be about 10% slower in Greg's tests.

em99010pepe · 2010-07-31, 19:48

Another thing I don't understand is the following. When I use LA for a 29 bits integer on a quad-core machine I don't have peaks of 99 % of CPU usage, instead I have ~85 %, but when I use LA for 31 bits integers I get peaks of 99 % on CPU usage. I get this behave of different quad-machines with different OS (Win XP 64 bits and Win 7), different clock speed, different type of memory (one DDR2 and the other DDR3).

Thank you in advance.

em99010pepe · 2010-07-31, 19:52

Quote:

Originally Posted by jasonp

Multithreading has been added to the vector-vector operations, so you should see a 5-10% speedup when using multiple threads, even without using MPI. Compiling with MPI and running on only one CPU adds a little overhead, it seems to be about 10% slower in Greg's tests.

I see...On quad-core I should run the new version without using MPI.

Greg, could you post here your benches?

jasonp · 2010-07-31, 20:02

My guess is that matrices from factorizations that use 29-bit large primes are not that large, all things considered, so with large enough caches on your machine the bottleneck would be in the cache controller trying to statisfy four hungry threads at the same time. Matrices derived from 31-bit large primes are going to have dimension 2-3x larger, and this would mean much more pressure on the DRAM controller, so multiple threads can keep up with the load in that case.

I should also mention that you can try compiling with LARGEBLOCKS=1; this turns on some optimizations due to Serge Batalov, that increase the memory use but make the LA a great deal faster (he reports 25% faster for large problems).

em99010pepe · 2010-08-01, 08:44

Quote:

Originally Posted by jasonp

I should also mention that you can try compiling with LARGEBLOCKS=1; this turns on some optimizations due to Serge Batalov, that increase the memory use but make the LA a great deal faster (he reports 25% faster for large problems).

Large problems, what matrices size?
Thank you.

jasonp · 2010-08-01, 13:55

The changes definitely help for NFS@home size matrices, and possibly for matrices smaller than that. Serge can provide more detail.

Batalov · 2010-08-01, 19:44

LARGEBLOCKS=1 needs testing (two runs with a standard and the experimental binary, comparison, repeat...). I didn't try it on small matrices, but it had been used on very large ones with good results. Note that L2/L3 cache size will matter; some CPUs will do better than others (I only tested K8/K10 AMD CPUs).

Similarly to increased TARGET_DENSITY, this patch may be not helping small projects. (see Tom's results for a smaller project)
_____________

The ZLIB patch is another thing that needs testing. I have tested it extensively in different scenarios and straigthened some wrinkles. In a nutshell, the .dat file can be now gzipped... or plain. Right now, for most users, there will be no perceptible difference (if the .dat file is plain, msieve reads and appends to it plainly), but adventurous users may want to modify the perl and python scripts to create and maintain a gzipped data file (when it is first created, with a single "N ...." line in it, gzip it; then lasieve with the option -z, and concatenate the gzipped relations >> test.dat.gz; msieve will read and will append gzipped free relations). When using msieve in QS mode, curious users will find that the .dat file is internally gzipped as well (I've tested that QS can be interrupted and continued; QS that was previously sieved with earlier msieve can be continued as well - the file will remain plain).

Some platforms don't have ZLIB. For these (or if you simply don't want this feature), use NO_ZLIB=1 when using Makefile.

debrouxl · 2010-08-02, 08:38

I think that you already have access to all you need in the way of large datasets - but should you need the RSALS datasets for experimenting with LARGEBLOCKS=1, we'll be happy to provide them

What about adding a switch to msieve for setting the value of TARGET_DENSITY at run-time, rejecting values outside of an area of sane values ? There are only two occurrences of TARGET_DENSITY in msieve, its definition and its use, both in common/filter/merge.c.

Batalov · 2010-08-02, 09:19

I think command-line can easily be filled with tons of parameters, but .fb (msieve doesn't read the .poly file, you know) may be a better place. TARGET_DENSITY could go there, and some other tunable parameters, e.g. MAX_IDEALS_WEIGHT_START 40 (which is another frequently tweaked parameter*). Jasonp will be a better person to decide.

______
*for computers with enough memory this defaults to 200 when filtering is done in memory; but when it doesn't fit, (old style) the program loops this value from 20 in steps of 5 with occasional "matrix can improve, retrying". With a good hunch, one can start from a value they like, e.g. 40 or 45; as of now, this requires recompilation.

jasonp · 2010-08-02, 12:42

The FB file is a good place to put extra options, although if you use msieve for sieving then the FB file will be huge. Right now modifiers to the command line options are handled in a pretty silly way, there is a nfs_lower and nfs_upper field which allows all NFS-related command line options to share two 64-bit numerical options. A much better idea would be to give each of the NFS phases a string that contains phase-specific options, and let each phase parse its own options. This would allow things like

Code:

msieve -np1 "-degree 5 -coeff_min 1000 -coeff_max 10000" -np2 "-target_evalue 8e-7"

with sensible defaults chosen for everything. Doing things this way would make msieve.exe act like a wrapper around a group of different binaries that are standalone projects in other NFS suites, much like openssl.exe wraps 50 different programs into one blob. I was reluctant to add all the bells and whistles that control NFS filtering, because the experience here shows that it's very easy to choose parameters that make the result 5% better but chew up 10x as much memory. But many people here also have their own custom msieve binaries with the bells and whistles changed, so that's an academic concern.

2010-07-31, 19:37	#1
em99010pepe Sep 2004 2830₁₀ Posts	Msieve v1.46 feedback jasonp, I have a stupid question, will msieve scale better on one socket quad machines?

2010-08-01, 19:44	#8
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22405₈ Posts	a few words about LARGEBLOCKS and ZLIB LARGEBLOCKS=1 needs testing (two runs with a standard and the experimental binary, comparison, repeat...). I didn't try it on small matrices, but it had been used on very large ones with good results. Note that L2/L3 cache size will matter; some CPUs will do better than others (I only tested K8/K10 AMD CPUs). Similarly to increased TARGET_DENSITY, this patch may be not helping small projects. (see Tom's results for a smaller project) _____________ The ZLIB patch is another thing that needs testing. I have tested it extensively in different scenarios and straigthened some wrinkles. In a nutshell, the .dat file can be now gzipped... or plain. Right now, for most users, there will be no perceptible difference (if the .dat file is plain, msieve reads and appends to it plainly), but adventurous users may want to modify the perl and python scripts to create and maintain a gzipped data file (when it is first created, with a single "N ...." line in it, gzip it; then lasieve with the option -z, and concatenate the gzipped relations >> test.dat.gz; msieve will read and will append gzipped free relations). When using msieve in QS mode, curious users will find that the .dat file is internally gzipped as well (I've tested that QS can be interrupted and continued; QS that was previously sieved with earlier msieve can be continued as well - the file will remain plain). Some platforms don't have ZLIB. For these (or if you simply don't want this feature), use NO_ZLIB=1 when using Makefile.

2010-08-02, 12:42	#11
jasonp Tribal Bullet Oct 2004 3541₁₀ Posts	The FB file is a good place to put extra options, although if you use msieve for sieving then the FB file will be huge. Right now modifiers to the command line options are handled in a pretty silly way, there is a nfs_lower and nfs_upper field which allows all NFS-related command line options to share two 64-bit numerical options. A much better idea would be to give each of the NFS phases a string that contains phase-specific options, and let each phase parse its own options. This would allow things like Code: msieve -np1 "-degree 5 -coeff_min 1000 -coeff_max 10000" -np2 "-target_evalue 8e-7" with sensible defaults chosen for everything. Doing things this way would make msieve.exe act like a wrapper around a group of different binaries that are standalone projects in other NFS suites, much like openssl.exe wraps 50 different programs into one blob. I was reluctant to add all the bells and whistles that control NFS filtering, because the experience here shows that it's very easy to choose parameters that make the result 5% better but chew up 10x as much memory. But many people here also have their own custom msieve binaries with the bells and whistles changed, so that's an academic concern.

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

2010-07-31, 19:45	#2
jasonp Tribal Bullet Oct 2004 3,541 Posts	Multithreading has been added to the vector-vector operations, so you should see a 5-10% speedup when using multiple threads, even without using MPI. Compiling with MPI and running on only one CPU adds a little overhead, it seems to be about 10% slower in Greg's tests.

2010-07-31, 19:48	#3
em99010pepe Sep 2004 2×5×283 Posts	Another thing I don't understand is the following. When I use LA for a 29 bits integer on a quad-core machine I don't have peaks of 99 % of CPU usage, instead I have ~85 %, but when I use LA for 31 bits integers I get peaks of 99 % on CPU usage. I get this behave of different quad-machines with different OS (Win XP 64 bits and Win 7), different clock speed, different type of memory (one DDR2 and the other DDR3). Thank you in advance.

2010-07-31, 20:02	#5
jasonp Tribal Bullet Oct 2004 3,541 Posts	My guess is that matrices from factorizations that use 29-bit large primes are not that large, all things considered, so with large enough caches on your machine the bottleneck would be in the cache controller trying to statisfy four hungry threads at the same time. Matrices derived from 31-bit large primes are going to have dimension 2-3x larger, and this would mean much more pressure on the DRAM controller, so multiple threads can keep up with the load in that case. I should also mention that you can try compiling with LARGEBLOCKS=1; this turns on some optimizations due to Serge Batalov, that increase the memory use but make the LA a great deal faster (he reports 25% faster for large problems).

2010-08-01, 13:55	#7
jasonp Tribal Bullet Oct 2004 3,541 Posts	The changes definitely help for NFS@home size matrices, and possibly for matrices smaller than that. Serge can provide more detail.

2010-08-02, 08:38	#9
debrouxl Sep 2009 977 Posts	I think that you already have access to all you need in the way of large datasets - but should you need the RSALS datasets for experimenting with LARGEBLOCKS=1, we'll be happy to provide them What about adding a switch to msieve for setting the value of TARGET_DENSITY at run-time, rejecting values outside of an area of sane values ? There are only two occurrences of TARGET_DENSITY in msieve, its definition and its use, both in common/filter/merge.c.

2010-08-02, 09:19	#10
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9477₁₀ Posts	I think command-line can easily be filled with tons of parameters, but .fb (msieve doesn't read the .poly file, you know) may be a better place. TARGET_DENSITY could go there, and some other tunable parameters, e.g. MAX_IDEALS_WEIGHT_START 40 (which is another frequently tweaked parameter). Jasonp will be a better person to decide. ______ for computers with enough memory this defaults to 200 when filtering is done in memory; but when it doesn't fit, (old style) the program loops this value from 20 in steps of 5 with occasional "matrix can improve, retrying". With a good hunch, one can start from a value they like, e.g. 40 or 45; as of now, this requires recompilation.