logo Thorsten Pawletta, Hochschule Wismar - University of Technology, Business & Design

View this page in English

Diplomarbeit

 

Thema: 

Möglichkeiten der Parallelisierung einer transaktionsorientierten Simulationsmethode durch Message Passing in einer interaktiven Softwareumgebung
 
Eingereicht am:  15. Juli 1998
von: 
 Gerald Krafft
Betreuer: 
 Prof. Dr.-Ing. T. Pawletta;
Prof. Dr.-Ing. M. Krüger
Dr.-Ing. S. Pawletta
 

Problemstellung:

Ein wichtiges Einsatzgebiet für Computer ist die Simulation. Sie erlaubt es, Aussagen über das dynamische Verhalten von wirklichen oder gedachten Systemen zu machen. Die wachsende Komplexität heutiger Simulationen führt aber auch auf modernen Computersystemen zu langen Laufzeiten. Eine kostengünstige Lösung dieses Problems ist die Verteilung der Simulation in einem Netzwerk-Cluster. Für die parallele Programmierung in Netzwerk-Clustern werden Message-Passing-Systeme, wie z.B. PVM eingesetzt.
Die interaktive Softwareumgebung Matlab eignet sich zum schnellen Prototyping. Unter Nutzung einer vorhandenen Message-Passing-Toolbox lassen sich Konzepte der verteilten Simulation hervorragend mit Matlab umsetzen und für komplexere Experimente und Optimierungen nutzen.
In dieser Arbeit werden Aspekte der parallelen Programmierung angeschnitten und Möglichkeiten der Parallelisierung von Simulationen beschrieben. Die daraus resultierenden Erkenntnisse werden auf die transaktionsorientierte Simulationen angewendet und ein ausgewählter Lösungsweg in dem Prototyp eines verteilten Simulators umgesetzt.
 

Möglichkeiten der Parallelisierung von Simulationen

  •  
 Parallelisierung auf Experimentebene: Hier werden verschiedene unabhängige Simulationsläufe parallel auf mehreren Prozessoren oder Rechnern ausgeführt.
  •  
 Parallelisierung von Hilfsfunktionen: Bei dieser Möglichkeit werden Hilfsfunktionen des Simulators, wie z.B. die Zufallszahlengenerierung parallel auf anderen Prozessoren ausgeführt.
  •  
 Parallelisierung auf Modellebene: Dieser Ansatz ermöglicht die Beschleunigung einzelner Simulationsläufe durch die Einteilung des Modells in Teilmodelle und deren parallele Bearbeitung. Voraussetzung für diesen Ansatz ist die geeignete Partitionierung des Modells, das richtige Synchronisationsverfahren sowie das Mapping.
 

Synchronisationsverfahren

Die Synchronisationsverfahren lassen sich in die drei grundlegenden Klassen der konservativen, der optimistischen und der hybriden Verfahren einteilen. Konservative Verfahren halten bei der Abarbeitung der Ereignisse die Kausalordnung strikt ein, indem nur garantierte Ereignisse ausgeführt werden. Optimistische Verfahren lassen eine Verletzung der Kausalordnung erst einmal zu, um sie gegebenenfalls durch Zurücksetzen auf einen früheren Zustand und erneutes Ausführen der Ereignisse zu korrigieren. Hybride Verfahren vereinigen konservative und optimistische Konzepte, um Vorteile von beiden zu nutzen.
 

Anforderungen an das Synchronisationsverfahren

Die Aufgabenstellung führt zu folgenden Anforderungen an ein mögliches Synchronisationsverfahren:  

Lösungsansatz

Die Parallelisierung auf Experimentebene wurde bereits ausführlich untersucht und läßt sich nicht zur Beschleunigung einzelner Simulationsläufe einsetzen. Bei der Parallelisierung von Hilfsfunktionen ist bei heutigen Simulationsalgorithmen und hinsichtlich von Netzwerk-Clustern als Zielsystem mit keiner signifikanten Beschleunigung zu rechnen. Aus diesem Grund wurde die Parallelisierung auf Modellebene als vielversprechender Ansatz untersucht.

