TypicalCPA - Typical Worst Case Compositional Performance Analysis
Final Report Abstract
Viele eingebettete Systeme sind Echtzeitsysteme, das sind Computersysteme, in denen wiederholt ausgeführte Berechnungen in einer begrenzten Zeit auszuführen sind. Wenn die Berechnungszeiten durch Deadlines begrenzt sind, die auf keinen Fall überschritten werden dürfen, spricht man von harten Echtzeitsystemen. Dies ist der klassische Typ eines Echtzeitsystems. Zahlreiche Anwendungen in der Regelungs- und Kommunikationstechnik sind jedoch robust gegenüber begrenzt häufig auftretenden Deadline-Verletzungen. Die Robustheit derartiger abgeschwächt-harter (Weakly-hard) Echtzeitsysteme kann für eine effiziente Auslegung eingebetteter Systeme ausgenutzt werden, erfordert jedoch den Nachweis, dass eine gegebene, maximale Häufigkeit an Deadline-Verletzungen unter keinen Umständen überschritten wird. Dieser Nachweis ist formal deutlich schwieriger als in klassischen harten Echtzeitsystemen, da zulässige Deadline-Verletzungen in vielfältigen Kombinationen auftreten können. Besonders herausfordernd ist die Handhabung in verteilten Systemen, wo sich Deadline-Verletzungen in unterschiedlicher Form fortpflanzen und das Ende-zu-Ende-Zeitverhalten von Anwendungen beeinflussen können. Zu Projektbeginn war es daher nur möglich, einen entsprechenden Nachweis für sehr einfache Systeme aus einzelnen Prozessoren oder einzelnen Netzwerksegmenten zu führen. Im abgeschlossenen Projekt wurden diese Arbeiten, insbesondere die Typical Worst Case Analyse (TWCA), kombiniert mit formalen Modellen und Methoden für die Echtzeitanalyse verteilter Systeme, die den Fluss von Information zwischen den Komponenten erfassen. Verwendet wurde der Formalismus CPA (Compositional Performance Analysis), der in Zusammenarbeit mit französischen Partnerinnen und Partnern um Eigenschaften des Network Calculus erweitert wurde, um somit Kopplungen von Komponenten durch den Informationsfluss sehr genau erfassen zu können. Darauf aufbauend wurde eine formale Zerlegung der aus dem Informationsfluss entstehenden Last in eine typische Last, die zu keinen Deadline-Verletzungen führt und eine Überlast, die Verletzungen erzeugt, abgeleitet. Schließlich konnte die Fortpflanzung der entstehenden Effekte formal geschlossen beschrieben und untersucht werden. Die daraus entstehende „TypicalCPA“ kann erstmals abgeschwächt-harte Echtzeitbedingungen auf der Ebene ganzer Systeme behandeln. Als weiteres erfreuliches, ursprünglich nicht geplantes Nebenresultat konnte die sehr einfache Einbindung des Programmierparadigmas LET, das in neueren Fahrzeugsystemen zur Beherrschung des Zeitverhaltens eingeführt wurde, gezeigt werden. Daraus entsteht die Chance, das Projektergebnis mittelfristig zur Verifikation des Zeitverhaltens großer praktischer Systeme, etwa in der Fahrzeugtechnik, einzusetzen, wo die klassische Echtzeitanalyse heute oft zu pessimistische Ergebnisse liefert. Nicht weiter verfolgt wurde die Modellierung von verlustbehaftetem Überlastverhalten, etwa dem Abbruch von Berechnungen oder dem Verlust oder Abwurf von Paketen in der Kommunikation. Die Ergebnisse legen nahe, dass Auftreten und Resultat solcher „Abwürfe“ schwer systematisch zu beherrschen sind, so dass durch ein derartiges Überlastverhalten keine sinnvoll nutzbare Lastbegrenzung erreicht wird. Auch dies ist ein sehr instruktives Ergebnis mit Relevanz für den praktischen Entwurf.
Publications
- (2015): Improved deadline miss models for real-time systems using typical worst-case analysis. In: Real-Time Systems (ECRTS), 2015 27th Euromicro Conference on. IEEE, S. 247–256
Xu, Wenbo; Hammadeh, Zain A. H.; Kröller, Alexander; Ernst, Rolf; Quinton, Sophie
(See online at https://doi.org/10.1109/ECRTS.2015.29) - (2016): Guarantees for runnable entities with heterogeneous real-time requirements. In: Proceedings of the 2016 Conference on Design, Automation & Test in Europe. EDA Consortium, S. 1646–1651
Ahrendts, Leonie; Hammadeh, Zain A. H.; Ernst, Rolf
- (2017): Bounding Deadline Misses in Weakly-Hard Real-Time Systems with Task Dependencies. In: Design, Automation and Test in Europe
Hammadeh, Zain A. H.; Ernst, Rolf; Quinton, Sophie; Henia, Rafik; Rioux, Laurent; Girault, Alain et al.
(See online at https://doi.org/10.23919/DATE.2017.7927054) - (2017): Budgeting Under-specified Tasks for Weakly-Hard Real- Time Systems. In: The 29th Euromicro Conference on Real-Time Systems (ECRTS17). Dubrovnik, Croatia
Hammadeh, Zain A. H.; Quinton, Sophie; Panunzio, Marco; Henia, Rafik; Rioux ,Laurent; Ernst, Rolf
(See online at https://doi.org/10.4230/LIPIcs.ECRTS.2017.17) - (2017): CPA - Compositional Performance Analysis. In: Soonhoi Ha und Jürgen Teich (Hg.): Handbook of Hardware/Software Codesign. Dordrecht: Springer Netherlands, S. 1–31
Hofmann, Robin; Ahrendts, Leonie; Ernst, Rolf
(See online at https://doi.org/10.1007/978-94-017-7267-9_24) - (2017): Exploiting Execution Dynamics in Timing Analysis Using Job Sequences. In: IEEE Design & Test
Ahrendts, Leonie; Quinton, Sophie; Ernst, Rolf
(See online at https://doi.org/10.1109/MDAT.2017.2746638) - (2018). System-level LET: Mastering cause-effect chains in distributed systems. In IECON 2018-44th Annual Conference of the IEEE Industrial Electronics Society, S.4084-4089
Ernst, R., Ahrendts, L., & Gemlau, K. B.
(See online at https://doi.org/10.1109/IECON.2018.8591550) - (2018). Verifying weakly-hard real-time properties of traffic streams in switched networks. In ECRTS 2018-30th Euromicro Conference on Real-Time Systems, S. 1-22
Ahrendts, L., Quinton, S., Boroske, T., & Ernst, R.
(See online at https://doi.org/10.4230/LIPIcs.ECRTS.2018.15) - (2019). Improving a compositional timing analysis framework for weakly-hard real-time systems. In 2019 IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS), S.. 228-240
Köhler, L., & Ernst, R.
(See online at https://doi.org/10.1109/RTAS.2019.00027) - (2019). Increasing accuracy of timing models: from CPA to CPA+. In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), S. 1210-1215
Köhler, L., Nikolic, B., Ernst, R., & Boyer, M.
(See online at https://doi.org/10.23919/DATE.2019.8714770) - (2020). A Platform Programming Paradigm for Heterogeneous Systems Integration. Proceedings of the IEEE, 109(4), S.582-603
Gemlau, K. B., Köhler, L., & Ernst, R.
(See online at https://doi.org/10.1109/JPROC.2020.3035874) - (2021). System-level logical execution time: Augmenting the logical execution time paradigm for distributed real-time automotive software. ACM Transactions on Cyber-Physical Systems, 5(2), S. 1-27
Gemlau, K. B., Köhler, L., Ernst, R., & Quinton, S.
(See online at https://doi.org/10.1145/3381847)
