Ablaufvorhersage für verteilte Programme mit Hilfe von Graphtransformationen

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 oglichkeiten  29

5  Erweiterte Taskgraphen  31

5.1  Darstellung der gemessenen Abl aufe  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 oglichkeiten 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

5

Inhaltsverzeichnis

6.3.2  Analyse mit formalen in AGG automatisierten Methoden  50

6.4  Ausbaum oglichkeiten f ur eine verbesserte Vorhersage  54

7  Verwendung der Graphgrammatik in der Vorhersageanwendung  55

7.1  Vor uberlegungen f ur 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

6

1 Einleitung

F¨ ur die L¨ osung von rechenintensiven Problemen werden h¨ aufig 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¨ angt, 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¨ uhrt wird. Diese Entscheidung ist allerdings schwierig zu treffen, wenn Informationen ¨ uber das Programm kaum und vor allem ¨ uber den zuk¨ unftigen Ablauf nicht bekannt sind. Wenn die Anpassung an die Struktur des Rechners erst kurz vor der Ausf¨ uhrung des Programms oder w¨ ahrend 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¨ at bei der Ausf¨ uhrung erreicht. Es ist also ein Weg zu suchen, der ausgehend von Informationen aus vergangenen Programml¨ aufen und dem bisherigen Verlauf des Programms den zuk¨ unftigen Programmablauf mit einer Vorhersage skizziert. Die in dieser Arbeit beschriebene Vorhersage kann dann als Basis f¨ ur eine Zuordnungseinheit dienen. Die Informationen ¨ uber den aktuellen Programmzustand sollen von einer getrennten Analyseanwendung bereitgestellt werden. Wie das Programm beobachtet werden kann und welche Werte gemessen werden k¨ onnen, wurde dazu in [Gra04] untersucht. Da die Programmabl¨ aufe sich klassischer Weise als Graph darstellen lassen, ist eine M¨ oglichkeit, 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¨ asst. Es soll daher auch untersucht werden, inwieweit sich die Regeln, mit denen sich der Aufbau der Vorhersage modellieren l¨ asst, 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¨ autern. Anschließend will ich eine Erweiterung zur Darstellung von Vorhersagen einf¨ uhren und darauf aufbauend Graphregeln definieren, mit denen diese Vorhersagen generiert werden k¨ onnen. Das so entstandene Modell soll

7

1 Einleitung

dann als Basis f¨ ur eine Implementierung einer Vorhersageanwendung dienen. Am Beispiel eines parallelen Programms werde ich den Aufbau der Vorhersage zeigen und dann pr¨ ufen, ob die Vorhersage ein realistisches Bild des Programmablaufs darstellt.

8

2 Parallelisierung von Programmen

Der Einsatz von Parallelrechnern soll es erm¨ oglichen, gr¨ oßere Probleme (scale-up) oder gleich große in k¨ urzerer Zeit (speed-up) zu l¨ osen [Hei94]. Die Rechner verf¨ ugen dazu ¨ uber mehrere Prozessoren, die gleichzeitig an unterschiedlichen Teilberechungen arbeiten k¨ onnen.

Um die M¨ oglichkeiten des Parallelrechners auszunutzen, muss das Programm bereits so angepasst werden, dass Berechnungen, die gleichzeitig stattfinden k¨ onnen, auch gleichzeitig auf den verschiedenen Prozessoren des Rechners ausgef¨ uhrt werden k¨ onnen. Dazu werden die notwendigen Berechnungen in Prozesse aufgeteilt, die wiederum von den einzelnen Prozessoren des konkreten Parallelrechners (Zielmaschine) ausgef¨ uhrt werden. Um mehreren Nutzern den Zugang zu einem Parallelrechner zu gew¨ ahren, werden diese h¨ aufig 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¨ uhrung 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¨ oglichkeiten der Zielmaschine orientieren sollte. Das heißt, es muss nicht soweit aufgeteil werden, wie es der Algorithmus erm¨ oglicht, wenn die Zielmaschine nicht ¨ uber entsprechend viele Prozes-soren verf¨ ugt. Die Teilberechnungen k¨ onnen von anderen abh¨ angig sein, zum Beispiel, wenn eine Berechnung auf dem Ergebnis einer vorherigen Berechnung beruht. Als Ergebnis dieses Schrittes sollte der Programmierer eine ¨ Ubersicht haben, welche

