Effiziente Leistungsbewertung mit Hilfe von Entscheidungsdiagrammen

• Applicant: Professor Dr.-Ing. Ulrich Herzog
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems
• Term: from 2001 to 2003
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5296896

Im Rahmen des beantragten Vorhabens sollen Datenstrukturen und Algorithmen für die Repräsentation und Analyse stochastischer Leistungsmodelle entwickelt werden. Zur Modellspezifikation werden stochastische Prozessalgebren mit Markov-Charakter eingesetzt. Durch die konsequente Ausnutzung der Strukturierungskonzepte von Prozessalgebren sollen neue Möglichkeiten der kompakten Repräsentation und effiziente Analyse erschlossen werden. Als Basis-Datenstruktur werden binäre Entscheidungsdiagramme (Multi-Terminal BDDs) verwendet. Es sollen Techniken entwickelt werden, die für eine breite Klasse prozessalgebraischer Modelle extrem speicherplatzsparende Repräsentationen gestatten. Ein wichtiges Ziel ist dabei die Beschleunigung der auf BDD-Datenstrukturen arbeitenden numerischen Analyseverfahren, da diese zur Zeit den Flaschenhals des BDD-basierten Ansatzes bilden. Zu diesem Zweck werden bestehende BDD-Algorithmen und ihre Implementierungen systematisch mit Hilfe von Messungen analysiert. Die besonders zeitkritischen Teile dieser Algorithmen sollen dann in Zusammenhang mit den am Lehrstuhl arbeitenden Experten für Hardware/Software Codesign in VHDL spezifiziert und prototypisch mittels prgrammierbarer Hardware realisiert werden. Mit Hilfe des dabei entstehenden BDD-Coprozessors soll die Geschwindigkeit der BDD-basierten Berechnungen erheblich gesteigert werden, wovon insbesondere die numerischen Verfahren für die Markovanalyse profitieren. Im Rahmen des Projekts wird auch ein prototypisches Software-Werkzeug entstehen, das die Datenstrukturen und die auf ihnen arbeitenden Verfahren implementiert und dazu die Funktionalität der beschriebenen Spezialhardware nutzt.

• DFG Programme: Research Grants
• Participating Person: Professor Dr.-Ing. Markus Siegle