PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

Message boards : Sieving : Fastest way to sieve on CPU?

Author Message
f1pokerspeed
Send message
Joined: 26 Nov 10
Posts: 11
ID: 74587
Credit: 14,655
RAC: 0

Message 53731 - Posted: 2 May 2012 | 23:05:06 UTC
Last modified: 2 May 2012 | 23:06:19 UTC

Currently, for my manual PPS sieving efforts, I'm using:

srsieve (dev version from mersenneforums)
PFGW

This is the process I use for large-candidate-set searches:

1) Sieve to pmax=1,000 with a range of 500,000 n's for a single k
2) Run through some trivial factoring with PFGW
3) Convert the file produced by PFGW to a sieve-able one via copying the *.out headers and converting with srfile
4) Sieving to remove false trivial primes
5) PRP testing

This is all performed on a single core - yet I have a quad core machine.

BTW: This whole process can get the list of candidates down to a few thousand within 60 seconds to a couple of minutes if done quickly enough.

Could anyone give me some advice on how I could speed up this process please? I have no GPU on this 64-bit laptop (and yes, 64-bit sieving is being performed). If anyone could give me some advice, I would appreciate it.

Profile Lennart SM5YMTProject donor
Honorary cruncher
Avatar
Send message
Joined: 7 May 07
Posts: 1125
ID: 7989
Credit: 694,692,344
RAC: 0
Discovered the World's First base 13 Generalized Woodall prime!!!Eliminated 22 conjecture "k"s2009 Tour de Primes highest prime count2009 Tour de Primes most Mountain Stage primes2010 Tour de Primes highest prime count2010 Tour de Primes highest prime score321 LLR Turquoise: Earned 5,000,000 credits (5,097,586)Cullen LLR Amethyst: Earned 1,000,000 credits (1,101,661)PPS LLR Emerald: Earned 50,000,000 credits (80,169,933)PSP LLR Jade: Earned 10,000,000 credits (18,921,475)SoB LLR Bronze: Earned 10,000 credits (55,453)SR5 LLR Ruby: Earned 2,000,000 credits (4,407,637)SGS LLR Ruby: Earned 2,000,000 credits (4,595,742)TPS LLR (retired) Silver: Earned 100,000 credits (360,998)TRP LLR Turquoise: Earned 5,000,000 credits (5,800,792)Woodall LLR Ruby: Earned 2,000,000 credits (4,885,194)321 Sieve Amethyst: Earned 1,000,000 credits (1,345,944)Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (27,566,122)PPS Sieve Double Silver: Earned 200,000,000 credits (220,787,724)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,694,194)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,986,371)AP 26/27 Amethyst: Earned 1,000,000 credits (1,780,026)GFN Jade: Earned 10,000,000 credits (18,585,003)PSA Double Silver: Earned 200,000,000 credits (287,482,568)
Message 53734 - Posted: 3 May 2012 | 1:01:19 UTC - in response to Message 53731.

Use srsieve first.

An example to get started:

$ srsieve --newpgen --nmin 5000 --nmax 10000 --pmax 400000 "24*7^n+1"

This will sieve the single sequence 24*7^n+1 with n in the range 5,000 -
10,000 for all factors up to 400,000 and write the remaining terms in newpgen
format to the file t16_b7_k24.npg. It is equivalent (and should produce an
identical file) to the following NewPGen invocation:



When thats done use sr2sieve after 100G-400G

check files here http://sites.google.com/site/geoffreywalterreynolds/programs


Lennart

f1pokerspeed
Send message
Joined: 26 Nov 10
Posts: 11
ID: 74587
Credit: 14,655
RAC: 0

Message 53766 - Posted: 3 May 2012 | 15:18:43 UTC - in response to Message 53734.

Thanks for the help.

rogue
Volunteer developer
Avatar
Send message
Joined: 8 Sep 07
Posts: 1194
ID: 12001
Credit: 18,565,548
RAC: 0
PPS LLR Bronze: Earned 10,000 credits (31,229)PSA Jade: Earned 10,000,000 credits (18,533,435)
Message 53768 - Posted: 3 May 2012 | 15:56:53 UTC