Teilberechnungen notwendig sind und wie sie voneinander abh¨ angen. Im n¨ achsten Schritt vor der Implementierung muss der Programmierer entscheiden, wie er die Teilberechnungen zu Prozessen zusammenf¨ ugt. Momentan ist es ¨ ublich, dass der Programmierer bei dieser Entscheidung den konkreten Aufbau der

9

2 Parallelisierung von Programmen

Abbildung 2.1: Der Entwicklungsprozess vom Algorithmus bis zur Ausf¨ uhrung.

Zielmaschine ber¨ ucksichtigt [RR00]. Das Ziel der Aufteilung soll dann eine m¨ oglichst optimale Verteilung der entstehenden Rechen- und Kommunikationslast auf die verschiedenen Prozesse sein. Die Rechenlast wird dabei ¨ uber die m¨ ogliche Anzahl

der Berechnungen f¨ ur jede Teilberechnung abgesch¨ atzt und soll dann in der Summe f¨ ur alle Prozesse relativ zu den Kapazit¨ aten der einzelnen Knoten der Zielmaschine m¨ oglichst gleichverteilt sein. Damit soll gew¨ ahrleistet werden, dass alle zur Verf¨ ugung stehenden Prozessoren ausgelastet sind und kein Prozess, mit einer deutlichen l¨ angeren Bearbeitungszeit als die anderen Prozesse, die Gesamtberechnung verz¨ ogert. Ein weiteres Kriterium ist das Kommunikationsverhalten. Dabei sollen m¨ oglichst wenige Daten zwischen zwei Prozessen ausgetauscht werden, da diese auf verschiedenen Prozessoren ausgef¨ uhrt werden k¨ onnen und die Daten dann aufw¨ andig ¨ ubertragen werden m¨ ussen. Das l¨ asst sich zum Beispiel dadurch erreichen, dass mit den selben Daten arbeitende Teilberechnungen auch im gleichen Prozess ausgef¨ uhrt werden (Datenlokalit¨ at).

Diese Aufteilung wird auch als Agglomeration [Fos95] (teilweise etwas zweideutig auch als Scheduling [RR00]) bezeichnet. Hinsichtlich der Herangehensweisen wird zwischen statischer und dynamischer Agglomeration unterschieden. W¨ ahrend bei der statischen Agglomeration die Aufteilung bei jedem Lauf gleich ist, kann bei der dynamischen Agglomeration, w¨ ahrend der Ausf¨ uhrung die Aufteilung vom parallelen Programm ge¨ andert werden. Allerdings werden auch dabei die wichtigsten

10

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 Betriebssystem zur Ausf¨ uhrung den konkreten Prozessoren der Zielmaschine zugeordnet. Dabei versucht das Betriebssystem eine optimale Auslastung der Prozessoren zu finden. Wenn der Programmierer, wie es heutzutage ¨ ublich ist, genau so viele Prozesse erzeugt hat, wie es Prozessoren in diesem Rechner gibt, ist diese Zuordnung trivial.

Das stellt den gr¨ oßten Vorteil der aktuellen Vorgehensweise dar. Das Betriebssystem ben¨ otigt f¨ ur das Mapping keine weitergehenden Informationen ¨ uber das Programm und kann sehr einfach die Mappingentscheidungen treffen. Die optimale Last-und Kommunikationsverteilung ist wie beschrieben bisher die Aufgabe des Programmierers. Auf der einen Seite kann er den besten ¨ Uberblick ¨ uber sein Programm haben,

aber andererseits ist die optimale Aufteilung ein zus¨ atzlicher Aufwand. Ein weiterer Nachteil ist, dass das Programm auf eine konkrete Maschine optimiert ist. Wenn dem Programm eine gr¨ oßere oder kleinere Partition der Maschine zur Verf¨ ugung steht oder das Programm gar auf einem anderen Parallelrechner ausgef¨ uhrt werden soll, hat das Betriebssystem kaum Spielraum, eine optimale Zuordnung zu finden. Das selbe Problem tritt auf, wenn das Betriebssystem die zur Verf¨ ugung stehenden Ressourcen dynamisch verwalten soll und so mehrere gleichzeitig laufende Programme m¨ oglichst optimal auf die Maschine verteilen soll.

2.2 Neuer Ansatz

Das Ziel ist es also, dem Programmierer die Verantwortung f¨ ur das optimale Verteilen der Rechenbelastung abzunehmen. Gleichzeitig soll das Betriebssystem in die Lage versetzet werden, die Zuordnung so optimal wie m¨ oglich vorzunehmen. Der Unterschied wird bei der Betrachtung der zuvor geschilderten drei Schritte deutlich.

