OK, thanks. So then both the polynomial selection and the sieving can be done embarassingly parallel, and only the matrix step (and the square root step?) have to be run on a single machine. Is the matrix step (and square-root step) parallelizable, but only on a shared memory machine? I assume that this is the case if it's a linear algebra routine. What are the "big dogs" using for the matrix step?:[URL="http://www.mersenneforum.org/showthread.php?t=13305"] http://www.mersenneforum.org/showthread.php?t=13305[/URL]

[QUOTE]What size composites are you planning on factoring? If they are smaller than 155 digits then the CUDA version of msieve polynomial selection would probably be faster for you, otherwise use the CPU version.[/QUOTE]I am presently factoring numbers in the 120-130 digit range, but am interested in general. Strange about the 155-digit CUDA rule? Does that come from the restriction to only fifth-order polynomial selection with CUDA, if that restriction still exists:
[QUOTE] - it can only find degree 5 polynomials (for technical reasons)[/QUOTE]

Douglas Staple,

Please check this thread:

[url]http://www.mersenneforum.org/showthread.php?t=15662[/url]

I think this is what you want, distributed polynomial selection.

@em99010pepe

The sad thing is that the thread you linked to is for the perl script factMsieve.pl and not the python script factmsieve.py that I have been using. It's unfortunate that apparently both of these scripts are under development. My understanding was that factmsieve.py is the newer/better, "the future" so to speak.

The linear algebra is a tightly coupled computation, everything else can run easily in parallel (the square root cannot, but you can thread one square root easily and can run several square roots in parallel).

The difference between CPU and CUDA poly selection is because they use different formulations of the same algorithm. The CPU version uses a hashtable, which only becomes really efficient for larger size problems.

[QUOTE=D. B. Staple;263983]@em99010pepe

The sad thing is that the thread you linked to is for the perl script factMsieve.pl and not the python script factmsieve.py that I have been using. It's unfortunate that apparently both of these scripts are under development. My understanding was that factmsieve.py is the newer/better, "the future" so to speak.[/QUOTE]To oversimplify, I find that the Python version is much the better on Windoze and the Perl version is much the better on Unix-like systems. YMMV.

AFAIK, both versions will be developed further and pretty much in parallel.


Paul

[QUOTE=D. B. Staple;263980]I am presently factoring numbers in the 120-130 digit range, but am interested in general. Strange about the 155-digit CUDA rule? Does that come from the restriction to only fifth-order polynomial selection with CUDA, if that restriction still exists:

[QUOTE]- it can only find degree 5 polynomials (for technical reasons) [/QUOTE]
[/QUOTE]
No, that restriction does not exist. Both the CPU and CUDA versions of msieve polynomial selection can find polynomials of degree 4, 5 or 6. The 155 digit threshold I mentioned is due to the differences in the way that each version of the code works. The CPU version uses a hashtable that takes advantage of the birthday paradox, and generally becomes more efficient as the problem size increases. The CUDA version uses a highly parallelized search that takes advantage of the hundreds of threads available on modern CUDA cards, making it faster than the CPU search for problems below about 155 digits.

I picked 155 out of the air. The real threshold depends on how capable your CUDA card is vs how fast your CPU is (and how many cores it has, if you choose to run multiple instances in parallel).

I have now added a multi-core msieve polynomial seach capability to the factmsieve.py driver program (attached). Please remember to set up the binary paths and other parameters for your particular use (these settings are early in the program code). Note, however, that this code will use multiple cores on one machine - it WON'T distribute polynomial seach across several machines.

Please also note that the multi-threading of msieve is new and needs testing. So there are likely to be errors. Please report any problems here.

Worked for me. However, the polyselection finished too soon. Is there no way to specify the leading coefficients ?

[QUOTE=Karl M Johnson;264059]Worked for me. However, the polyselection finished too soon. Is there no way to specify the leading coefficients ?[/QUOTE]

I can add this easily. Should it be a command line option or should I add something to one of the initialisation files?

Hmm, how about a configurable parameter in the python script itself ? Like, If I specify np 1,100000 in the script, it will automatically split all that range for N cores.

POLY_MIN_LC and POLY_MAX_LC in the attached version. Note the search starts at POLY_MIN_LC + 1.