Multithreaded QS/NFS sieve stage

[nuggetprime]

Is it possible to run the qs/nfs sieve process multithreaded with the current version of msieve?
when i run a qs job with -t 4, it uses only one of my 4 cores for sieving.
Regards,
nugget

[jasonp]

Afraid not; msieve only uses multiple threads for the linear algebra, and then only if the matrix is larger than anything the QS part can produce. I've always assumed that if you wanted more than one sieving process that you'd just run the msieve binary more than once (with relations going to a different data file each time).

[nuggetprime]

Thanks for the fast reply

--nugget

[henryzz]

Originally Posted by jasonp

Afraid not; msieve only uses multiple threads for the linear algebra, and then only if the matrix is larger than anything the QS part can produce. I've always assumed that if you wanted more than one sieving process that you'd just run the msieve binary more than once (with relations going to a different data file each time).

i have always wondered why it does that
are there any disadvantages to it or is it hard to implement

[jasonp]

Originally Posted by henryzz

i have always wondered why it does that
are there any disadvantages to it or is it hard to implement

For the linear algebra, the lower limit on the size of the matrix is around 250k rows; even with one thread this completes in less than 10 minutes on a modern machine.

As for why sieving isn't multithreaded, that's because sieving parallelizes trivially but the machinery for writing multithreaded programs may not be trivial. If you want several threads to sieve, you have to go through all the data structures and figure out which ones can be shared, which ones need to be copied and how the threads will interact with each other. If they don't interact with each other, whoever spawns them is itself a thread so there is still some thread interactions to deal with. For very large problems that need huge factor bases and large auxiliary data, it might be beneficial to split the sieving up, but in all cases it's easier for the user to write a script that runs "msieve -l <unique_datfile> <other_options> &" in a loop.

Not to say that it's impossible to do, just that it's a low priority for me, behind bug fixes and NFS postprocessing improvements. If you do NFS sieving using GGNFS or the Franke tools, and you have multiple machines, then you have to do the parallel processing manually anyway.

[henryzz]

Originally Posted by jasonp

For the linear algebra, the lower limit on the size of the matrix is around 250k rows; even with one thread this completes in less than 10 minutes on a modern machine.

As for why sieving isn't multithreaded, that's because sieving parallelizes trivially but the machinery for writing multithreaded programs may not be trivial. If you want several threads to sieve, you have to go through all the data structures and figure out which ones can be shared, which ones need to be copied and how the threads will interact with each other. If they don't interact with each other, whoever spawns them is itself a thread so there is still some thread interactions to deal with. For very large problems that need huge factor bases and large auxiliary data, it might be beneficial to split the sieving up, but in all cases it's easier for the user to write a script that runs "msieve -l <unique_datfile> <other_options> &" in a loop.

Not to say that it's impossible to do, just that it's a low priority for me, behind bug fixes and NFS postprocessing improvements. If you do NFS sieving using GGNFS or the Franke tools, and you have multiple machines, then you have to do the parallel processing manually anyway.

it would be most helpful for things like 100-digit mpqs
i understand ur reasons for not doing it