mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2010-10-18, 17:52   #1
bchaffin
 
Sep 2010
Portland, OR

7×53 Posts
Default Multi-threaded factoring

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!
bchaffin is offline   Reply With Quote
Old 2010-10-18, 18:07   #2
Karl M Johnson
 
Karl M Johnson's Avatar
 
Mar 2010

41110 Posts
Default

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:
Code:
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.
Karl M Johnson is offline   Reply With Quote
Old 2010-10-18, 18:11   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·13·127 Posts
Default

Quote:
Originally Posted by bchaffin View Post
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.
bsquared is offline   Reply With Quote
Old 2010-10-18, 18:36   #4
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

11000011000012 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
mdettweiler is offline   Reply With Quote
Old 2010-10-18, 18:42   #5
bchaffin
 
Sep 2010
Portland, OR

7·53 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.
bchaffin is offline   Reply With Quote
Old 2010-10-18, 19:09   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×13×127 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
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 is offline   Reply With Quote
Old 2010-10-18, 19:13   #7
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×13×127 Posts
Default

Quote:
Originally Posted by bchaffin View Post
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.
bsquared is offline   Reply With Quote
Old 2010-10-19, 18:10   #8
bchaffin
 
Sep 2010
Portland, OR

7×53 Posts
Default

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...
bchaffin is offline   Reply With Quote
Old 2010-10-24, 13:38   #9
Greebley
 
Greebley's Avatar
 
May 2009
Dedham Massachusetts USA

15138 Posts
Default

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.
Greebley is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
RSA multi factor labba FactorDB 2 2016-01-30 23:25
multi-core TF dbaugh Information & Answers 3 2011-09-06 01:32
Multi-Core / Multi-CPU Assignments (missing) worknplay Software 3 2008-11-05 17:26
NEW MERSENNES AND MULTI-THREADED SOFTWARE lpmurray Software 13 2005-12-21 08:24
Prime95 a multi-threaded application? Unregistered Software 10 2004-06-11 05:31

All times are UTC. The time now is 08:35.

Sat Oct 31 08:35:10 UTC 2020 up 51 days, 5:46, 2 users, load averages: 1.60, 1.45, 1.54

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.