Ablaufvorhersage für verteilte Programme mit Hilfe von Graphtransformationen

Mémoire (de fin d'études) , 2004 , 84 Pages , Note: 1,3

Informatique - Programmation

Für die Lösung von rechenintensiven Problemen werden häufig Parallelrechner eingesetzt.
Diese werden in der Regel so gebaut, dass nicht alle Prozessoren die selben
Ressourcen nutzen oder dass der Rechner gleich aus vielen in sich abgeschlossenen
Rechnern – Cluster von Rechnern – besteht. Da nicht nur die dazu notwendige
Kommunikation zwischen zwei Programmteilen stark von den jeweils ausf¨uhrenden
Prozessoren abhängt, muss ein Programm an die Struktur dieses parallelen Rechners
angepasst werden. Diese Aufgabe soll dem Programmierer eine Zuordnungseinheit
abnehmen, die entscheidet, welches Teilprogramm zu welcher Zeit auf welchem Teilsystem
ausgeführt wird. Diese Entscheidung ist allerdings schwierig zu treffen, wenn
Informationen über das Programm kaum und vor allem über den zukünftigen Ablauf
nicht bekannt sind. Wenn die Anpassung an die Struktur des Rechners erst kurz
vor der Ausführung des Programms oder während des Programmlaufes stattfindet, so
kann das Programm ohne Modifikationen auf Rechnern mit unterschiedlicher Architektur
eingesetzt werden. Auf dieseWeise wird nicht nur der Programmierer entlastet,
sondern auch mehr Flexiblität bei der Ausführung erreicht.
Es ist also ein Weg zu suchen, der ausgehend von Informationen aus vergangenen
Programmläufen und dem bisherigen Verlauf des Programms den zukünftigen Programmablauf
mit einer Vorhersage skizziert. Die in dieser Arbeit beschriebene Vorhersage
kann dann als Basis für eine Zuordnungseinheit dienen. Die Informationen
über den aktuellen Programmzustand sollen von einer getrennten Analyseanwendung
bereitgestellt werden.Wie das Programm beobachtet werden kann und welche Werte
gemessen werden können, wurde dazu in [Gra04] untersucht.
Da die Programmabläufe sich klassischer Weise als Graph darstellen lassen, ist
eine Möglichkeit, diese Graphen mit Hilfe eines Graphtransformationssystems auf
dem laufenden Stand zu halten. Graphtransformationssysteme beschreiben das regelbasierte
Modifizieren von graphartigen Strukturen. Sie sind als Spezifikationstechnik
formal definiert. Allerdings ist es leicht vorstellbar, dass sich mit solchen Regelsystemen
auch programmieren lässt. Es soll daher auch untersucht werden, inwieweit
sich die Regeln, mit denen sich der Aufbau der Vorhersage modellieren lässt, auch
zur Umsetzung in einem Vorhersageprogramm nutzen lassen. [...]

Inhaltsverzeichnis

• 1 Einleitung
• 2 Parallelisierung von Programmen
  • 2.1 Aktuelle Vorgehensweise
  • 2.2 Neuer Ansatz
• 3 Modellierung von parallelen Programmen
  • 3.1 Kommunikationsgraphen
  • 3.2 Ablaufmodellierung mit UML
  • 3.3 Petrinetze
  • 3.4 Taskgraphen
• 4 Graphtransformationen
  • 4.1 Graphen formal betrachtet
  • 4.2 Graphtransformationen
  • 4.3 AGG – Ein Programm zur Simulation von Graphtransformationen
    • 4.3.1 Regeln
    • 4.3.2 Grammatik
    • 4.3.3 Analysemöglichkeiten
• 5 Erweiterte Taskgraphen
  • 5.1 Darstellung der gemessenen Abläufe
  • 5.2 Darstellung der Kommunikation und Kooperation
  • 5.3 Darstellung der Vorhersage
  • 5.4 Bewertung.
• 6 Modellierung des automatischen Aufbaus der Vorhersage
  • 6.1 Erkennung des Ablaufes
    • 6.1.1 Umsetzung mit Hilfe von AGG
    • 6.1.2 Graphregeln zur Erkennung des Ablaufes
  • 6.2 Integration einer einfachen Vorhersage
    • 6.2.1 Möglichkeiten zur Integration
    • 6.2.2 Umsetzung mit Hilfe von AGG
  • 6.3 Analyse der Modellierung des Aufbaus der Vorhersage
    • 6.3.1 Experimentelle Analyse

Zielsetzung und Themenschwerpunkte

Diese Diplomarbeit beschäftigt sich mit der Vorhersage des Ablaufs verteilter Programme mithilfe von Graphtransformationen. Das Ziel ist es, eine Methode zu entwickeln, die es ermöglicht, den Ablauf eines Programms vorherzusagen, bevor es tatsächlich ausgeführt wird.

• Parallelisierung von Programmen
• Modellierung von parallelen Programmen
• Graphtransformationen
• Erweiterte Taskgraphen
• Automatischer Aufbau der Vorhersage

Zusammenfassung der Kapitel

Die Arbeit beginnt mit einer Einführung in die Thematik der Parallelisierung von Programmen und stellt die aktuelle Vorgehensweise sowie einen neuen Ansatz vor. Im Anschluss werden verschiedene Modelle zur Modellierung von parallelen Programmen, wie Kommunikationsgraphen, UML, Petrinetze und Taskgraphen, vorgestellt.

Kapitel 4 widmet sich den Graphtransformationen. Es werden die formalen Grundlagen von Graphen und Graphtransformationen erläutert sowie das Programm AGG zur Simulation von Graphtransformationen vorgestellt. In Kapitel 5 werden erweiterte Taskgraphen zur Darstellung der gemessenen Abläufe, der Kommunikation und Kooperation sowie zur Darstellung der Vorhersage eingeführt. Abschließend wird die Bewertung dieser Modellierung diskutiert.

Kapitel 6 befasst sich mit der Modellierung des automatischen Aufbaus der Vorhersage. Die Erkennung des Ablaufes mittels AGG und die Integration einer einfachen Vorhersage werden beschrieben. Die Analyse der Modellierung des Aufbaus der Vorhersage durch experimentelle Analyse rundet die Arbeit ab.

Schlüsselwörter

Parallelisierung, verteilte Programme, Graphtransformationen, Taskgraphen, Vorhersage, Ablaufmodellierung, AGG, Kommunikation, Kooperation, experimentelle Analyse.

• Université: Technical University of Berlin (Kommunikations- und Betriebssystem - Fak. IV Elektrotechnik und Informatik)
• Note: 1,3
• Auteur: Jörg Schneider (Auteur)
• Année de publication: 2004
• Pages: 84
• N° de catalogue: V25842
• ISBN (ebook): 9783638283588
• Langue: allemand
• mots-clé: Ablaufvorhersage, Programme, Hilfe, Graphtransformationen