Advanced Course on Real-Time Workload Models with Efficient Analysis
September 2-4, 2014 – Retis Lab
Workload models of hard real-time systems allow to describe task activations at different levels of expressiveness, ranging from traditional periodic models to sophisticated graph-based ones. An inherent conflict arises between the expressiveness and analysis efficiency of task models. Higher expressiveness allows higher modeling accuracy but comes at the price of higher computational complexity of corresponding analysis methods.
In this series of lectures, we investigate the trade-off between expressiveness and analysis efficiency. A new digraph-based task model is introduced and contrasted with previously proposed ones like multiframe models, branching models or adaptive variable-rate (AVR) models. For the new model, we develop methods for efficient analysis despite the strictly increased expressiveness. Presented analysis methods include pseudo-polynomial feasibility tests, static priority schedulability analysis and response-time analysis. Main focus is on the key techniques such as path abstractions for efficient graph traversal and combinatorial abstraction refinement for coping with exponential worst-case complexity. Theoretical upper and lower complexity bounds as well as evaluation results will be briefly discussed as well.
Martin Stigge is a researcher in the group of Prof. Wang Yi at Uppsala University, Sweden. He received an M.Sc. degree from Humboldt University Berlin in 2008 and a Ph.D. degree from Uppsala University in 2014. His main research interest is in formal analysis of timed systems with special focus on scheduling theory.