Sieved files/sieving coordination

[gd_barnes]

Originally Posted by Anonymous

Okay, that's fine with me. In the meantime, we might want to see about finding an always-on computer that can run the LLRNet server--Gary, would any of your crunchers possibly work? Even if running this Sierpinski Base 4 k on it fell through, there's plenty of other bases/k's that would be great for LLRNet. (For bases that are powers of 2, you simply use the stock LLRNet client; for other bases, you can use the version modified by the Sierpinski/Riesel Base 5 project.)

My crunchers are unbelievably busy right now. All my machines (12 cores total) are on 24/7 but I only have one machine, a Dell core-duo, that is connected to the internet 24/7 that is worthy of LLRing. (The Athlon that I have connected is used only for sieving...too slow at LLRing.) It is dedicated to this effort and both of its cores are currently sieving Sierp base 16. Then there's starting on both sides of base 256, Riesel base 16, and Sierp base 6. I think these are all higher priority than anything else on this effort. I expect in 4 weeks, I'll be able to free up a couple of cores from an RPS effort to put a total of 4 cores on this effort. At that point, I would be able to dedicate my connected Duo to an LLRnet effort.

Originally Posted by Anonymous

Yes, LLRNet doesn't affect the reporting of a prime--it's reported the same as if it was done with manual LLR. Thus, the reporting would be exactly the same as if the prime was found by someone who was testing those numbers normally.

Very good. So...whomever's machine it is running on at the time a prime is found would report it? For instance, if a sieved file ends up being tested across multiple people's machines, will the person whose machine finds the prime need to report it? What if they know little about reporting large primes? (I guess I should assume that if you are setting up your machine as an LLRNet server that you'd know about such things but I can't be too sure here.)


Thanks,
Gary

[mdettweiler]

Originally Posted by gd_barnes

My crunchers are unbelievably busy right now. All my machines (12 cores total) are on 24/7 but I only have one machine, a Dell core-duo, that is connected to the internet 24/7 that is worthy of LLRing. (The Athlon that I have connected is used only for sieving...too slow at LLRing.) It is dedicated to this effort and both of its cores are currently sieving Sierp base 16. Then there's starting on both sides of base 256, Riesel base 16, and Sierp base 6. I think these are all higher priority than anything else on this effort. I expect in 4 weeks, I'll be able to free up a couple of cores from an RPS effort to put a total of 4 cores on this effort. At that point, I would be able to dedicate my connected Duo to an LLRnet effort.

It seems like you're thinking LLRNet is something different than it is, and that you've misunderstood my question about your machines (my bad, I could have worded it more clearly). LLRNet is a client-server setup for LLR, sort of like BOINC in the sense that it's automated, except much more simple, and specialized to LLR. You run the server part on one machine--you give it a sieved file as input (just like you would with regular LLR), and specify some server settings. Then, when clients, using the LLRNet client software, connect to the server, the server hands out one test (or more, if they specified so in their client settings) to the client. The client crunches it, then sends the results back to the server. The server then amalgamates the result into a main file (sort of like an lresults file, but with more information, such as what user did the test, and when it was reported as complete).

The LLRNet server component is, as far as I know, very resource-light. It's not CPU-intensive (the actual work is done only by the client app--though of course if you want, the server can run the client app simultaneously and connect to itself, if you want to get work from the LLRNet queue). It can run in the background on the server computer, while your normal distributed computing apps do their own work as normal.

Think of it as like running a small, low-traffic web server on the computer--except that instead of serving up web pages it's serving up LLR tests.

Very good. So...whomever's machine it is running on at the time a prime is found would report it? For instance, if a sieved file ends up being tested across multiple people's machines, will the person whose machine finds the prime need to report it? What if they know little about reporting large primes? (I guess I should assume that if you are setting up your machine as an LLRNet server that you'd know about such things but I can't be too sure here.)

Each user who wants to receive work from the LLRNet server needs to specify a username to their LLRNet client--in this case it should be the same as their mersenneforum username. When results are received by the server, it keeps track of who returned what results--so if a prime is returned, I (or you, for that matter) could see exactly who turned in that result and when. Also, the LLRNet client keeps a local lresults.txt file so the user can keep a log of what tests he's done.

