Generation and Optimization of Real-Time Code for Embedded Multiprocess and Multiprocessor Systems (E = Mp2)

Fact Sheet

AcronymE = Mp2
NameGeneration and Optimization of Real-Time Code for Embedded Multiprocess and Multiprocessor Systems
(in German: Generierung und Optimierung von Echtzeitfähigem Code für Eingebettete Multiprozess- und Multiprozessor-Systeme)
Role of TUHHApplicant
Start Date01/02/2012
End Date30/09/2017
Funds DonorDeutsche Forschungsgemeinschaft (DFG)


During the design of safety-critical real-time systems like, e.g., airbag or flight attitude controllers, their behavior is specified at a high abstraction level. Compilers are an indispensible tool on the way from such a model-based specification to an actual implementation. For singlecore and singleprocess systems, compilers have recently been extended to support real-time properties already during compilation. For multiprocess and multiprocessor systems, compilers currently lack such a support despite of the increasing relevance of such parallel systems.

E = Mp2 aims to provide a software development environment for multiprocess and multiprocessor systems which produces efficient and optimized program code that provably meets real-time constraints. For this purpose, it has to be clarified how compiler and scheduler of an operating system need to cooperate. In addition, novel timing models supporting response times of processes and schedulability of entire systems need to be developed. Based on these timing models, novel compiler optimizations targeting on worst-case timing aspects and schedulability are designed.

In multiprocess systems, tasks can preempt each other and thus interfere. E = Mp2 develops compiler optimizations considering such context switches and scheduling strategies. In multiprocessor systems, different cores can access shared resources (e.g., buses or memories) at the same time and thus can cause additional interference. Therefore, this project works on compiler optimizations minimizing the worst-case timing of such systems by considering accesses to shared resources.

E = Mp2 Publications of the Embedded Systems Design Group

Title: Simple Analysis of Partial Worst-case Execution Paths on General Control Flow Graphs. <em>In Proceedings of the International Conference on Embedded Software (EMSOFT)</em>
Written by: Jan C. Kleinsorge, Heiko Falk and Peter Marwedel
in: October (2013).
Volume: Number:
on pages:
Series: 20131001-emsoft-kleinsorge.pdf
Address: Montreal / Canada
ISBN: 10.1109/EMSOFT.2013.6658594
how published: 13-50 KFM13 EMSOFT

Note: hfalk, ESD, emp2, tacle, WCC

Abstract: One of the most important computations in static worst-case execution time analyses is the path analysis which computes the potentially most time-consuming execution path in a program. This is typically done either with an implicit path computation based on solving an integer linear program, or with explicit path computations directly on the program's control flow graph. The former approach is powerful and comparably simple to use but hard to extend and to combine with other program analyses due to its restriction to the linear equation model. The latter approaches are often restricted to well-structured graphs, suffer from inaccuracy or require non-trivial structural analyses or graph transformations upfront or during their computations.<br /> In this paper, we propose a generalized computational model and a comprehensive explicit path analysis that operates on arbitrary directed control flow graphs. We propose simple and yet effective techniques to deal with unstructured control flows and complex flow fact models. The analysis does not require a control flow graph to be mutable, is non-recursive, fast, and provides the means to compute all worst-case paths from arbitrary source nodes. It is well suited for solving local problems and the computation of partial solutions, which is highly relevant for problems related to scheduling and execution modes alike.