321 Prime Search

[pschoefer]

Beim Subprojekt 321 Prime Search wurden zunächst Zahlen der Form 3*2^n-1 für 0<n<5M (M=Mega=10^6=1.000.000) untersucht, derzeit sind die Zahlen der Form 3*2^n+1 für den gleichen Bereich im Fokus. Sobald der derzeitige Bereich vollständig bearbeitet ist, soll die Suche für beide Formen parallel fortgesetzt werden. Wie bei jeder Primzahlsuche, ist es sehr sinnvoll, zunächst möglichst viele Primzahlkandidaten auszusieben, in dem man versucht, die Kandidaten durch kleinere Zahlen zu teilen. Eine solche Division ist im Gegensatz zu einem LLR-Primzahltest sehr schnell durchgeführt, also können mit relativ wenig Rechenaufwand sehr viele Stunden (sogar viele Jahre!) CPU-Zeit eingespart werden, denn wenn eine Zahl einen Faktor hat, ist sie nicht prim.

Derzeit wird für die 321 Prime Search im Bereich 5M<n<25M ein Sieving mit dem Programm sr2sieve von Geoff Reynolds durchgeführt (das gleiche Programm kommt auch für die beiden PG-Subprojekte PSP sieve und PPS sieve zum Einsatz). Mangels Ressourcen wird dieses Sieving allerdings nicht als Subprojekt unter BOINC eingebunden, sondern manuell durchgeführt. Dennoch bekommt man für diese Arbeit BOINC-Credits gutgeschrieben (wobei es einige Zeit dauern kann, weil das alles manuell gemacht wird)!

Und so funktioniert's (siehe auch englische Beschreibung bei PrimeGrid):

Achtung! Seit dem 17.02.2009 ist 321 Prime Search (Sieve) unter BOINC verfügbar, das manuelle Sieving ist geschlossen!

1. Herunterladen der Software
Es wird das Programm sr2sieve in der Version 1.8.2 verwendet. Diese findet sich für Windows und Linux, jeweils x86 (32bit) und x86-64 (64bit) in einem Zip-Archiv auf http://pgllr.mine.nu/PGSIEVE321/software/ (der Sourcecode ist verfügbar, wer also ein anderes System wie Mac, Solaris oder BSD und ein wenig Know-How hat, kann sich die Software selbst kompilieren). Die Datei sr2sieve-command-line.txt sollte ebenfalls heruntergeladen werden.

2. Vorbereitung
Als nächstes muss die Software entpackt werden. Auf Mehrkern-Rechnern unter Windows muss man für jeden Kern, auf dem das Programm laufen soll, ein extra Verzeichnis anlegen und die sr2sieve.exe und die sr2sieve-command-line.txt dorthin kopieren, unter Linux reicht ein Verzeichnis (da gibt es einen Schalter in der command-line, um das Programm auf mehreren Kernen laufen zu lassen). Außerdem muss noch das Sievefile (die Liste der Kandidaten) heruntergeladen werden, zu finden auf http://pgllr.mine.nu/PGSIEVE321/sievefiles/. Dabei sollte man immer die aktuelle Version nehmen, derzeit ist das die 321comb5M-25M_230TE0.txt.

3. Reservieren eines Bereiches
Um zu verhindern, dass mehrere User das gleiche rechnen, ist Koordination natürlich besonders wichtig. Hierfür gibt es den Thread 321 Sieving Reservation. Dort ist eine Liste zu finden, wer welchen Bereich reserviert hat (man sollte aber immer auch einen Blick in die nachfolgenden Posts werfen, ob schon jemand etwas neues reserviert hat). Um selbst etwas zu reservieren, schreibt man einfach einen Post in der Form "Reserving Bereich Username", also z.B. Reserving 98T-100T pschoefer.

