Ablaufvorhersage für verteilte Programme mit Hilfe von Graphtransformationen

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
6.3.2 Analyse mit formalen in AGG automatisierten Methoden
6.4 Ausbaumöglichkeiten für eine verbesserte Vorhersage

7 Verwendung der Graphgrammatik in der Vorhersageanwendung
7.1 Vorüberlegungen für 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

Literaturverzeichnis

1 Einleitung

Für die Lösung von rechenintensiven Problemen werden häufig Parallelrechner ein- gesetzt. Diese werden in der Regel so gebaut, dass nicht alle Prozessoren die selben Ressourcen nutzen oder dass der Rechner gleich aus vielen in sich abgeschlosse- nen 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 Teil- system ausgeführt wird. Diese Entscheidung ist allerdings schwierig zu treffen, wenn Informationen über das Programm kaum und vor allem über den zukünftigen Ab- lauf 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 Archi- tektur 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 Darstel- lung 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 dar- stellt.

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 Teilberechun- gen arbeiten können.

Um die Möglichkeiten des Parallelrechners auszunutzen, muss das Programm be- reits 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 wie- derum 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 Nut- zer 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 Aufga- ben (Tasks) zerlegt. Dabei wird bisher davon ausgegangen, dass man sich bei der Aufteilung bereits an den offensichtlichen Möglichkeiten der Zielmaschine orien- tieren sollte. Das heißt, es muss nicht soweit aufgeteil werden, wie es der Algo- rithmus ermöglicht, wenn die Zielmaschine nicht über entsprechend viele Prozes- soren verfügt. Die Teilberechnungen können von anderen abhängig sein, zum Bei- spiel, 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.

Im nächsten Schritt vor der Implementierung muss der Programmierer entschei- den, wie er die Teilberechnungen zu Prozessen zusammenfügt. Momentan ist es üblich, dass der Programmierer bei dieser Entscheidung den konkreten Aufbau der

2 Parallelisierung von Programmen

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Der Entwicklungsprozess vom Algorithmus bis zur Ausführung. Der vorgestellte Ansatz soll mehr Flexiblität bei der Zuordnung ermöglichen und weniger Aufwand bei der Agglomeration erzeugen.

Zielmaschine berücksichtigt [RR00]. Das Ziel der Aufteilung soll dann eine mög- lichst optimale Verteilung der entstehenden Rechen- und Kommunikationslast auf die verschiedenen Prozesse sein. Die Rechenlast wird dabei über die mögliche Anzahl der Berechnungen für jede Teilberechnung abgeschätzt und soll dann in der Sum- me für alle Prozesse relativ zu den Kapazitäten der einzelnen Knoten der Zielma- schine möglichst gleichverteilt sein. Damit soll gewährleistet werden, dass alle zur Verfügung stehenden Prozessoren ausgelastet sind und kein Prozess, mit einer deut- lichen längeren Bearbeitungszeit als die anderen Prozesse, die Gesamtberechnung verzögert. Ein weiteres Kriterium ist das Kommunikationsverhalten. Dabei sollen möglichst wenige Daten zwischen zwei Prozessen ausgetauscht werden, da diese auf verschiedenen Prozessoren ausgeführt werden können und die Daten dann aufwändig übertragen werden müssen. Das lässt sich zum Beispiel dadurch erreichen, dass mit den selben Daten arbeitende Teilberechnungen auch im gleichen Prozess ausgeführt werden (Datenlokalität).

Diese Aufteilung wird auch als Agglomeration [Fos95] (teilweise etwas zweideu- tig auch als Scheduling [RR00]) bezeichnet. Hinsichtlich der Herangehensweisen wird zwischen statischer und dynamischer Agglomeration unterschieden. Während bei der statischen Agglomeration die Aufteilung bei jedem Lauf gleich ist, kann bei der dynamischen Agglomeration, während der Ausführung die Aufteilung vom par- allelen Programm geändert werden. Allerdings werden auch dabei die wichtigsten

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.2: Einordnung der Begriffe Programm, Prozess und Task