11

2 Parallelisierung von Programmen

Der Programmierer muss immer noch sein Programm im ersten Schritt in Tasks zerlegen, sollte dabei jedoch die Granularit¨ at so w¨ ahlen, wie es f¨ ur sein Problem angemessen ist, unabh¨ angig von der nun beliebigen Zielmaschine. Im n¨ achsten Schritt m¨ ussen f¨ ur die Implementierung wiederum die Tasks zu Prozessen zusammengef¨ ugt werden. Dabei sollte jetzt aber das Augenmerk auf m¨ oglichst hochgradige Parallelisierung gelegt werden. Es sollen jetzt also so viele Aufgaben wie m¨ oglich in getrennten Prozessen durchgef¨ uhrt werden. Die Anzahl der Prozesse muss dabei nicht konstant sein, sondern kann sich direkt an den M¨ oglichkeiten zur parallelen Ausf¨ uhrung orientieren. Diese Aufteilung muss auch nicht statisch sein. So ist es zum Beispiel auch m¨ oglich, je nach Eingabedaten, unterschiedlich viele Prozesse zu starten. Das ist, ausgehend von der Modellierung der Teilberechnungen und deren Abh¨ angigkeiten untereinander, nicht sehr aufw¨ andig und der Programmierer kann sich verst¨ arkt auf das eigentliche Programm konzentrieren. Bei der Ausf¨ uhrung auf dem Parallelrechner kann dieses Programm jetzt ohne Probleme auf verschiedenen Architekturen ausgef¨ uhrt 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¨ oße der Partition, die das Programm nutzen darf, ¨ andert und die

Prozesse danach neu verteilt. Es werden dann abh¨ angig von der tats¨ achlichen Pro-zessorausnutzung dynamische Partitionen ¹ [FRS ⁺ 97] einsetzt. In diesem Fall sorgt also das Betriebssystem allein f¨ ur die m¨ oglichst optimale Abbildung auf die konkrete Maschine.

Ein Nachteil bei dieser Vorgehensweise ist allerdings, dass Informationen ¨ uber

das Programm, die der Programmierer bei der anderen Vorgehensweise eventuell ber¨ ucksichtigt h¨ atte, vom Betriebssystem nicht in die Entscheidung einfließen. So sollte der Programmierer auf Datenlokalit¨ at achten. Das Betriebssystem dagegen kann nicht erahnen, welche Teilberechnungen in welchen Prozessen auf die selben Daten zugreifen. Auch konnte der Programmierer bereits grob absch¨ atzen, wie lange die verschiedenen Berechnungen dauern w¨ urden. Weiterhin gibt es Mehrkosten bei der parallelen Ausf¨ uhrung auf einem Prozessor gegen¨ uber der sequentiellen Ausf¨ uhrung, die zum Beispiel durch die Kontextwechsel entstehen. Diese Mehrkosten k¨ onnen reduziert werden, wenn die Prozesse vom Betriebssystem wie zum Beispiel beim Gang-Scheduling nacheinander ausgef¨ uhrt werden. Dazu m¨ usste das Betriebssystem aber wiederum Informationen ¨ uber die Prozesse und ihr Verhalten in der Zukunft haben.

Der Ansatz besteht nun darin, die Flexiblit¨ at zu erh¨ ohen, 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

¹ Teilweise auch atmende Partitionen genannt.

12

Abbildung 2.3: Verwendung einer Vorhersage f¨ ur die Zuordnung von Prozessoren

notwendigen Informationen k¨ onnen direkt vom Programmierer geliefert werden oder sie m¨ ussen 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 ¨ uber den

vermutlichen Programmablauf erhalten. Diese soll dann als Basis f¨ ur eine entsprechend erweiterte Zuordnungseinheit dienen und auf den Beobachtungen vergangener Abl¨ aufe beruhen. Dabei wird davon ausgegangen, dass sich die einzelnen Abl¨ aufe des Programms so stark ¨ ahneln, dass aus einer Menge von Beobachtungen eine akzeptable Vorhersage generiert werden kann.