Primes are reported by the user whose computer's LLRNet client returned the prime--just the same as they would be in a regular team drive, where the user that tested the prime candidate reports it.

LLRNet is sort of like any old team drive, except that it's done automatically over the internet.

Thanks,
Gary

[gd_barnes]

That's clear now! Thanks for the detailed explanation. Server = distributor of something; not what is doing the actual testing. That should be a big duh on my part.

Yep, I have a 24x7 connected Athlon that is my sieving machine that could be the server. Even if the server slightly slows down the sieving; no big deal.

Can you start checking into it now? Even if someone picks up k=64494 for Sierp base 4, I'm sure we could use this for other efforts.

I'm thinking an LLRNet server will work best for distributing annoying tasks such as testing on bases that are not multiples of 2 that are taking quite a while but that are not quite top-5000.


Gary

[mdettweiler]

Originally Posted by gd_barnes

That's clear now! Thanks for the detailed explanation. Server = distributor of something; not what is doing the actual testing. That should be a big duh on my part.

Yep, I have a 24x7 connected Athlon that is my sieving machine that could be the server. Even if the server slightly slows down the sieving; no big deal.

Can you start checking into it now? Even if someone picks up k=64494 for Sierp base 4, I'm sure we could use this for other efforts.

I'm thinking an LLRNet server will work best for distributing annoying tasks such as testing on bases that are not multiples of 2 that are taking quite a while but that are not quite top-5000.


Gary

Actually, I've already done some checking into it. I'm sending you a PM with all the necessary details right after posting this.

[gd_barnes]

Sieving on Sierp base 16 for n=25K-200K has completed to P=400G. Separate sieved files for each k have now been uploaded to the Sierp Base 16 reservations web page.

I chose to keep reserved k's in the sieve to help out some with those because it saved little extra time to delete them. If you have a reserved k and hadn't already sieved to P=400G, downloading the sieved file will probably save you doing some tests.

The sieve depth should be more than sufficient for n=100K but if no prime is found by that point, I don't recommend testing above that limit until they have been further sieved. I'm now estimating an optimum sieve depth of P=1.7T-2T for testing up to n=200K.


Gary

[mdettweiler]

Originally Posted by gd_barnes

Sieving on Sierp base 16 for n=25K-200K has completed to P=400G. Separate sieved files for each k have now been uploaded to the Sierp Base 16 reservations web page.

I chose to keep reserved k's in the sieve to help out some with those because it saved little extra time to delete them. If you have a reserved k and hadn't already sieved to P=400G, downloading the sieved file will probably save you doing some tests.

The sieve depth should be more than sufficient for n=100K but if no prime is found by that point, I don't recommend testing above that limit until they have been further sieved. I'm now estimating an optimum sieve depth of P=1.7T-2T for testing up to n=200K.


Gary

I only sieved to p=120G for k=2908, which was way past optimal depth, but I'll download the sieve file for it anyway when I get around to it, since it would still have some more candidates removed.

[gd_barnes]

Sieving on Riesel base 16 for n=25K-200K started yesterday on the remaining 33 k's. It is currently nearing P=100G for all k's. Initially, I'll be sieving to P=400G, which should be complete by Wed. morning. Sometime on Wed., I'll post separate sieved files for all k's similar to the Sierp side. That sieving depth should be sufficient for testing beyond n=100K but not to n=200K so I'll sieve it more later.

When the above is done, I'll switch back to sieving Sierp base 16.


Gary

[gd_barnes]

Sieving on Riesel base 16 for n=25K-200K has completed to P=400G. Separate sieved files for each k have now been uploaded to the Riesel Base 16 reservations web page for the range of n=25K-100K. I'll call this one 'big bad sieved file #2'.

Although I am sieving the range of 25-200, I chose to only post the smaller range of 25-100. I also changed the Sierp files to only include the smaller range. The files aren't sieved far enough for testing much beyond n=100K on most k's and I thought it would create confusion to leave them as they were.

