Unterstützung bei Aufsetzen eines Projekts

Rakesearch, Fermat Search, NumberFields@home, OGR, ...
Nachricht
Autor
cyrix
Taschenrechner
Taschenrechner
Beiträge: 7
Registriert: 26.01.2017 22:48

Unterstützung bei Aufsetzen eines Projekts

#1 Ungelesener Beitrag von cyrix » 14.04.2017 15:38

Hallo zusammen,

Kurzfassung: C-Programm liegt vor, Einbindung in Infrastruktur für Verteiltes Rechnen fehlt noch. Dafür wird hier Unterstützung gesucht.

Langfassung:


im Rahmen einer Diskussion auf einem Mathematik-Forum [1] entstand ein nun doch recht optimiertes Projekt, dass für alle Startzahlen unterhalb einer gegebenen oberen Schranke die Collatz-Vermutung nachweist (bzw. eher: nachrechnet; sollte sie für eine Startzahl nicht erfüllt sein, fällt das dann dabei auf).

Im Vergleich zum schon existierenden Boinc-Projekt "Collatz Conjecture" wird ein (bei angenommener gleicher Rechenleistung, die investiert wird) um eine Größenordnung höherer Durchsatz erreicht. Auch gibt es bei diesem Projekt keinerlei Dokumentation über den Zahlenbereich unterhalb der gewählten Startzahl 2^71. (Und dass das Vorgängerprojekt in seiner kurzen Laufzeit von 9 Monaten im Jahr 2008 einen mehr als doppelt so großen Bereich abgesucht haben soll als das derzeitige Projekt in seiner Laufzeit seit 2009 inkl. deutlicher Verbesserung der Hardware in dieser Zeit [derzeit sucht man bei dem Boinc-Projekt im Bereich um rund 1,4 * 2^71], ist doch sehr unglaubwürdig, zumal es auch niemand behauptet.)

Insofern erscheint es sinnvoll, die eigene Variante mal zum Vergleich zu stellen und ein wissenschaftlich sinnvolles, gerade so noch handhabbares Projekt auf die Beine zu stellen. Das Ziel ist es, die Collatz-Vermutung für alle Startzahlen < 2^67 nachzuweisen. (Der aktuelle Stand dazu stammt noch aus dem Jahr 2009 und beträgt 1,25 * 2^62.) Das ist auch deshalb ein guter Wert, weil man damit eine neue untere Schranke für die Länge eines potentiellen nicht-trivialen Collatz-Zyklus beweisen könnte. Und dies sollte dann eine Veröffentlichung wert sein, da auch dafür dann ein paar neue Betrachtungs-Methoden eingeflossen sind. (Normalerweise wäre die Schranke, bis wohin man dafür rechnen müsste, etwas höher.)

Für dieses abgesteckte Ziel würde das dabei entwickelte Programm ca. 50.000 CPU-Kern-Tage benötigen. (Eine Portierung auf GPUs ist derzeit noch nicht erfolgt, verspricht aber möglicherweise auch nur mäßige, weitere Performance-Steigerungen, da ja moderne CPUs schon Mehr-Kern-Prozessoren mit [inkl. Hyperthreading] einer nicht kleinen Anzahl an Kernen sind...) Zum Vergleich: Das Boinc-Projekt hat mittlerweile (pessimistisch gerechnet) etwa 5 Millionen CPU-Kern-Tage Rechenleistung verbraten, also etwa die hundertfache Menge dessen, was wir hier ansetzen; und dabei aber nur einen Bereich, der um einen Faktor 6 bis 8 größer ist, abgesucht.

