Analyse kontextabhängigen Systemverhaltens im Entwurf eingebetteter Systeme
Zusammenfassung der Projektergebnisse
Aufgrund der steigenden Komplexität der Funktion eingebetteter Systeme hat sich der Einsatz der Simulation zur Systemverifikation, sowohl von der Abdeckung der kritischen Fälle als auch von der Rechenzeit her, zunehmend als inadäquat gezeigt. Ein zuverlässiger Korrektheitsnachweis des Echtzeitverhaltens eingebetteter Systeme kann deshalb nur noch mit analytischen Verfahren erzielt werden, deren Ergebnisse für alle m¨oglichen Kombinationen von Eingabedaten und Systemzuständen gelten. Ausgang des Projekts war ein existierender Ansatz zur formalen Performanzanalyse komplexer heterogener Systeme mit unterschiedlichen Schedulingstrategien und eine zugehörige Entwurfssoftware, SymTA/S. Dieser Ansatz sowie die zugehörige Entwurfssoftware wurden im Rahmen dieses Projekts durch Verfahren zur Erfassung und Auswertung von Systemkontexten für die Analyse erweitert, um präzisere Analyseergebnisse zu liefern. Dadurch ergeben sich engere Intervalle für Antwortzeiten der Tasks, also weniger Pessimismus bei der Analyse und damit die Möglichkeit, Grenzen des Systemverhaltens zu berechnen, die wesentlich näher an den tatsächlichen Grenzen liegen, ohne die wichtige Eigenschaft der Analyse, konservativ zu sein, zu verlieren. Dies ermöglicht eine effizientere Systemoptimierung. Als erstes wurden Intra Event Stream Kontexte zur genaueren Berechnung der im System produzierten minimalen bzw. maximalen Last ausgewertet. Intra Event Stream Kontexte sind Systemkontexte, die Informationen über die Abfolge verschiedener Typen von Ereignissen in einem Ereignisstrom betreffen. Je nach empfangenem Ereignistyp kann der empfangende Task sehr unterschiedlich reagieren, was man in Ausführungsmodi eines Tasks zusammenfassen kann. Das Auswertungsverfahren der Intra Event Stream Kontextinformation wurde von den eigentlichen Analysealgorithmen getrennt. Die Analyse ist weiterhin unabhängig davon, ob Intra Event Stream Kontexte vorhanden sind. Dank dieser Trennung zwischen Analyse und Auswertungsverfahren von Intra Event Stream Kontexten konnten neue Analyseverfahren mühelos integriert werden. Damit profitieren sie automatisch von der Auswertung der Intra Event Stream Kontextinformation. Dadurch war es möglich, Intra Event Stream Kontexte für heterogene Systeme mit unterschiedlichen Schedulingstrategien zu berücksichtigen, ohne die entsprechenden Analysen an die Auswertung von Kontexten anzupassen. Das Konzept der Intra Event Stream Kontexte wurde zudem verallgemeinert, indem auch partiell bekannte Information über die Abfolge von Ereignistypen in einem Ereignisstrom zur Bestimmung einer genaueren minimalen bzw. maximalen Last des Tasks ausgewertet werden kann. Die Intra Event Stream Kontexte wurden ebenfalls zur genaueren Modellierung von konditionalem Verhalten an den Taskausgängen verwendet. Bei einem Task mit konditionalem Verhalten ist nämlich die Produktion von Ereignissen an seinen Ausgängen durch den Typ des konsumierten Ereignisses bedingt, was zu unterschiedlichen Ereignismodellen an den Taskausgängen führen kann. Neben der präzisen Bestimmung der einzelnen Ausgangsereignismodelle eines Tasks mit konditionalem Verhalten, wurde zudem die Intra Event Stream Kontextinformation an jedem Ausgang des Tasks aus der Intra Event Stream Kontextinformation an seinem Eingang und den Ausführungsmodi des Tasks hergeleitet. Dadurch kann die Intra Event Stream Kontextinformation weiter zwischen Tasks propagiert und für die Analyse nachfolgender Komponenten verwendet werden. Informationen über zeitlich korrelierte Ereignisse in verschiedenen Ereignisströmen, so gennante Inter Event Stream Kontexte, wurden zur genaueren Berechnung der Verteilung der Last über die Zeit im System ausgewertet. Konkret werden Phasenlagen zwischen den Ereignissen der betroffenen Ereignisströme betrachtet, welche aufgrund der Datenabhängigkeiten zwischen Tasks in verteilten Systemen entstehen. Aussagen über mögliche Phasenlagen der Taskaktivierungen wurden genutzt, um bestimmte gegenseitige Unterbrechungen bei der Analyse auszuschließen. Als Referenz zur Phasenlageberechnung zwischen Ereignissen unterschiedlicher Ereigniströme wurde, statt der tatsächlichen Ereignisse, eine virtuelle zeitliche Referenz verwendet, die früheste mögliche Ankunft der Ereignisse an den Systemeingängen. Dadurch war es möglich, das Konzept zur Erfassung der Inter Event Stream Kontextinformation für alle Standard-Ereignismodelle zu erweitern. Die letztgenannte Erweiterung hat den Grundstein gelegt, um die Kompatibilität von Inter Event Stream kontextsensitiven und kontextfreien Analysen zu gewährleisten. Dadurch wurde die Übertragung von Inter Event Stream Kontexten zwischen verschiedenen Systemkomponenten ermöglicht. Für jede Komponente kann die Analyse immer dann Inter Event Stream kontextsensitiv sein, wenn ein entsprechendes Verfahren zur Auswertung der Inter Event Stream Kontextinformation zur Verfügung steht. Existiert noch kein Auswertungsverfahren oder bringt die Auswertung der Inter Event Stream Kontextinformation keinen Gewinn, funktioniert die Analyse Inter Event Stream kontextfrei. Unabhängig von der Auswertung der vorhandenen Inter Event Stream Kontextinformation, wird diese dann an die nächste Komponente übertragen. Dadurch ist es uns gelungen, Inter Event Stream Kontexte für heterogene Systeme mit unterschiedlichen Schedulingstrategien zu berücksichtigen. Das Feld der Inter Event Stream kontextsensitiven Analysen wurde zudem für weitere Schedulinganalysen erweitert (u.a. Static Priority Non Preemptive Scheduling, ERCOSEK, EDF, CAN. Dazu wurde ein Verfahren entwickelt, das eine Berechnung und Auswertung von genaueren Phasenlagen zwischen Taskaktivierungen erlaubt. Die grundlegende Idee dieses Verfahrens ist es, zusätzliche zeitliche Referenzen zur Erfassung von Phasenlagen zu verwenden (z.B. Phasenlage bezüglich der Produktion von Ereignissen an den Ausgängen eines gemeinsamen Vorgängertasks). Diese neue Art der Inter Event Stream Kontextinformation konnte automatisch von den bereits existierenden Algorithmen zur Übertragung von Inter Event Stream Kontexten zwischen Komponenten profitieren. Als nächstes wurden Szenarien berücksichtigt. Szenarien stellen Systemkontexte dar, die das mögliche Verhalten von Tasks über längere zeitliche Abschnitte einschränken. Innerhalb eines solchen Szenarios lassen sich viel engere Grenzen des Zeitverhaltens bestimmen als im allgemeinen Fall. Sie werden daher getrennt analysiert. Szenarien haben schon heute eine große praktische Bedeutung, etwa zur Beschreibung des Verhaltens einer verteilten Fahrzeugelektronik in verschiedenen Fahrzuständen. Der Ansatz ist dabei, die Szenarien getrennt zu entwerfen und dabei jeweils als statisch zu betrachten. Kritisch sind dann die Übergänge zwischen Szenarien, an denen ein Einschwingverhalten auftritt. Es konnte gezeigt werden, dass, als Folge eines Szenarioübergangs in einem verteilten System, transiente Überlastsituationen, in Form von ’Lastwellen’, entstehen können, die dann zwischen den Systemkomponenten unkontrolliert propagiert werden und dadurch zu unbeherrschbaren Systemen führen können. Sowohl dieser Lastwellen- Effekt als auch ein Lösungsansatz zur Analyse von Szenarienübergängen wurden publiziert. Systemkontexte, wurden zudem in Kombination berücksichtigt. Es konnte gezeigt werden, dass Szenarien, Intra Event Stream Kontexte und Intra Event Stream Kontexte orthogonal zu einander sind. Dadurch führt ihre Kombination zu noch enger berechneten Intervallen der Antwortzeiten der Tasks als wenn man nur eine Art von Systemkontexten berücksichtigt. Eine Veröffentlichung zur Kombination von Intra und Inter Event Stream Kontexten wurde zudem zu einer der einflussreichsten Veröffentlichungen in der Geschichte der DATE-Konferenz gewählt und entsprechend publiziert. Mittlerweile wird die Berücksichtigung der Systemkontexte zur Verbesserung der Performanzanalyse über den Spin-Off Symtavision in der industriellen Analyse eingesetzt.
Projektbezogene Publikationen (Auswahl)
- Arne Hamann, Rafik Henia, Razvan Racu, Marek Jersak, Kai Richter, Rolf Ernst. "SymTA/S - Symbolic Timing Analysis for Systems." In WIP Proc. of the IEEE Euromicro Conference on Real-Time Systems 2004 (ECRTS), pp 17-20, Catania, Italy, June 2004.
- Marek Jersak, Rafik Henia, Rolf Ernst. "Context-Aware Performance Analysis for Efficient Embedded System Design." In Proc. ACM/IEEE Design, Automation and Test in Europe (DATE), Paris, France, March 2004.
- Rafik Henia, Arne Hamann , Marek Jersak, Razvan Racu, Kai Richter, Rolf Ernst. "System Level Performance Analysis - the SymTA/S Approach." In IEE Proceedings Computers and Digital Techniques, 2005.
- Rafik Henia, Arne Hamann, Marek Jersak, Razvan Racu, Kai Richter, Rolf Ernst. Bashir M. Al-Hashimi (editor). "System Level Performance Analysis - the SymTA/S Approach." Volume System-on-Chip: Next Generation Electronics, pp 29-72, 2006.
- Rafik Henia, Razvan Racu, Rolf Ernst. "Improved Output Jitter Calculation for Compositional Performance Analysis of Distributed Systems." In Proc. of the Workshop on Parallel and Distributed Real-Time Systems (WPDRS), Long Beach, CA, USA, March 2007.
- Rafik Henia, Rolf Ernst. "Context-Aware Scheduling Analysis of Distributed Systems with Tree-shaped Task-Dependencies." In Proc. ACM/IEEE Design, Automation and Test in Europe (DATE), Munich, Germany, March 2005.
- Rafik Henia, Rolf Ernst. "Improved Offset-Analysis Using Multiple Timing-References." In Proc. ACM/IEEE Design, Automation and Test in Europe (DATE), Munich, Germany, March 2006.
- Rafik Henia, Rolf Ernst. "Scenario Aware Analysis for Complex Event Models and Distributed Systems." In Proc. of the Real-Time Systems Symposium (RTSS), pp 171 - 180, Tucson, AZ, USA, December 2007.
- Razvan Racu, Li Li, Rafik Henia, Arne Hamann, Rolf Ernst. "Improved Response Time Analysis of Tasks Scheduled under Preemptive Round-Robin." In Proc. of the ACM/IEEE International Conference on Hardware-Software Codesign and System Synthesis (CODESISSS), pp 179 - 184, Salzburg, Austria, October 2007.
- Simon Perathoner, ErnestoWandeler, Lothar Thiele, Arne Hamann, Simon Schliecker, Rafik Henia, Razvan Racu, Rolf Ernst, Michael Gonzalez Harbour. "Influence of Different System Abstractions on the Performance Analysis of Distributed Real-Time Systems." In Proc. of the ACM Embedded Systems Software Conference (EMSOFT), Salzburg, Austria, October 2007.
- Simon Schliecker, Arne Hamann, Rafik Henia, Razvan Racu, Jonas Rox, Rolf Ernst. "Formal Performance Analysis for Real-Time Heterogeneous Embedded Systems". In Model-Based Design of Heterogeneous Embedded Systems. CRC Press. late 2008.
