uu.seUppsala University Publications
Change search
Link to record
Permanent link

Direct link
BETA
Stigge, Martin
Publications (10 of 18) Show all publications
Ekberg, P., Guan, N., Stigge, M. & Yi, W. (2015). An optimal resource sharing protocol for generalized multiframe tasks. The Journal of logical and algebraic methods in programming, 84(1), 92-105
Open this publication in new window or tab >>An optimal resource sharing protocol for generalized multiframe tasks
2015 (English)In: The Journal of logical and algebraic methods in programming, ISSN 2352-2208, E-ISSN 2352-2216, Vol. 84, no 1, p. 92-105Article in journal (Refereed) Published
National Category
Computer Engineering
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-235474 (URN)10.1016/j.jlamp.2014.10.001 (DOI)000347601600007 ()
Projects
UPMARC
Available from: 2014-10-16 Created: 2014-11-04 Last updated: 2018-01-11Bibliographically approved
Stigge, M. & Yi, W. (2015). Combinatorial abstraction refinement for feasibility analysis of static priorities. Real-time systems, 51(6), 639-674
Open this publication in new window or tab >>Combinatorial abstraction refinement for feasibility analysis of static priorities
2015 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 51, no 6, p. 639-674Article in journal (Refereed) Published
National Category
Computer Engineering
Identifiers
urn:nbn:se:uu:diva-265808 (URN)10.1007/s11241-015-9220-5 (DOI)000362744100002 ()
Available from: 2015-02-21 Created: 2015-11-03 Last updated: 2018-01-10Bibliographically approved
Stigge, M. & Yi, W. (2015). Graph-based models for real-time workload: a survey. Real-time systems, 51(5), 602-636
Open this publication in new window or tab >>Graph-based models for real-time workload: a survey
2015 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 51, no 5, p. 602-636Article in journal (Refereed) Published
National Category
Computer Engineering
Identifiers
urn:nbn:se:uu:diva-261947 (URN)10.1007/s11241-015-9234-z (DOI)000359748300004 ()
Available from: 2015-08-01 Created: 2015-09-07 Last updated: 2018-01-11Bibliographically approved
Guan, N., Tang, Y., Abdullah, J., Stigge, M. & Yi, W. (2015). Scalable timing analysis with refinement. In: Tools and Algorithms for the Construction and Analysis of Systems: . Paper presented at TACAS 2015, April 13–17, London, UK (pp. 3-18). Springer
Open this publication in new window or tab >>Scalable timing analysis with refinement
Show others...
2015 (English)In: Tools and Algorithms for the Construction and Analysis of Systems, Springer, 2015, p. 3-18Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Springer, 2015
Series
Lecture Notes in Computer Science ; 9035
National Category
Computer Engineering
Identifiers
urn:nbn:se:uu:diva-317679 (URN)10.1007/978-3-662-46681-0_1 (DOI)978-3-662-46680-3 (ISBN)
Conference
TACAS 2015, April 13–17, London, UK
Projects
UPMARC
Available from: 2015-04-24 Created: 2017-03-16 Last updated: 2018-01-13Bibliographically approved
Stigge, M. (2014). Real-Time Workload Models: Expressiveness vs. Analysis Efficiency. (Doctoral dissertation). Uppsala: Acta Universitatis Upsaliensis
Open this publication in new window or tab >>Real-Time Workload Models: Expressiveness vs. Analysis Efficiency
2014 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

The requirements for real-time systems in safety-critical applications typically contain strict timing constraints. The design of such a system must be subject to extensive validation to guarantee that critical timing constraints will never be violated while the system operates. A mathematically rigorous technique to do so is to perform a schedulability analysis for formally verifying models of the computational workload. Different workload models 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. The more expressive a task model is, the more accurately it can describe a system design, reducing over-approximations and thus minimizing wasteful over-provisioning of system resources. However, more expressiveness implies higher computational complexity of corresponding analysis methods. Consequently, an ideal model provides the highest possible expressiveness for which efficient exact analysis methods exist.

This thesis investigates the trade-off between expressiveness and analysis efficiency. A new digraph-based task model is introduced, which generalizes all previously proposed models that can be analyzed in pseudo-polynomial time without using any analysis-specific over-approximations. We develop methods allowing to efficiently analyze variants of the model despite their strictly increased expressiveness. A key contribution is the notion of path abstraction which enables efficient graph traversal algorithms. We demonstrate tractability borderlines for different classes of schedulers, namely static priority and earliest-deadline first schedulers, by establishing hardness results. These hardness proofs provide insights about the inherent complexity of developing efficient analysis methods and indicate fundamental difficulties of the considered schedulability problems. Finally, we develop a novel abstraction refinement scheme to cope with combinatorial explosion and apply it to schedulability and response-time analysis problems. All methods presented in this thesis are extensively evaluated, demonstrating practical applicability.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2014. p. 172
Series
Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1104-2516 ; 103
Keywords
Real-time systems, task models, EDF, fixed-priority scheduling, schedulability analysis, response-time analysis, abstraction refinement
National Category
Computer Engineering
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-219307 (URN)978-91-554-8888-8 (ISBN)
Public defence
2014-04-11, Room 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Projects
UPMARC
Available from: 2014-03-20 Created: 2014-02-26 Last updated: 2019-02-25
Stigge, M., Guan, N. & Yi, W. (2014). Refinement-based Exact Response-Time Analysis. In: 2014 26TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS (ECRTS 2014): . Paper presented at 26th Euromicro Conference on Real-Time Systems (ECRTS), JUL 08-11, 2014, Madrid, SPAIN (pp. 143-152).
Open this publication in new window or tab >>Refinement-based Exact Response-Time Analysis
2014 (English)In: 2014 26TH EUROMICRO CONFERENCE ON REAL-TIME SYSTEMS (ECRTS 2014), 2014, p. 143-152Conference paper, Published paper (Refereed)
Abstract [en]

