Dienstag, 21. Juni 2016

Genetische Algorithmen und OpenMPI

Dinge die passieren - einen aber ärgerlich stimmen - wie zum Beispiel das ich diesen Artikel bereits geschrieben hatte und ich ihn nun komplett schreiben muss, da die Datei in der er stand leider bei einem unerwarteten Zwangs-Reset meines Rechners verloren ging.

In dem verlorenen Artikel hatte ich darüber geschrieben das es etwas wie genetische Algorithmen gibt, welche dazu herangezogen werden könne Probleme zu lösen für die man z.B. keinen Lösungsansatz besitzt aber das Ziel kennt. Außerdem habe ich über Affen geschrieben die auf Schreibmaschinen tippen und per Evolution in der Lage wären einen Text wie Shakespeares Sommernachtstraum zu schreiben. Bei diesem so genannten Infinite-Monkey-Theorem kann mathematisch, auch ohne Evolution, bereits bewiesen werden das dies möglich ist. Die Evolution soll dabei nur den Fortschritt unterstützen. Diese Aufgabe ist in Etwa gleichzustellen wie ein erstes "Hello World" bei der Verwendung einer neuen Programmiersprache. Aber vielleicht auch ein klein wenig aufwändiger umzusetzen.

Schlussendlich, mal von den ganzen Affen abgesehen, wollte ich nur darüber berichten das ich nun endlich für meinen Cluster eine Software geschrieben habe die alle Elemente des Systems einmal gründlich ausnutzt. Also das Netzwerk, die 20 Prozessor-Cores der OrangePis und auch den RAM gut ausgelastet.

Die Programmiersprache meiner Wahl bei der Umsetzung ist in diesem Fall python - bzw. pypy - in Verbindung mit MPI4PY und OpenMPI. Die Laufzeit ist durch die Verwendung von pypy deutlich reduziert und durch die Möglichkeit der verteilten Berechnungen und Aktivitäten, welche per OpenMPI ermöglicht werden, kann diese weiter reduziert werden. Leider musste ich bei meinen Tests feststellen das mein Notebook mit dem Intel i7 Quadcore - Prozessor der 16GB RAM zur Verfügung hat immer noch schneller ist als der Cluster - aber schnelle und Moderne Hardware kaufen kann ja jeder.

Mein Script ist unterteilt in zwei Bestandteile, einen generischen Teil der für die Ausführung des genetischen Algorithmus zuständig ist und einem ausführenden Hauptteil der unter anderem für MPI zuständig ist. Weiter gibt es seit kurzem einen weiteren generischen Teil welcher den Aufwand der MPI-Kommunikation (welche per SSH realisiert ist) dadurch reduziert indem ein Node-lokales Multiprozessing verwendet wird.

Der Grundlegende Ablauf bei einem solchen genetischen Algorithmus ist immer gleich. Zunächst wird eine initiale Population von DNA-Elementen erzeugt, auf diese einzelnen DNA-Stränge dann eine Fitness-Funktion angewandt, daraufhin aus den besten n-Stück und durch Rekombination eine neue Population (Generation) erzeugt und schlussendlich Mutationen in dieser neuen Population erzeugt. Danach wird der Vorgang beim ausführen der Fitness-Funktion neu begonnen und fortgefahren bis entweder im Idealfall eine Lösung ermittelt worden ist, oder eben eine maximale Anzahl von Versuchen den Vorgang beendet.

Da es genug Tutorials, Beispiele und Quellen zu finden gibt verzichte ich hier auf weitere Details zu meiner Implementierung. Es war eben auch nur ein Test um die Funktionalität des Clusters zu verifizieren. Die Performance kann in dieser Software an einigen Stellen optimiert werden.

So ist die Verwendung der Sprache Python und des pypy-Interpreters sicher nicht performanter als wenn man eine Hochsprache wie C oder C++ verwenden würde. Weiterhin ist ein häufiges austauschen von Daten zwischen den Nodes und des Masters per SSH, unter Berücksichtigung das es sich bei meiner Hardware um Embeddedsystems handelt, vielleicht auch eher ein Flaschenhals. Ebenso wie das 100MBit Netzwerk, aber um die Hardware geht es hier nicht. Weiterhin wird in meiner generalisierten Implementierung des Multiprocessings für jede anstehende Berechnung einer oder mehrere Prozesse neu gestartet und diese daraufhin wieder beendet, was weiteren Overhead auf der CPU erzeugt den man durch geschickte Verwendung eines anderen Prozessschemas verringern könnte.
Auch die Implementierung der Datenstrukturen in Python-spezifischen Datentypen wie Listen und Dictionaries anstatt der Verwendung von numpy wirkt sich vermutlich nicht positiv auf die Performance aus.

Hierbei muss man sich in jedem Fall vermutlich selbst für sich überlegen ob es einen Sinn ergibt seine Software im Nachhinein zu optimieren oder gleich von Anfang an die Beste der Besten der Besten Verfahren, Datenstrukturen und Soft- und Hardwarekomponenten verwendet. In meinem Fall würde ich noch hinzufügen - Hauptsache es macht Spaß und es gibt neues zu entdecken.

Insgesamt bin ich dennoch zufrieden, da der Cluster bewiesen hatte das er zuverlässig, auch unter Volllast mit einem System-Load von 8 (bei 4 CPU-Cores) und mehr trotzdem weiterhin korrekt Arbeitet.

Keine Kommentare:

Kommentar veröffentlichen