srsieve/sr2sieve enhancements - Page 19

rogue · 2019-04-30, 21:09

After a long hiatus, I finally started working on srsieve2 again. Based upon very limited testing srsieve2 is about 20% faster than srsieve. srsieve2 doesn't have all of the features of srsieve yet, but I will be adding the features I intend to add when I have time. BTW, srsieve2 will also incorporate the sr2sieve logic after I work out any bugs in the logic. There will be two code paths, one for abs(max(c)) = 1 (sr2sieve) and one for abs(max(c)) > 1 (srsieve). I don't know about sr1sieve yet, but I think it is basically sr2sieve but for a single sequence. If necessary I will create a third code path for that.

rogue · 2019-05-01, 15:38

I'm looking at the options available to srsieve, sr1sieve, sr2sieve, and srfile and comparing to what I've done so far with srsieve2. You can see the comparison below. I'm looking for feedback from all users of these programs to tell me which command line features they use in those programs and want me to implement in srsieve2. The ones with '??' are ones that I intend to add, but haven't implemented. I'll open up the discussion for new features after I release this code.

Code:

srsieve options:           srsieve2 options:
   -p --pmin P0               -p
   -P --pmax P1               -P
   -n --nmin N0               -n
   -N --nmax N1               -N
   -o --output FILE           -o
   -r --report X                    not configurable, always reports every 60 seconds
   -s --save X                      not configurable, always saves every 60 minutes
   -S --stop-rate X                 no corresponding option
   -m --minimum X                   factors are only written to factor file if -O is specified
   -B --babystep X                  no corresponding option
   -H --hashtable X                 no corresponding option
   -F --force-base X                no corresponding option
   -L --limit-base X                no corresponding option
   -M --mod M,a,b,..                no corresponding option
   -f --factors               -O
   -g --newpgen                     no corresponding option
   -G --prp                         no corresponding option
   -w --pfgw                  -fA
   -a --abcd                  -fD   (default)
   -c --check                       all factors are verified
      --no-check                    cannot be disabled
   -C --checkpoint                  always saves every 60 minutes
   -d --duplicates                  no corresponding option
   -y --no-filter                   no corresponding option
   -z --idle                        always runs at idle priority
   -Z --no-idle                     always runs at idle priority
   -A --affinity N                  no corresponding option
   -v --verbose                     no corresponding option
   -q --quiet                       no corresponding option
   -h --help                  -h
   SEQUENCE ...               -s    can use multiple times, can specify a sequence of file of sequences
   FILE ...                   -i
                              
sr2sieve options:             
   -s --sierpinski                  no corresponding option
   -r --riesel                      no corresponding option
   -i --input FILE            -i
                              
   -p --pmin P0               -p
   -P --pmax P1               -P
   -f --factors FILE          -O
   -u --uid STRING                  no corresponding option
   -c --cache                       no corresponding option
   -C --cache-file FILE             no corresponding option
   -l --L1-cache SIZE               no corresponding option
   -L --L2-cache SIZE               no corresponding option
   -B --baby METHOD                 no corresponding option
   -G --giant METHOD                no corresponding option
      --ladder METHOD               no corresponding option
   -H --hashtable SIZE              no corresponding option
   -Q --subseq Q                    no corresponding option
      --scale-giant X               no corresponding option
      --min-giant NUM               no corresponding option
   -D --duplicates FILE             no corresponding option
      --log-factors                 no corresponding option
   -R --rate SECONDS                no corresponding option
   -S --save TIME                   always saves every 60 minutes
   -z --lower-priority              no corresponding option
   -Z --raise-priority              no corresponding option
   -A --affinity N                  no corresponding option
   -j --sobistrator                 no corresponding option
   -X --skip-cubic                  no corresponding option
   -x --no-lookup             ??
   -d --dual                  ??
   -q --quiet                       factors are only written to factor file if -O is specified
   -v --verbose                     no corresponding option
   -h --help                  -h
                              
sr1sieve options:             
   -p --pmin P0               -p
   -P --pmax P1               -P
   -i --input FILE            -i
   -o --output FILE           -o
   -f --factors FILE          -O
   -C --cache-file FILE             no corresponding option
   -s --save TIME                   always saves every 60 minutes
      --sse2                        no corresponding option
      --no-sse2                     no corresponding option
   -l --L1-cache SIZE               no corresponding option
   -L --L2-cache SIZE               no corresponding option
   -B --baby METHOD                 no corresponding option
   -G --giant METHOD                no corresponding option
   -H --hashtable SIZE              no corresponding option
   -Q --subseq Q                    no corresponding option
   -F --format=f              -fD (ABCD, default) and -fA (ABC)
   -x --no-lookup             ??
   -z --lower-priority              always runs at idle priority
   -Z --raise-priority              always runs at idle priority
   -A --affinity N                  no corresponding option
   -d --duplicates                  no corresponding option
   -q --quiet                       factors are only written to factor file if -O is specified
   -v --verbose                     no corresponding option
   -h --help                  -h
                              