(Dies hat auch etwas mit der zum Teil leicht anderen Neben-Fragestellung zu tun: Während das Boinc-Projekt als "Nebenprodukt" zusätzlich zur Bestätigung, dass jede betrachtete Collatz-Folge in den Zyklus 4-2-1 mündet, wird auch die Anzahl der Folgenglieder bestimmt, bis man dort ankommt. Uns interessiert dies weniger, sondern als "Nebenprodukt" eher die Frage, wie groß die Folgenglieder maximal werden, bevor man dann schließlich in den Zyklus einbiegt. Das führt dazu, dass man algorithmisch noch ein wenig mehr optimieren und so besseres Laufzeitverhalten erhalten kann.)



Tja, nun habe ich da ein soweit ganz gut schon aus-optimiertes C-Programm auf meinem Rechner liegen, und würde gern schauen, dass ich die oben genannte Laufzeit in realistischer Real-Zeit abreißen kann. Dafür bietet sich Verteiltes Rechnen an, da die Aufgabe hochgradig parallelisierbar ist. Mit 200 Kernen wäre man z.B. schon in unter einem Jahr damit fertig...

Das ist aber nun schon nicht mehr die Größenordnung, dass man das mit ein paar Freunden privat hinbekommt, sondern zumindest etwas Infrastruktur braucht. Hierfür suche ich nun Unterstützung, damit das Projekt nicht versandet. Wäre schön, wenn sich jemand fände, damit man dies auf die Beine stellen kann!


Viele Grüße
Cyrix

[1]: http://www.matheplanet.com/matheplanet/ ... id=1631565

Benutzeravatar
yoyo
Vereinsvorstand
Vereinsvorstand
Beiträge: 8045
Registriert: 17.12.2002 14:09
Wohnort: Berlin
Kontaktdaten:

Re: Unterstützung bei Aufsetzen eines Projekts

#2 Ungelesener Beitrag von yoyo » 14.04.2017 18:07

Du bekommst Mail von mir.
HILF mit im Rechenkraft-WiKi, dies gibts zu tun.
Wiki - FAQ - Verein - Chat

Bild Bild

ChristianB
Admin
Admin
Beiträge: 1920
Registriert: 23.02.2010 22:12

Re: Unterstützung bei Aufsetzen eines Projekts

#3 Ungelesener Beitrag von ChristianB » 14.04.2017 18:19

Klingt nach einem sehr interessanten Projekt. Wenn ihr Hilfe braucht schickt mir am besten eine Mail. Im Slack bin ich in letzter Zeit eher weniger.

cyrix
Taschenrechner
Taschenrechner
Beiträge: 7
Registriert: 26.01.2017 22:48

Re: Unterstützung bei Aufsetzen eines Projekts

#4 Ungelesener Beitrag von cyrix » 14.04.2017 18:29

Vielen Dank für die Angebote! Ich komme gerne darauf zurück. :)

Cyrix

Benutzeravatar
Michael H.W. Weber
Vereinsvorstand
Vereinsvorstand
Beiträge: 22417
Registriert: 07.01.2002 01:00
Wohnort: Marpurk
Kontaktdaten:

Re: Unterstützung bei Aufsetzen eines Projekts

#5 Ungelesener Beitrag von Michael H.W. Weber » 18.04.2017 15:00

...kann man wohl in Yoyo@home einklinken...

Michael.
Fördern, kooperieren und konstruieren statt fordern, konkurrieren und konsumieren.

http://signature.statseb.fr I: Kaputte Seite A
http://signature.statseb.fr II: Kaputte Seite B

Bild Bild Bild

cyrix
Taschenrechner
Taschenrechner
Beiträge: 7
Registriert: 26.01.2017 22:48

Re: Unterstützung bei Aufsetzen eines Projekts

#6 Ungelesener Beitrag von cyrix » 01.08.2017 12:16

So, Vorlesungs- und Prüfungszeit ist rum. Nun kann ich auch - zumindest mal für nen Monat - wieder inhaltlich arbeiten. :)