4. Anpassen der sr2sieve-command-line.txt
Bevor es dann losgehen kann, muss die Kommandozeilendatei angepasst werden. Die Vorlage sieht wie folgt aus:
sr2sieve -p##e12 -P##e12 -i321comb5M-25M_230TE0.txt -f321_5M-25M_##T-##Tf.txt -t4 -q -Z
Die einzelnen Schalter bedeuten folgendes:
-p##e12: untere Grenze der Zahlen, durch die geteilt werden soll; ##e12 bedeutet ##*10^12 (10^12=1T (Tera)=1.000.000.000.000)
-P##e12: obere Grenze
-i321comb5M-25M_230TE0.txt: der Dateiname der zu verwendenden Kandidatenliste, in diesem Fall also 321comb5M-25M_230TE0.txt
-f321_5M-25M_##T-##Tf.txt: die Datei, in die gefundene Faktoren geschrieben werden sollen, in diesem Fall also 321_5M-25M_##T-##Tf.txt
-t4: die Arbeit wird auf 4 Kerne/Threads verteilt (funktioniert nur unter Linux)
-q: gefundene Faktoren werden nur in die unter -f angegebene Datei geschrieben und nicht im sr2sieve-Fenster angezeigt
-Z: die Priorität wird auf 0 gesetzt (nur Linux)

Die ## ersetzt man nun durch die Grenzen des reservierten Bereiches, in meinem Beispiel (98T-100T) würde die Datei dann also so aussehen:
sr2sieve -p98e12 -P100e12 -i321comb5M-25M_230TE0.txt -f321_5M-25M_98T-100Tf.txt -t4 -q -Z

Unter Windows funktioniert der Schalter -t nicht, dort muss man die Arbeit manuell auf die Kerne aufteilen!
Möchte man auf einem Windows-Rechner mehrere Kerne nutzen, muss man für jeden Kern ein eigenes Verzeichnis mit der sr2sieve.exe und der sr2sieve-command-line.txt erstellen. Es empfiehlt sich dann, das Sievefile im übergeordneten Verzeichnis zu speichern und auch die Faktordatei dorthin schreiben zu lassen. Wenn ich also den Bereich von 98T-100T gleichmäßig auf 4 Kerne aufteilen möchte, sehen die 4 sr2sieve-command-line.txt-Dateien so aus:
sr2sieve -p98e12 -P98500e9 -i..\321comb5M-25M_230TE0.txt -f..\321_5M-25M_98T-100Tf.txt
sr2sieve -p98500e9 -P99e12 -i..\321comb5M-25M_230TE0.txt -f..\321_5M-25M_98T-100Tf.txt
sr2sieve -p99e12 -P99500e9 -i..\321comb5M-25M_230TE0.txt -f..\321_5M-25M_98T-100Tf.txt
sr2sieve -p99500e9 -P100e12 -i..\321comb5M-25M_230TE0.txt -f..\321_5M-25M_98T-100Tf.txt

Man beachte:
-Jeder Kern berechnet einen Bereich von 0.5T (=500G, G=Giga=10^9=1.000.000.000), man darf aber z.B. für 98.5T als Obergrenze nicht -P98.5e12 schreiben, sondern muss das in -P98500e9 umrechnen.
-durch das ..\ bei den Angaben zum Sievefile und der Faktordatei wird das übergeordnete Verzeichnis aufgerufen; alle 4 Threads nutzen das gleiche Sievefile und schreiben ihre gefundenen Faktoren in die gleiche Datei

5. Ausführen
Das Schlimmste ist geschafft, jetzt muss nur noch die sr2sieve ausgeführt werden. Es erscheint dann ein Fenster, wo in der untersten Zeile einige Informationen zum Fortschritt stehen und eine Schätzung, wann die Berechnung fertig ist (ETA), stehen. Das Programm setzt alle 5 Minuten einen Checkpoint, wenn man es zwischendurch beenden muss, sollte man das mit der Tastenkombination Strg+C tun, dann wird der Fortschritt gespeichert und beim nächsten Start von dieser Stelle fortgesetzt.

