Universität Augsburg Institut für Informatik Lehrstuhl für Softwaretechnik und Programmiersprachen Theoretische Informatik Prof. Dr. Walter Vogler Jannis

Universität AugsburgInstitut für InformatikLehrstuhl für Softwaretechnik und ProgrammiersprachenTheoretische InformatikProf. Dr. Walter Vogler

Seminar Petrinetze, 9.5.2005Jannis Hermanns

Fighting State Explosion

Automatische Berechnung eines

Fortschrittsmaßes für die Sweep-

Line-Methode



Quelle• Paper zu einem Vortrag von

Dr. habil. Karsten Schmidt im Rahmen der Konferenz „Tools and Algorithms for the Construction and Analysis of Systems“ (29.3.-2.4.2004) in Barcelona

• Originaltitel „Automated generation of a progress measure for the sweep-line method“

• Veröffentlicht in: LNCS 2988, Springer-Verlag 2004, S. 192-204.



Problem

• Effiziente Beantwortung von

Erreichbarkeitsfragen für beschränkte

Petrinetze

• 12 Speisende Philosophen: 60 Stellen, 48

Transitionen & beschränkt

• Aber: 531.440 erreichbare Zustände

Problem: State-Explosion!



Ziel

• Jeden erreichbaren Zustand

mindestens einmal betrachten

• Darauf verzichten, dabei den gesamten

Zustandsraum speichern zu müssen

Speicherplatz sparen!



Lösung

• Bestimmte Eigenschaften des Netzes kurz analysieren

• Während der Erforschung des Zustandsraumes bestimmte Zustände aussortieren

Immer nur einen Teil der erreichbaren Markierungen im Speicher haben!



Inhalt

1. Sweep-Line-Methode

2. Theorie: Monotones Fortschrittsmaß

3. Allgemeine Sweep-Line-Methode

4. Praxis: Inkrementelles Fortschrittsmaß

5. Geometrische Interpretation

6. Optimierungsmöglichkeiten

7. Kombination mit anderen Reduktionstechniken




• Unterteilung der Zustände in drei

Gruppen

1. Unbekannte Zustände

2. Gesehene Zustände (noch nicht fertig

abgearbeitet)

3. Komplett abgearbeitete Zustände




• Die zweite Gruppe wird als „Front“

bezeichnet

• Die dritte Gruppe soll möglichst klein

gehalten werden

• Darf man Zustände aus der dritten

Gruppe einfach löschen?




• Man darf Zustände, die nie wieder

vorkommen können, löschen

• Während der Erforschung des

Zustandsraumes Erreichbarkeitsfragen für

jeden Zustand beantworten

• Wie kann man entscheiden, welche Zustände

frühzeitig gelöscht werden dürfen



2. Monotones Fortschrittsmaß

• Ein Fortschrittsmaß ist eine Funktion

p:MN (N sei beliebige Menge mit

partieller Ordnung ≤)

• p(M) liefert den Fortschrittswert der

Markierung M