srfile options:               
   -o --output FILE           -o
   -k --known-factors FILE    -I
   -d --delete SEQ            ??
   -g --newpgen                     no corresponding option
   -G --prp                         no corresponding option
   -w --pfgw                  -fA (ABC format)
   -a --abcd                  -fD (ABCD format, default)
   -Q --subseqs X                   no corresponding option
   -B --newbase BASE                no corresponding option
   -E --extract KLIST               no corresponding option
   -c --congruence X                no corresponding option
   -p --pfactor X                   no corresponding option
                            
   -v --verbose                     no corresponding option
   -q --quiet                       no corresponding option
   -h --help                  -h
   INFILE ...                 -i
   
other srsieve2 options:
   -w number of primes per chunk per worker, default 1e6
   -W number of worker threads
   -A apply factors from -I and exit

VBCurtis · 2019-05-01, 16:37

I use -m to suppress screen output when a sieve is first starting up; printing factors to screen can reduce sieve speed dramatically when the factors-found rate is in thousands per second.

On srsieve, this is important also because the status line scrolls off the screen along with factors; if one is finding hundreds of factors per second one is unable to ever see the status line on-screen. this isn't a problem with sr2sieve, as that status line stays at the bottom (and is printed with every factor found, not just every 60 seconds- perhaps that's why sieve speed suffers so much!)

rogue · 2019-05-01, 17:04

Quote:

Originally Posted by VBCurtis

I use -m to suppress screen output when a sieve is first starting up; printing factors to screen can reduce sieve speed dramatically when the factors-found rate is in thousands per second.

On srsieve, this is important also because the status line scrolls off the screen along with factors; if one is finding hundreds of factors per second one is unable to ever see the status line on-screen. this isn't a problem with sr2sieve, as that status line stays at the bottom (and is printed with every factor found, not just every 60 seconds- perhaps that's why sieve speed suffers so much!)

Sorry that I wasn't clear in how factors are handled.

For all programs built on the mtsieve framework, no factors are written to the console. You can only write factors to a factor file and that can be done with the -O switch. The mtsieve programs will output a status update once every 60 seconds overwriting the previous status line. Once every 60 minutes the remaining candidates are written to an output file. For most of the mtsieve programs the name of that file is auto-generated. srsieve2 will auto-generate that file name.

There are two reasons to use the -O switch. The first is if you are sieving the same range across multiple computers and need to merge all of the factor files to generate a new candidate file. The second is if you want to independently verify that factors found are truly factors with pfgw. All of the mtsieve programs will verify factors and terminate if one is invalid, but there is always the possibility that the math used to verify factors is wrong. But considering how much time I spend in validating factors that are found with pfgw, that is a very slim possibility. I would rather that a the software misses a factor than reports an invalid one.

rogue · 2019-05-01, 18:41

I'm looking at the sr2sieve code and what is driving me crazy is the number of optimizations that are driven by changing values in sr2sieve.h and recompiling. All of that is going away. I'm focusing on base case since that is how I've compiled and released sr2sieve. If there are any users/projects that need specific optimizations associated with their build, please let me know. Two specific optimizations are "dual sierpinski" and base 5 which is used to create sr5sieve.

Besides multi-threading, some features are only enabled if using the GNU compiler. Those restrictions will go away. I'm hoping that by the time I'm done that srsieve2 will be fast enough that there is no reason to continue using sr1sieve, sr2sieve, or sr5sieve. There might be opportunities to optimize very specific cases even further, but that is for the future and only upon request.

CRGreathouse · 2019-05-02, 02:47

Quote:

Originally Posted by rogue

I'm hoping that by the time I'm done that srsieve2 will be fast enough that there is no reason to continue using sr1sieve, sr2sieve, or sr5sieve.

It would be amazing to maintain only one codebase.

henryzz · 2019-05-02, 09:52

-r is an option I frequently use when I use srsieve. Sometimes I want longer that the default and sometimes shorter while experimenting. Output should always be controllable.

rob147147 · 2019-05-03, 15:56

