A multiple k/c sieve for Sierpinski/Riesel problems

[mdettweiler]

Originally Posted by geoff

In practice, yes. (Actually it doesn't get set to normal priority, it just doesn't set the priority at all. So without -z, -Z, etc. sr2sieve will run at the same priority as the process that started it. In most cases that will be normal priority).

If anyone has a better plan then this is the time to say so. The problem with the old way of doing it (idle priority by default) is that I am getting a lot of questions about why sr2sieve is running slower on 64-bit operating systems than on 32-bit systems, which is because the (newer) 64-bit OS lowers the CPU frequency in situations that the (older) 32-bit OS doesn't.

Ah, I see. Actually, from my personal experience, I've noticed that certain versions of Ubuntu (i.e., all recent versions except 7.10) will incorrectly remain scaled down regardless of whether it's 32-bit or 64-bit (or, rather, I've only ever seen it happen on 32-bit, but from what I've picked up from some Google searches, it seems to be an across-the-board thing). I don't know whether or not Windows is affected by this, though I'm pretty sure it's not. (Probably a number of other Linux distros other than Ubuntu have a similar issue, though the only one I've had experience with in this way is Ubuntu.)

I have, however, found a somewhat easy way to work around this issue (on Linux, at least): install some of those little "CPU Frequency Scaling Monitor" widgets on your taskbar (one for each core) and set each one to Performance mode (i.e. always remain at full power except in case of CPU temperature emergency). Unfortunately, this is reset every time the computer is restarted, but once you get a habit of adjusting the widgets every time you start the computer, it's not a problem.

In case this is helpful for anyone else, I put together some instructions on how to do this a little while back for a friend who's also using affected versions of Ubuntu. The instructions should also work for any other GNOME-based Linux installation (and can probably be adapted for KDE):
---------------------------
-Right-click on the upper taskbar (at the top of the screen). Click Add to Panel.

-From the list that appears, click "CPU Frequency Scaling Monitor". Click Add. You will now see, on your upper taskbar, a little thing that shows a computer-chip icon, a little bar next to that, and a number representing the current CPU frequency. Click Add again. Once another one of those doodads has appeared, click Add again. Repeat yet again after that, so you have four CPU Frequency Scaling Monitor applets on your taskbar (one for each core).

-Right-click on the first one (i.e. the one farthest to the left) and click Preferences. Make sure that the "Monitored CPU" drop-down box is set to "CPU 0". Click Close.

-Repeat for the other three applets, selecting "CPU 1", "CPU 2", and "CPU 3", etc., respectively. You now have one applet set for each core.

-With prime search apps running on all four cores, look at the four monitors. Do they show the full clock speed of your CPU? Are the capacity bars on each full filled in, in green? If not, your CPU is not running at full capacity, and you should proceed with these instructions. If all checks out, you're doing fine and you need not continue further.

-If you are not running at full capacity, open a terminal and type the command "sudo dpkg-reconfigure gnome-applets" and press Enter. You will be prompted for your password. You will then see a blue and grey screen with a bunch of technobabble fill your terminal window. Press Enter. It will ask "Should cpufreq-selector run with root privileges?" Use the arrow keys to make sure "Yes" is highlighted in red, and press Enter. You will now be dumped back at the terminal prompt; close the terminal window.

