Multi-threaded factoring

[bchaffin]

I'm trying to get the most out of a multi-core system when factoring -- specifically when running aliqueit. Some pieces are simple; yafu and ggnfs are easily configured to run multiple threads. But ecm and polynomial selection run single-threaded, and when running with many cores these portions start to dominate the run time. Of course one approach is just to run fewer curves and jump to yafu's SIQS sooner, and to push the ggnfs cutoff higher, but a nicer solution would be to make more effective use of multiple threads.

Surely I'm not the first to ask this. Is there already a way to thread ecm and poly selection? Or is there something inherently serial about them that I'm missing? (I'm new to factoring and don't claim to understand much of the underlying math.) For ecm it seems like you could easily just divide the number of curves to run across any number of threads. I understand poly selection even less but it seems like that also consists of many independent tests.

Any help or pointers appreciated. Thanks!

[Karl M Johnson]

If you are on Windows, you can just create a batch file for ECM, and run it 4 times(if you have 4 cores).
Here's how I've done the batch file:

ecm.exe -c 800 2500000 2500000000 <factorme.txt >> OUT\ECM[%random%]N[%random%]

This way, all 4 runs are independent, and output results in for different files.

As for polynomial selection, better use a GPU for that.
Msieve supports Nvidia GPUs currently.

[bsquared]

Originally Posted by bchaffin

For ecm it seems like you could easily just divide the number of curves to run across any number of threads.

I implemented ECM in this way in yafu... it will do N curves at a time where N is the number of threads you specify. Unfortunately, my implementation of ECM is slower than GMP-ECM, by at least a factor of reasonable values of N. So single threaded GMP-ECM will in most cases still give you higher throughput (the yafu executable is by default configured to use GMP-ECM).

To my knowledge, GMP-ECM is not easily threadable. Its code makes use of a global structure of primes in a way that defeats threading by curves. However, it is fairly easy to run multiple instances of the executable to achieve the same effect; although I don't know of a good, ready-made script for automating this.

[mdettweiler]

Originally Posted by bsquared

I implemented ECM in this way in yafu... it will do N curves at a time where N is the number of threads you specify. Unfortunately, my implementation of ECM is slower than GMP-ECM, by at least a factor of reasonable values of N. So single threaded GMP-ECM will in most cases still give you higher throughput (the yafu executable is by default configured to use GMP-ECM).

To my knowledge, GMP-ECM is not easily threadable. Its code makes use of a global structure of primes in a way that defeats threading by curves. However, it is fairly easy to run multiple instances of the executable to achieve the same effect; although I don't know of a good, ready-made script for automating this.

How do the recent versions of yafu with GMP-ECM compiled in handle multithreading? If they do what I'd guess they'd do (for N threads, spawn N instances of the GMP-ECM library code to run 1 curve each), then an easy way to implement multithreaded ECM in aliqueit might simply be to pass the job on to yafu.

[bchaffin]

Originally Posted by bsquared

I implemented ECM in this way in yafu... it will do N curves at a time where N is the number of threads you specify.

Interesting... I have yafu configured to run 8 threads, via the .ini file. I'm running on SLES10 linux, and when it runs SIQS, 'top' reports it using 700-800% CPU. But when it's doing ecm it shows 100% CPU, and the progress is slower than a single instance of gmp-ecm (so consistent with only running 1 curve at a time). I'm using the pre-compiled 64-bit binary from version 1.19.2. Is there something else I need to configure?

Anyway I may take a crack at modifying aliqueit to launch N ecm instances in parallel, unless somebody says they've already done it.

As for poly selection, my machines don't have GPUs (they're monitor-less servers) so that's not an option for me. I'll see if I can figure out MT ecm before I tackle that one.

[bsquared]

Originally Posted by mdettweiler

How do the recent versions of yafu with GMP-ECM compiled in handle multithreading? If they do what I'd guess they'd do (for N threads, spawn N instances of the GMP-ECM library code to run 1 curve each), then an easy way to implement multithreaded ECM in aliqueit might simply be to pass the job on to yafu.

If yafu is configured to use GMP-ECM, which it is in the provided binaries, it ignores the threading flag. I didn't want to build into yafu the ability to launch multiple external processes and monitor them, since that becomes a portability mess.

To use the native multithreaded ecm (which is slower), you'd need to recompile.

[bsquared]

Originally Posted by bchaffin

Interesting... I have yafu configured to run 8 threads, via the .ini file. I'm running on SLES10 linux, and when it runs SIQS, 'top' reports it using 700-800% CPU. But when it's doing ecm it shows 100% CPU, and the progress is slower than a single instance of gmp-ecm (so consistent with only running 1 curve at a time). I'm using the pre-compiled 64-bit binary from version 1.19.2. Is there something else I need to configure?

Yep, that sounds like the expected behavior. To run the native (slower) ECM, you'd need to recompile. I don't recommend it - my ECM implementation is much less sophisticated than GMP-ECM... I only mentioned it as a sort of proof-of-concept in ECM threading.

I've kicked around the idea of modifying GMP-ECM to be thread friendly, but I've never got around to doing it... one of these days maybe.

[bchaffin]

OK, thanks for the explanation, that all makes sense.

I have a version of aliqueit which runs multi-threaded ecm, and it seems to be working OK. I have no idea whether it's portable -- it uses signal() and killpg() to clean up child threads so it may not be -- but I'm happy to share it if anyone's interested.

Msieve's polyfind is much more difficult since it uses a bunch of heuristics to set time limits, which may not work when searching subranges. A better approach might be to run polyfind and ecm in parallel. I'll think about that...

[Greebley]

For aliquot sequences there are enough of them that one can simply run one sequence per processor. With -p, I have found I can run at 100% (of all) cpu and still use the computer for other things.

OTOH, if the factor is big enough to need more than 1 processor then the overhead of manually doing things (or writing a script) is small compared to the running time.