6. Hochladen der Ergebnisdatei
Wenn das Programm bzw. auf Mehrkernern unter Windows alle Instanzen des Programmes durchgelaufen sind, muss man nur noch die Datei mit den gefundenen Faktoren (321_5M-25M_##T-##Tf.txt) hochladen. Dazu gibt es eine Upload-Seite unter http://pgllr.mine.nu/PGSIEVE321/upload321/. Dort einfach oben rechts auf Upload klicken und dann die entsprechende Datei auf dem Rechner auswählen und hochladen. Abschließend kann man noch im Reservation Thread posten, dass man fertig ist (und den nächsten Bereich reservieren ).


Ich weiß, dass das alles auf den ersten Blick vielleicht etwas kompliziert erscheint und sicherlich nicht jedermanns/jederfraus Sache ist, aber vielleicht hat ja jemand Interesse, dem Projekt auf diese Weise zu helfen.

Besonders für Offline-Rechner ist es vielleicht eine gute Alternative zu BOINC, denn es kann absolut nichts schiefgehen und nach dem ersten Einrichten beschränkt sich auch der Aufwand nur noch auf das Reservieren der Bereiche, das Anpassen der Command-Line, das Hochladen der (nur wenige kB großen) Faktordateien und nur ganz selten das Ersetzen des Sievefile durch eine neuere Version.

Auf Mehrkernrechnern können auch durchaus BOINC und sr2sieve parallel laufen. Wenn man BOINC so einstellt, dass es nicht alle Kerne benutzen darf, gibt es da keinerlei Probleme.

Zum Thema Laufzeit: Mein Q9450@3,2GHz mit WinXP x64 braucht etwa 104 Stunden für 1T auf einem Kern. Wie es von den Sieve-Projekten unter BOINC bekannt ist, gibt es auch hier einen Vorteil für 64bit-Systeme (ca. 50%).

Bei Fragen und Problemen stehen dieser Thread und das PG-Forum natürlich jederzeit zur Verfügung.

[puzzle-peter]

John schreibt, man solle die Prio auf -3 setzen. Wie macht man das? Ich habe eben testhalber

/usr/bin/nice -n -3 top

probiert, bekomme dafür allerdings die Meldung

/usr/bin/nice: das Datum kann nicht gesetzt werden: Permission denied

[pschoefer]

John schreibt, man solle die Prio auf -3 setzen. Wie macht man das?

Der Befehl lautet renice Priorität -p Prozess-ID, also in deinem Fall

renice -3 -p Prozess-ID

Die Prozess-ID kriegst du entweder im "Taskmanager" (ich weiß nicht, wie das Pendant unter Ubuntu heißt ) oder mit dem Befehl ps -ax (der zeigt alle laufenden Prozesse mit der PID an, dort dann nach sr2sieve suchen). Sollte dann beim Ausführen des renice-Befehls noch eine Fehlermeldung auftreten, versuche mal den Befehl als root auszuführen (einfach ein sudo davor und dann Password eingeben).

Es gibt sicherlich noch bessere Möglichkeiten, aber ich bin kein Linuxer und habe gerade auch keins verfügbar.

[puzzle-peter]

Merci für die schnelle Antwort! Für die Prozess-ID ist mir das Kommando top vertraut. Der Prozess müsste ja bei den größeren CPU-Verbrauchern zu finden sein. Ansonsten ps -ef |grep <username> für die eigenen Prozesse.

Es gibt da auch was grafisches, nennt sich "Systemmonitor", aber irgendwie bevorzuge ich doch die Kommandozeile

EDIT: Ich nehme alles zurück und behaupte das Gegenteil! In diesem Systemmonitor kann man nämlich die Prio ändern. Per Schieberegler Rechtsklick auf den Prozess, dann bekommt man ein Menü, das unter anderem "Change Prio" enthält. Hübsch!

Noch mehr von Edith: Mit dem Systemmonitor klappt das nicht, vermutlich muss man da als root eingeloggt sein. mit sudo renice -3 -p <pid> klappt es. Also mein kleiner Testrange läuft, ich bin gespannt!

[dh1saj]

Noch mehr von Edith: Mit dem Systemmonitor klappt das nicht, vermutlich muss man da als root eingeloggt sein. mit sudo renice -3 -p <pid> klappt es. Also mein kleiner Testrange läuft, ich bin gespannt!

"Als root eingeloggt" isnich bei Ubuntu. Geht alles nur über sudo. Für die grafischen Anwendungen ist das swiw manchmal ein bischen tricky - aber starten über ALT-F2 und dann "sudo Anwendung" klappt meistens.
Hab grad nur keine Mühle unter Hardy zur Hand....

Meine 2T Testrange läuft auch, allerdings unter Vista64 und nur unter einem Core. Die Range hat jetzt Zeit bis zum 06.09. bis ich mal wieder hier an dem Rechner vorbeikomm....

Aha, die ersten 8 Faktoren hat er schon und am 04.09 will er fertig sein. Geht ja ruckzuck. ;-)