Sieving is now continuing on Sierp 'big bad sieved file #1'. K's with a prime have been removed. Thanks for saving sieving time Anon and Tnerual! It'll probably be about 1 to 1-1/2 weeks before we get the team drive going.


Gary

[VBCurtis]

I find this project's intent makes calculating optimal sieve depth an interesting question. Conceptually, we should take into account the cumulative probability of finding a prime in the first x% of a sieve file, which makes the rest of the file useless. If I find myself with a large real-world project that needs procrastinating, I'll likely tackle this and make some estimates for single-k sieves.

For searches you don't really expect a prime (very low weight k, small n-range), you should use Gary's 70% rule of thumb- sieve until factor-found rate is equal to LLR rate for n-value 70% of the way from n-min to n-max. For searches where a prime is likely (say, a sieve from 25k to 200k), LLR testing should be done in stages up to roughly n-min= (0.5)n-max, then apply the 70% rule on the last part of the sieve, rounding down a bit for the chance of prime-finding. Those stages should be LLRed when the largest n in a range LLRs at about the same time as factor-found rate.

Finally, a general rule: sieving within 20% of the optimal sieve depth is good enough, in either direction. oversieving by 20% will waste very little time, ditto undersieving by 20%. Something like 10-20 hours out of a month's effort! That said, if you have a machine very well suited to sieving that sometimes is forced into LLR duty, you should consider over-sieving a bit to best use that machine- it will cut the time your LLR machines need, though the overall project effort-required may rise a tiny bit from the "wasting" of your sieving CPU time.

Finally-er: for most searches where the entire file will be processed, 5% of the overall processing time is spent on an optimal sieve. If you sieve for 1 day and LLR for 5, you sieved too far. If you sieve one day and LLR for 50, you didn't sieve enough- in this case, a 2nd day sieving would likely have saved 2 days of LLR. This is a pleasant hindsight tool, not much more than that.

Riesel 28:
5886 complete to 25k.
-Curtis

[gd_barnes]

Originally Posted by VBCurtis

I find this project's intent makes calculating optimal sieve depth an interesting question. Conceptually, we should take into account the cumulative probability of finding a prime in the first x% of a sieve file, which makes the rest of the file useless. If I find myself with a large real-world project that needs procrastinating, I'll likely tackle this and make some estimates for single-k sieves.

For searches you don't really expect a prime (very low weight k, small n-range), you should use Gary's 70% rule of thumb- sieve until factor-found rate is equal to LLR rate for n-value 70% of the way from n-min to n-max. For searches where a prime is likely (say, a sieve from 25k to 200k), LLR testing should be done in stages up to roughly n-min= (0.5)n-max, then apply the 70% rule on the last part of the sieve, rounding down a bit for the chance of prime-finding. Those stages should be LLRed when the largest n in a range LLRs at about the same time as factor-found rate.

Finally, a general rule: sieving within 20% of the optimal sieve depth is good enough, in either direction. oversieving by 20% will waste very little time, ditto undersieving by 20%. Something like 10-20 hours out of a month's effort! That said, if you have a machine very well suited to sieving that sometimes is forced into LLR duty, you should consider over-sieving a bit to best use that machine- it will cut the time your LLR machines need, though the overall project effort-required may rise a tiny bit from the "wasting" of your sieving CPU time.

Finally-er: for most searches where the entire file will be processed, 5% of the overall processing time is spent on an optimal sieve. If you sieve for 1 day and LLR for 5, you sieved too far. If you sieve one day and LLR for 50, you didn't sieve enough- in this case, a 2nd day sieving would likely have saved 2 days of LLR. This is a pleasant hindsight tool, not much more than that.

Riesel 28:
5886 complete to 25k.
-Curtis

Thanks Curtis for the detailed analysis. The cumulative probability of finding a prime is a most interesting question regarding sieving. This entire project is full of interesting mathematical analysis/calculations that are needed like algebraic factors/GFN's/k's that are a multiple of the base/optimal sieving depth/etc.

As a general rule, I've been sieving until the removal rate was about 10% less than the LLR rate at the 70% n-range to account for the possibility of a prime.