Aktueller Stand des Projekts ist folgender: Es liegt inhaltlich schon ganz gut ausoptimierter Quellcode vor, der aber bisher in erster Linie darauf ausgelegt ist, dass er auf einer Maschine sinnvoll läuft. (Ein paar Anpassungen sind also noch vorzunehmen, worum ich mich kümmere, sobald ich weiß, wie genau der Spaß ausschauen und was er leisten soll.) Der sollte nun in ein BOINC-Projekt (was wahrscheinlich das Einfachste sein wird) eingebunden werden.

Was ist an Kommunikation zwischen Server (der auch erst aufzusetzen wäre) und Client relevant? Hin- und her gehen eigentlich nur ein paar kleine Text-Dateien: Hin: worktodo.txt (die i.W. nur ein paar Zahlenwerte über Beginn und Ende der Workunit im abzuarbeitenden Bereich beinhaltet), zurück: cleared.txt (die die abgearbeiteten Bereiche enthält und als Checkpoint-Datei dienen kann) und candidates.txt (die die ausgesiebten Kandidaten-Zahlen enthält). Letztere Dateien müssen gesammelt und dann gesondert nachprozessiert werden. (Dies würde ich aber "händisch" auf dem eigenen Rechner machen, brauche also nur sämtliche solche Dateien, die die Clients berechnet haben.)


Wie würde man hierfür weiter vorgehen?

Viele Grüße
Cyrix

Benutzeravatar
yoyo
Vereinsvorstand
Vereinsvorstand
Beiträge: 8045
Registriert: 17.12.2002 14:09
Wohnort: Berlin
Kontaktdaten:

Re: Unterstützung bei Aufsetzen eines Projekts

#7 Ungelesener Beitrag von yoyo » 01.08.2017 12:36

Hi,
in der Woche ab 14.8. hab ich Zeit und wollte mich Deinen Sourcen widmen und diese Boincifizieren. Heißt da müssen an etwa 5 Stellen Boinc API aufrufe rein, damit es eine echte Boinc App wird. Diese würde ich dann mit #ifdef BOINC klammern, damit man die Sourcen auch ohne Boinc libs übersetzen kann.
Für eine App und die Kommunikation muß folgendes festgelegt werden:
- Welche Dateien gehören zur Applikation?
- Welche Dateien sind Input- bzw. Output?
Ich hab mal alle Fragen hier https://www.rechenkraft.net/wiki/Benutz ... subproject zusammengefaßt.

yoyo

BTW: Komm doch in unseren Chat: https://www.rechenkraft.net/wiki/Rechenkraft:Chat
HILF mit im Rechenkraft-WiKi, dies gibts zu tun.
Wiki - FAQ - Verein - Chat

Bild Bild

Benutzeravatar
yoyo
Vereinsvorstand
Vereinsvorstand
Beiträge: 8045
Registriert: 17.12.2002 14:09
Wohnort: Berlin
Kontaktdaten:

Re: Unterstützung bei Aufsetzen eines Projekts

#8 Ungelesener Beitrag von yoyo » 16.08.2017 10:41

Für alle die hier mitlesen. Das Projekt ist jetzt als neues Subprojekt in yoyo@home aktiv. Bei der jetzigen Geschwindigeit wird es wohl in 4-5 Monaten alle Workunits berechnet haben. Wer also noch das entsprechende Collatz Badge haben möchte sollte sich ranhalten.

yoyo
HILF mit im Rechenkraft-WiKi, dies gibts zu tun.
Wiki - FAQ - Verein - Chat

Bild Bild

Benutzeravatar
Michael H.W. Weber
Vereinsvorstand
Vereinsvorstand
Beiträge: 22417
Registriert: 07.01.2002 01:00
Wohnort: Marpurk
Kontaktdaten:

Re: Unterstützung bei Aufsetzen eines Projekts

#9 Ungelesener Beitrag von Michael H.W. Weber » 16.08.2017 14:16

