Projektdokumentation

Aus Verteilte Systeme - Wiki
Zur Navigation springen Zur Suche springen

Parallele Vogelschwarmsimulation mit MPI

Einleitung

Der Ausgangspunkt für dieses Projekt ist eine einfache OpenGL Implementierung des Boids Algorithmus, auf der Webseite von John Hammond von Fachbereich Mathematik an der University of Texas. Die Implementierung hat den Titel „An OpenGL/GLUT based application featuring 32 grey cones that fly around in self-organizing flocks chasing 3 colored balls that bounce off the walls of a wire frame cube“ und wurde in C geschrieben. Die Arbeit basiert auf dem Algorithmus von Craig Reynolds, das 1986 entwickelt wurde. „Die Boids stellen ein künstliches Leben-Programm dar, das das Schwarmverhalten von Vögeln simuliert.“ Wie Craig Reynolds auf seiner Webseite schreibt, basiert der Algorithmus auf dreidimensionalen Computational Geometry, die häufig in der Computer-Animation eingesetzt wird. Um das typische Verhalten nachzuahmen werden für jeden Vogel Regeln definiert die dieser für die Vögel in seiner direkten Umgebung zu beachten hat. So versucht der Vogel einerseits in der Nähe der anderen Vögel zu bleiben, gleichzeitig achtet er aber darauf nicht mit diesen zusammen zu stoßen. Des Weiteren versucht der Vogel sich der Flugrichtung seiner Nachbarn anzupassen. In der einfachsten Variante gelten folgende Regeln:

• Separation: wähle eine Richtung, die einer Häufung von Boids entgegenwirkt

• Angleichung: wähle eine Richtung, die der mittleren Richtung der benachbarten Boids entspricht

• Zusammenhalt: wähle eine Richtung, die der mittleren Position der benachbarten Boids entspricht

Bild 1: Kräfte durch die der Vogel beeinflusst wird


Die Kraft „cohesion“ sorgt für den Zusammenhalt des Vogelschwarms. Sie zieht den Vogel zur mittleren Position seiner Nachbarn. Die Kraft „seperation“ verhindert ein Kollidieren der Vögel. Zu diesem Zweck wird eine von den anderen Vögeln wegführende Kraft bestimmt und addiert. Die Kraft „alignment“ schließlich sorgt davor, dass der Vogel sich der Flugrichtung seiner Nachbarn anpasst. Zu diesem Zweck wird die mittlere Richtung der anderen Vögel bestimmt und auf die Richtung des Vogels addiert. Da jeder Vogel nur auf seine Nachbarn reagieren soll, benötigt man noch eine Methode um diese zu bestimmen. Nach Reynolds ist ein Vogel genau dann ein Nachbar wenn er nicht weiter als eine vorgegebene Distanz entfernt ist und zusätzlich in einem durch einen Winkel begrenzten Bereich liegt. Dieser Winkel definiert das Sichtfeld des Vogels ausgehend von seiner aktuellen Flugrichtung.

Bild 2: Sichtbereich des Vogels


Jede Iteration des Algorithmus erfordert also für jeden Vogel eine Überprüfung welche Vögel sich in seinem Umfeld befinden. Für jeden Nachbarvogel werden dann die oben beschriebenen Kräfte berechnet und auf den Vogel angewendet. In der Implementierung von John Hammond verfolgen die Schwarm Mitglieder mehrere Objekte im Bild, die targets. Jeder boid wird immer das am nächsten entfernte Zielobjekt (target) verfolgen. Sowohl die Anzahl der Schwarm Mitglieder als auch die Anzahl der Zielobjekte sind änderbar und sollen fur die performance Auswertungen der MPI Parallelisierung verwendet werden. Als MPI Platform wird Scali MPI benutzt. Es gibt 5 MPI Knoten: thales, hpc-1, hpc-2, hpc-3, hpc-4. Der Thales-Rechner wird als Koordinator dienen. Die Visualisierung, in OpenGL realisiert (xWindow) wird vom Thales-Rechner auf den lokalen Rechner weitergeleitet. Durch die Netzkommunikation sinkt die Performance der Anzeige.


Konzept


Simulation

Die Vögeln (boids struct) werden in einem Array definiert. Jeder Vogel speichert seine Lage (position) und seine Anfangsgeschwindigkeit (velocity). Die Vögeln verfolgen Ziele auf dem Bildschirm. Die targets werden in einem separaten Feld gespeichert. Zusätzlich zu den Vögeln besitzen die targets auch ein RGB Wert um diese auf dem Bildschirm zu zeichen und schneller zu sehen. Alle diese Werte werden am Anfang vom Koordinator mit „random“ Werte initialisiert. Die Anzahl der boids wird auf die einzelnen MPI Knoten verstreut. Jeder Knoten ist für die Berechung der Lage und der Geschwindigkeit einer bestimmten Anzahl von Vögeln zuständig. Es gibt einen Master-Knoten (Koordinator) und n-Slaves (MPI Knoten). Nachdem der Koordinator die boids und targets initialisiert, teilt er die Anzahl der Vögeln auf die Anzahl der MPI Knoten auf und schickt jeden Slave seinen Teil des boids array. Es wird damit erreicht dass die Last auf die einzelnen Knoten gleich ist. Der Koordinator ist für die Berechnung der targets und das Verbreiten dieser Informaton (mit Hilfe eines mpi_ broadcast) zu den anderen Knoten zuständig. Zusätzlich sammelt der Koordinator die Daten der einzelnen slaves auf und ist für die OpenGL Anzeige zuständig. Mit Hilfe der timer() callback Funktion aus OpenGL, sammelt der Koordinator regelmäßig die Daten von den einzelnen Knoten, zeigt diese an und schickt allen Knoten die aktuelle Lage der Zieleobjekten (targets). Die slaves schicken dem Koordinator ständig die neu berechneten Informationen (Lage und Geschwindigkeit) von den boids, mit Hilfe von MPI_Isend (nicht blockierendes Senden).


