Application of data compression techniques to the numerical analysis of time-extended petri nets with large state space

• Applicant: Professor Dr.-Ing. Günter Hommel
• Subject Area: Software Engineering and Programming Languages
• Term: from 2004 to 2007
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5413287

Zeiterweiterte Petrinetze eignen sich für die Modellierung von Computer-, Kommunikations- und Fertigungssystemen. Durch die numerische 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 existieren bereits effiziente Verfahren, die den Speicherbedarf von der Anzahl der Zustände entkoppeln. Für den Iterations- bzw. Lösungsvektor gibt es jedoch noch kein Verfahren. Dessen Größe ist momentan der begrenzende Faktor bei der numerischen Analyse. Ziel des Forschungsvorhabens ist die Entwicklung eines neuen approximativen Verfahrens für die numerische Analyse. Es soll ein möglichst allgemein anwendbares Verfahren entwickelt werden, das nicht auf bestimmte Modellklassen angewiesen ist. Dabei sollen verlustbehaftete Datenkompressionsverfahren für die Speicherung des Iterationsvektors verwendet werden. Grundlage ist die Ausnutzung von Korrelationen, die sich aus dem Modellkontext ergeben. Darauf baut ein typisches Kompressionsverfahren mit Dekorrelation, Quantisierung und Entropiekodierung auf. Der verlustbehaftete Quantisierungsschritt geschieht in Abhängigkeit von gewählten Fehlertoleranzen. Das Verfahren muss effizient in einen iterativen Gleichungslöser integriert werden. Die Methode wird in das Modellierungswerkzeug TimeNET implementiert und an Praxisbeispielen getestet.

• DFG Programme: Research Grants