Collatz Conjecture – Planet 3DNow! Distributed Computing Wiki

Steckbrief
Kategorie:	Mathematik
Betreiber:	Jon Sonntag
Nationalität:	USA
Start:	Juli 2009
Status:	Stabil
Checkpoints:	ja
Webseite:	boinc.thesonntags.com/collatz/
Anmelde-URL:	http://boinc.thesonntags.com/collatz/
Clients
x86	x	x	-	-	-
x86-64	x	x	x	-	-
Android	-	-	-	-	-
RaspberryPi	-	-	-	-	-
GPU (CAL)	x	-	-	-	-
GPU (CUDA)	x	x	-	-	-
GPU (OpenCL)	x	x	-	-	-
GPU (Intel)	x	x	-	-	-
Planet 3DNow! Teamstatistik
Platzierung Planet 3DNow!: (powered by BOINCstats)

Projektbeschreibung

Das Projekt Collatz Conjecture hat das Ziel, das sog. Collatz-Problem aus dem Bereich der Mathematik zu lösen.

In der Mathematik existieren mathematisch generierte Zahlenfolgen, welche auf eine gesetzmäßige Regelmäßigkeit schließen lassen, diese jedoch mit bekannten mathematischen Regeln nicht abschließend bewiesen werden können. Somit bleiben es bekannte Regelmäßigkeiten ohne endgültigen mathematischen Beweis, was ihre Verwendung in der Mathematik sowie allen darauf aufbauenden Bereichen in der Praxis stark einschränkt oder nach den Regeln der Mathematik gänzlich verbietet.

Da ein mathematischer Beweis bislang nicht erbracht werden konnte, existiert als Alternative nur der Weg des Beweises (der Ungültigkeit) durch Widerspruch. Dieses Verfahren konnte bereits bei anderen, vergleichbaren mathematischen Problemen erfolgreich angewendet werden.

Collatz Conjecture setzt auf die Suche nach einem solchen Widerspruch durch Testen immer weiter steigender Ausgangswerte.

Kurzbeschreibung des Collatz-Problems :

man nehme eine natürliche Zahl x > 0
ist x gerade, so wird sie durch 2 geteilt (x = x / 2)
ist x ungerade, so wird sie mit 3 multipliziert und um +1 erhöht (x = 3x+1)
der Vorgang wird wiederholt, bis die Zahlenfolge bei x=1 endet

Scheinbar endet die resutierende Zahlenfolge für jeden Ausgangswert x > 0 zwangsläufig bei 1. Dieses jedoch ist mathematisch unbewiesen und es gilt entweder, diesen Beweis zu führen - oder einen experimentellen Widerspruch herbei zu führen.

Erfolge des Projekts

Aktuell (Stand Nov 2014) nähert sich das Projekt der Zahl 2,4 * 10E21 , ein Widerspruch konnte bislang nicht nachgewiesen werden.

Planet 3DNow!

Planet 3DNow! nimmt seit dem 02.07.2009 mit einem eigenen Team an Collatz Conjecture teil.

Teilnahme

Das Projekt wird über die BOINC-Plattform betrieben. Die Anmelde-URL lautet: http://boinc.thesonntags.com/collatz/

Besonderheiten

Die GPU OpenCL- bzw. CUDA-Applications von Collatz arbeiten mit sehr konservativen Parametern, was ab Werk zu einer nur relativ niedrigen GPU-Auslastung und einer geringen Performance führt.

Durch Verwendung von optimierten Parametern lässt sich die GPU-Auslastung sowie die Performance signifikant steigern.

Die Parameter stehen in den folgenden, ab Werk leeren Konfigurations Dateien im Projektverzeichnis von Colllatz :

Beispielhaft für OpenCL-Applications mit AMD GPU :

large_collatz_6.04_windows_x86_64__opencl_amd_gpu.config
solo_collatz_6.04_windows_x86_64__opencl_amd_gpu.config
mini_collatz_6.04_windows_x86_64__opencl_amd_gpu.config

Beispiel für das Format der Config-Datei :

verbose=1

threads=8

items_per_kernel=20

kernels_per_reduction=8

sleep=1

Bekannte optimale Parameter :

AMD R9 290......| verbose=1, threads=10, items_per_kernel=22, kernels_per_reduction=9, sleep=1
AMD HD7970.....| verbose=1, threads=10, items_per_kernel=22, kernels_per_reduction=9, sleep=1
AMD R9 270......| verbose=1, threads=10, items_per_kernel=22, kernels_per_reduction=9, sleep=1
AMD HD7850.....| verbose=1, threads=10, items_per_kernel=22, kernels_per_reduction=9, sleep=1
AMD HD7790.....| verbose=1, threads=10, items_per_kernel=21, kernels_per_reduction=9, sleep=1
AMD HD7750.....| verbose=1, threads=10, items_per_kernel=21, kernels_per_reduction=9, sleep=1
AMD R7 240......| verbose=1, threads=10, items_per_kernel=20, kernels_per_reduction=9, sleep=1
NVidia GT720M..| verbose=1, threads= 8, items_per_kernel=21, kernels_per_reduction=9, sleep=1
intel HD4000.....| verbose=1, threads= 8, items_per_kernel=18, kernels_per_reduction=8, sleep=1

Bei der Credit-Vergabe erfolgt eine ca. 15%ige Reduktion der Credits für alle Ergebnisse mit <30 Minuten Laufzeit. Mit den Web-Preferences auf der Collatz Account Seite sind die Nutzer daher angehalten, ggf. die für ihre Hardware passende Auswahl zwischen Micro, Mini, Solo und Large zu treffen.

Da der Server u.U. auch relativ langsamer Hardware nach der ersten Anmeldung eine Large-Workunit zusendet (was in extrem langen Berechnungszeiten münden kann), ist es sehr empfehlenswert, diese Auswahl vor Hinzufügen von Rechnern zu treffen.

NVidia-Benutzer sollten in den Collatz Web-Preferences NVidia_OpenCL deaktivieren, da sich gegenüber der CUDA Application kein erkennbarer Vorteil - aber eine weitaus höhere CPU-Belastung ergibt.

Sofern GPUs mit hohen Optimierungen betrieben werden, benötigen AMD (OpenCL) und NVidia (CUDA) GPUs keinen extra für Collatz reservierten CPU-Kern.