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 Analysemoglichkeiten
5 Erweiterte Taskgraphen
5.1 Darstellung der gemessenen Ablaufe
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 Moglichkeiten zur Integration
6.2.2 Umsetzung mit Hilfe von AGG
6.3 Analyse der Modellierung des Aufbaus der Vorhersage
6.3.1 Experimentelle Analyse
6.3.2 Analyse mit formalen in AGG automatisierten Methoden
6.4 Ausbaumoglichkeiten fur eine verbesserte Vorhersage
7 Verwendung der Graphgrammatik in der Vorhersageanwendung
7.1 Voruberlegungen fur die Umsetzung
7.2 Umsetzung
7.3 Bewertung
8 Beispiel einer Ablaufvorhersage
8.1 Das Testprogramm
8.2 Exemplarischer Aufbau der Vorhersage
8.3 Untersuchung der automatischen Verbesserung der Vorhersage
9 Fazit und Ausblick
A Kommunikation zwischen Analyse- und Vorhersageanwendung
B Graphregeln
B.1 Aufbau des Ablaufes
B.1.1 Typen
B.1.2 Regeln
B.2 Integrierte Vorhersage
B.2.1 Typen
B.2.2 Regeln
Zielsetzung und Themen
Die Arbeit befasst sich mit der automatischen Ablaufvorhersage für verteilte Programme, um eine effiziente Ressourcenzuordnung zu ermöglichen, ohne den Programmierer mit manuellen Optimierungen zu belasten. Ziel ist es, durch die Analyse vergangener Programmläufe eine prädiktive Modellierung zu erstellen, die den zukünftigen Programmablauf skizziert und somit als Basis für eine dynamische Zuordnungseinheit dient.
- Grundlagen der Parallelisierung und bisherige Vorgehensweisen.
- Modellierung paralleler Programme mittels Graphtransformationen und Taskgraphen.
- Entwicklung erweiterter Taskgraphen zur Darstellung von Vorhersagen.
- Automatisierter Aufbau der Vorhersage unter Verwendung der Simulationsumgebung AGG.
- Validierung des Modells durch Fallbeispiele und Analyse der Modellierungsgüte.
Auszug aus dem Buch
2.2 Neuer Ansatz
Das Ziel ist es also, dem Programmierer die Verantwortung für das optimale Verteilen der Rechenbelastung abzunehmen. Gleichzeitig soll das Betriebssystem in die Lage versetzet werden, die Zuordnung so optimal wie möglich vorzunehmen. Der Unterschied wird bei der Betrachtung der zuvor geschilderten drei Schritte deutlich.
Der Programmierer muss immer noch sein Programm im ersten Schritt in Tasks zerlegen, sollte dabei jedoch die Granularität so wählen, wie es für sein Problem angemessen ist, unabhängig von der nun beliebigen Zielmaschine.
Im nächsten Schritt müssen für die Implementierung wiederum die Tasks zu Prozessen zusammengefügt werden. Dabei sollte jetzt aber das Augenmerk auf möglichst hochgradige Parallelisierung gelegt werden. Es sollen jetzt also so viele Aufgaben wie möglich in getrennten Prozessen durchgeführt werden. Die Anzahl der Prozesse muss dabei nicht konstant sein, sondern kann sich direkt an den Möglichkeiten zur parallelen Ausführung orientieren. Diese Aufteilung muss auch nicht statisch sein. So ist es zum Beispiel auch möglich, je nach Eingabedaten, unterschiedlich viele Prozesse zu starten. Das ist, ausgehend von der Modellierung der Teilberechnungen und deren Abhängigkeiten untereinander, nicht sehr aufwändig und der Programmierer kann sich verstärkt auf das eigentliche Programm konzentrieren.
Bei der Ausführung auf dem Parallelrechner kann dieses Programm jetzt ohne Probleme auf verschiedenen Architekturen ausgeführt werden. Das Betriebssystem muss dann meist mehr Prozesse als Prozessoren zuordnen und kann so bei der Zuteilung der Prozessoren Einfluss auf die Rechenlastverteilung nehmen. Auch ist es leicht vorstellbar, dass bei solch einem Programm das Betriebssystem, bei der Belegung oder dynamisch, die Größe der Partition, die das Programm nutzen darf, ändert und die Prozesse danach neu verteilt. Es werden dann abhängig von der tatsächlichen Prozessorausnutzung dynamische Partitionen eingesetzt. In diesem Fall sorgt also das Betriebssystem allein für die möglichst optimale Abbildung auf die konkrete Maschine.
Zusammenfassung der Kapitel
1 Einleitung: Die Einleitung motiviert die Problematik der automatischen Lastverteilung in Parallelrechnern und skizziert die Idee, durch Graphtransformationen Vorhersagen für Programmabläufe zu generieren.
2 Parallelisierung von Programmen: Dieses Kapitel erläutert den klassischen Prozess von der Aufteilung über die Agglomeration bis zur Zuordnung und stellt den neuen Ansatz zur Entlastung des Programmierers vor.
3 Modellierung von parallelen Programmen: Es werden gängige Modellierungstechniken wie Kommunikationsgraphen, UML-Diagramme, Petrinetze und Taskgraphen hinsichtlich ihrer Eignung für parallele Programme analysiert.
4 Graphtransformationen: Dieses Kapitel liefert die theoretischen Grundlagen der Graphtransformation und stellt das Werkzeug AGG zur Simulation und Analyse vor.
5 Erweiterte Taskgraphen: Hier wird eine neue Notation entwickelt, die messbare Ablaufdaten integriert und alternative Abläufe für Vorhersagezwecke modellierbar macht.
6 Modellierung des automatischen Aufbaus der Vorhersage: Der Fokus liegt auf der Umsetzung des Modells mittels AGG, einschließlich der Definition von Graphregeln zur Erkennung und Vorhersage von Programmabläufen.
7 Verwendung der Graphgrammatik in der Vorhersageanwendung: Dieses Kapitel beschreibt die praktische Implementierung des Vorhersagesystems als eigenständiges Programm, welches die entwickelte Graphgrammatik als Kernlogik nutzt.
8 Beispiel einer Ablaufvorhersage: Anhand des Testprogramms "mptte" wird die Funktionsweise und automatische Anpassungsfähigkeit der entwickelten Vorhersage demonstriert.
9 Fazit und Ausblick: Zusammenfassung der Ergebnisse hinsichtlich der Eignung des Verfahrens und Diskussion potenzieller Verbesserungen durch statistische Analysen.
Schlüsselwörter
Ablaufvorhersage, Parallele Programme, Graphtransformation, AGG, Graphgrammatik, Taskgraphen, Lastverteilung, Betriebssystem, Automatisierung, Modellierung, Dynamische Partitionierung, Scheduling, Simulation.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Diplomarbeit behandelt die automatische Vorhersage von Programmabläufen für verteilte Systeme, um die Lastverteilung auf Parallelrechnern zu optimieren, ohne manuelle Anpassungen durch den Programmierer zu erfordern.
Was sind die zentralen Themenfelder?
Die Arbeit vereint Methoden der Parallelprogrammierung, Graphentheorie und Graphtransformationssysteme zur Modellierung und Simulation von Programmstrukturen.
Was ist das primäre Ziel der Untersuchung?
Ziel ist es, ein Modell zu entwickeln, das automatisch aus Beobachtungen vergangener Programmläufe eine Vorhersage generiert, die als Basis für eine intelligente Zuordnungseinheit dienen kann.
Welche wissenschaftliche Methode wird verwendet?
Es wird ein regelbasierter Ansatz mittels Graphtransformationen und Graphgrammatiken verfolgt, wobei das Werkzeug AGG zur Simulation und experimentellen Analyse eingesetzt wird.
Was wird im Hauptteil behandelt?
Der Hauptteil befasst sich mit der Entwicklung erweiterter Taskgraphen, der Formalisierung dieser in Graphregeln für AGG sowie der Implementierung einer Vorhersageanwendung, die diese Regeln zur Laufzeit anwendet.
Welche Schlüsselwörter charakterisieren die Arbeit?
Ablaufvorhersage, Graphtransformation, Parallelrechner, Taskgraphen, AGG, Lastverteilung und automatische Modellanpassung.
Wie wird mit Schleifen in den Programmabläufen umgegangen?
Im Modell wird ein spezieller Schleifenknoten als Spezialisierung der Bedingung eingeführt, um Zyklen im Graphen kontrolliert und ohne unnötige Komplexität darzustellen.
Was ist der Vorteil der Implementierung mittels Graphtransformation?
Der Hauptvorteil ist, dass die entwickelte Graphgrammatik direkt als Kernlogik des Vorhersageprogramms dienen kann, was die Konsistenz zwischen Modell und Implementierung sicherstellt und den Entwicklungsaufwand reduziert.
- Arbeit zitieren
- Jörg Schneider (Autor:in), 2004, Ablaufvorhersage für verteilte Programme mit Hilfe von Graphtransformationen, München, GRIN Verlag, https://www.grin.com/document/25842