Joe

[puzzle-peter]

So, die erste Ladung ist durch, gerade rechtzeitig zur yoyo-Aktion

Auffällig war, dass meine 3 Lattice-WUs nur ca. 70% CPU-Leistung gezogen haben, solange gesiebt wurde. Kaum war das beendet, sind sie auf 99-100% gegangen.

[puzzle-peter]

Ich komme mir etwas einsam vor hier beim manuellen Sieben. Für mich ist das klasse, weil wir im Büro etliche Rechner haben, auf denen ich keine Admin-Rechte habe. BOINC installieren ist also nicht möglich. Die Sieberei zu starten hingegen schon und da die Kisten nachts und am Wochenende ohnehin idlen würden, stört es auch niemanden.

Hat niemand mehr Lust hier mitzuhelfen? Je mehr gesiebt wird, um so besser sind später die Trefferchancen bei den LLR WUs.

[dh1saj]

Nach der Challenge wieder......
Im Moment läuft fast alles auf Woodall LLR.
Ein paar extrem lahme Gurken auf PPS LLR und ein Rechner filtriert PPS.

Joe

[Sysadm@Nbg]

Chat heute mit pschoefer
ab Montag wird manuell gesiebt im Dienst. Der Stick ist schon geladen
x)x)x)

[puzzle-peter]

Chat heute mit pschoefer
ab Montag wird manuell gesiebt im Dienst. Der Stick ist schon geladen
x)x)x)

Das klingt gut! Wie gesagt, ist das perfekt für Rechner wo man nichts installieren kann. Ich hätte ja echt mal Lust, unser Cluster zu testen. Ein paar hundert CPUs sollten einiges wegsieben können. Wenn nur die lästigen Kollegen nicht ständig arbeiten wollten

[Sysadm@Nbg]

New sieve file is available:

321comb5M-25M_55TE1.zip is the current sieve file

You can update the sieve file in the middle of a run. Just download the new sieve file, ctrl-c to stop sr2sieve, edit your command-line.txt file to reflect the name of the new sieve file, and restart sr2sieve. You are now sieving on the new file.

Wenn ich den offiziellen Post von John verstehe, kann man das sieve-File bei einem Zwischenstop ohne Probleme austauschen. Sollte man das auch machen

[pschoefer]

Wenn ich den offiziellen Post von John verstehe, kann man das sieve-File bei einem Zwischenstop ohne Probleme austauschen. Sollte man das auch machen

Schaden kann es nicht, das Sieving läuft schneller, wenn weniger Kandidaten im Sieve-File stehen.

[puzzle-peter]

Es gibt mal wieder ein neues Sieve file 321comb5M-25M_55TE2.txt

Fühle mich immer noch etwas alleine. Lennart hat seine Aktivitäten scheinbar verlagert, so dass ich zur Zeit nahezu die gesamte Sieberei inne habe.

[Sysadm@Nbg]

Fühle mich immer noch etwas alleine. Lennart hat seine Aktivitäten scheinbar verlagert, so dass ich zur Zeit nahezu die gesamte Sieberei inne habe.