Die Umsetzung dieses Ansatzes kann in drei Aufgaben unterteilt werden. Als erstes m¨ ussen die einzelnen Programml¨ aufe beobachtet werden und die Messwerte zur Rechen- und Kommunikationslast aufbereitet, aber auch die Struktur der Abl¨ aufe geeignet erkannt werden. Im n¨ achsten Schritt m¨ ussen diese Daten zu einem Modell eines konkreten Ablaufes zusammengefasst werden und dann aus einer Menge dieser Modelle eine Vorhersage f¨ ur k¨ unftige Abl¨ aufe erstellt werden. Als letztes muss die Zuordnungseinheit so erweitert werden, dass sie die Informationen der Vorhersage geeignet ber¨ ucksichtigt.

In dieser Arbeit sollen L¨ osungsans¨ atze f¨ ur den zweiten Aufgabenbereich vorgestellt werden. Verfahren f¨ ur die geeignete Messung und Bereitstellung der Messwerte werden in [Gra04] pr¨ asentiert. Die M¨ oglichkeiten zur Erweiterung der Zuordnungseinheit werden derzeit in einer weiteren Arbeit untersucht. Die Vorhersage soll automatisch aus den Beobachtungen vorheriger Programml¨ aufe erstellt werden und sich an den aktuellen Stand des vorhergesagten Programmlaufes anpassen. Die Vorhersage soll sich anpassen, wenn sie den beobachteten Programmlauf nicht vorhergesagt hat. Ein weiteres Ziel ist, dass ein Programmlauf, wenn

13

2 Parallelisierung von Programmen

er ein zweites Mal unver¨ andert beobachtet wird, fehlerfrei vorhergesagt wird. Zuerst soll der Aufbau der Vorhersage mit Hilfe von Graphtransformationen modelliert werden. Anschließend wird ¨ uberpr¨ uft, ob sich das entstandene Graphtransformationssystem direkt f¨ ur eine Implementierung der hier vorgestellten Vorhersageanwendung einsetzen l¨ asst.

14

3 Modellierung von parallelen Programmen

F¨ ur die Entwicklung von parallelen Programmen muss f¨ ur die im vorherigen Kapitel beschriebenen Schritte zuerst ein Modell des Algorithmuses angefertigt werden, aus dem die Eigenschaften der Aufteilung in Teilberechnungen ersichtlich sind. Dieses Modell bildet dann die Basis f¨ ur die Agglomeration und die Implementation. Im Folgenden sollen einige bekannte Modellierungstechniken f¨ ur parallele Programme beziehungsweise Softwaresysteme allgemein vorgestellt werden. Die Modellierungstechniken werden als Basis zur Entwicklung der Darstellung einer Vorhersage genutzt.

3.1 Kommunikationsgraphen

Mit Hilfe von Kommunikationsgraphen [Hei94, HH89] kann man ¨ ubersichtlich darstellen, welche Teile eines parallelen Programms mit welchen anderen Teilen kommunizieren. Dabei werden die einzelnen Prozesse als Knoten dargestellt. Es wird davon ausgegangen, dass die Anzahl der Prozesse konstant ist. Miteinander kommunizierende Prozesse werden mit einer Kante verbunden. An die Kanten kann dann zus¨ atzlich in Form eines Gewichts eine Kenngr¨ oße f¨ ur die Kommunikation notiert werden.

Die Kommunikationsgraphen stellen dabei entweder die gesamte Kommunikation w¨ ahrend des Programmlaufes dar oder sie bilden das Kommunikationsverhalten eines Zeitpunktes beziehungsweise einer Phase des Programms ab. Da die Kommunikationsinfrastruktur der Zielmaschine meist als konstant angenommen wird, bietet die Gesamtkommunikation ein geeignetes Bild der Zuordnung von Kommunikationsinfrastruktur und der anfallenden Kommunikation. F¨ ur ein feineres Bild, das ebenfalls die zeitlichen ¨ Anderungen im Kommunikationsverhalten ber¨ ucksichtigt sind die dynamischen Kommunikationsgraphen [Hei94] geeignet. Diese stellen in einer Art Phasenmodell das Kommunikationsverhalten f¨ ur mehrere Phasen des Programmablaufs dar.

3.2 Ablaufmodellierung mit UML

Im Rahmen von UML ¹ sind eine Reihe von visuellen und textuellen Notationen f¨ ur den Softwareentwicklungsprozess definiert. Darunter fallen auch die Aktivit¨ atsdiagramme (activity diagrams) und die Zustandsdiagramme (state charts). Diese beiden

¹ UML - Unified Modeling Language.

15

3 Modellierung von parallelen Programmen

Abbildung 3.1: Dynamische Kommunikationsgraphen stellen das Kommunikations-

