mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2010-08-31, 03:48   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

135338 Posts
Default What's the best way to use PFGW in parallel?

I'm trying to find a (probable) prime of the form 2n - 2293. What's the best way for me to use a multicore machine to check candidates?

Should I just split the sieved list into 4-8 parts? This is not quite the best approach: it would be easiest to dole out sequential chunks, but then balancing load is hard. I could write a script to move the first, fifth, ... or first, ninth, ... numbers to their own file; maybe that's the best, though it's a pain if I discover that I need k of the cores for some other purpose and I can't support that many tasks anymore.

Also, ideally there would be a way to end the processes if any one of the searches found a prime, but I'm prepared to do this manually since I imagine it will be a while.

A -j cores switch would be great, but I don't imagine I'm that lucky...

Last fiddled with by CRGreathouse on 2010-08-31 at 03:49
CRGreathouse is offline   Reply With Quote
Old 2010-08-31, 04:38   #2
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

186916 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I'm trying to find a (probable) prime of the form 2n - 2293. What's the best way for me to use a multicore machine to check candidates?

Should I just split the sieved list into 4-8 parts? This is not quite the best approach: it would be easiest to dole out sequential chunks, but then balancing load is hard. I could write a script to move the first, fifth, ... or first, ninth, ... numbers to their own file; maybe that's the best, though it's a pain if I discover that I need k of the cores for some other purpose and I can't support that many tasks anymore.

Also, ideally there would be a way to end the processes if any one of the searches found a prime, but I'm prepared to do this manually since I imagine it will be a while.

A -j cores switch would be great, but I don't imagine I'm that lucky...
Using a script to dole out the pairs to x files in a round-robin fashion as you described would be the most effective way to balance load across multiple cores without resorting to a client-server setup; NewPGen has a built-in tool for doing this but I don't suppose it works with the kind of numbers you're testing.

What would provide the most flexibility is to run a PRPnet server. PRPnet is a client/server system for primality testing of numbers of various forms that supports the use of LLR, PFGW, Phrot, and genefer to do the underlying computations. You feed the sieve file into the server, and when clients connect to it, they're given the next untested number on the list to run. When that's done the result is returned to the server and logged; the client then grabs another number from the server ad infinitum. Stopping a client via Ctrl-C, flipping an option in its configuration file, and running it again is all that's needed to clean out the pairs in its local queue (informing the server that it can hand them out to other clients instead) and free up that core for other work.

PRPnet should be able to handle the numbers you're doing pretty easily. It's designed primarily for numbers of the form k*b^n+-c, but 2^n-2293 can be easily converted to that form as 1*2^n-2293. The PRPnet client would be able to do the PRP tests on these using either LLR or PFGW (though it somewhat arbitrarily uses PFGW first for this form if it's available).

While setting up a PRPnet server can be a bit of a hassle at first if you're not familiar with how it works, the client is quite easy to use. At the No Prime Left Behind project farther down the forum, which I co-admin, we use PRPnet (and its predecessor LLRnet--long story) to distribute our large-scale Riesel prime search efforts to individual members; since we've already got the infrastructure set up to run the servers, it's not much work to add and administrate additional servers. Thus, I have a standing offer to host a PRPnet server on the NPLB site for anyone who's interested--if you're interested, just send me the sieve file and I can get a server set up in no time.

Max

Last fiddled with by mdettweiler on 2010-08-31 at 04:38
mdettweiler is offline   Reply With Quote
Old 2016-03-05, 18:58   #3
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Default Exponent Testing

Quote:
Originally Posted by CRGreathouse View Post
I'm trying to find a (probable) prime of the form 2n - 2293. What's the best way for me to use a multicore machine to check candidates?

Should I just split the sieved list into 4-8 parts? This is not quite the best approach: it would be easiest to dole out sequential chunks, but then balancing load is hard. I could write a script to move the first, fifth, ... or first, ninth, ... numbers to their own file; maybe that's the best, though it's a pain if I discover that I need k of the cores for some other purpose and I can't support that many tasks anymore.

Also, ideally there would be a way to end the processes if any one of the searches found a prime, but I'm prepared to do this manually since I imagine it will be a while.

A -j cores switch would be great, but I don't imagine I'm that lucky...
If you want to manually test exponents, test exponents >11 congruent to 1 mod 4. Proof:
if n is 0 or 2 mod 4, 2^n-2293 is divisible by 3. If n is 3 mod 4, 2^n-2293 is divisible by 5.
PawnProver44 is offline   Reply With Quote
Old 2016-03-05, 23:36   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

32·557 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
If you want to manually test exponents, test exponents >11 congruent to 1 mod 4. Proof:
if n is 0 or 2 mod 4, 2^n-2293 is divisible by 3. If n is 3 mod 4, 2^n-2293 is divisible by 5.
Sieving and trial division are standard pretesting procedure. Your "proof" is equivalent to sieving to 5; a sieve to billions or trillions is common, the depth determined by the size of the candidate (and corresponding PRP-test time).

A sieve is performed on a list of candidates, while trial division is the same concept performed on one candidate at a time.
VBCurtis is online now   Reply With Quote
Old 2016-03-06, 00:21   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16158 Posts
Default

A post from 2009 plus a little looking shows that n=24k+1. But as VBCurtis points out, the factors are tiny so they'd be caught by trial factor or a sieve with little effort.

The thread is also almost 6 years old. It'd be nice to hear what any results were. The farthest test I've seen went to 360k, but that's not much more than was done in 2009.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Parallel sieving with newpgen fivemack And now for something completely different 3 2017-05-16 17:55
PFGW 3.3.6 or PFGW 3.4.2 Please update now! Joe O Sierpinski/Riesel Base 5 5 2010-09-30 14:07
Which bits of gmp-ecm are now parallel? fivemack GMP-ECM 5 2010-09-05 06:49
Parallel memory bandwidth fivemack Factoring 14 2008-06-11 20:43
Parallel Prime Search DonaldTripp Software 2 2007-02-17 19:35

All times are UTC. The time now is 00:56.


Thu Oct 28 00:56:43 UTC 2021 up 96 days, 19:25, 0 users, load averages: 2.80, 2.83, 2.74

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.