Multicore Worst-Case Response Time Analysis using Implicit Path Enumeration Technique

• Typ der Arbeit: Bachelorarbeit
• Status der Arbeit: reserviert
• Projekte: AHA
• Betreuer: Andreas Kässens, Daniel Lohmann
• Bearbeiter: Laurin Maximilian Pelz

[Generated with AI]

Context

Within the AHA project, we research specialized embedded systems with real-time requirements. Using the Automatic Real-time Analyzer (ARA), we perform static analysis to find interactions between different tasks, resulting in a State Transition Graph (STG)¹.

With the latest extension called HyperSSE, we can analyze interactions between isolated virtual machines (domains) on a static partitioning hypervisor (SPH). This allows for timing analysis of cross-domain interactions between multiple RTOSes, accelerators, coprocessors or dynamic, general-purpose OSes like Linux.

Problem

The results of the HyperSSE are stored in a Hypervisor State Transition Graph (HSTG), including the timing annotations per atomic basic block (ABB). Using these, we can derive Worst-Case Response Times across domains (WCRT) manually (neglecting hardware effects). However, using the Implicit Path Enumeration Technique (IPET)², we could automatically calculate that timings.

Goal

In this thesis, the student shall create a timing graph and provide an IPET formulation, that can be solved automatically by ILP solvers.

The following steps are required for a bachelor's thesis:

• Understand the HSTG representation of a given Real-Time System
• Derive a timing graph for a given source and destination state node
• Formulate the IPET
• Solve the ILP using an existing solver

Additionally:

• Tighten the WCRT-bound at Synchronization Points, where executed programs are interrupted

Topics: Worst-Case Response Time Analysis, Real-Time, Python

References

Performance analysis of embedded software using implicit path enumeration

Yau-Tsun Steven Li, Sharad MalikACM SIGPLAN Notices1995.
[BibTex]

BibTex Entry

@inproceedings{li:1995:sigplan,
author = {Li, Yau-Tsun Steven and Malik, Sharad},
booktitle = {ACM SIGPLAN Notices},
organization = {ACM},
pages = {88-98},
title = {Performance analysis of embedded software using implicit path enumeration},
volume = {30},
wcec_number = {11},
year = {1995},
}

RTAS Conference A Outstanding Paper Award
SysWCET: Whole-System Response-Time Analysis for Fixed-Priority Real-Time Systems

Christian Dietrich, Peter Wägemann, Peter Ulbrich, Daniel LohmannProceedings of the 23rd IEEE International Symposium on Real-Time and Embedded Technology and Applications (RTAS '17)IEEE Computer Society Press2017Outstanding Paper Award.
PDF Raw Data 10.1109/RTAS.2017.37 [BibTex]

BibTex Entry

@inproceedings{dietrich:17:rtas,
location = {Washington, DC, USA},
ar = {},
author = {Christian Dietrich and Peter W{ä}gemann and Peter Ulbrich and Daniel Lohmann},
booktitle = {Proceedings of the 23rd IEEE International Symposium on Real-Time and Embedded Technology and Applications (RTAS '17)},
category = {WCET, WCRT, IPET, ILP},
doi = {10.1109/RTAS.2017.37},
entrysubtype = {Conference},
isbn = {978-1-5090-5269-1},
pages = {37-48},
publisher = {IEEE Computer Society Press},
title = {SysWCET: Whole-System Response-Time Analysis for Fixed-Priority Real-Time Systems},
year = {2017},
}

ECRTS Conference B Best Student Paper Award
HyperSSE: Cross-Domain Static Analysis of Partitioned Real-Time Hypervisor Systems

Andreas Kässens, Mareike Burg, Daniel LohmannProceedings of the 38th Euromicro Conference on Real-Time Systems (ECRTS '26)2026Best Student Paper Award.
PDF Details Slides 10.4230/LIPIcs.ECRTS.2026.23 [BibTex]

BibTex Entry

@inproceedings{kaessens:26:ecrts,
author = {Andreas Kässens and Mareike Burg and Daniel Lohmann},
booktitle = {Proceedings of the 38th Euromicro Conference on Real-Time Systems (ECRTS '26)},
date = {2026-07-02},
doi = {10.4230/LIPIcs.ECRTS.2026.23},
entrysubtype = {Conference},
series = {ECRTS '26},
title = {{HyperSSE:} Cross-Domain Static Analysis of Partitioned Real-Time Hypervisor Systems},
year = {2026},
}