Application of data compression techniques to the numerical analysis of time-extended petri nets with large state space
Final Report Abstract
Zeiterweiterte Petrinetze eignen sich für die Modellierung von Computer-, Kommunikations- und Fertigungssystemen. Durch die stationäre Analyse können Leistungs- und Zuverlässigkeitsmaße gewonnen werden. Dazu werden alle Zustände des Petrinetzes erzeugt, und ein lineares Gleichungssystem in der Größe der Anzahl der Zustände iterativ gelöst. Der Lösungsvektor gibt die Zustandswahrscheinlichkeiten an, aus denen die interessierenden Maße berechnet werden. Da die Anzahl von Zuständen exponentiell mit der Größe des Petrinetzes anwächst, ist das Verfahren für Modellierungsaufgaben aus der Praxis oft nicht anwendbar. Für die Speicherung des Zustandsraums und der Koeffizientenmatrix des Gleichungssystems (Generatormatrix) existieren bereits effiziente Verfahren, die den Speicherbedarf von der Anzahl der Zustände entkoppeln. Momentan ist die Größe des Iterations- bzw. Lösungsvektors der begrenzende Faktor bei der numerischen Analyse. In diesem Projekt wurden Lösungsverfahren entwickelt, die eine approximierte, kompakte Darstellung des Iterationsvektors verwenden. Dazu wurden zunächst die Eigenschaften des Lösungsvektors untersucht. Es konnte gezeigt werden, dass die Elemente des Vektors in der Regel log-normal verteilt sind. Daraus folgt, dass wenige Vektoreinträge den Großteil der Wahrscheinlichkeitsmasse enthalten. Die meisten Maße können hinreichend genau berechnet werden, wenn nur diese größten Vektoreinträge bekannt sind. Es wurde ein modifiziertes Gauß-Seidel-Verfahren entwickelt, das diese Eigenschaft ausnutzt. Dabei werden Vektoreinträge gesucht, die über einem Schwellwert liegen. Nur diese werden für die weitere Berechnung gespeichert, wodurch sich eine erhebliche Reduzierung des Aufwands ergibt. Eine weitere neu entwickelte Methode benutzt die Haar-Transformation als Methode zur Dekorrelation von Daten. Auf den Lösungsvektor wird eine mehrdimensionale Haar-Transformation angewendet, wobei jeder Komponente eine Dimension zugeordnet ist. Dabei wird ausgenutzt, dass Wahrscheinlichkeiten für Zustände mit ähnlichen Markierungen korreliert sind. In der transformierten Darstellung des Vektors werden wieder nur die größten Werte gespeichert, wodurch ein gewisser Approximationsfehler resultiert. Dieser ist umso kleiner, je größer die Korrelation zwischen benachbarten Wahrscheinlichkeiten ist. Um die Haar-Transformation in das Lösungsverfahren zu integrieren, wird eine Haar-transformierte Generatormatrix in kompakter Matrixdiagramm- Darstellung erzeugt. Das Lösungsverfahren kann dann unverändert auf der transformierten Matrix und dem transformierten Vektor ablaufen. Außerdem wurde ein Verfahren für das Thresholding auf Matrixdiagrammen entwickelt. Damit kann die Repräsentation von Matrixelementen gelöscht werden, die unter einem Schwellwert liegen und keinen großen Beitrag zur Lösung liefern, wodurch eine Verringerung des Aufwands resultiert. Die beschriebenen Verfahren wurden in C++ implementiert. Daneben wurden neue und bekannte Algorithmen zur Manipulation von Matrixdiagrammen umgesetzt und das Satoratfon-Verfahren zur Erzeugung des Zustandsraums implementiert. Der entwickelte Quellcode steht unter der Adresse http://dontcry.cs.tu-berlin.de/trac/analvsis zur Verfügung.
Publications
- A. Zimmermann, M. Knoke, A. Huck, and G. Hommel: Towards Version 4.0 ofTimeNET. 13th GI/ITG Conference on Measurement, Modeling, and Evaluation of Computer and Communication Systems, MMB 2006 March 2006, Nürnberg, Germany, pp. 477-480.