A recent trend in the theory of real-time scheduling is to consider generalizations of the classical periodic task model. Work on the associated schedulability and feasibility problems has resulted in algorithms that run efficiently and provide exact results. While these analyses give black-and-white answers about whether timing constraints are being met or not, response-time analysis adds a quantitative dimension. This brings new challenges for models more expressive than the classical periodic task model. An exact quantification of response time is difficult because of non-deterministic task behavior and a lack of combinable task-local worst cases. Therefore, previous approaches all make a trade-off between efficiency and precision, resulting in either prohibitively slow analysis run-times or imprecise over-approximate results. In this paper, we show that analysis can be both exact and efficient at the same time. We develop novel response-time characterizations to which we apply combinatorial abstraction refinement. Our algorithms for static-priority and EDF scheduling give exact results and are shown to be efficient for typical problem sizes. We advance the state-of-the-art by providing the first exact response-time analysis framework for graph-based task models.

Series
Euromicro Workshop on Real-Time Systems-Proceedings, ISSN 1068-3070
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-247631 (URN)10.1109/ECRTS.2014.29 (DOI)000349236400015 ()978-1-4799-5798-9 (ISBN)
Conference
26th Euromicro Conference on Real-Time Systems (ECRTS), JUL 08-11, 2014, Madrid, SPAIN
Available from: 2015-03-23 Created: 2015-03-22 Last updated: 2018-01-11Bibliographically approved
Stigge, M. & Yi, W. (2013). Combinatorial Abstraction Refinement for Feasibility Analysis. In: IEEE 34TH REAL-TIME SYSTEMS SYMPOSIUM (RTSS 2013): . Paper presented at IEEE 34th Real-Time Systems Symposium (RTSS), DEC 03-06, 2013, Vancouver, CANADA (pp. 340-349).
Open this publication in new window or tab >>Combinatorial Abstraction Refinement for Feasibility Analysis
2013 (English)In: IEEE 34TH REAL-TIME SYSTEMS SYMPOSIUM (RTSS 2013), 2013, p. 340-349Conference paper, Published paper (Refereed)
Abstract [en]

The traditional periodic workload model for hard real-time systems has been extended by more expressive models in recent years. These models based on different classes of directed graphs allow modeling of structures like frames, branching and loops. With more expressiveness comes higher complexity of the associated analysis problems. Feasibility of digraph-based models with dynamic priority schedulers has been shown to be tractable via pseudo-polynomial algorithms. However, the problem was shown to be intractable for static priority scheduling since it is strongly coNP-hard already for the relatively simple class of cyclic digraphs. The core of this problem is an inherent combinatorial explosion caused by combining different behaviors of the participating tasks, lacking local worst cases. We introduce a novel iterative approach to efficiently cope with this combinatorial explosion, called combinatorial abstraction refinement. In combination with other techniques it significantly reduces exponential growth of run-time for most inputs. A prototype implementation for analysing static priority feasibility outperforms the state-of-the art pseudo-polynomial analysis for dynamic priority feasibility. It further shows better scaling behavior for typical problem sizes. We believe that this method can be applicable to a variety of combinatorial problems in the theory of real-time systems with certain abstraction structures.

