Sonntag, 25. April 2010
Nochmal Optimierungen :P, auch für 3D
Neuer Performance-Stand für 2D-Rechteck: ~13200 Lösungen / 20 Sekunden
Montag, 19. April 2010
SpheroPuzzle - jetzt wirklich fast fertig :)
Mittlerweile braucht das Lösen des Lonpos Original ca. 15 Minuten und es gibt 371020 Lösungen, statt der von der Firma angegebenen 360984.
Auch werden alle anderen Spielbretter im Eiltempo gelöst. Lediglich das Lösen der große 3D-Pyramide (könnte) noch optimiert werden.
Der Vergleich von den ursprünglichen 3000 Lösungen / Tag und der jetztigen 9000 Lösungen / 20 Sekunden ist irgendwie witzig. Viel mehr Optimierungsmöglichkeiten fallen mir auf den ersten Blick nicht ein. Jetzt müsste man wahrscheinlich wirklich schon bald auf Assembler-Ebene gehen und Compiler-Optimierungen durchführen.
Auch werden alle anderen Spielbretter im Eiltempo gelöst. Lediglich das Lösen der große 3D-Pyramide (könnte) noch optimiert werden.
Der Vergleich von den ursprünglichen 3000 Lösungen / Tag und der jetztigen 9000 Lösungen / 20 Sekunden ist irgendwie witzig. Viel mehr Optimierungsmöglichkeiten fallen mir auf den ersten Blick nicht ein. Jetzt müsste man wahrscheinlich wirklich schon bald auf Assembler-Ebene gehen und Compiler-Optimierungen durchführen.
Sonntag, 18. April 2010
Mittwoch, 14. April 2010
spheropuzzle - prefinal results
Mit Intels tbb (threading building blocks) wurde nun eine Multicore-unterstützte Variante entworfen.
Im Wesentlichen wird die riesige Aufgabe rekursiv in einzelne tasks zerlegt (Rotationsgrenzen der Steine). Die Grenzen werden jedoch lediglich bei einer Tiefe von vier Steinen aufgeteilt, da möglicherweise ansonsten unnötig Tasks erzeugt und zerstört werden müssen. (Da diese ja nichts zu tun haben, weil unter Umständen mit diesen Kombinationen keine Lösungen möglich sind) Diese werden dann von der geeigneten Anzahl an Threads (bei meinem Dualcore 2) abgearbeitet.
Schwierigkeiten dabei: Optimierung, Synchronisation, Abspeichern der Stacks (die Abarbeitung der Tasks ist mehr oder weniger zufällig, daher legt jeder Task eine Speicherungsdatei anhand seiner zugeordneten Rotationsgrenzen = eindeutige Kombination ab. Ob beim nächsten Start an den gespeicherten Lösungen weiter gearbeitet wird oder nicht, ist daher völlig egal, denn die Ergebnisse gehen nicht verloren! Diese werden halt dann später beim übernächsten Mal oder irgendwann anders weiter verwendet. Solange die Dateien nicht gelöscht werden, geht also nichts verloren! Der Task-Scheduler von Intel entscheidet nämlich, wann ein Task verarbeitet wird. Und wenn jetzt ein bereits gespeicherter Task an die Reihe kommt, wird weitergearbeitet. Hat dieser noch nichts gespeichert, fängt er halt von vorne an.)
Zusätzlich läuft im Hintergrund ein Monitorthread, der die in der Queue (high-performance concurrent_queue von Intel) abgespeicherten Lösungen auf die Festplatte knallt.
Für jeden Task wird ein eigenes Model (= Steinliste && Brett && Stack) angelegt, damit jeder Thread unabhängig arbeiten kann.
Dafür wurde gebrauch von einer atomic-Variable gemacht. (Der Monitor-Thread braucht ja Referenzen auf diese Objekte, damit er diese wieder freigeben / beenden / Lösungen holen etc. kann)
Mit einer atomic-Variable erreicht man üblicherweise viel bessere Performance-Werte, als würde man mit Mutexes / Semaphoren oder anderen üblichen Threadsynchronisationsobjekten synchronisieren.
Die Performancewerte sind einfach wahnsinnig: Nach 20 Sekunden wurden bereits über 50 Lösungen berechnet!
Im Wesentlichen wird die riesige Aufgabe rekursiv in einzelne tasks zerlegt (Rotationsgrenzen der Steine). Die Grenzen werden jedoch lediglich bei einer Tiefe von vier Steinen aufgeteilt, da möglicherweise ansonsten unnötig Tasks erzeugt und zerstört werden müssen. (Da diese ja nichts zu tun haben, weil unter Umständen mit diesen Kombinationen keine Lösungen möglich sind) Diese werden dann von der geeigneten Anzahl an Threads (bei meinem Dualcore 2) abgearbeitet.
Schwierigkeiten dabei: Optimierung, Synchronisation, Abspeichern der Stacks (die Abarbeitung der Tasks ist mehr oder weniger zufällig, daher legt jeder Task eine Speicherungsdatei anhand seiner zugeordneten Rotationsgrenzen = eindeutige Kombination ab. Ob beim nächsten Start an den gespeicherten Lösungen weiter gearbeitet wird oder nicht, ist daher völlig egal, denn die Ergebnisse gehen nicht verloren! Diese werden halt dann später beim übernächsten Mal oder irgendwann anders weiter verwendet. Solange die Dateien nicht gelöscht werden, geht also nichts verloren! Der Task-Scheduler von Intel entscheidet nämlich, wann ein Task verarbeitet wird. Und wenn jetzt ein bereits gespeicherter Task an die Reihe kommt, wird weitergearbeitet. Hat dieser noch nichts gespeichert, fängt er halt von vorne an.)
Zusätzlich läuft im Hintergrund ein Monitorthread, der die in der Queue (high-performance concurrent_queue von Intel) abgespeicherten Lösungen auf die Festplatte knallt.
Für jeden Task wird ein eigenes Model (= Steinliste && Brett && Stack) angelegt, damit jeder Thread unabhängig arbeiten kann.
Dafür wurde gebrauch von einer atomic-Variable gemacht. (Der Monitor-Thread braucht ja Referenzen auf diese Objekte, damit er diese wieder freigeben / beenden / Lösungen holen etc. kann)
Mit einer atomic-Variable erreicht man üblicherweise viel bessere Performance-Werte, als würde man mit Mutexes / Semaphoren oder anderen üblichen Threadsynchronisationsobjekten synchronisieren.
Die Performancewerte sind einfach wahnsinnig: Nach 20 Sekunden wurden bereits über 50 Lösungen berechnet!
Sonntag, 11. April 2010
Der Lösungsalgorithmus wird erwachsen
Was gestern noch über einen Tag dauerte, geht jetzt schon in 6 Minuten! Mit weiteren Optimierungen errechnet das erweiterte Lösungs-Programm in Blitztempo auf Snow Leopard die Beispiele fuer das neue Lonpos-Puzzle.
Nächstes Ziel: Die Werte unter neu sollen noch einmal durch die Anzahl der Kerne geteilt werden (vernünftige Multi-Core-Unterstützung). Bin gespannt, was im Endeffekt raus kommen wird.
ganz alt:
------
380: 24 stunden
alt:
---
1. loesung: 30 sekunden
70: 5 minuten
101 : 5:30
neu:
---
1. loesung: 13 sekunden
70: 2 minuten
101: 2 minuten
190: 5:30 minuten
370: 11 minuten
390: 12 minuten
Nächstes Ziel: Die Werte unter neu sollen noch einmal durch die Anzahl der Kerne geteilt werden (vernünftige Multi-Core-Unterstützung). Bin gespannt, was im Endeffekt raus kommen wird.
ganz alt:
------
380: 24 stunden
alt:
---
1. loesung: 30 sekunden
70: 5 minuten
101 : 5:30
neu:
---
1. loesung: 13 sekunden
70: 2 minuten
101: 2 minuten
190: 5:30 minuten
370: 11 minuten
390: 12 minuten
Samstag, 10. April 2010
macosx snow leopard - lonpos ready
Puuuu, schon lange nichts mehr gepostet!!!
Aufgrund von unserem neuen iPhone-Projekt wurde jetzt mein Windows-Pc zu einem Hackintosh umfunktioniert. Der Apfel-Sticker leuchtet zwar nicht, dafür die CPU aber umso mehr! Funktioniert alles recht gut, statt WLAN gibts einen kompatiblen Stick, Card-Reader geht leider nicht, während Sound teilweise funktioniert. Grafik & Co geht auch bestens.
Naja mit einem neuen, alten Apfel... ...da kann das Lonpos-Teil ja nur gut werden.
Aufgrund von unserem neuen iPhone-Projekt wurde jetzt mein Windows-Pc zu einem Hackintosh umfunktioniert. Der Apfel-Sticker leuchtet zwar nicht, dafür die CPU aber umso mehr! Funktioniert alles recht gut, statt WLAN gibts einen kompatiblen Stick, Card-Reader geht leider nicht, während Sound teilweise funktioniert. Grafik & Co geht auch bestens.
Naja mit einem neuen, alten Apfel... ...da kann das Lonpos-Teil ja nur gut werden.
Abonnieren
Posts (Atom)