-Click on the first CPU Frequency Scaling Monitor applet, and choose "Performance" from the drop-down list. (*If it's grayed out, see below.) After selecting "Performance", you should see the capacity bar turn green and be fully filled in, and the number next to it should shwo the full clock speed rating of your CPU.

Now you should be all set, and you should notice a marked increase in speed! Please keep this in mind, though: these settings are reset each time you restart the computer. Thus, each time you start up the computer, make sure that the first thing you do is to click on each of the applets and choose "Performance" mode, so that all your the applets show green and that the numbers read equivalent to your CPU's full capacity.

*If the choices in the applet's drop-down menus were grayed out even after doing the stuff in the terminal, try rebooting your computer. If that doesn't work, send me a note because something's gone wrong.
---------------------------
I hope this is useful!

Anon

[Cruelty]

I've been running sr(x)sieve on several 64-bit Ubuntu distributions (6.10, 7.04, 7.10, 8.04) and I have never had an issue with OS adjusting frequency of the CPU. Simple solution: disable all advanced CPU features in BIOS (e.g. EIST, speed-step, thermal monitoring, Cool'n'Quiet, etc.)

[mdettweiler]

Originally Posted by Cruelty

I've been running sr(x)sieve on several 64-bit Ubuntu distributions (6.10, 7.04, 7.10, 8.04) and I have never had an issue with OS adjusting frequency of the CPU. Simple solution: disable all advanced CPU features in BIOS (e.g. EIST, speed-step, thermal monitoring, Cool'n'Quiet, etc.)

Oh yeah, duh! I don't know why I didn't think of that. Okay, I think I'll try that next time I get the chance to go into my BIOS--and I'll recommend it for my friend for some new machines that he's getting and that will probably be affected!

[geoff]

The underlying problem is that distributed computing applications are expected to use only spare cycles. In the old days running at idle priority achieved this nicely. But what is a `spare' cycle now that the operating system can vary the number that are produced?

[mdettweiler]

Originally Posted by geoff

The underlying problem is that distributed computing applications are expected to use only spare cycles. In the old days running at idle priority achieved this nicely. But what is a `spare' cycle now that the operating system can vary the number that are produced?

Hmm, I see. I guess if you think about it, there are still plenty of "spare" cycles hanging around even if the CPU is at, say, half-clock (I don't usually desktop CPU's go lower than half their rated clock speed even when fully idle)--though definitely not as much as when it's at full clock.

Yeah, I guess it is a good idea to have sr(x)sieve stay at normal priority by default. Maybe it would be helpful, though, to have the program output an easily-noticeable warning message each time it starts at normal priority, just to give users a heads-up that if their system doesn't have any problems with auto-downclocking in regard to lowest-priority apps, to run it with the -z or -zz options to avoid potential resource conflicts with "higher-priority" apps.

[geoff]

If the sr2sieve-command-line.txt file has a DOS end-of-line marker then the Linux executables will stop with an error when trying to read it. I will fix this shortly.

This only applies to the -command-line.txt file, other files should be read correctly regardless of whether they have DOS or UNIX end-of-line markers.

[geoff]

The only visible change is that the process priority is no longer changed by default: if you want to run at idle priority as in earlier versions then you will need to add -zz to the command line.

The algorithm has been improved to avoid the need to compute 1/k mod p for each p, but since sr1sieve only ever has a single k in the sieve the gain is barely noticeable in most cases.

[Cruelty]

What about sr2sieve v1.8.2? What has changed since 1.8.1?

[geoff]

Originally Posted by Cruelty

What about sr2sieve v1.8.2? What has changed since 1.8.1?

sr2sieve 1.8.2 fixes a problem reading DOS format sr2sieve-command-line.txt files on Linux. (Also fixed in sr1sieve 1.4.0).

[Cruelty]

Below is an output from sr2sieve under Linux_x64. Although benchmark for ladder method indicates that "gen/6" is the fastest the program chooses "gen/4"...

sr2sieve 1.8.2 -- A sieve for multiple sequences k*b^n+/-1 or b^n+/-k.
Compiled on Sep 23 2008 with GCC 3.4.6 (Debian 3.4.6-1).
SSE2 code path, L1 data cache 32Kb (detected), L2 cache 4096Kb (detected).
Read 49695 terms for 4 sequences from ABCD format file `sr2data.txt'.
Split 4 base 10 sequences into 35 base 10^60 subsequences.
Using 93Kb for subsequence congruence tables.
Using 8 Kb for the baby-steps giant-steps hashtable, maximum density 0.16.
Best time for baby step method gen/2: 10692.
Best time for baby step method gen/4: 7848.
Best time for baby step method gen/6: 7911.
Best time for baby step method gen/8: 7461.
Best time for ladder method gen/2: 1044.
Best time for ladder method gen/4: 729.
Best time for ladder method gen/6: 702.
Best time for ladder method gen/8: 738.
Best time for ladder method add/1: 1089.
Baby step method gen/8, giant step method new/4, ladder method gen/4.
BSGS range: 120*112 - 671*20.
Using 2048Kb for the Sieve of Eratosthenes bitmap.
Expecting to find factors for about 675.84 terms in this range.
sr2sieve 1.8.2 started: 195028 <= n <= 999976, 9928865958919 <= p <= 15000000000000

[geoff]

Originally Posted by Cruelty

Below is an output from sr2sieve under Linux_x64. Although benchmark for ladder method indicates that "gen/6" is the fastest the program chooses "gen/4"...

This is deliberate, the gen/6 methods were written to suit AMD and will not currently be selected on Intels. In testing on my Core 2 I found that although they ran fast during the benchmarks, they ran slower during actual sieving.

For the baby-steps you can select the gen/6 method manually using the switch -Bgen/6, but there isn't a way to manually select the ladder methods (I should add one).