Since you have a single k, I recommend sieving to a nominal depth p such that p > k, with srsieve, then switch to sr1sieve. It is much faster than srsieve for single k.

Also, I recommend d/ling the latest versions of srsieve/sr1sieve. I've made changes to Geoff's code that might benefit you. Look here for more information:

http://www.mersenneforum.org/showthread.php?t=15833

f1pokerspeed
Send message
Joined: 26 Nov 10
Posts: 11
ID: 74587
Credit: 14,655
RAC: 0

Message 53779 - Posted: 3 May 2012 | 18:17:59 UTC - in response to Message 53768.
Last modified: 3 May 2012 | 18:30:43 UTC

Thanks for the tips. I'm using your version of srsieve already rogue, it's quite a bit faster!

One thing: do you already perform the algebraic factorizations, or do I need to add a switch to make it work? Also, your latest version of srsieve is crashing for me after a while, and it isn't reaching the pmax of about 1e12.

Also, how do you make it run properly (sr1sieve)? I can't get it to work.

Profile Lennart SM5YMTProject donor
Honorary cruncher
Avatar
Send message
Joined: 7 May 07
Posts: 1125
ID: 7989
Credit: 694,692,344
RAC: 0
Discovered the World's First base 13 Generalized Woodall prime!!!Eliminated 22 conjecture "k"s2009 Tour de Primes highest prime count2009 Tour de Primes most Mountain Stage primes2010 Tour de Primes highest prime count2010 Tour de Primes highest prime score321 LLR Turquoise: Earned 5,000,000 credits (5,097,586)Cullen LLR Amethyst: Earned 1,000,000 credits (1,101,661)PPS LLR Emerald: Earned 50,000,000 credits (80,169,933)PSP LLR Jade: Earned 10,000,000 credits (18,921,475)SoB LLR Bronze: Earned 10,000 credits (55,453)SR5 LLR Ruby: Earned 2,000,000 credits (4,407,637)SGS LLR Ruby: Earned 2,000,000 credits (4,595,742)TPS LLR (retired) Silver: Earned 100,000 credits (360,998)TRP LLR Turquoise: Earned 5,000,000 credits (5,800,792)Woodall LLR Ruby: Earned 2,000,000 credits (4,885,194)321 Sieve Amethyst: Earned 1,000,000 credits (1,345,944)Cullen/Woodall Sieve (suspended) Sapphire: Earned 20,000,000 credits (27,566,122)PPS Sieve Double Silver: Earned 200,000,000 credits (220,787,724)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (2,694,194)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (8,986,371)AP 26/27 Amethyst: Earned 1,000,000 credits (1,780,026)GFN Jade: Earned 10,000,000 credits (18,585,003)PSA Double Silver: Earned 200,000,000 credits (287,482,568)
Message 53793 - Posted: 4 May 2012 | 3:03:47 UTC - in response to Message 53779.

sr1sieve -p1e9 -P10e9 -it16_b2_k5.npg -fk5_factor_1G-10G.txt -q

This is a example in a dos CMD window.

-p start p -P stop p -i input sievefile -f output factors file

you can also add -o filename and you get a resultfile with all factors removed.

-p --pmin P0
-P --pmax P1 Sieve for factors p in the range P0 <= p <= P1
-i --input FILE Read sieve from NewPGen format file FILE.
-o --output FILE Write sieve to NewPGen format file FILE.
-f --factors FILE Append new factors to file FILE.
-C --cache-file FILE Load (or save) Legendre symbol tables from (or to) FILE.
-s --save TIME Update output file every TIME (default 60) minutes.
-l --L1-cache SIZE Assume L1 data cache is SIZE Kb.
-L --L2-cache SIZE Assume L2 cache is SIZE Kb.
-B --baby METHOD Use METHOD for baby step mulmods.
-G --giant METHOD Use METHOD for giant step mulmods.
-H --hashtable SIZE Force use of a SIZE Kb hashtable.
-Q --subseq Q Force sieving k*b^n+c as subsequences (k*b^d)*(b^Q)^m+c.
-x --no-lookup Don't pre-compute Legendre symbol lookup tables.
-z --lower-priority Run at low priority. (-zz lower).
-Z --raise-priority Run at high priority. (-ZZ higher).
-A --affinity N Set affinity to CPU N.
-d --duplicates Report factors that don't eliminate any composite.
-q --quiet Don't print found factors.
-v --verbose Print some extra messages.
-h --help Print this help.

