Schäck, Christian Alexander (2011)
Konfigurierbare Prozessorsysteme zur hardwareunterstützten Simulation von Agentensystemen auf der Basis von Globalen Zellularen Automaten.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung

Kurzbeschreibung (Abstract)

In dieser Arbeit werden verschiedene Hardwarearchitekturen für das GCA-Modell (engl.: Global Cellular Automata, GCA) entwickelt, bewertet und für die Simulation von Multi-Agenten- Systemen optimiert. Das GCA-Modell besteht aus einer Menge von Zellen, die ihren Zustand synchron-parallel abhängig von den Zuständen der Nachbarzellen ändern. Damit ist es ein massiv-paralleles Berechnungsmodell, bei dem, im Gegensatz zum CA-Modell, die Nachbarschaft nicht fest und lokal, sondern global und variabel ist. Das GCA-Modell eignet sich gut für die Umsetzung von Multi-Agenten-Systemen, da u. a. auch mit einfachen Zellregeln komplexes Verhalten simuliert werden kann und die Zellregel unabhängig von der Anzahl der Prozessoren ist. Die Programmierung kann einfach gehalten werden, da keine komplexen Synchronisationskonstrukte verwendet werden müssen. Es wird die unterschiedliche Leistungsfähigkeit verschiedener Architekturen dargestellt und aufgezeigt, in welcher Art und Weise diese weiter optimiert werden können bzw. wurden. Die Auswertung der Architekturen erfolgt auf verschiedenen FPGAs (Field Programmable Gate Array) mit unterschiedlichen Testdaten. Obwohl die in dieser Arbeit gezeigten Architekturen allgemein einsetzbar sind, liegt der Fokus auf der beschleunigten Simulation von Multi-Agenten-Systemen. Zunächst wurde eine allgemeine Hardwarearchitektur für das GCA-Modell entwickelt und dabei verschiedene Verbindungsnetzwerke untersucht und optimiert. Als Verbindungsnetzwerke wurden das Busnetzwerk mit zwei verschiedenen Arbitrierungsmöglichkeiten, das Omeganetzwerk mit unterschiedlichen Optimierungen und das Ringnetzwerk ebenfalls mit einer Optimierung, um die Zugriffe zu beschleunigen, realisiert und ausgewertet. Um die Simulation von Multi-Agenten-Anwendungen weiter zu beschleunigen, wurde eine Architektur mit Hashfunktionen implementiert, bei der leere Zellen von der Berechung ausgeschlossen werden. Diese Architektur erweist sich als sehr leistungsfähig, obwohl die Skalierbarkeit stark begrenzt ist und die maximale Taktfrequenz eher gering ist. In einer weiteren speicheroptimierten Architektur wurde der gleiche Ansatz zugrunde gelegt, aber die Skalierbarkeit verbessert. Durch die nun höhere maximale Taktfrequenz und den einfacheren Aufbau der Architektur waren weitere Beschleunigungen möglich. Die allgemeine Hardwarearchitektur eignet sich für die Berechnung von Multi-Agenten-Systemen, die sehr viele Agenten beinhalten. Multi-Agenten-Systeme mit weniger Agenten, dafür aber sehr großen Agentenwelten, können dafür sehr gut auf der Hardwarearchitektur mit Hashfunktionen simuliert werden, da hier die Größe der Agentenwelt irrelevant ist und lediglich die Anzahl der Agenten durch die Speichergröße limitiert ist. Die speicheroptimierte Hardwarearchitektur zeichnet sich durch eine sehr hohe Simulationsgeschwindigkeit aus. Da der Begriff des Agenten in der Literatur unterschiedlichste Verwendung findet, erfolgt zuerst eine Definition des Agenten, wie er in dieser Arbeit verstanden wird. Für die Darstellung der Agentenwelten sowie für die Konfiguration der FPGAs ist ein Simulationsprogramm (AgentSim) in Java entwickelt worden. Die Hauptfunktionen des Simulationsprogramms sind die Darstellung, Auswertung, Fehleranalyse, Programmierung und Simulation verschiedenster Agentenwelten. Die Anwendungen für Multi-Agenten-Systeme sind sehr vielfältig und erstrecken sich u. a. über Gebiete der Biologie, Soziologie, Verkehrsphysik, Evakuierungssimulation, Computergraphik, Filmtechnik sowie Wirtschaftssimulation.

Frage zum Eintrag

Redaktionelle Details anzeigen