Bachelor and Master Theses

Title: End-to-End Timing Analysis of Task-Chains
Subject: Computer Science
Level: Advanced
Description: Embedded systems often face strict timing requirements. In addition to the common deadlines tasks face for their periodic execution, many domains additionally require more elaborate timing requirements for a system to be deemed correct.
One example is the automotive domain where end-to-end timing constraints can be found for the propagation of data through a chain of tasks. Several activation patterns are possible for such chains. On one hand tasks can be triggered periodically, i.e. there is no signalling between preceding tasks in a chain and shared variables are used for communication, a task always reads the current value of the shared variable. A second common form is triggering, where a preceding task triggers the execution of a second task. In industrial applications a single chain of tasks can comprise a mixture of both activation patterns. This increases the complexity of the timing analysis.
In [1], Feiertag et al. first describe the different end-to-end delay metrics found in automotive systems and later propose a respective timing analysis technique. This analysis requires information which is only available in the implementation level.
In contrast [2] presents an analysis for end-to-end constraints which is applicable in early design phases. Later in [3] it was shown how to reduce pessimism of the analysis technique when information from the implementation level is available.

The thesis will focus on the comparison of the two analysis techniques [1][3]. Different aspects, such as the tightness of the produced result as well as memory consumption and analysis time are of interest.
Since a system designer may freely combine different activation pattern in one chain the thesis will also examine the effects of such design decisions on the resulting end-to-end latencies.

Expected main results:
• Literature review
• An extensive comparison of the two analysis techniques
• Evaluation of different trigger patterns and their effect on the end-to-end latency
• A written thesis

Requirements:
• Programming knowledge (C and/or Java)
• Basic understanding of real-time systems

The thesis can be adapted for 1-2 students and for 15 or 30CP.

[1] N. Feiertag, K. Richter, J. Norlander, and J. Jonsson, “A compositional framework for end-to-end path delay calculation of automotive systems under different path semantics,” in Int. Workshop on Compositional Theory and Technology for Real- Time Embedded Systems (CRTS), 2008.

[2] M. Becker, D. Dasari, S. Mubeen, M. Behnam, and T. Nolte, “Synthesizing job-level dependencies for automotive multi-rate effect chains,” in 22th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), 2016.

[3] M. Becker, D. Dasari, S. Mubeen, M. Behnam, and T. Nolte, “Analyzing End-to-End Delays in Automotive Systems at Various Levels of Timing Information,” in IEEE 4th International Workshop on Real-Time Computing and Distributed systems in Emerging Applications (REACTION), 2016.
Start date: 27-03-2017
Student: Jin Zhiqun zjn16001@student.mdh.se
Student: Zhu Shijie szu16001@student.mdh.se
IDT supervisor: Matthias Becker
matthias.becker@mdh.se, 076-781 16 04
Examinator: Saad Mubeen
Saad Mubeen
saad.mubeen@mdh.se, +4621103191

  • Mälardalen University |
  • Box 883 |
  • 721 23 Västerås/Eskilstuna |
  • 021-101300, 016-153600 |
  • webmaster |
  • Latest update: 2017.08.23