Entscheidungen zur Aufteilung vom Programmierer im Rahmen der Implementierung getroffen.

Im letzten Schritt werden die Prozesse beim so genannten Mapping vom Betriebs- system zur Ausführung den konkreten Prozessoren der Zielmaschine zugeordnet. Da- bei versucht das Betriebssystem eine optimale Auslastung der Prozessoren zu finden. Wenn der Programmierer, wie es heutzutage üblich ist, genau so viele Prozesse er- zeugt hat, wie es Prozessoren in diesem Rechner gibt, ist diese Zuordnung trivial.

Das stellt den größten Vorteil der aktuellen Vorgehensweise dar. Das Betriebssys- tem benötigt für das Mapping keine weitergehenden Informationen über das Pro- gramm und kann sehr einfach die Mappingentscheidungen treffen. Die optimale Last- und Kommunikationsverteilung ist wie beschrieben bisher die Aufgabe des Program- mierers. Auf der einen Seite kann er den besten Überblick über sein Programm haben, aber andererseits ist die optimale Aufteilung ein zusätzlicher Aufwand. Ein weiterer Nachteil ist, dass das Programm auf eine konkrete Maschine optimiert ist. Wenn dem Programm eine größere oder kleinere Partition der Maschine zur Verfügung steht oder das Programm gar auf einem anderen Parallelrechner ausgeführt werden soll, hat das Betriebssystem kaum Spielraum, eine optimale Zuordnung zu finden. Das selbe Problem tritt auf, wenn das Betriebssystem die zur Verfügung stehenden Res- sourcen dynamisch verwalten soll und so mehrere gleichzeitig laufende Programme möglichst optimal auf die Maschine verteilen soll.

2.2 Neuer Ansatz

Das Ziel ist es also, dem Programmierer die Verantwortung für das optimale Ver- teilen 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 Pro- zessen zusammengefügt werden. Dabei sollte jetzt aber das Augenmerk auf mög- lichst hochgradige Parallelisierung gelegt werden. Es sollen jetzt also so viele Aufga- ben wie möglich in getrennten Prozessen durchgeführt werden. Die Anzahl der Pro- zesse 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 Programmie- rer kann sich verstärkt auf das eigentliche Programm konzentrieren.

Bei der Ausführung auf dem Parallelrechner kann dieses Programm jetzt ohne Pro- bleme 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 vor- stellbar, 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 Pro- zessorausnutzung dynamische Partitionen¹ [FRS+97] einsetzt. In diesem Fall sorgt also das Betriebssystem allein für die möglichst optimale Abbildung auf die konkre- te Maschine.

Ein Nachteil bei dieser Vorgehensweise ist allerdings, dass Informationen über das Programm, die der Programmierer bei der anderen Vorgehensweise eventuell berücksichtigt hätte, vom Betriebssystem nicht in die Entscheidung einfließen. So sollte der Programmierer auf Datenlokalität achten. Das Betriebssystem dagegen kann nicht erahnen, welche Teilberechnungen in welchen Prozessen auf die selben Daten zugreifen. Auch konnte der Programmierer bereits grob abschätzen, wie lan- ge die verschiedenen Berechnungen dauern würden. Weiterhin gibt es Mehrkosten bei der parallelen Ausführung auf einem Prozessor gegenüber der sequentiellen Aus- führung, die zum Beispiel durch die Kontextwechsel entstehen. Diese Mehrkosten können reduziert werden, wenn die Prozesse vom Betriebssystem wie zum Beispiel beim Gang-Scheduling nacheinander ausgeführt werden. Dazu müsste das Betriebs- system aber wiederum Informationen über die Prozesse und ihr Verhalten in der Zu- kunft haben.