in der Notation recht ¨ ahnlichen Diagramme wurden zur Darstellung des Verhaltens

eines Softwaresystems entworfen. Eine ¨ Techniken bietet unter anderem [Par98].

In einem Zustandsdiagramm stehen die Knoten f¨ ur die Zust¨ ande des Systems und die Kanten f¨ ur m¨ ogliche ¨ Uberg¨ ange, wobei mehrere Zustands¨ uberg¨ ange von einem Zustand ausgehen k¨ onnen, von denen wiederum aber immer nur einer ausgef¨ uhrt wird. Diese Zustands¨ uberg¨ ange sind ereignisgesteuert, wobei die Ereignisse von anderen Zustands¨ uberg¨ angen oder von der Systemumgebung erzeugt werden. Die Erzeugung von Ereignissen und die Reaktion auf Ereignisse stellen eine synchrone Kommunikation dar. Die Verkn¨ upfung zwischen dem Sender und den Empf¨ angern wird allerdings nicht visuell notiert, sondern durch den Signalnamen gekennzeichnet. In den Zustandsdiagrammen k¨ onnen auch nebenl¨ aufige Prozesse dargestellt werden. Dabei werden die Abl¨ aufe, die gleichzeitig stattfinden k¨ onnen, in unterschiedlichen Teildiagrammen, getrennt durch eine Linie notiert. Diese Teildiagramme k¨ onnen auch eine Verfeinerung eines Zustandes sein, so dass auch Abl¨ aufe mit sich ¨ anderndem Grad der Nebenl¨ aufigkeit dargestellt werden k¨ onnen. Im Gegensatz dazu stehen bei den Aktivit¨ atsdiagrammen die Knoten f¨ ur Aktivit¨ atszust¨ ande [Par98]. Mit diesen Aktivit¨ aten lassen sich die Teilberechnungen aus dem vorhergehenden Kapitel darstellen. Die Kanten stehen f¨ ur die ¨ Uberg¨ ange. Ein ¨ Ubergang wird ausgef¨ uhrt, wenn die entsprechende Aktivit¨ at beendet wurde. F¨ ur die Steuerung des Kontrollflusses existieren weitere Elemente, mit denen ein bedingter ¨ Ubergang oder Nebenl¨ aufigkeit notiert werden kann. F¨ ur die Bedingungen wird ein

16

Abbildung 3.2: Zwei Notationen f¨ ur Abl¨ aufe aus UML: a) Zustandsdiagramme

b) Aktivit¨ atsdiagramme

Bedingungsknoten eingef¨ ugt, der wiederum mehrere ausgehende Kanten besitzt. Von diesen wird jeweils eine ausgew¨ ahlt und die darauf folgende Aktivit¨ at ausgef¨ uhrt. F¨ ur die Nebenl¨ aufigkeit gibt es spezielle Aufteilungs- und Zusammenf¨ uhrungsknoten. Von den Aufteilungsknoten gehen mehrere Kanten aus und wenn die vorhergehende Aktivit¨ at beendet wurde, werden alle nachfolgenden aktiviert. Bei den Zusammenf¨ uhrungsknoten wird die nachfolgende Aktivit¨ at erst ausgef¨ uhrt, wenn alle Vorg¨ anger beendet wurden.

Die Notationen f¨ ur Nebenl¨ aufigkeit und bedingte Abl¨ aufe der Aktivit¨ atsdiagramme sollen als Vorbild f¨ ur die hier entwickelte Notation der Vorhersage dienen.

3.3 Petrinetze

Eine weitere Technik zur Darstellung von Abl¨ aufen sind Petrinetze. Die Petrinetze und ihr Verhalten sind formal definiert und sind daher f¨ ur Analysen geeignet. Mit ihrem Schaltverhalten lassen sich nebenl¨ aufige Abl¨ aufe gut darstellen. Ein Petrinetz besteht aus zwei Typen von Knoten: den Stellen und Transitionen. Die Stellen k¨ onnen eine Markierung, die so genannten Token, besitzen. Kanten k¨ onnen nur zwischen Knoten unterschiedlichen Typs verlaufen. Wenn auf allen Stellen des Vorbereichs einer Transition, das heißt allen Stellen von denen eine Kante zu dieser Transition l¨ auft, 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¨ ugt. Wenn sich die Vorbereiche nicht ¨ uberschneiden, k¨ onnen die Transitionen gleichzeitig

17