Diplomarbeit

Ablaufvorhersage für verteilte Programme
 mit Hilfe von Graphtransformationen

von

Jörg Schneider

22. April 2004

Inhaltsverzeichnis

1 Einleitung ... 7

2 Parallelisierung von Programmen  ... 9
2.1 Aktuelle Vorgehensweise  ...  9
2.2 Neuer Ansatz  ...  11

3 Modellierung von parallelen Programmen ... 15
3.1 Kommunikationsgraphen ...  15
3.2 Ablaufmodellierung mit UML  ... 15
3.3 Petrinetze ... 17
3.4 Taskgraphen ...  18

4 Graphtransformationen  ... 21
4.1 Graphen formal betrachtet ...  21
4.2 Graphtransformationen  ...  22
4.3 AGG – Ein Programm zur Simulation von Graphtransformationen ...  26
4.3.1 Regeln  ... 27
4.3.2 Grammatik ... 28
4.3.3 Analysemöglichkeiten ... 29

5 Erweiterte Taskgraphen  ... 31
5.1 Darstellung der gemessenen Abläufe ...  31
5.2 Darstellung der Kommunikation und Kooperation  ...  33
5.3 Darstellung der Vorhersage ...  34
5.4 Bewertung  ... 35

6 Modellierung des automatischen Aufbaus der Vorhersage  ... 39
6.1 Erkennung des Ablaufes  ...  39
6.1.1 Umsetzung mit Hilfe von AGG ... 39
6.1.2 Graphregeln zur Erkennung des Ablaufes ... 41
6.2 Integration einer einfachen Vorhersage ...  42
6.2.1 Möglichkeiten zur Integration  ...  42
6.2.2 Umsetzung mit Hilfe von AGG  ...  45
6.3 Analyse der Modellierung des Aufbaus der Vorhersage  ...  49
6.3.1 Experimentelle Analyse ... 49
6.3.2 Analyse mit formalen in AGG automatisierten Methoden . . 50
6.4 Ausbaumöglichkeiten für eine verbesserte Vorhersage ...  54

7 Verwendung der Graphgrammatik in der Vorhersageanwendung  ... 55
7.1 Vorüberlegungen für die Umsetzung ... 55
7.2 Umsetzung ...  56
7.3 Bewertung ... 57

8 Beispiel einer Ablaufvorhersage  ... 59
8.1 Das Testprogramm  ...  59
8.2 Exemplarischer Aufbau der Vorhersage  ... 60
8.3 Untersuchung der automatischen Verbesserung der Vorhersage  ...  62

9 Fazit und Ausblick  ... 63

A Kommunikation zwischen Analyse- und Vorhersageanwendung  ... 65
B Graphregeln  ... 71
B.1 Aufbau des Ablaufes ... 71
B.1.1 Typen ...  71
B.1.2 Regeln ...  71
B.2 Integrierte Vorhersage ... 73
B.2.1 Typen ...  73
B.2.2 Regeln  ...  73

Literaturverzeichnis 81

1 Einleitung

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ührenden 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 diese Weise 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.

Zuerst soll die Motivation untermauern, welche Vorteile aus einer automatisierten Zuordnung entstehen und warum eine Vorhersage dabei hilfreich ist. Dann werde ich die verwendeten Konzepte zur Beschreibung von parallelen Programmen und der Graphtransformation erläutern. Anschließend will ich eine Erweiterung zur Darstellung von Vorhersagen einführen und darauf aufbauend Graphregeln definieren, mit denen diese Vorhersagen generiert werden können. Das so entstandene Modell soll dann als Basis für eine Implementierung einer Vorhersageanwendung dienen. Am Beispiel eines parallelen Programms werde ich den Aufbau der Vorhersage zeigen und dann prüfen, ob die Vorhersage ein realistisches Bild des Programmablaufs darstellt.

2 Parallelisierung von Programmen

Der Einsatz von Parallelrechnern soll es ermöglichen, größere Probleme (scale-up) oder gleich große in kürzerer Zeit (speed-up) zu lösen [Hei94]. Die Rechner verfügen dazu über mehrere Prozessoren, die gleichzeitig an unterschiedlichen Teilberechungen arbeiten können.

Um die Möglichkeiten des Parallelrechners auszunutzen, muss das Programm bereits so angepasst werden, dass Berechnungen, die gleichzeitig stattfinden können, auch gleichzeitig auf den verschiedenen Prozessoren des Rechners ausgeführt werden können. Dazu werden die notwendigen Berechnungen in Prozesse aufgeteilt, die wiederum von den einzelnen Prozessoren des konkreten Parallelrechners (Zielmaschine) ausgeführt werden. Um mehreren Nutzern den Zugang zu einem Parallelrechner zu gewähren, werden diese häufig mit Space-Sharing betrieben. Dabei erhalten die Nutzer jeweils eine Partition des Rechners zugewiesen, auf der ihre Programme exklusiv ablaufen.

2.1 Aktuelle Vorgehensweise

Es sind drei Schritte von der Programmidee beziehungsweise dem Algorithmus bis zur konkreten Ausführung auf einem Parallelrechner notwendig [RR00]:

• Aufteilung
• Agglomeration
• Zuordnung

Zuerst werden die notwendigen Berechnungen in Teilberechnungen oder Aufgaben (Tasks) zerlegt. Dabei wird bisher davon ausgegangen, dass man sich bei der Aufteilung bereits an den offensichtlichen Möglichkeiten der Zielmaschine orientieren sollte. Das heißt, es muss nicht soweit aufgeteilt werden, wie es der Algorithmus ermöglicht, wenn die Zielmaschine nicht über entsprechend viele Prozessoren verfügt. Die Teilberechnungen können von anderen abhängig sein, zum Beispiel, wenn eine Berechnung auf dem Ergebnis einer vorherigen Berechnung beruht. Als Ergebnis dieses Schrittes sollte der Programmierer eine Übersicht haben, welche Teilberechnungen notwendig sind und wie sie voneinander abhängen.

[....]