Der Ansatz besteht nun darin, die Flexiblität zu erhöhen, ohne die vorgestellten Nachteile auftreten zu lassen. Es sollen Vorhersagen des Programmablaufs erstellt werden, damit das Betriebssystem die Entscheidungen treffen kann, die vorher der Programmierer explizit oder implizit gut oder weniger gut treffen musste. Die dazu

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.3: Verwendung einer Vorhersage für die Zuordnung von Prozessoren

notwendigen Informationen können direkt vom Programmierer geliefert werden oder sie müssen aus dem fertigen Programm entnommen werden. Da der Programmierer entlastet werden soll, wird hier der zweite Weg untersucht.

Das Betriebssystem muss also eine automatisch generierte Vorhersage über den vermutlichen Programmablauf erhalten. Diese soll dann als Basis für eine entsprechend erweiterte Zuordnungseinheit dienen und auf den Beobachtungen vergangener Abläufe beruhen. Dabei wird davon ausgegangen, dass sich die einzelnen Abläufe des Programms so stark ähneln, dass aus einer Menge von Beobachtungen eine akzeptable Vorhersage generiert werden kann.

Die Umsetzung dieses Ansatzes kann in drei Aufgaben unterteilt werden. Als ers- tes müssen die einzelnen Programmläufe beobachtet werden und die Messwerte zur Rechen- und Kommunikationslast aufbereitet, aber auch die Struktur der Abläufe ge- eignet erkannt werden. Im nächsten Schritt müssen diese Daten zu einem Modell eines konkreten Ablaufes zusammengefasst werden und dann aus einer Menge dieser Modelle eine Vorhersage für künftige Abläufe erstellt werden. Als letztes muss die Zuordnungseinheit so erweitert werden, dass sie die Informationen der Vorhersage geeignet berücksichtigt.

In dieser Arbeit sollen Lösungsansätze für den zweiten Aufgabenbereich vorgestellt werden. Verfahren für die geeignete Messung und Bereitstellung der Messwerte werden in [Gra04] präsentiert. Die Möglichkeiten zur Erweiterung der Zuordnungseinheit werden derzeit in einer weiteren Arbeit untersucht.

Die Vorhersage soll automatisch aus den Beobachtungen vorheriger Programm- läufe erstellt werden und sich an den aktuellen Stand des vorhergesagten Programm- laufes anpassen. Die Vorhersage soll sich anpassen, wenn sie den beobachteten Pro- grammlauf nicht vorhergesagt hat. Ein weiteres Ziel ist, dass ein Programmlauf, wenn er ein zweites Mal unverändert beobachtet wird, fehlerfrei vorhergesagt wird. Zuerst soll der Aufbau der Vorhersage mit Hilfe von Graphtransformationen modelliert wer- den. Anschließend wird überprüft, ob sich das entstandene Graphtransformations- system direkt für eine Implementierung der hier vorgestellten Vorhersageanwendung einsetzen lässt.

3 Modellierung von parallelen Programmen

Für die Entwicklung von parallelen Programmen muss für die im vorherigen Kapi- tel beschriebenen Schritte zuerst ein Modell des Algorithmuses angefertigt werden, aus dem die Eigenschaften der Aufteilung in Teilberechnungen ersichtlich sind. Die- ses Modell bildet dann die Basis für die Agglomeration und die Implementation. Im Folgenden sollen einige bekannte Modellierungstechniken für parallele Program- me beziehungsweise Softwaresysteme allgemein vorgestellt werden. Die Modellie- rungstechniken werden als Basis zur Entwicklung der Darstellung einer Vorhersage genutzt.

3.1 Kommunikationsgraphen

Mit Hilfe von Kommunikationsgraphen [Hei94, HH89] kann man übersichtlich dar- stellen, welche Teile eines parallelen Programms mit welchen anderen Teilen kom- munizieren. Dabei werden die einzelnen Prozesse als Knoten dargestellt. Es wird davon ausgegangen, dass die Anzahl der Prozesse konstant ist. Miteinander kommu- nizierende Prozesse werden mit einer Kante verbunden. An die Kanten kann dann zusätzlich in Form eines Gewichts eine Kenngröße für die Kommunikation notiert werden.

