I don't remember if I ever mentioned this publicly, but my calculations put the optimal sieving level for GFN15 at p=26000P. As I write this, we're reserved through 25023P. Sieving for GFN16, 17, 21 and 22 will still be available. At some point in the future, I'll probably open up GFN18, 19 and 20 for further sieving.

While other n's give less credit per 1P sieved, they all give more or less the same credit per hour of sieving. Sieving higher n's is faster, so the credit rate is lower.

I don't remember if I ever mentioned this publicly, but my calculations put the optimal sieving level for GFN15 at p=26000P. As I write this, we're reserved through 25023P. Sieving for GFN16, 17, 21 and 22 will still be available. At some point in the future, I'll probably open up GFN18, 19 and 20 for further sieving.

While other n's give less credit per 1P sieved, they all give more or less the same credit per hour of sieving. Sieving higher n's is faster, so the credit rate is lower.

Could you elaborate on "optimal depth"? I really wonder what that means... well, I get the part where "optimal sieve is when you remove candidates faster by PRP testing than sieving", but that's kinda vague. See, different hardware are sure to have different depths, as one might GFN faster / slower, when normalizing per sieve speed.

Speaking of sieve, what about n=15 and strong GPUs that take multiple instances of the program running (and therefore, multiple CPU cores that could be used for PRP testing instead)? And is this optimal point considering the full b=400.000 range, or more of a "we only expect to go up until 150k in the near future" type of calculation? And perhaps even something else I'm forgetting right now...

I'm really curious as to how you / PG sees it.

I really wish people would just take my word for it once in a while... (because it took me three hours to write this).

The optimal sieving calculation is really not all that complex. I have a first-generation Titan card and any timings I'm giving involve running on that card. I'm not really interested in what other cards can do because I have no intention of building some huge model to take everything into account.

On my card, it takes 100 seconds to test (with genefer) the largest GFN15 candidate below b=400M. By using that timing, rather than the 80 seconds it takes for current leading edge candidates, my optimal sieving level is, if anything, conservative. In other words the optimal level is higher using the longer testing time. I'm going to double those times to 200 and 160 seconds to account for the fact that each genefer test is run twice, whereas each sieving range is run once.

Sieving produces a list of factors and the candidate each factor refers to. How many factors are found doesn't matter for this calculation. What matters is how many candidates are removed from the sieve file. That's because a lot of candidates have already been removed by previous sieving. In fact at the moment in GFN15 only about 14.76% of the factors found result in removals from the sieve. Those numbers are available in the sieving statistics page. I'm specifically looking at the 160P 23931P-24091P range because larger ranges give more accurate numbers. Plus it straddles 24000P, which we'll get to below.

GFN15 and GFN16 sieving cover 1<b<2G. While we currently can't make use of anything over 400M, those extra factors are "free". The algorithm used calculates them in any case so we might as well collect them. The sieving stats table for GFN15 is only reporting data for b<400M as genefer currently cannot test beyond that. But that number of factors needs to be adjusted for where we are in genefer testing GFN15 in BOINC. Factors for candidates we've already tested aren't worth anything. The leading edge of Genefer testing for n=15 is at about 42.2M, so we're really only interested in factors for b=42.4M-400M. That's 357.8M or 89.45% of the full 400M range. So, the 4447 factors resulting in removals becomes 4447*.8945=3978 usable factors. Divide that by the 160P range length and you get 24.86 removals per 1P of sieving on the 23931P-24091P range.

On my card, sieving 1P of GFN15 takes 76 minutes or 4560 seconds. On that 23931P-24091P range there were 24.86 candidates removed per 1P tested. But in 4560 seconds I can primality test 22.8 candidates at 200 seconds each (or 28.5 candidates at 160 seconds each). So sieving gives 24.86, testing gives 22.8/28.5 candidates. Sieving is superior at the moment. That 24.86 sieving number becomes 24.86*24000/26000 = 22.95 candidates at p=26000P. 22.8 and 22.95 are close enough for me to call this optimal sieving.

