haRTStone - Automated Generation of Benchmark Programs for the Evaluation of Analyses and Optimizations for Hard Real-Time Systems
Final Report Abstract
Viele eingebettete Systeme sind sicherheitskritische Echtzeitsysteme, die Daten in fest vorgegebener Zeit verarbeiten müssen (z.B. Airbag- oder Fluglagesteuerungen). Wichtigstes Kriterium beim Entwurf solcher Echtzeitsysteme ist zu garantieren, dass alle Tasks des Systems ihre vorgegebenen Deadlines einhalten. Hierzu bedarf es spezieller Analyseverfahren, die das schlimmstmögliche zeitliche Verhalten eines Systems untersuchen und solche Garantien geben können. Im Fall, dass Deadlines nicht eingehalten werden, müssen Optimierungsverfahren angewendet werden, um den Code des Systems so zu verändern, dass zeitliche Schranken abschließend dennoch eingehalten werden. Die Erforschung solcher Analyse- und Optimierungsverfahren für harte Echtzeitsysteme ist ein überaus lebendiger Bereich, in dem regelmäßig und in kurzen Intervallen neue Ergebnisse präsentiert werden. Naturgemäß spielt die Evaluation solcher Verfahren eine wichtige Rolle. Diese beruht üblicherweise auf Benchmarking, so dass Analyse- und Optimierungsverfahren auf existierende Sammlungen von Anwendungen, Tasks oder Programm-Codes angewendet werden. Die derzeitig verwendeten Benchmarks sind jedoch nicht ausreichend für die Durchführung einer fundierten wissenschaftlichen Evaluation neuartiger Verfahren. Zur fundierten und reproduzierbaren Evaluation von Optimierungs- und Analyseverfahren harter Echtzeitsysteme besteht ein dringender Bedarf an universell einsetzbaren und für die wissenschaftliche Gemeinschaft frei verfügbaren Benchmarkverfahren. Diese sollen einerseits den Anforderungen unterschiedlicher Forschungszweige (z.B. Schedulability-Analyse, WCET-Analyse oder Compiler-Optimierung) genügen, andererseits aber auch möglichst realitätsnah verschiedene Anwendungsbereiche (z.B. Steuerungs- /Regelungsanwendungen oder Signalverarbeitung) repräsentieren. Ziel des Projekts war, einen flexiblen und parametrisierbaren Benchmark-Generator zur automatisierten, pseudo-randomisierten und reproduzierbaren Erzeugung von Benchmarks zu entwickeln. Hierzu wurde zunächst eine umfangreiche und möglichst realitätsnahe Sammlung an Benchmark-Programmen bestehend aus verfügbaren Benchmark-Programmsammlungen angelegt, die als Datengrundlage bzw. als Musterbeispielsammlung dient. Aufbauend auf diesen gesammelten Benchmarks wurde eine Reihe von charakteristischen Features definiert, die grundlegende relevante Eigenschaften der Benchmarks darstellen. Auf Basis dieser Features wurden die Benchmarks klassifiziert und ihren Anwendungsbereichen zugeordnet. Diese Arbeiten haben zum Ziel, einem künftigen Benchmark-Generator präzise Modelle zur Struktur von Programm-Codes aus den unterschiedlichsten Anwendungsbereichen zur Verfügung zu stellen. Weiterhin wurde eine Vielzahl von Wekzeugen implementiert, die die eingangs definierten Features aus dem Code von Benchmark-Programmen extrahieren. Zudem wurde ein Modell basierend auf künstlichen neuronalen Netzen realisiert, das auf der Grundlage solcher extrahierter Features automatisch eine Klassifizierung von Programmen in ihre Anwendungsbereiche mit hoher Genauigkeit vornimmt. Zur Evaluation der Aussagekraft der extrahierten Features sowie zur Bewertung der Leistungsfähigkeit dieses neuronalen Netzes wurde abschließend eine Reihe von Klassifikationstests durchgeführt. Durch deren Ergebnisse wurde erfolgreich gezeigt, dass sowohl die ausgewählten Features aussagekräftig sind, als auch dass das verwendete neuronale Netz zuverlässig richtige Vorhersagen macht. Sämtliche Projektergebnisse werden der wissenschaftlichen Gemeinschaft quelloffen und frei in Form von Software-Artefakten und Datensätzen zur Verfügung gestellt.