Die Kommunikationsgraphen stellen dabei entweder die gesamte Kommunikation während des Programmlaufes dar oder sie bilden das Kommunikationsverhalten eines Zeitpunktes beziehungsweise einer Phase des Programms ab. Da die Kommunikati- onsinfrastruktur der Zielmaschine meist als konstant angenommen wird, bietet die Gesamtkommunikation ein geeignetes Bild der Zuordnung von Kommunikationsin- frastruktur und der anfallenden Kommunikation. Für ein feineres Bild, das ebenfalls die zeitlichen Änderungen im Kommunikationsverhalten berücksichtigt sind die dy- namischen Kommunikationsgraphen [Hei94] geeignet. Diese stellen in einer Art Pha- senmodell das Kommunikationsverhalten für mehrere Phasen des Programmablaufs dar.

3.2 Ablaufmodellierung mit UML

Im Rahmen von UML¹ sind eine Reihe von visuellen und textuellen Notationen für den Softwareentwicklungsprozess definiert. Darunter fallen auch die Aktivitätsdia- gramme (activity diagrams) und die Zustandsdiagramme (state charts). Diese beiden

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.1: Dynamische Kommunikationsgraphen stellen das Kommunikations- verhalten in verschiedenen Phasen des Programmablaufs dar (aus [Hei94]).

in der Notation recht ähnlichen Diagramme wurden zur Darstellung des Verhaltens eines Softwaresystems entworfen. Eine Übersicht über UML und darin definierte Techniken bietet unter anderem [Par98].

In einem Zustandsdiagramm stehen die Knoten für die Zustände des Systems und die Kanten für mögliche Übergänge, wobei mehrere Zustandsübergänge von einem Zustand ausgehen können, von denen wiederum aber immer nur einer ausgeführt wird. Diese Zustandsübergänge sind ereignisgesteuert, wobei die Ereignisse von an- deren Zustandsübergängen oder von der Systemumgebung erzeugt werden. Die Er- zeugung von Ereignissen und die Reaktion auf Ereignisse stellen eine synchrone Kommunikation dar. Die Verknüpfung zwischen dem Sender und den Empfängern wird allerdings nicht visuell notiert, sondern durch den Signalnamen gekennzeich- net. In den Zustandsdiagrammen können auch nebenläufige Prozesse dargestellt wer- den. Dabei werden die Abläufe, die gleichzeitig stattfinden können, in unterschiedli- chen Teildiagrammen, getrennt durch eine Linie notiert. Diese Teildiagramme kön- nen auch eine Verfeinerung eines Zustandes sein, so dass auch Abläufe mit sich änderndem Grad der Nebenläufigkeit dargestellt werden können.

Im Gegensatz dazu stehen bei den Aktivitätsdiagrammen die Knoten für Akti- vitätszustände [Par98]. Mit diesen Aktivitäten lassen sich die Teilberechnungen aus dem vorhergehenden Kapitel darstellen. Die Kanten stehen für die Übergänge. Ein Übergangwird ausgeführt, wenn die entsprechende Aktivität beendet wurde. Für die Steuerung des Kontrollflusses existieren weitere Elemente, mit denen ein bedingter Übergang oder Nebenläufigkeit notiert werden kann. Für die Bedingungen wird ein

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2: Zwei Notationen für Abläufe aus UML: a) Zustandsdiagramme b) Aktivitätsdiagramme

Bedingungsknoten eingefügt, der wiederum mehrere ausgehende Kanten besitzt. Von diesen wird jeweils eine ausgewählt und die darauf folgende Aktivität ausgeführt. Für die Nebenläufigkeit gibt es spezielle Aufteilungs- und Zusammenführungsknoten. Von den Aufteilungsknoten gehen mehrere Kanten aus und wenn die vorhergehen- de Aktivität beendet wurde, werden alle nachfolgenden aktiviert. Bei den Zusam- menführungsknoten wird die nachfolgende Aktivität erst ausgeführt, wenn alle Vor- gänger beendet wurden.

