"Verteilte Primzahlen" - mit Erlang
Warum diesmal?
Eigentlich ging es nur darum etwas Erlang zu lernen. Erlang ist eine schöne funktionale Programmiersprache, die gleichzeitig Nebenläufigkeit und verteilte Programmierung mitbringt. Soll heißen: Man nimmt sich einen haufen Rechner, die wild Prozesse spawnen, welche dann untereinander wild Nachrichten hin und her schicken.
Um das mal richtig auszuprobieren reichte einfach kein Ping-Pong aus den Tutorials (obwohl es sehr gut zum lernen war! Doku kriegt ein deutliches plus!). Also nimmt man sich wie immer das nächstbeste mathematische Problem und wirft da Rechenkraft drauf.
Funktionsweise
Es gibt einen Masterserver (prim_master.erl). Ein Client (prim_client.erl) meldet sich nun beim Master und sagt, wie viele Prozesse er gleichzeitig am laufen haben möchte.
1 client(N) ->
2 {master, ?master} ! {self(), master_I_am_here_to_serve_you, N},
3 client(N, []).
1 % subprozess zum filtern der primzahlen
2 calc_primes(From, To) ->
3 Range = prim_helper:range(From, To),
4 {TimeTaken, Primes} = timer:tc(lists, filter,
5 [fun prim_helper:isPrim/1, Range]),
6 client ! {self(), primes_ready, {From, To}, Primes, TimeTaken},
7 ok.
Die Funktion, die dabei benutzt wurde um die Primzahlen zu finden ist die simple "Hau solange drauf, bis eine Antwort herausfällt": Für X alle Zahlen bis sqrt(X) auf Teilbarkeit prüfen. Aber sie ist schnell implementiert und lässt sich gut verteilt benutzen. Und schließlich ging es darum Erlang zu lernen.
Ergebnisse (25.09.2010)
"Starte etwas, wo man Rechenkraft reinhängen kann - Nerds mit Rechenkraft werden kommen."
Es wurden bis knapp unter 17.000.000.000 alle Primzahlen berechnet, teils von 12 Nodes gleichzeitig. Die komprimierten Primzahlenlogs sind insgesamt knapp 2 GB groß.
Wie oben geschrieben: Stellt man einen solchen Server auf finden sich sofort ein paar Leute, die fröhlich mit dran rumrechnen. Vielen Dank an euch! Damit das nicht vergessen wird... Hier die Statistiken der einzelnen Nodes bzw. der Gruppen.
| Nodegruppen | Einzelne Nodes | |||||
|---|---|---|---|---|---|---|
| Platz | Ranges | Node | Platz | Ranges | Node | Besitzer |
| 1. | 55560 | MasterOfJOKers | 1. | 41426 | worker@testine.someserver.de | seba |
| 2. | 50435 | Random Unirecher | 2. | 24267 | blackhole@wh17.tu-dresden.de | MasterOfJOKers |
| 3. | 45752 | seba | 3. | 19090 | starbuck@cs.tu-berlin.de | Uni |
| 4. | 14326 | x2017 | 4. | 18095 | apollo@cs.tu-berlin.de | Uni |
| 5. | 1049 | Konrad | 5. | 16798 | HeartofGold@wh17.tu-dresden.de | MasterOfJOKers |
| 6. | 740 | spucky | 6. | 14326 | primes@zeus.chubig.net | x2017 |
| 7. | 270 | joerg | 7. | 13250 | boomer@cs.tu-berlin.de | Uni |
| 8. | 8317 | jokpad@wh17.tu-dresden.de | MasterOfJOKers | |||
| 9. | 4326 | intersect@seba.is-a-geek.org | seba | |||
| 10. | 3237 | jokerserver2@wh17.tu-dresden.de | MasterOfJOKers | |||
| 11. | 2941 | dhcp@wh17.tu-dresden.de | MasterOfJOKers | |||
| 12. | 740 | spucky@someserver.de | spucky | |||
| 13. | 559 | dornroeschen@reich.sowjet.biz | Konrad | |||
| 14. | 289 | rumpelstilzchen@reich.sowjet.biz | Konrad | |||
| 15. | 179 | joerg@freitagsrunde.org | joerg | |||
| 16. | 109 | froschkoenig@reich.sowjet.biz | Konrad | |||
| 17. | 92 | quichotte@reich.sowjet.biz | Konrad | |||
| 18. | 91 | joergfer@cs.tu-berlin.de | joerg | |||
...und seba kann jetzt etwas mehr Erlang als vorher.
Kann man noch mitspielen?
Wenn der Master noch steht... Klar! Im git gibts eine README, in der beschrieben steht, wie man mitmachen kann. Da ihr sowieso einen Erlang-Cookie brauchen werdet und mich dannach fragen müsst, kann ich euch dann auch sagen, ob überhaupt noch gespielt wird.
JOKers Patch
JOKer fand den Algorithmus zu ineffizient und hat spontan etwas in Python geschrieben das Erlangcode erzeugt. Wie das Funktioniert und was es genau tut... Schaut es euch einfach selber an. Ist auch ein ganz gutes Stück schneller... (JOKers Patch (12kb)