Series
Real-Time Systems Symposium-Proceedings, ISSN 1052-8725
National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-228256 (URN)10.1109/RTSS.2013.41 (DOI)000335336500033 ()978-1-4799-2007-5 (ISBN)
Conference
IEEE 34th Real-Time Systems Symposium (RTSS), DEC 03-06, 2013, Vancouver, CANADA
Available from: 2014-07-08 Created: 2014-07-08 Last updated: 2018-01-11Bibliographically approved
Stigge, M., Ekberg, P. & Yi, W. (2013). The fork-join real-time task model. Paper presented at Work-in-Progress (WiP) session of the 33rd IEEE Real-Time Systems Symposium (RTSS'12), December 5-7, 2012, San Juan, Puerto Rico. ACM SIGBED Review, 10(2), 20-20
Open this publication in new window or tab >>The fork-join real-time task model
2013 (English)In: ACM SIGBED Review, ISSN 1551-3688, Vol. 10, no 2, p. 20-20Article in journal, Meeting abstract (Refereed) Published
Abstract [en]

Hard real-time task models have evolved from periodic models to more sophisticated graph-based ones like the Digraph Real-Time Task Model (DRT) [1]. These models have in common that tasks are sequential in nature and do not allow for forking structures, modeling job releases that occur in parallel within the same task. To capture these, we present a task model that extends the DRT model with the possibility of forking and joining release paths. We are developing an exact schedulability test for EDF on uniprocessor systems with a pseudo-polynomial bound of its runtime.

National Category
Computer Sciences
Identifiers
urn:nbn:se:uu:diva-213295 (URN)10.1145/2518148.2518158 (DOI)
Conference
Work-in-Progress (WiP) session of the 33rd IEEE Real-Time Systems Symposium (RTSS'12), December 5-7, 2012, San Juan, Puerto Rico
Projects
UPMARC
Available from: 2013-12-20 Created: 2013-12-20 Last updated: 2018-01-11Bibliographically approved
Stigge, M. & Yi, W. (2012). Hardness Results for Static Priority Real-Time Scheduling. In: Proceedings Of The 24th Euromicro Conference On Real-Time Systems (Ecrts 2012): . Paper presented at 24th Euromicro Conference on Real-Time Systems (ECRTS), JUL 10-13, 2012, Pisa, ITALY (pp. 189-198).
Open this publication in new window or tab >>Hardness Results for Static Priority Real-Time Scheduling
2012 (English)In: Proceedings Of The 24th Euromicro Conference On Real-Time Systems (Ecrts 2012), 2012, p. 189-198Conference paper, Published paper (Refereed)
Abstract [en]

Real-time systems are often modeled as a collection of tasks, describing the structure of the processor's workload. In the literature, task-models of different expressiveness have been developed, ranging from the traditional periodic task model to highly expressive graph-based models. For dynamic priority schedulers, it has been shown that the schedulability problem can be solved efficiently, even for graph-based models. However, the situation is less clear for the case of static priority schedulers. It has been believed that the problem can be solved in pseudo-polynomial time for the generalized multiframe model (GMF). The GMF model constitutes a compromise in expressiveness by allowing cycling through a static list of behaviors, but disallowing branching. Further, the problem complexity for more expressive models has been unknown so far. In this paper, we show that previous results claiming that a precise and efficient test exists are wrong, giving a counterexample. We prove that the schedulability problem for GMF models (and thus also all more expressive models) using static priority schedulers is in fact coNP-hard in the strong sense. Our result thus establishes the fundamental hardness of analyzing static priority real-time scheduling, in contrast to its dynamic priority counterpart of pseudo-polynomial complexity.

Series
Euromicro Workshop on Real-Time Systems-Proceedings, ISSN 1068-3070
National Category
Natural Sciences Engineering and Technology
Identifiers
urn:nbn:se:uu:diva-207203 (URN)10.1109/ECRTS.2012.13 (DOI)000322959300018 ()978-0-7695-4739-8 (ISBN)
Conference
24th Euromicro Conference on Real-Time Systems (ECRTS), JUL 10-13, 2012, Pisa, ITALY
Available from: 2013-09-10 Created: 2013-09-10 Last updated: 2013-09-10Bibliographically approved
Guan, N., Stigge, M., Yi, W. & Yu, G. (2012). Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling. In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS): . Paper presented at 26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), MAY 21-25, 2012, Shanghai, PEOPLES R CHINA (pp. 261-272).
Open this publication in new window or tab >>Parametric Utilization Bounds for Fixed-Priority Multiprocessor Scheduling
2012 (English)In: 2012 IEEE 26th International Parallel and Distributed Processing Symposium (IPDPS), 2012, p. 261-272Conference paper, Published paper (Refereed)
Abstract [en]

Future embedded real-time systems will be deployed on multi-core processors to meet the dramatically increasing high-performance and low-power requirements. This trend appeals to generalize established results on uniprocessor scheduling, particularly the various utilization bounds for schedulability test used in system design, to the multiprocessor setting. Recently, this has been achieved for the famous Liu and Layland utilization bound by applying novel task splitting techniques. However, parametric utilization bounds that can guarantee higher utilizations (up to 100%) for common classes of systems are not yet known to be generalizable to multiprocessors as well. In this paper, we solve this problem for most parametric utilization bounds by proposing new task partitioning algorithms based on exact response time analysis. In addition to the worst-case guarantees, as the exact response time analysis is used for task partitioning, our algorithms significantly improve average-case utilization over previous work.

Series
International Parallel and Distributed Processing Symposium IPDPS
National Category
Engineering and Technology
Identifiers
urn:nbn:se:uu:diva-184746 (URN)10.1109/IPDPS.2012.33 (DOI)000309131900024 ()978-0-7695-4675-9 (ISBN)
Conference
26th IEEE International Parallel and Distributed Processing Symposium (IPDPS), MAY 21-25, 2012, Shanghai, PEOPLES R CHINA
Projects
UPMARC
Available from: 2012-11-14 Created: 2012-11-13 Last updated: 2014-01-23
Organisations

Search in DiVA

Show all publications