Sry; aber meine AMD-Kiste im Dienst cruncht nur 5x8h; Ich hoffe Mitte der Woche meine erste Lieferung fertig zu bekommen - geht aber nicht wirklich schnell bei mir.
Muss mal schauen, ob ich ein paar Server "rekrutieren" darf ... - da idlet noch eine Menge rum - muss aber erst fragen ...

[puzzle-peter]

Genau. Ein paar idlende Workstations und Server kann man ja ruhig über Nacht beschäftigen. Dank Scheduler oder unter Linux dem at-Kommando kann man das ja abends spät genug starten und morgens beenden bevor der erste Kollege ans Arbeiten denkt. So wird niemand behindert.

[Sysadm@Nbg]

Muss mal schauen, ob ich ein paar Server "rekrutieren" darf ... - da idlet noch eine Menge rum - muss aber erst fragen ...

"Probeweise" darf ich auf zwei Win2003-Server-Kisten (32-bit-Systeme ; jeweils zwei Xeon-CPUs / 8 Threads / 2GB Ram) 4 Threads = 50% mit Priorität "IDLE" belegen; lass da jeweils mal 1T durchlaufen und dann schau mer mal weiter ...

[puzzle-peter]

Immerhin kein spontanes "Nein", das ist doch schon mal etwas! Und wenn das jetzt problemlos läuft, ist ja vielleicht noch ein Ausbau möglich.

Das sind Rechner, die ansonsten überhaupt keinen Beitrag liefern würden, da ist 50% doch schon klasse!

Gruß, Peter

[pschoefer]

Ich bin auch mal wieder an Bord, Quad braucht Futter, während er nicht im Netz ist...

[puzzle-peter]

Bin ja mal gespannt, wie das Creditsystem aussehen wird. Sie wollen es in 100T-Schritten machen. Also wenn 0-100T erledigt ist, werden die Credits gutgeschrieben. Wenn 100T-200T erledigt ist (ist bereits erledigt ) kommt der nächste Schwung usw...

Wenn ich die Rechenzeiten mit den Woodalls von der letzten Challenge vergleiche, wären 1000Cr./1T schon sehr sparsam. Was tatsächlich geplant ist - keine Ahnung. Wir werden sehen...

[pschoefer]

Es gibt wieder ein neues Sievefile (55TE3) und Version 1.8.2 von sr2sieve steht bereit. Mal schauen, ob die neue Programmversion einen ähnlichen Geschwindigkeitszuwachs bringt wie bei PPS Sieve.

Ich für meinen Teil habe nochmal 5T reserviert, mal schauen, ob das reicht, bis ich wieder Internet am Quad habe...

[puzzle-peter]

Ist die neue Applikation nur für Windows verfügbar? Von der letzten Version gab es eine _linux Variante, die sehe ich von der neuen nicht.

Edit: Sehe gerade, dass der gezippte Ordner beide Versionen enthält

[pschoefer]

Die Credits für das 321 Sieving, die gerade vergeben werden, kommen wirklich genau zur richtigen Zeit. So ist mein Output wenigstens von 0 verschieden.

[puzzle-peter]

Wo sehe ich denn, wieviele Credits und für welche range diese verteilt werden?

[Sysadm@Nbg]

nachdem pschoefer das auch nur durch eigentliches Nicht-Crunchen festgestellt hat, hab ich mal eine Anfrage gepostet:
http://www.primegrid.com/orig/forum_...rap=true#11230

[Sysadm@Nbg]

sry für den Doppelpost - hier die Antwort von

There's no specific place to see this. You'll only notice it as a bump in your normal daily production. Additionally, manual credit may take between 2 weeks and 4 months before it is awarded.

Es gibt keinen bestimmten Ort, um dies - gemeint die Credits für das manuelle Sieben - zu sehen. Du bemerkst es nur als eine Erhöhung deiner normalen täglichen Produktion. Zusätzliche Bemerkung: Die manuelle Creditvergabe kann zwischen 2 Wochen und 4 Monaten dauern