Python Driver for GGNFS and MSIEVE

[jasonp]

That error is very unusual, it means one of the matrix columns had 500 or more entries in it. My guess is that you will need to sieve a little more, the filtering is complaining because it is forced to create an unusably dense matrix.

[VolMike]

Originally Posted by jasonp

That error is very unusual, it means one of the matrix columns had 500 or more entries in it. My guess is that you will need to sieve a little more, the filtering is complaining because it is forced to create an unusably dense matrix.

Thanks! I'll try to sieve little more dependencies.

[Karl M Johnson]

Howdy. I have a quad core Q6600 CPU, so I set the settings in the script:

NUM_CPUS = 1
NUM_THREADS = 4

This works fine for the sieving phase, however, all other phases launch with "-t 1" parameter, and use only one core.I guess it reads NUM_CPUS instead of NUM_THREADS.
A fix, perhaps ?

[Brian Gladman]

Yes, it uses NUM_CPUS for the -t parameter. Here is a revised version.

Brian

[Karl M Johnson]

Works fine now, thanks!

[fivemack]

A Q6600 ought to have NUM_CPUS=4 and NUM_THREADS=1 (an i7 has NUM_CPUS=4 and NUM_THREADS=2); running linear algebra -t8 on an i7 is significantly slower than -t4.

So I think Karl is wrong and his machine actually has NUM_CPUS=4 NUM_THREADS=1 (maybe NUM_CORES and NUM_THREADS_PER_CORE might be better names for them)

[Karl M Johnson]

Well, the naming might be confusing.
I'll run some tests and report the difference between settings.

Ok, here's previous version of script with CPUS=4 and THREADS=1 :

Number: ffd
N = 100023192364023742517184923168889209295796105381780803962304871964052363826693613 (81 digits)
Divisors found:
r1=10001158228759415041770554485354675568677 (pp41)
r2=10001160873187288054865015344344468553769 (pp41)
Version: Msieve v. 1.45
Total time: 0.22 hours.
Factorization parameters were as follows:
n: 100023192364023742517184923168889209295796105381780803962304871964052363826693613
Y0: -17965666793766529855
Y1: 6146235961
c0: -23204711110570516456812
c1: -6479240622121010469
c2: 51026760543472
c3: 362588644
c4: 960
skew: 150054.35 
type: gnfs
name: goose
Factor base limits: 350000/500000
Large primes per side: 3
Large prime bits: 24/24
Sieved algebraic special-q in [0, 0)
Total raw relations: 970405
Relations: 42998 relations
Pruned matrix : 31977 x 32205
Polynomial selection time: 0.00 hours.
Total sieving time: 0.22 hours.
Total relation processing time: 0.00 hours.
Matrix solve time: 0.00 hours.
time per square root: 0.00 hours.
Prototype def-par.txt line would be: gnfs,80,4,52,1500,0.005,0.3,220,15,10000,400,350000,500000,24,24,37,37,1.7,1.7,10000
total time: 0.22 hours.
Intel64 Family 6 Model 15 Stepping 11, GenuineIntel
Windows-post2008Server-6.1.7600
processors: 4, speed: 3.51GHz

Here's the latest script with CPUS=1 and THREADS=4 :

Number: ffd
N = 100023192364023742517184923168889209295796105381780803962304871964052363826693613 (81 digits)
Divisors found:
r1=10001158228759415041770554485354675568677 (pp41)
r2=10001160873187288054865015344344468553769 (pp41)
Version: Msieve v. 1.45
Total time: 0.09 hours.
Factorization parameters were as follows:
n: 100023192364023742517184923168889209295796105381780803962304871964052363826693613
Y0: -17965666793766529855
Y1: 6146235961
c0: -23204711110570516456812
c1: -6479240622121010469
c2: 51026760543472
c3: 362588644
c4: 960
skew: 150054.35 
type: gnfs
name: goose
Factor base limits: 350000/500000
Large primes per side: 3
Large prime bits: 24/24
Sieved algebraic special-q in [0, 0)
Total raw relations: 970404
Relations: 42862 relations
Pruned matrix : 31978 x 32207
Polynomial selection time: 0.00 hours.
Total sieving time: 0.08 hours.
Total relation processing time: 0.01 hours.
Matrix solve time: 0.00 hours.
time per square root: 0.00 hours.
Prototype def-par.txt line would be: gnfs,80,4,52,1500,0.005,0.3,220,15,10000,400,350000,500000,24,24,37,37,1.7,1.7,10000
total time: 0.09 hours.
Intel64 Family 6 Model 15 Stepping 11, GenuineIntel
Windows-post2008Server-6.1.7600
processors: 4, speed: 3.51GHz