How about running two sieves simultaneously? On my card each range now takes a minute longer but we get double the candidates. Now I've got 49.72 removals in 4620 seconds. I can primality test 23.1 @ 200 seconds or 28.88 candidates @ 160 seconds. In this scenario, the optimal level is much higher. 49.72 / 23.1 * 24000P gives an optimal level of 51657P.

How about running three sieves simultaneously? Each range now takes 79 minutes on my card. In 4740 seconds we're removing 74.58 candidates. I can primality test 23.7 candidates on the GPU (@ 200 seconds) or 29.63 candidates @ 160 seconds. The optimal level here is 74.58 / 23.7 * 24000P = 75524P.

So why do I want to close GFN15 sieving now? First of all, not every GPU can run three sieving processes simultaneously and I'm not sure how many people bother. Plus each process requires a full CPU core to feed the GPU.

Secondly, all the higher n's are much further from optimal. GFN16 is only 1/10 of the way to optimal. I don't have numbers handy for the rest, suffice it to say they've all got a long way to go. Sieving is more valuable (more candidates removed) the further from optimal it is. We have a limited number of users willing/able to do manual sieving and I'd like to use them as efficiently as I can. We also have a lot of users who like running GFN15 in BOINC. There are far more users testing with Genefer than doing sieving. Removing a few hundred GFN15 candidates doesn't really make that much of an impact vs the 9000+ GFN15 tests done per day recently.

I'd much rather eliminate candidates for less-popular higher n's that take much longer to test. The sieving credit rate is the same per hour, as close as we could make it. If GFN15 was the only GFN sieving I'd push it higher, but it's not worth it when there are 7 other n's that could use the attention.

Secondly, all the higher n's are much further from optimal. GFN16 is only 1/10 of the way to optimal. I don't have numbers handy for the rest, suffice it to say they've all got a long way to go.

This is an indirect question to know if a GFN sieve in BOINC is to be considered.

Technically, it is possible, I have this app. I've used it myself with few remote systems. But it makes sense only with high GFN, may be starting from GFN-18, where sieving uses no CPU and can fully utilize GPU. Otherwise it's impossible to describe (in Boinc) a task which uses lot of CPU and undefined percent of GPU - the GPU will never be fully utilized.

There's no pressing need to do GFN sieving in BOINC.

Technically, it is possible, I have this app. I've used it myself with few remote systems. But it makes sense only with high GFN, may be starting from GFN-18, where sieving uses no CPU and can fully utilize GPU. Otherwise it's impossible to describe (in Boinc) a task which uses lot of CPU and undefined percent of GPU - the GPU will never be fully utilized.

Watch out for screen lag. We either go back to having a B field like the CUDA app days (which Michael once said was NOT going to happen ever again) or force people to deal with app_config and scare away many crunchers.

I'm not sure what you're referring to, but I suspect the comment you may be thinking of was about GeneferCUDA rather than the sieving app (which is also CUDA). I haven't personally done any GFN sieving in a while. Don't we still use the same app we've always used? The one with the B (block) parameter for tuning?

I've also said that new apps should be written for OCL rather than CUDA, but that's because I'd rather have an app that runs on both red and green GPUs rather than only half of them. There's nothing inherently wrong with CUDA, except, of course, that it won't run on AMD GPUs.

I'm not sure what you're referring to, but I suspect the comment you may be thinking of was about GeneferCUDA rather than the sieving app (which is also CUDA). I haven't personally done any GFN sieving in a while. Don't we still use the same app we've always used? The one with the B (block) parameter for tuning?

I've also said that new apps should be written for OCL rather than CUDA, but that's because I'd rather have an app that runs on both red and green GPUs rather than only half of them. There's nothing inherently wrong with CUDA, except, of course, that it won't run on AMD GPUs.

Remember the days when we crunched GFN with the CUDA app? Yeah, in those days, there was a B parameter that the user could select in the preferences page. When proposing that such option was made available for a potential GFN SV, you've said that it was a mistake to ever allow it to show up on the site, as it raised more problems with confused users than it solved, so such solution would never be implemented ever again.

Do you have a link to that? I'd like to see precisely what I said. Perhaps I was just having a grumpy day.

Or maybe I'm just forgetting the ugly parts. :)