Als Synchronisationsverfahren wurde das SPEEDES-Verfahren ausgewählt, da es als hybrides Verfahren Vorteile von konservativen und optimistischen Verfahren vereint und einen geringen Kommunikationsaufwand und einen einfachen Kommunikationsablauf  besitzt.
 

Das SPEEDES-Verfahren

Analog zu optimistischen Verfahren, führt das SPEEDES-Verfahren Ereignisse in der lokalen Ereignisliste in chronologischer Reihenfolge sofort aus. Allerdings werden nur garantierte Ereignisse an einen anderen LP verschickt, indem für andere LPs bestimmte Ereignisse zuvor in einer lokalen Liste gespeichert werden und erst nach Empfang einer entsprechenden GVT-Approximation von der zentralen Instanz an den jeweiligen LP gesendet werden. Zur Bestimmung der GVT-Approximation sendet jeder LP eine bestimmte Nachricht an die zentrale Instanz, sobald seine lokale Simulationszeit die minimale Ereigniszeit der in der Ausgangsliste vorhandenen Ereignisse erreicht oder überschreitet. Nach dem Empfang von Ereignissen werden diese in die lokale Ereignisliste eingefügt und gegebenenfalls ein Rollback durchgeführt.
 

Umsetzung

Folgende Punkte waren hinsichtlich der Implementation eines auf dem SPEEDES-Verfahren basierenden, verteilten Simulators zu betrachten: Den Betrachtungen zur Anpassung des SPEEDES-Verfahrens an die transaktionsorientierte Simulation folgend, ist es bei der Umsetzung notwendig, die Prioritäten in die GVT-Approximation einzubeziehen. Dazu wurde ein Tupel bestehend aus einer Zeit- und einer Prioritätsinformation genutzt. Die GVT-Approximation ergibt sich so aus der minimalen Ereigniszeit aller Nachrichten und der maximalen Priorität der Nachrichten, mit der minimalen Ereigniszeit. Die folgende Darstellung zeigt ein Beispiel:

GVT-Approximation mit Prioritäten

Da das SPEEDES-Verfahren eine zentrale Instanz zur Bestimmung der GVT-Approximation benötigt, wurde für die Umsetzung das Master/Slave-Paradigma gewählt. Die LP-Instanzen arbeiten demnach als Slave-Instanzen und werden durch die zentrale Instanz als Master-Instanz gestartet, gesteuert und beendet. Gut zu erkennen ist diese Funktionsweise in der Darstellung des Kommunikationsablaufes des verteilten Simulators.

Kommunikationsablauf beim verteilten Simulator
 

Zusammenfassung

Im Rahmen der vorliegenden Arbeit wurden Möglichkeiten der Parallelisierung einer transaktionsorientierten Simulationsmethode unter Nutzung von Message-Passing-Systemen in einer interaktiven Softwareumgebung untersucht und die Umsetzung einer dieser Möglichkeiten anhand des Prototyps eines verteilten Simulators demonstriert. Für die Umsetzung wurde das SPEEDES-Verfahren genutzt, welches jedoch zuvor an die transaktionsorientierte Simulation angepaßt werden mußte. Die Implementation und die Validierung an Beispielmodellen führte zu der Erkenntnis, daß das SPEEDES-Verfahren zwar gut für die Umsetzung der transaktionsorientierten Simulation auf verteilten Systemen geeignet ist, es aber nicht seine volle Leistungsfähigkeit entfalten kann, da Transaktionen während ihrer Bewegung keine Simulationszeit verbrauchen und so je Transaktionsaustausch oft nur eine Transaktion übertragen werden kann.
 

Komplette Diplomarbeit

Die komplette Diplomarbeit (mit Ausnahme von einigen Teilen des Anhangs) kann hier als PDF-Datei heruntergeladen werden.
Download der kompletten Diplomarbeit (PDF, 536 KB)
 

Weiterführende Arbeit

Eine weiterführende Arbeit zu einem ähnlichen Thema ist unter folgendem Link zu finden:
M.Sc. thesis - Transaction-Oriented Simulation In Ad Hoc Grids
oder alternativ in arXiv.org unter der Dokument-ID 0704.1827