Die Notationen für Nebenläufigkeit und bedingte Abläufe der Aktivitätsdiagramme sollen als Vorbild für die hier entwickelte Notation der Vorhersage dienen.

3.3 Petrinetze

Eine weitere Technik zur Darstellung von Abläufen sind Petrinetze. Die Petrinetze und ihr Verhalten sind formal definiert und sind daher für Analysen geeignet. Mit ihrem Schaltverhalten lassen sich nebenläufige Abläufe gut darstellen.

Ein Petrinetz besteht aus zwei Typen von Knoten: den Stellen und Transitionen. Die Stellen können eine Markierung, die so genannten Token, besitzen. Kanten kön- nen nur zwischen Knoten unterschiedlichen Typs verlaufen. Wenn auf allen Stellen des Vorbereichs einer Transition, das heißt allen Stellen von denen eine Kante zu die- ser Transition läuft, mindestens ein Token liegt, kann diese Transition schalten. Wenn sie schaltet, wird von allen Stellen des Vorbereichs je ein Token entfernt und auf alle Stellen, an denen eine Kante von dieser Transition endet, je ein Token hinzugefügt. Wenn sich die Vorbereiche nicht überschneiden, können die Transitionen gleichzeitig

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.3: Ein Petrinetz als Modell eines parallelen Programms mit vier Pro- zessen (aus [Ang98], die Zeitinformationen sind nicht dargestellt) schalten, daher eignen sie sich auch gut für die Modellierung von parallelen Programmen [HH89].

Es gibt inzwischen eine Reihe von Erweiterungen, um zusätzliche Informationen mit zu modellieren. Beispiele dafür sind Erweiterungen, die dem Verhalten des Petri- netzes auch Zeitinformationen zuordnen. Diese Timed Petri Nets wurden in [Ang98] genutzt um parallele Programme mit ihrem erwarteten Verhalten und ihrer erwarteten Kommunikation darzustellen. Die Petrinetze sollen dabei mit Hilfe des Entwicklers entstehen. Da die Stellen und Transitionen jedoch ununterscheidbar sind, lässt sich aus dem entstandenen Petrinetz nur schwer die Struktur des Programms ablesen (Ab- bildung 3.3).

3.4 Taskgraphen

Im Kapitel 2 wurde beschrieben, dass für die Agglomeration ein Modell des Programms notwendig ist, aus dem für jede Teilaufgabe ersichtlich ist, von welchen Teilaufgaben sie abhängt. Teilaufgaben können zum Beispiel dadurch voneinander abhängen, dass eine auf dem Ergebnis der anderen beruht.

Dieses Modell wird klassischerweise mit einem Taskgraphen [RR00, Fos95, Fea94] (Präzedenzgraphen [Ger82], Vorgängergraphen [Hei94]) dargestellt. In einem Task- graphen steht jeder Knoten für eine Teilaufgabe (Task) und die Pfeile zeigen je- weils auf die davon abhängigen Teilaufgaben. Mit Hilfe dieses Graphen kann man,

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.4: Ein Taskgraph ohne Gewichte und eine mögliche Aufteilung in Pro- zesse

wie bereits beschrieben, ein Programm in mehrere paralelle Prozesse aufteilen. Diese Prozesse führen dann die einzelnen Teilaufgaben nacheinander aus und sorgen durch geeignete Synchronisationstechniken dafür, dass die im Taskgraphen definierten Abhängigkeiten eingehalten werden.

Da eine Teilaufgabe weder direkt noch indirekt von sich selbst abhängig sein kann, sind die Taskgraphen als zyklenfreie gerichtete Graphen (DAG² ) definiert. Wenn ein Programm jedoch sehr stark von Schleifen Gebrauch macht, wird der Taskgraph damit unnötig groß. Ursache dafür ist, dass die Tasks des Schleifenkörpers je Schleifendurchlauf einmal notiert werden. Es wurden daher in der Literatur verschiedene Ansätze vorgestellt, die Schleifenkonstrukte möglichst nahtlos in die ansonsten zyklenfreien Taskgraphen zu integrieren [YF97, GK91].