Mag vielleicht mal jemand den Unterschied von diesem in Yoyo@home laufenden CPU-Collatz zu dem seit Jahren extern laufenden GPU-Collatz erklären?
Sind für die ODROIDs irgendwelche speziellen Anpassungen durchzuführen, damit das Subprojekt läuft?

Michael.
Fördern, kooperieren und konstruieren statt fordern, konkurrieren und konsumieren.

http://signature.statseb.fr I: Kaputte Seite A
http://signature.statseb.fr II: Kaputte Seite B

Bild Bild Bild

cyrix
Taschenrechner
Taschenrechner
Beiträge: 7
Registriert: 26.01.2017 22:48

Re: Unterstützung bei Aufsetzen eines Projekts

#10 Ungelesener Beitrag von cyrix » 16.08.2017 19:41

@Michael: Ich antworte mal zur inhaltlichen Fragestellung:

Das seit 2009 laufende Collatz-Conjecture-Projekt (der Vorgänger lief 2008 ein paar Monate) hat sich das Ziel gesetzt, möglichst lange Collatz-Folgen (*) zu finden. Dafür hat man bei einer willkürlich gewählten großen Zahl (2^71) angefangen und ab da weiter die nächsten Startzahlen untersucht.

(*) Für eine natürliche Zahl n definiere C(n) als C(n):=n/2 für n gerade und C(n):=3n+1 für n ungerade. Nun betrachte die Folge n, C(n), C(C(n)):=C^2(n), C^3(n):=C(C^2(n)) usw. Die Collatz-Vermutung besagt, dass diese Folge irgendwann bei 1 landet, dass es also für jedes n ein k mit C^k(n)=1 gibt. Collatz-Conjecture sucht nach Folgen, die möglichst lang brauchen, bis irgendwann das erste mal die 1 als Folgenglied auftritt.



Dabei geht man dort mathematisch/ algorithmisch nicht unbedingt clever vor. Das Hauptmanko ist aber, dass die Daten nutzlos sind, da keine Untersuchung der Zahlen < 2^71 stattgefunden hat. (Und beliebig lange Collatz-Folgen kann man recht einfach konstruieren: Die Folge zur Startzahl 2^k-1 ist immer mindestens k lang. Die Frage nach besonders langen Folgen ergibt also nur dann Sinn, wenn man weiß, dass es keine mindestens genauso lange Folgen zu kleineren Startzahlen gibt. Diese Frage kann aber das Projekt aufgrund der fehlenden Untersuchung der kleineren Startwerte nicht beantworten.)

