Algebraic Task Models

• Applicant: Professor Dr.-Ing. Frank Slomka
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems
• Term: since 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 513671169

There exists a bunch of event and task models for examining real-time systems. This follows from the fact that to date there is no known model for the different requirements for the analysis of the most diverse applications in the field of real-time systems. On the one hand there are systems with hard deadlines and simple excitation patterns, on the other hand communication systems with soft deadlines but strongly fluctuating execution times. In addition, the formal connection between the different models is not well understood. On the one hand, because each task model has its own analysis algorithms that are closely linked to this model, and on the other hand, because new applications or platforms of embedded real-time systems require new and complex analysis methods. In this project, an alternative approach is pursued in contrast to the known procedure: The task modeling is to be reduced to a few methods well established in engineering and physics. The main steps for the analysis of embedded real-time systems, event and task modelling, the setting up of bounds with the determination of the worst case and the subsequent analysis should be formally encapsulated and mathematically unambiguously linked. For this purpose, on the one hand, vector calculation for event and task models is to be used, on the other hand, the algebra known from network calculus is to be adapted. The project aims to prove that it is possible to derive every event and task model described in the literature using three basic mathematical operations. First, tasks, their activation patterns and net execution times are modeled as vectors and converted into bounds to be analyzed using, for example, the scalar product and integral calculus. The worst case is then constructed using a discrete interval transformation or convolution from the min-plus algebra, and the real-time analysis is carried out on the basis of this new bound. This procedure should always be the same for all possible applications, so that specific models and the algorithms linked to them are no longer necessary. In order to show this, at the end of the project we want to describe the most important models from the literature of the past 40 years in the new methodology and examine the general connections between them.

• DFG Programme: Research Grants