TU Darmstadt / ULB / tuprints

Konfigurierbare Prozessorsysteme zur hardwareunterstützten Simulation von Agentensystemen auf der Basis von Globalen Zellularen Automaten

Schäck, Christian Alexander :
Konfigurierbare Prozessorsysteme zur hardwareunterstützten Simulation von Agentensystemen auf der Basis von Globalen Zellularen Automaten.
Technische Universität Darmstadt
[Ph.D. Thesis], (2011)

[img]
Preview
PDF
Dissertation.pdf
Available under Simple publication rights for ULB.

Download (3125Kb) | Preview
Item Type: Ph.D. Thesis
Title: Konfigurierbare Prozessorsysteme zur hardwareunterstützten Simulation von Agentensystemen auf der Basis von Globalen Zellularen Automaten
Language: German
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.

Alternative Abstract:
Alternative AbstractLanguage
In this work several different hardware architectures for the GCA-model (Global Cellular Automata, GCA) have been developed, evaluated and optimized for the simulation of multi-agent systems. The GCA-model consists of a set of cells which change their states synchronously parallel depending on the states of the neighbor cells. Therefore it is a massively parallel computation model. In differentiation to the CA-model the neighbors are neither fixed nor local, instead they are variable and global. The GCA-model is suitable for implementing multi-agent systems because complex behavior can be simulated with rather simple cell rules and the cell rule is independent of the amount of processors used in the hardware architecture. Programming can be kept simple as no complex synchronization patterns have to be used. The capability of each architecture is pointed out and it is shown in which way they can be further optimized. The evaluation of the architectures has been done using different FPGAs (Field Programmable Gate Array) with varying test sets. Although the architectures can be generally used, the focus lies within the accelerated simulation of multi-agent systems. Starting with a general architecture for the GCA-model several networks have been examined and optimized. A bus network with two arbitration techniques, an omega network with several optimizations and a ring network with an optimization to accelerate the accesses through the network have been realized and evaluated. To further accelerate the simulation of multi-agent systems a architecture with hash functions, thus excluding empty cells from computation, has been implemented. This architecture has been proven to be very efficient, even though the scalability and the maximum clock frequency are rather low. In another memory optimized architecture the same approach was kept but the scalability was improved. With a higher clock frequency and a simpler design of the architecture further accelerations were reached. The general architecture is suitable for calculating multi-agent systems that involve many agents. Multi-agent systems with less agents but a very large agent world can be simulated very well with the architecture using hash functions, as the size of the agent world is irrelevant and only the amount of agents is limited by the size of the memory. The memory optimized architecture reaches a very high simulation speed. As the term agent is used in a very divers way in the literature it is necessary to first give a definition of how the term is used in this work. To display the agent worlds and to configure the FPGA a Java simulation application (AgentSim) has been developed. The main features of the simulation application are to display, evaluate, error analysis, programming and simulation of different agent worlds. The applications for multi-agent simulation are versatile range from topics such as biology, sociology, traffic physics, evacuation simulation, computer graphics, film technique to economy simulation.English
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
Divisions: Fachbereich Informatik > Rechnerarchitektur
Date Deposited: 01 Jul 2011 09:22
Last Modified: 07 Dec 2012 12:00
URN: urn:nbn:de:tuda-tuprints-26455
License: Simple publication rights for ULB
Referees: Hoffmann, Prof. Dr. Rolf and Huss, Prof. Dr. Sorin A.
Refereed: 21 June 2011
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/2645
Export:

Actions (login required)

View Item View Item