rogue
Volunteer developer
Avatar
Send message
Joined: 8 Sep 07
Posts: 1194
ID: 12001
Credit: 18,565,548
RAC: 0
PPS LLR Bronze: Earned 10,000 credits (31,229)PSA Jade: Earned 10,000,000 credits (18,533,435)
Message 53802 - Posted: 4 May 2012 | 12:41:28 UTC - in response to Message 53779.

Thanks for the tips. I'm using your version of srsieve already rogue, it's quite a bit faster!

One thing: do you already perform the algebraic factorizations, or do I need to add a switch to make it work? Also, your latest version of srsieve is crashing for me after a while, and it isn't reaching the pmax of about 1e12.

Also, how do you make it run properly (sr1sieve)? I can't get it to work.


It will always remove candidates with algebraic factorizations, i.e. you can't control that behavior.

Are you using the Win64 build or did you build your own? I need to know what system you are running on. Could you also PM me the input files/switches you are are running with?

Profile [SG]Puzzle-PeterProject donor
Volunteer tester
Avatar
Send message
Joined: 14 Jun 08
Posts: 374
ID: 24128
Credit: 92,652,187
RAC: 0
Discovered the World's First base 68 Generalized Cullen prime!!!Eliminated 4 conjecture "k"s321 LLR Gold: Earned 500,000 credits (517,694)Cullen LLR Bronze: Earned 10,000 credits (22,649)PPS LLR Ruby: Earned 2,000,000 credits (3,716,757)PSP LLR Amethyst: Earned 1,000,000 credits (1,255,162)SoB LLR Amethyst: Earned 1,000,000 credits (1,529,355)SGS LLR Bronze: Earned 10,000 credits (79,385)TRP LLR Bronze: Earned 10,000 credits (42,673)Woodall LLR Silver: Earned 100,000 credits (360,820)321 Sieve Bronze: Earned 10,000 credits (21,641)Cullen/Woodall Sieve (suspended) Ruby: Earned 2,000,000 credits (2,449,647)PPS Sieve Ruby: Earned 2,000,000 credits (4,110,585)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Bronze: Earned 10,000 credits (75,714)TRP Sieve (suspended) Bronze: Earned 10,000 credits (54,880)AP 26/27 Bronze: Earned 10,000 credits (42,894)PSA Emerald: Earned 50,000,000 credits (78,365,420)
Message 53955 - Posted: 6 May 2012 | 6:16:56 UTC - in response to Message 53779.
Last modified: 6 May 2012 | 6:19:33 UTC

Also, how do you make it run properly (sr1sieve)? I can't get it to work.


This may be trivial, but just to make sure I will add this to what Lennart already posted: make sure your input file has the correct format (.npg). If not, use srfile to convert.

I would also suggest switching to sr1sieve sooner than p=1e12 as it is faster than srsieve for a single k.
____________
There are only 10 kinds of people - those who understand binary and those who don't

rogue
Volunteer developer
Avatar
Send message
Joined: 8 Sep 07
Posts: 1194
ID: 12001
Credit: 18,565,548
RAC: 0
PPS LLR Bronze: Earned 10,000 credits (31,229)PSA Jade: Earned 10,000,000 credits (18,533,435)
Message 53980 - Posted: 6 May 2012 | 13:24:27 UTC - in response to Message 53955.

I would also suggest switching to sr1sieve sooner than p=1e12 as it is faster than srsieve for a single k.


Once p > k, you can switch, but I would suggest sieving a little deeper so that the output file is smaller.

f1pokerspeed
Send message
Joined: 26 Nov 10
Posts: 11
ID: 74587
Credit: 14,655
RAC: 0