I'll stick to 1 CPU with 4 threads.

[Brian Gladman]

Originally Posted by fivemack

A Q6600 ought to have NUM_CPUS=4 and NUM_THREADS=1 (an i7 has NUM_CPUS=4 and NUM_THREADS=2); running linear algebra -t8 on an i7 is significantly slower than -t4.

So I think Karl is wrong and his machine actually has NUM_CPUS=4 NUM_THREADS=1 (maybe NUM_CORES and NUM_THREADS_PER_CORE might be better names for them)

Hi Fivemack,

In my view we have to worry about how NUM_CPUS and NUM_THREADS are used by the scripts since this is what determines their meaning.

In the old scripts (both Perl and Python) the siever uses NUM_THREADS but all the msieve calls use NUM_CPUS for the '-t' parameter. Morover this is the only use of NUM_CPUS in the scripts.

Jason may have to correct this, but I am guessing that he uses the '-t' parameter to launch a number of Windows software threads and relies on the Windows process scheduler to map these threads onto physical cores and physical threads provided by the hardware. So if NUM_CPUS is set to 1, only one thread will be lauched and only one hardware core will be used.

If I am right about this, the use of NUM_CPUS in the scripts as the msieve '-t' parameter is wrong since it should be at least NUM_THREADS or even, possibly, NUM_CPUS * NUM_THREADS - the number of software threads that msieve should launch.

In the latest Python script I have used NUM_THREADS for the msieve '-t' parameter and this means that the Python script now depends only on NUM_THREADS since NUM_CPUS is no longer used anywhere in the script (other than for setting NUM_THREADS).

Of course, I could be wrong, but if I am right the two variables in the old script woulld be better named SIEVER_THREADS and MSIEVE_THREADS. Keeping them as distinct variables (whiich the new version dooesn't do) might well be sensible as this would allow people to shoose whether to try 'cores only' or 'cores with hyperthreads' for both sieving and msieve processing separately.

For my part I am happy to do what people think makes most sense in the Python script. But I don't think it makes much sense in the old script to set NUM_CPUS to 1 on multicore processors since this limits msieve to one thread only running on one core as Karl discovered.

Brian

[jasonp]

Brian,

You're correct, currently -t is only used to calculate the number of threads that msieve should fire off when conducting the linear algebra (QS or NFS, but QS matrices never get big enough that it is a win to multithread them). Msieve does not attempt to set any type of CPU affinity for those threads.

On the off chance that other portions of the library become multithreaded someday, i.e. like polynomial selection, maybe you should use LA_THREADS instead of MSIEVE_THREADS.

[Brian Gladman]

Originally Posted by jasonp

Brian,

You're correct, currently -t is only used to calculate the number of threads that msieve should fire off when conducting the linear algebra (QS or NFS, but QS matrices never get big enough that it is a win to multithread them). Msieve does not attempt to set any type of CPU affinity for those threads.

On the off chance that other portions of the library become multithreaded someday, i.e. like polynomial selection, maybe you should use LA_THREADS instead of MSIEVE_THREADS.

Thanks for confirming my suspicions Jason.

I have now added two variables, SV_THREADS and LA_THREADS, to control siever and linear algebra threading respectively.

I have also added some names with NUM_CPUS changed to NUM_CORES and a new THREADS_PER_CORE variable.

The new version is here:

http://gladman.plushost.co.uk/oldsit...ieve.py.74.zip

I have not uploaded it here because I worry that my frequent postings of these updates as attachments might be unwelcome from the site owner's perspective as there is no obvious way to delete the outdated ones.

Brian

[Karl M Johnson]

Cant launch

Traceback (most recent call last):
  File "C:\Program Files (x86)\msieve\ggnfs\example\factmsieve[N].py", line 1984, in <module>
    .format(NUM_CORES, ('' if NUM_CORES == 1 else 's'), THREADS_PER_CORE))
ValueError: unmatched '{' in format