In einem Taskgraphen können noch weitere Informationen modelliert werden. Wenn davon ausgegangen wird, dass die einzelnen Task potenziell auf verschie- denen Rechnern ausgeführt werden, sind sie nicht nur voneinander abhängig, son- dern es müssen auch die notwendigen Daten zwischen den ausführenden Einheiten übertragen werden, damit der darauffolgende Task ausgeführt werden kann. Daher wird dann eine Abhängigkeit mit einer synchronen Kommunikation gleichgesetzt und die Abhängigkeitspfeile mit einem Gewicht markiert, das den Kommunikati- onskosten entspricht. Die einzelnen Teilaufgaben wiederum sind nicht alle gleich aufwändig. Daher gibt es auch eine Erweiterung, in der die Knoten im Taskgraphen mit einem Gewicht für den Aufwand dieser Teilaufgabe markiert werden [Fea94].

Mit Hilfe eines Taskgraphen ist es dann möglich, die Teilberechnungen auf die Prozesse zu verteilen. Vor allem im Bereich der eingebetten Systeme wird solch ein Taskgraph als Basis genommen, um die einzelnen Aufgaben auf einen oder meh- rere Prozessoren zu verteilen. Mit Hilfe der zusätzlichen Informationen kann dann abgeschätzt werden, wie lange die jeweiligen Prozesse laufen beziehungsweise wie- viel Zeit das gesamte Programm bis zur Beendigung benötigt. Es gibt eine Reihe von Algorithmen, die eine Aufteilung oder eine Reihenfolge finden, bei der die ab- geschätzte Ausführungszeit für eine gegebene Maximalanzahl an Prozessen minimal wird [Ger82, YG94, KA96].

Das Konzept der Taskgraphen soll die Basis für die Darstellung des Ablaufs eines parallelen Programms sein. Der zukünftige Ablauf eines Programms soll ebenfalls mit Taskgraphen dargestellt werden, damit bei der Zuordnung die für Taskgraphen bekannten Konzepte zur Verteilung verwendet werden können. Allerdings sind noch einige Erweiterungen notwendig, um auch Vorhersagen darstellen zu können. Zu- dem sollen die Informationen über das Kommunikationsverhalten explizit modelliert werden, um auch die asynchrone Kommunikation geeignet darzustellen.

4 Graphtransformationen

Modellierung mit Hilfe von Graphen wird inzwischen in vielen Bereichen der Infor- matik genutzt, vor allem, da sich die mit solchen Graphen dargestellten Informationen formal betrachten lassen. Gleichzeitig sind sie eine intuitiv verständliche Darstellung. Mit Hilfe der Graphtransformation ist es möglich, Graphen regelbasiert zu modifizie- ren.

Da die Vorhersage des parallelen Programms eine Graphstruktur sein wird, bietet sich die Graphtransformation als Werkzeug an, um zu untersuchen, wie solch eine Vorhersage entstehen kann. Der Aufbau der Vorhersage soll durch ein Graphtrans- formationssystem modelliert werden. Anschließend wird untersucht, inwieweit sich dieses Modell des Aufbaus der Vorhersage für eine mögliche Implementierung nut- zen lässt.

4.1 Graphen formal betrachtet

Ein Graph besteht aus einer Menge von Knoten E und einer Menge von Kanten V . Außerdem muss für jede Kante eine Zuordnung definiert werden, an welchem Knoten sie beginnt (s) und an welchem Knoten sie endet (t). Wie im vorherigen Kapitel beschrieben, besteht ein Graph häufig aus mehreren Arten von Knoten und Kanten. Diese Typisierung erfolgt durch die Labelmenge L und die Zuordnung l, die jedem Element des Graphen ein Label zuweist und somit den Typ bestimmt. Ein solcher Graph lässt sich also als Tupel G = (V, E, L, s, t, l) mit s, t : E → V und l : E ∪ V → L beschreiben.

