Effiziente Analyseverfahren für die Performability-Bewertung verteilter Systeme

• Applicant: Professor Dr.-Ing. Markus Siegle
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems
• Term: from 2007 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 55928509

Zur Bewertung quantitativer Eigenschaften verteilter Systeme, wie Leistungsfähigkeit und Zuver-lässigkeit (kurz: Performability-Bewertung), werden häufig Markovmodelle verwendet, die mit Hilfe strukturierter high-level Beschreibungsformalismen spezifiziert und anschließend automatisch analysiert werden. Im praktischen Einsatz treten dabei sehr grosse Zustandsräume auf, deren Analyse immense Rechenzeit und Speicherbedarf erfordert (Problem der sog. Zustandsraumexplosion). Durch die Verwendung spezieller Datenstrukturen, insbesondere von Entscheidungsdiagrammen, wurden in Vorarbeiten bei der Generierung und Speicherung solcher Modelle bereits bedeutende Fortschritte erzielt. Die numerische Analyse hingegen ist der verbleibende Flaschenhals, unter dem bisher alle einschlägigen Methoden und Werkzeuge leiden. Um die Geschwindigkeit der numerischen Analyse grosser Markovmodelle zu verbessern, sollen in diesem Vorhaben mehrstufige Aggregations-/Disaggregationsverfahren (sog. Multilevel-Verfahren) erstmals auf Basis von Entscheidungsdiagrammen realisiert werden. Entscheidungsdiagramme sind eine für Multilevel-Verfahren bestens geeignete Datenstruktur, da sie gemeinsam der Struktur der zugrundeliegenden high-level Beschreibung aufgebaut sind und einen einfachen Zugriff auf verschiedene geschachtelte Blockstrukturen der codierten Matrix ermöglichen. Aufgrund dieser günstigen Kombination von Datenstruktur und Algorithmus hat der hier vorgeschlagene Ansatz das Potenzial, den Stand der Technik wirklich voranzubringen.

• DFG Programme: Research Grants