I use the cache options -c/-C of sr2sieve almost all the time as it generally provides good speedups. I have also found -Q useful when building/testing my CUDA version of sr2sieve, and sometimes you can find greater speed in sr2sieve by using it to change the number of subsequences being sieved.

rogue · 2019-05-03, 18:14

Quote:

Originally Posted by rob147147

I use the cache options -c/-C of sr2sieve almost all the time as it generally provides good speedups. I have also found -Q useful when building/testing my CUDA version of sr2sieve, and sometimes you can find greater speed in sr2sieve by using it to change the number of subsequences being sieved.

I do see value in -c/-C, but I'm not as familiar with -Q. I am not familiar with any CUDA version of sr2sieve.

pepi37 · 2019-05-03, 18:24

Quote:

Originally Posted by rogue

I do see value in -c/-C, but I'm not as familiar with -Q. I am not familiar with any CUDA version of sr2sieve.

PPS sieva?
Running on GPU for base2

pepi37 · 2019-05-03, 18:31

Quote:

Originally Posted by rob147147

I use the cache options -c/-C of sr2sieve almost all the time as it generally provides good speedups. I have also found -Q useful when building/testing my CUDA version of sr2sieve, and sometimes you can find greater speed in sr2sieve by using it to change the number of subsequences being sieved.

Can you give me some example?
Also, how much speed gain you can get? 10%, more?

2019-04-30, 21:09	#199
rogue "Mark" Apr 2003 Between here and the 6354₁₀ Posts	After a long hiatus, I finally started working on srsieve2 again. Based upon very limited testing srsieve2 is about 20% faster than srsieve. srsieve2 doesn't have all of the features of srsieve yet, but I will be adding the features I intend to add when I have time. BTW, srsieve2 will also incorporate the sr2sieve logic after I work out any bugs in the logic. There will be two code paths, one for abs(max(c)) = 1 (sr2sieve) and one for abs(max(c)) > 1 (srsieve). I don't know about sr1sieve yet, but I think it is basically sr2sieve but for a single sequence. If necessary I will create a third code path for that. Last fiddled with by rogue on 2019-04-30 at 21:23

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Sieving twins with srsieve	henryzz	Twin Prime Search	0	2014-03-18 12:44
Intel announces multi-core enhancements for Haswell chips	ixfd64	Hardware	8	2012-02-10 20:32
LLRnet enhancements	kar_bon	No Prime Left Behind	10	2008-03-28 11:21
TODO list and suggestions/comments/enhancements	Greenbank	Octoproth Search	2	2006-12-03 17:28
Suggestions for future enhancements	Reboot It	Software	16	2003-10-17 01:31

2019-05-01, 16:37	#201
VBCurtis "Curtis" Feb 2005 Riverside, CA 2²×1,217 Posts	I use -m to suppress screen output when a sieve is first starting up; printing factors to screen can reduce sieve speed dramatically when the factors-found rate is in thousands per second. On srsieve, this is important also because the status line scrolls off the screen along with factors; if one is finding hundreds of factors per second one is unable to ever see the status line on-screen. this isn't a problem with sr2sieve, as that status line stays at the bottom (and is printed with every factor found, not just every 60 seconds- perhaps that's why sieve speed suffers so much!)

2019-05-01, 18:41	#203
rogue "Mark" Apr 2003 Between here and the 2·3²·353 Posts	I'm looking at the sr2sieve code and what is driving me crazy is the number of optimizations that are driven by changing values in sr2sieve.h and recompiling. All of that is going away. I'm focusing on base case since that is how I've compiled and released sr2sieve. If there are any users/projects that need specific optimizations associated with their build, please let me know. Two specific optimizations are "dual sierpinski" and base 5 which is used to create sr5sieve. Besides multi-threading, some features are only enabled if using the GNU compiler. Those restrictions will go away. I'm hoping that by the time I'm done that srsieve2 will be fast enough that there is no reason to continue using sr1sieve, sr2sieve, or sr5sieve. There might be opportunities to optimize very specific cases even further, but that is for the future and only upon request.

2019-05-02, 09:52	#205
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2·3³·109 Posts	-r is an option I frequently use when I use srsieve. Sometimes I want longer that the default and sometimes shorter while experimenting. Output should always be controllable.

2019-05-03, 15:56	#206
rob147147 Apr 2013 Durham, UK 3²·7 Posts	I use the cache options -c/-C of sr2sieve almost all the time as it generally provides good speedups. I have also found -Q useful when building/testing my CUDA version of sr2sieve, and sometimes you can find greater speed in sr2sieve by using it to change the number of subsequences being sieved.