Message 54191 - Posted: 8 May 2012 | 19:19:12 UTC
Last modified: 8 May 2012 | 19:20:35 UTC

I apologise for not posting in a while, I was on a business trip in Germany and I had no internet connection (lousy 2-star hotel).

@rogue:

1) I create my own input files with srsieve
2) Running Win7 x64 on Intel Sandy Bridge laptop, I also have a desktop PC with Core2 Duo and an nVidia GTX 220 (I think it's CC1.3)
3) Using *.npg files, it now works fine.
4) How deep is deep enough? if k=1m, then pmax=1m<k<2m? (or something like that)?

@Lennart:

1) Thanks for the tips on the CMD line switches.
2) So, once done, do I just upload the factors or do I PRP test myself?

@[SG]:

1) I use srfile a lot now, thanks for the tip.

Scott BrownProject donor
Volunteer moderator
Project administrator
Volunteer tester
Project scientist
Avatar
Send message
Joined: 17 Oct 05
Posts: 2034
ID: 1178
Credit: 7,324,840,894
RAC: 4,574,691
Discovered the World's First base 116 Generalized Cullen prime!!!Discovered 25 mega primesEliminated 7 conjecture "k"sDiscovered 1 Sophie Germain pairDiscovered 2 Fermat divisors2012 Tour de Primes highest prime count2012 Tour de Primes most Mountain Stage primes2015 Tour de Primes highest prime count2016 Tour de Primes highest prime countFound 23 primes in the 2018 Tour de PrimesFound 1 mega prime in the 2018 Tour de PrimesFound 2 primes in the 2018 Tour de Primes Mountain Stage2019 Tour de Primes highest prime countFound 22 primes in the 2019 Tour de Primes2020 Tour de Primes highest prime scoreFound 21 primes in the 2020 Tour de PrimesFound 4 mega primes in the 2020 Tour de Primes321 LLR Double Bronze: Earned 100,000,000 credits (110,931,288)Cullen LLR Double Bronze: Earned 100,000,000 credits (103,870,990)ESP LLR Double Bronze: Earned 100,000,000 credits (155,058,979)Generalized Cullen/Woodall LLR Double Bronze: Earned 100,000,000 credits (108,461,080)PPS LLR Double Gold: Earned 500,000,000 credits (612,539,975)PSP LLR Double Bronze: Earned 100,000,000 credits (126,982,721)SoB LLR Double Bronze: Earned 100,000,000 credits (135,747,083)SR5 LLR Double Silver: Earned 200,000,000 credits (214,194,272)SGS LLR Double Bronze: Earned 100,000,000 credits (182,480,743)TPS LLR (retired) Silver: Earned 100,000 credits (235,439)TRP LLR Double Bronze: Earned 100,000,000 credits (121,443,822)Woodall LLR Double Bronze: Earned 100,000,000 credits (101,447,725)321 Sieve Double Silver: Earned 200,000,000 credits (210,818,608)Cullen/Woodall Sieve (suspended) Emerald: Earned 50,000,000 credits (83,794,448)Generalized Cullen/Woodall Sieve (suspended) Double Silver: Earned 200,000,000 credits (285,139,652)PPS Sieve Double Ruby: Earned 2,000,000,000 credits (2,181,877,259)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Double Silver: Earned 200,000,000 credits (203,523,358)TRP Sieve (suspended) Double Silver: Earned 200,000,000 credits (201,489,157)AP 26/27 Double Silver: Earned 200,000,000 credits (261,475,474)GFN Double Amethyst: Earned 1,000,000,000 credits (1,664,380,789)PSA Double Silver: Earned 200,000,000 credits (259,058,048)
Message 54193 - Posted: 8 May 2012 | 19:25:14 UTC - in response to Message 54191.

...an nVidia GTX 220 (I think it's CC1.3)
...


GT 220 (no GTX with that model number) is actually CC1.2


Message boards : Sieving : Fastest way to sieve on CPU?

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2020 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.64, 1.05, 1.55
Generated 1 Jun 2020 | 22:53:54 UTC