Although we initially went that way with CUDA and block sizes, we replaced it with an internal self-optimization that would select the fastest block size. Offering a user selectable block size was a mistake I'm not looking to repeat.

Do you have a link to that? I'd like to see precisely what I said. Perhaps I was just having a grumpy day.

Or maybe I'm just forgetting the ugly parts. :)

Perhaps http://www.primegrid.com/forum_thread.php?id=6576&nowrap=true#92302?

Although we initially went that way with CUDA and block sizes, we replaced it with an internal self-optimization that would select the fastest block size. Offering a user selectable block size was a mistake I'm not looking to repeat.

Do you have a link to that? I'd like to see precisely what I said. Perhaps I was just having a grumpy day.

Or maybe I'm just forgetting the ugly parts. :)

Perhaps http://www.primegrid.com/forum_thread.php?id=6576&nowrap=true#92302?

Although we initially went that way with CUDA and block sizes, we replaced it with an internal self-optimization that would select the fastest block size. Offering a user selectable block size was a mistake I'm not looking to repeat.

^This.

Now, I get that it was referring to selecting the GFN transform, but the same idea still applies for a hypothetical GFN SV.

My question was not "is it possible to run a GFN sieve 'efficiently' (i.e. CPU load ~0 and no screen lag)?" because to my point of view the answer is yes.
If the GPU tasks are too small, the CPU load is high. If they are too big, screen lags can happen. The duration of a GPU task should be > 100 µs and < 1 ms. In OpenCL, some profiling commands can be used to measure this time accurately (with a GPU timer). Then we can set block size such that duration ~ 500 µs during the initialisation of the program.

My question is: "Let n = 20. According to http://www.primegrid.com/server_status_tasks.php, genefer execution time on GPU is ~ 10 hours. How many candidates does the sieve remove in 10 hours?". Of course if the reference GPU is a Titan, 10 => 4 hours.

If the answer is 5 or 10 candidates then a GFN sieve in BOINC is to be considered!
Then we can also study the algorithm. Today the sieve is based on http://fatphil.org/maths/GFN/maths.html (no?). Is it really more efficient than trial divisions if we want to sieve a small range first (800,000-2,000,000 for n=20) and when divisors are large? Pollard's P−1 may be efficient too.

I don't have those answers at the moment and real life is going to keep me from calculating them for a few days. Meanwhile I've enabled sieving on GFN18, GFN19 and GFN20. I don't remember any more why they weren't turned on originally - possibly because genefer couldn't test very high on GPU back then and we were optimal for the more limited b-range then possible.

We don't have any plans to start GFN sieving on BOINC. While we're not at optimal levels we're far more heavily sieved than we ever thought possible before the availability of GPU-based sieving. Moving the sieves to BOINC has costs in both time and impact on the server. We don't feel those costs are worth it at this time.

I'll have a good answer on that in a few days, between Christmas and New Years Day some time. I have to either find all my timings from the last time I did this (which is probably before I obtained the Titan card) or redo them all.

Personally I'd sieve GFN17 at the moment as we're pulling candidates from two different places in the sieve file.

Here is an estimate on a slow computer (i3-3217U + GeForce GT 740M).

It takes 39 h 20 mn to test 900000^2^20+1 with genefer/ocl4.

The sieve/ocl finds about 6 factors / mn around 40000P, then approximately 14000 factors for about 39 h 20 mn.

63.8% candidates were already removed from sieve then 14000 * (1 - 0.638) ~ 5000 new candidates are removed from sieve.

The range of the sieve is b in [2-2.10^9] and 5000 / 2.10^9 = 1 / 400000.

The optimal sieving calculation depends on the goal. At n=20, the goal is at least one prime, ten primes within a few years.
The expected number of primes (n=20) is 1 at b ~ 900,000, 2 at b ~ 2,000,000 and 10 at b ~ 11,000,000.
If the target is ten GFN20 primes, the range is b in [2-12,000,000]. In this range, the sieve removes 30 candidates when genefer removes one.
But of course if we want to find one prime, genefer can do it but not the sieve, the dilemma of sieving...