FYI for everyone, to the best of my knowledge it was Curtis who came up with the 70% rule so I can't take credit for it. It has to do with the fact that LLR time varies by the square of n, i.e. sqrt(0.5) = ~0.7.

I'm now nearing P=600G on the 'big sieve' for Sierp Base 16 (will be done Friday morning) and have now concluded what Curtis stated here. Sieving n=25K-200K is too large of an n-range for sieving for such a project. Therefore, I think I'll start a team drive for n=25K-100K and continue sieving on n=100K-200K while removing k's as primes are found. The same thing on Riesel Base 16. I've sieved n=25K-200K to P=400G. I'll take it up to P=600G and do the same as the Sierp side.

Curtis, part of that was a completely new learning experience for me. I could never quite figure out how to decide when to break off sieving pieces of a large sieved n-range like you are doing for k=5 at RPS. Sieving each piece to the n-max LLR rate of that piece makes a lot of sense. Brilliant! I intuitavely knew that it couldn't be the 70% n-range of each piece. In the n=25K-100K case above, the P=600G removal rate is nearing the LLR test rate at n=100K so now the entire range can be tested. So technically the lower n-range was somewhat over-sieved. (I'm sure people won't mind though.)

So everyone, look for a thread titled 'Conjectures team drive #1' (or something similar) in the next couple of days. There will be n-ranges of the 'big sieve file' for Sierp base 16 split up for everyone to have fun with. I'll also post it in the news when the drive starts.


Gary

[VBCurtis]

Originally Posted by gd_barnes

Thanks Curtis for the detailed analysis. The cumulative probability of finding a prime is a most interesting question regarding sieving. This entire project is full of interesting mathematical analysis/calculations that are needed like algebraic factors/GFN's/k's that are a multiple of the base/optimal sieving depth/etc.

Curtis, part of that was a completely new learning experience for me. I could never quite figure out how to decide when to break off sieving pieces of a large sieved n-range like you are doing for k=5 at RPS. Sieving each piece to the n-max LLR rate of that piece makes a lot of sense. Brilliant! I intuitavely knew that it couldn't be the 70% n-range of each piece. In the n=25K-100K case above, the P=600G removal rate is nearing the LLR test rate at n=100K so now the entire range can be tested. So technically the lower n-range was somewhat over-sieved. (I'm sure people won't mind though.)

Gary

You're welcome for the analysis. The k=5 or multi-k sieve calculation of when to break off pieces is quite a bit different, though- I simplified and rounded down a great deal for this project because of the "Wasted sieve" effect of finding a prime earlier. For Conjectures R us, we should test rather earlier than optimal because of the sizable shrink in project time every time a prime is found and k removed.

Fair warning: remainder of post is off-topic for this forum, just sieving discussion.

The k=5/multi-k analysis is done by a marginal analysis. I did some trial and error testing, comparing the marginal speedup in the sieve from breaking off a range versus the lost factors from not leaving that range in. I learned that while the sieve in principle has speed inversely proportional to the square root of n-range, in practice breaking off a small range produces almost no speedup- at the cost of finding fewer factors per p tested (fewer candidates in sieve means fewer factors per p-range). Extensive experimentation showed me that for the "big sieve" sheep is running, a range should be broken off when factors-found time is equal to 2.2 to 2.3 times the LLR rate for that range!!! This is how I arrived at 250T as optimal for 1250k LLR tests, and why I ignored all of your opinions that I had sieved enough at 60T. I'd done the calculations, and I am quite sure of what I am doing.
The actual calculation consisted of calculating the time to sieve the next 10T block with the lowest range (I used 50k range-pieces) left in, and the time to sieve with it removed. I then noted the expected factors found for each case. If the time saved from sieving with the range removed was not enough to LLR the difference in expected factors, the small range stayed in.

The upshot of this is that when sieving a large range and planning to test the entire sieve, break off pieces when factors-found time is *double* LLR time for a range, until that time is also equal to the LLR time for the 70% point of the entire sieve. At that point, the sieve is complete. For my big sieve, this will happen at 800T or so.

-Curtis