Es wäre wohl auch utopisch bei 0 anzufangen, denn obwohl das Projekt haufenweise Rechenleistung zur Verfügung gestellt bekommt, ist man kaum voran gekommen. (Ich finde es gerade nicht wieder, meine aber mal von in der Gegend von 2^71+2^70 als aktuell untersuchte Zahlen gelesen zu haben. Das heißt, in den 8 Jahren seit Projektbeginn hätte man gerade einmal die Hälfte der Arbeit erledigt, die man hätte machen müssen, bevor man sich dieser Startzahl von 2^71 widmet.

Anders formuliert: Hier wird i.W. einfach nur elektrisch geheizt.




Beim Projekt 'Nontrivial Collatz Cycle' ist die Ausgangslage wie folgt: Um einen Satz (**) zu zeigen (bzw. genauer: um eine gezeigte Aussage weiter zu verbessern) benötigt es den Nachweis, dass alle Collatz-Folgen für Startzahlen < 87*2^60 auf 1 fallen. Das Projekt ist damit erst einmal per se schon endlich, was bedeutet, dass man ein Ergebnis erwarten kann. Daneben ist auch der Umfang in einem Bereich, der es in realistischer Zeit erledigen lässt. (Die obere Schranke von 87*2^60 wurde dabei zuvor gegenüber einem naiven Ansatz auch erst einmal noch durch ein bisschen Theorie und eine vorgeschaltete Optimierung etwas mehr als halbiert.)

(**) Ist die Collatz-Vermutung falsch, dann deshalb, weil eine Collatz-Folge unbeschränkt wächst, oder aber in einen vom trivialen Zyklus 1-->4-->2-->1--> ... verschiedenen, nicht-trivialen Zyklus übergeht.

Vermutung: Ein solcher nicht-trivialer Zyklus besteht aus mehr als 17 Milliarden Folgengliedern. (Bisheriger Stand [seit dem Jahr 2008] ist, dass er aus mehr als 1 Milliarde Folgengliedern bestehen muss.)



Wichtig bei dieser Untersuchung der Startzahlen < der zu zeigenden Schranke ist auch, dass hier nicht die Länge der Collatz-Folgen von Relevanz ist. Es geht nur um den Nachweis, dass sie irgendwann bei 1 landen. Deshalb greifen ein paar weitere algorithmische Optimierungsmöglichkeiten, die den Prozess um Größenordnungen beschleunigen. Dadurch ist - bei deutlich kleinerem Einsatz an Rechenarbeit - nicht nur ein relevantes Ziel in greifbarer Nähe, welches sich dann auch in einer wissenschaftlichen Veröffentlichung wiederfinden wird, sondern auch der Datendurchsatz je GFlop deutlich größer als im angesprochenen großen Projekt. (Für die genauen Zahlen müsste ich noch mal nachlesen.)

Bei dieser Suche nehmen wir quasi en passent die Untersuchung nach Pfadrekorden mit, also der Frage, welche Startzahlen größere Folgenglieder in ihren Collatz-Folgen stehen haben als alle kleineren Startzahlen. Hier kann also der Finder sich in die Entdeckerliste http://www.ericr.nl/wondrous/pathrecs.html eintragen. (Dergleichen ist bei dem Collatz-Conjecture-Projekt aufgrund der fehlenden Untersuchung der Startzahlen < 2^71 eben auch nicht möglich...) Es sollten sich in dem untersuchten Bereich wohl mehrere neue Pfadrekorde befinden.


Wen weiteres interessiert: Ich habe vorhin mal den Spaß als Grob-Überblick der verwendeten Ideen auf meine Uni-Seite geschrieben: https://www.uni-flensburg.de/mathematik ... tz-zyklen/ (Genaue mathematische Beweise kommen dann ins Paper. Die sind noch nicht ordentlich dokumentiert.)


Ich hoffe, einen kleinen Überblick gegeben zu haben. :)

Cyrix

cyrix
Taschenrechner
Taschenrechner
Beiträge: 7
Registriert: 26.01.2017 22:48

Re: Unterstützung bei Aufsetzen eines Projekts

#11 Ungelesener Beitrag von cyrix » 16.08.2017 20:12

Aber, das habe ich vorhin vergessen zu schreiben: Ein Großes Dankeschön an yoyo für die Unterstützung beim Aufsetzen des Projekts und die Super-Betreuung als Teil von yoyo@home ! :) Da ging einiges an Arbeitszeit hinein, die ich so nicht hätte leisten können. Vielen Dank! :)

Cyrix

Benutzeravatar
yoyo
Vereinsvorstand
Vereinsvorstand
Beiträge: 8045
Registriert: 17.12.2002 14:09
Wohnort: Berlin
Kontaktdaten:

Re: Unterstützung bei Aufsetzen eines Projekts

#12 Ungelesener Beitrag von yoyo » 16.08.2017 20:42

Michael H.W. Weber hat geschrieben: Sind für die ODROIDs irgendwelche speziellen Anpassungen durchzuführen, damit das Subprojekt läuft?
Michael.
Da muß lediglich ein 64 bit Linux drauf laufen und Boinc natürlich.
HILF mit im Rechenkraft-WiKi, dies gibts zu tun.
Wiki - FAQ - Verein - Chat

Bild Bild

Antworten

Zurück zu „Andere Mathematik-Projekte“