• Folgt aus M[tM‘, dass p(M) ≤ p(M‘) so heißt

das Fortschrittsmaß monoton

• Jedes Feuern einer Transition bedeutet einen

Fortschritt des Systems (bzw. keinen

Rückschritt)

• Antwort auf die Frage, welche Zustände

frühzeitig gelöscht werden dürfen




• Ziel der S-L-M: Speicherplatz sparen

• S-L-M benutzt ein Fortschrittsmaß, um Zustände während der Erforschung des Zustandsraumes löschen zu können

• Welche Zustände dürfen gelöscht werden?




• Start: Front besteht nur

aus MN

• Alle aktivierten

Transitionen werden

geschaltet und die

erreichten Zustände zur

Front hinzugefügt

• MN verlässt die Front




• Front besteht aus

unmittelbaren

Folgezuständen von MN

• MN ist (in) „komplett

erforscht“

• Entscheidung: MN

löschen, oder noch

nicht?




• Warum MN nicht einfach

löschen?




• Warum MN nicht einfach

löschen?

• MN könnte auf einem

Kreis liegen,

• Algorithmus würde in

Endlosschleife geraten!

• Wann darf MN gelöscht

werden?




• Regel: Aus „komplett

erforscht“ dürfen alle

die Zustände gelöscht

werden, deren

Fortschrittswert kleiner

ist als der minimale in

der Front

• Sie kommen nie mehr

vor




• Ein monotones Fortschrittsmaß ermöglicht erst das Anwenden der Sweep-Line-Methode

• Dieser Ansatz hat nur begrenzte Reichweite

• Was passiert bei Kreisen im Erreichbarkeitsgraphen?

• Hier besteht Verbesserungsbedarf!




• Verallgemeinerung der klassischen Sweep-Line-Methode:Forderung der Monotonie an das Fortschrittsmaß wird fallen gelassen

• System kann „zurückfallen“, d.h. der Fortschrittswert wird durch das Feuern einer Transition verringert. Problem!




• Zwei Markierungen M und M‘ mit M[tM‘ und p(M)>p(M‘) bilden eine Rückschrittskante

• Problem: Algorithmus weiß nicht, ob er M‘ schon untersucht hat

• Lösung: Markierungen wie M‘ werden als persistent markiert.




• Bei Entdeckung einer

Rückschrittskante wird

die erreichte Markierung

sofort aus der Front

entfernt und als

persistent markiert

• Mit dem Rest der

Markierungen wird wie

gewohnt verfahren




• Nachdem alle Zustände erforscht worden sind, bleibt eine Menge von als persistent markierten Zuständen

• Diese werden als Front für eine weiteren Durchgang der S-L-M benutzt

• So können zwar weitere Durchgänge nötig werden, aber es wird schließlich jede Markierung mindestens einmal besucht




• Warum terminiert der Algorithmus?

• Sweep-Line-Methode funktioniert nur

mit beschränkten Petrinetzen

• Wurde ein Zustand einmal als persistent

markiert, wird er nicht mehr gelöscht




• Jeder neue Durchgang benötigt eine „frische“ persistente Markierung

• Der Vorrat an Markierungen ist begrenzt

Algorithmus besucht jede erreichbare Markierung mindestens ein Mal und terminiert



4. Inkrementelles Fortschrittsmaß

• Fortschrittsmaß soll sich einfach und schnell berechnen lassen

• Idee: inkrementelles Fortschrittsmaß, bestehend aus:

– Fortschrittswert der Anfangsmarkierung MN

– Abstandsfunktion für Transitionen o:TQ

– Für alle M[tM‘ gilt p(M‘)=p(M)+o(t)




• Ist einfach und schnell in der Handhabung,

aber wie gewinnt man es?

Fortschrittswert der Anfangsmarkierung

beliebig, Abstände der Transitionen dürfen

jedoch nicht willkürlich gewählt werden

• Problem: Jeder Markierung muss genau ein

Fortschrittswert zugeordnet werden




• Lässt sich eine Markierung durch zwei verschiedene Schaltfolgen erzeugen, müssen die Summen der Abstände beider Schaltfolgen gleich sein

• Sei M[wM‘ und M[w‘M‘ undparikh(w)parikh(w‘) sowie w=t1...tn und w‘=tn+1...tm

• Dann ist mindestens eine Transition in {t1,...,tm}

linear abhängig von den restlichen




• Diese lineare Abhängigkeit ist zentrale Eigenschaft der automatischen Berechnung eines Fortschrittsmaßes:1. Bestimmung einer maximale Teilmenge U von

linear unabhängigen Transitionen

2. Definieren der Abstände der Transitionen in U

3. Berechnung der Abstände der restlichen Transitionen




• Transitionen in U sind

linear unabhängig, ihre

Abstände deshalb

beliebig wählbar

• Abstände der restlichen

Transitionen lassen sich

jetzt leicht berechnen!




• Wir wissen: alle tU

sind linear abhängig

von t1,...,tnU

• Also gilt:

∆t= 1∆t1+...+n∆tn

• Als Abstand für t ergibt

sich

o(t)= 1o(t1)+...+ no(∆tn)




• Dieses Fortschrittsmaß ist leicht zu

berechnen und einfach zu handhaben

• Allerdings ist die Berechnung in zwei

Punkten nicht deterministisch:

1. Wahl von U

2. Wahl der Abstände der Transitionen in U




• Negative Abstände sind schlecht

• Jeder Zustand, der durch eine Transition mit negativem Abstand erreicht wird, muss gespeichert werden

• Je mehr Transitionen mit negativem Abstand, desto geringer die Speicherplatzersparnis




• Für n linear unabhängige Transitionen lässt sich das Fortschrittsmaß als n-dimensionales Koordinatensystem verstehen

• Jeder erreichbare Markierung entspricht einem Punkt

• ∆t wird als Vektor betrachtet: M[tM‘ wird verstanden als die Verschiebung des Punktes M durch den Vektor t auf den Punkt M‘







• Vorgehensweise zur automatischen Berechnung von p() ist in zwei Punkten nicht deterministisch:

1. Wahl von U

2. Abstände von Transitionen in U

• Kann man so die Qualität von p() beeinflussen?













• U sollte so gewählt werden, dass möglichst

viele Transitionen einen kleinen positiven,

möglichst wenige einen großen negativen

Abstand erhalten

• Beides konnte aber noch nicht als lineares

Optimierungsproblem formuliert werden

• Future research!




• Nicht mit allen Reduktionstechniken für

Zustandsräume kompatibel

• Tiefensuche macht Anwenden der S-L-

M sinnlos (warum?)

• Besonders effektiv im Zusammenspiel

mit „Partial-Order-Reduction“




PH5 PH10 PH12

Kompletter Zustandsraum

Zustände 242 59048 531440

Gefeuerte Transitionen 805 393650 4251516

Zeit (Sekunden) 0,1 5,8 71,0

Sweep-Line Methode

Anzahl Iterationen 3 3 3

Max. Anzahl von Zuständen 183 54122 502378

Anzahl persistenter Zustände 169 53299 497969

Gefeuerte Transitionen 1544 720428 7710664

Zeit (Sekunden) 0,1 24,3 277,8

„Partial-Order“-reduzierter Zustandsraum

Zustände 272

Gefeuerte Transitionen 370

Zeit (Sekunden) 0,5

Sweep-Line Methode kombiniert Partial-Order-Reduction

Anzahl Iterationen 3



Vielen Dank für eure Aufmerksamkeit

Documents

Universität Augsburg Institut für Informatik Lehrstuhl für Softwaretechnik und Programmiersprachen Theoretische Informatik Prof. Dr. Walter Vogler Jannis