Visualisierung

Die Visualisierung wird in OpenGL realisiert und vom Master-Knoten (Koordinator) durchgeführt. Jeder Vogel hat einen Lage-Vector, wo die x,y,z Fensterkoordinaten aktualisiert werden. Die einzelnen Knoten aktualisieren die Lage und die Geschwindigkeit der boids und schicken die neuen Werte dem Koordinator. Weil die Visualisierung auf dem thales Knoten stattfindet und der xWindow eigentlich auf einen remote Rechner nur weitergeleitet wird (ssh -l b_pred002 -X thales) erscheint die OpenGL Anzeige, wegen Netzverkehr, verzögert. Um auf Windows das X-Fenster von thales anzuzeigen wurde Xming benutzt. Xming ist eine Implementierung eines X-Servers für Windows. Xming kann mit SSH-Implentierungen wie PuTTY genutzt werden, so dass X11-Sitzungen verschlüsselt von entfernten Unix-Maschinen laufen können. Das Xming-Paket umfasst keine eigenen X-Clients.


Bild 3: Visualisierung auf remote Rechner


Implementierung


Scali MPI Connect

Die boids Implementierung läuft auf einer Scali MPI Platform. Es handelt sich bei den Rechnern um 64-bit (AMD64) Systeme. Es gibt 5 MPI Knoten: thales, hpc-1, hpc-2, hpc-3, hpc-4. Auf der internen Wiki von Informatik gibt es ein kleines Beispiel wie man ein MPI Program kompiliert und startet. Für dieses Projekt wurde eine eigene Makefile erzeugt wo neben der MPI Bibliothek auch die OpenGL Bibliothek eingebunden wurde. Zum Starten des Projektes auf allen MPI Knoten wird der mpimon benutzt:

• mpimon <programm> <programm optionen> -- <node name> [<anzahl>] [<node name> [<anzahl>]]...

• konkret: mpimon boids -- thales 1 hpc-1 1 hpc-2 1 hpc-3 1 hpc-4 1;

• Im obigen Beispiel wird also auf den Nodes thales, hpc-1, hpc-2, hpc-3 und hpc-4 das Programm boids in jeweils einer Instanz gestartet.


MPI Implementierung der boids

Jeder MPI Knoten speichert sein lokales rank. Der Koordinator hat den rank 0. Der rank hängt von der Reihenfolge aus mpimon ab. Im obigen Beispiel hat also der hpc-1 rank 1, kpc-2 rank 2, unsw. Anhand des ranks wird bestimmt, welcher Knoten für welchen Bereich des boid arrays zuständig ist. Bei MPI läuft derselbe Programmcode auf allen Knoten. Man kann festlegen welche Code-Bereiche nur auf bestimmte Knoten laufen, indem man den rank abfragt. Die Implementierung besteht aus folgenden Teilen:

• Variablen und Typen Deklarationen

• Vektor Operationen

• Funktionen für random Werte

• Funktionen für die Berechung der boids und targets

• OpenGL Funktionen

• MPI Funktionen

Bild 4: MPI Implementierung


Programmablauf

Als erster Schritt wird die MPI Umgebung initialisiert. Als nächstes initialisiert der Koordinator alle boids und targets mit random Werte fur die Lage und die Geschwindigkeit. Zusätzlich bekommt jedes Zielobjekt eine random Farbe. Der Koordinator schickt dann allen Knoten mit Hilfe der MPI_Bcast Funktion die targets. Nächster Schritt ist das Verstreuen der boids auf die einzelnen slaves. Danach laufen alle slaves in einer Endlosschleife rein, wo sie ständig die Werte der boids neu berechnen und nicht blockierend diese dem Koordinator senden. Im letzen (regelmaßigen) Schritt berechnet und schickt der Koordinator die neuen Koordinaten der targets, sammelt die Daten von den slaves und zeichnet in OpenGL die boids und die targets.

Bild 5: Programmablauf


Bewertung (Zeitmessungen)


Bild 6: Zeitmessungen


Nützliche Dokumente (Materialien)


• An OpenGL/GLUT based application featuring 32 grey cones that fly around in self-organizing flocks chasing 3 colored balls that bounce off the walls of a wire frame cube. - John Hammond - Department of Mathematics University of Texas at Austin

• Boids Algorithmus - Craig Reynolds

• Studienarbeit Simulation von Vogelschwarmen - Andrea Unger und Thomas Steube

• Simulation und Visualisierung eines Vogelschwarms - Holger Rohde

• MPI: A Message-Passing Interface Standard

• RS/6000 SP: Practical MPI Programming