Nach dieser Definition werden nur die Informationen betrachtet, die sich so durch die Verknüpfung von Knoten und Kanten ergeben. Die visuellen Eigenschaften (Form, Farbe und Lage) werden dabei vernachlässigt. Bei den einfachen Taskgraphen beispielsweise werden alle Informationen über die Abhängigkeiten durch das Vorhandensein oder Nichtvorhandensein von Kanten dargestellt. Die konkrete visuelle Darstellung liefert keine weiteren Informationen.

Mit Hilfe von Graphmorphismen können zwei Graphen in Beziehung gesetzt wer- den. Ein Morphismus m besteht dabei aus einem Paar von Abbildungen (mV , mE ). Die Abbildung mV bildet zwischen den Knotenmengen ab und die Abbildung mE bildet zwischen den Kantenmengen ab. Zusätzlich müssen noch eine Reihe von Ver- träglichkeitsbedingungen gelten. Für den Morphismus m zwischen den zwei Graphen G1 = (V1,E1,L1,s1,t1,l1) und G2 = (V2,E2,L2,s2,t2,l2) muss gelten:¹

Abbildung in dieser Leseprobe nicht enthalten

Die ersten beiden Bedingungen stellen die Typverträglichkeit sicher und die letzten beiden stellen die Strukturverträglichkeit sicher. Aus den letzten beiden Bedingungen ergibt sich auch, dass der Defintionsbereich, genauso wie der Wertebereich, immer einen Teilgraphen von G1 beziehungsweise G2 darstellt.

Bei den Notationen im vorherigen Kapitel wurden häufig noch zusätzliche Informationen an den Knoten oder Kanten notiert. Diese Informationen werden formal in Form von Attributen definiert. Dabei werden die Elemente einer Attributmenge den Elementen des Graphen analog zu den Labeln zugeordnet. Die Attributmenge kann durch eine algebraische Spezifikation und einer Algebra dazu definiert sein. Aus diesen Attributen können dann wiederum die Eigenschaften für die visuelle Darstellung abgeleitet werden. Auch für attributierte Graphen können analog zu den unattributierten Graphen Morphismen definiert werden. [CMR+97]

Nach dieser Definition können beliebige Graphen mit beliebigen Attributen be- trachtet werden. Da aber, abhängig vom gegebenen Problem, bereits einige Ein- schränkungen der zu betrachtenden Graphen gemacht werden können, wird das ein- geführte Typkonzept erweitert. Der Typ eines Objektes im Graph soll auch die er- laubten Attribute definieren. Auch die möglichen Kombinationen von Knoten und Kanten sind bekannt. Mit Hilfe des Typs kann auch definiert werden, Kanten welchen Typs bei Knoten bestimmter Typen beginnen oder enden. Diese Information lässt sich wiederrum in einem Graphen darstellen, dem Typgraphen. Der Typgraph enthält für jeden Knotentyp genau einen Knoten dieses Typs und für jeden erlaubten Kantentyp eine Kante. Für alle Graphen, die zu diesem Typgraphen passen, lässt sich dann ein totaler Morphismus von dem Graphen zum Typgraphen finden.[CMR96, HKT02]

4.2 Graphtransformationen

Die regelbasierte Ersetzung von Termen findet schon seit vielen Jahren in der Informatik Anwendung. Am bekanntesten sind sicherlich die Grammatiken der ChomskyHierarchie. Diese Ideen wurden auch auf Graphen übertragen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4.1: Schema für die Anwendung einer Graphregel.

[...]

---

¹ Teilweise auch atmende Partitionen genannt.

¹ UML - Unified Modeling Language.

² DAG - Directed Acyclic Graph.

¹ Dabei steht dom(f ) mit f : A → B für den Definitionsbereich der Abbildung f , also eine Teilmenge von A