Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

This paper advocates a strict compositional and hybrid approach for obtaining key (performance) metrics of embedded systems. At its core the developed methodology abstracts system components by either flow-oriented and purely analytic descriptions or by state-based models in the form of timed automata. The interaction among the heterogeneous components is modeled by streams of discrete activity-triggers. In total this yields a hybrid framework for the compositional analysis of embedded systems. It supplements contemporary techniques for the following reasons: (a) state space explosion as intrinsic to formal verification is limited to the level of isolated components; (b) computed performance metrics such as buffer sizes, delays and utilization rates are not overly pessimistic, because coarse-grained purely analytic models are used for components only which conform to the stateless model of computation. For demonstrating the usefulness of the presented ideas we implemented a corresponding tool-chain and investigated the performance of a two-staged computing system, where one stage exhibits state-dependent behavior only coarsely coverable by a purely analytic and stateless component abstraction.

REFERENCES

• 1: Rajeev Alur , David L. Dill, Automata For Modeling Real-Time Systems, Proceedings of the 17th International Colloquium on Automata, Languages and Programming, p.322-335, July 16-20, 1990
• 2: G. Behrmann, A. David, and K. G. Larsen. A tutorial on uppaal. In M. Bernardo and F. Corradini, editors, Formal Methods for the Design of Real-Time Systems: 4th International School on Formal Methods for the Design of Computer, Communication, and Software Systems, SFM-RT 2004, number 3185 in LNCS, pages 200--236. Springer-Verlag, September 2004.
• 3: J. Bengtsson and W. Yi. Timed automata: Semantics, algorithms and tools. In Lectures on Concurrency and Petri Nets, volume 3098 of LNCS, pages 87--124. Springer, 2004.
• 4: Jean-Yves Le Boudec , Patrick Thiran, Network calculus: a theory of deterministic queuing systems for the internet, Springer-Verlag New York, Inc., New York, NY, 2001
• 5: Samarjit Chakraborty , Simon Kunzli , Lothar Thiele, A General Framework for Analysing System Properties in Platform-Based Embedded System Designs, Proceedings of the conference on Design, Automation and Test in Europe, p.10190, March 03-07, 2003
• 6: Samarjit Chakraborty , Linh T. X. Phan , P. S. Thiagarajan, Event Count Automata: A State-Based Model for Stream Processing Systems, Proceedings of the 26th IEEE International Real-Time Systems Symposium, p.87-98, December 05-08, 2005 [doi>10.1109/RTSS.2005.21]
• 7: Henning Dierks , Alexander Metzner , Ingo Stierand, Efficient Model-Checking for Real-Time Task Networks, Proceedings of the 2009 International Conference on Embedded Software and Systems, p.11-18, May 25-27, 2009 [doi>10.1109/ICESS.2009.26]
• 8: M. González Harbour , J. J. Gutiérrez García , J. C. Palencia Gutiérrez , J. M. Drake Moyano, MAST: Modeling and Analysis Suite for Real Time Applications, Proceedings of the 13th Euromicro Conference on Real-Time Systems, p.125, June 13-15, 2001
• 9: M. Hendriks and M. Verhoef. Timed automata based analysis of embedded system architectures. In Proc. of the 20th Int. Parallel and Distributed Processing Symposium (IPDPS 2006). IEEE, 2006.
• 10: R. Henia, A. Hamann, M. Jersak, R. Racu, K. Richter, and R. Ernst. System Level Performance Analysis-The SymTA/S Approach. IEEE Proceedings-Computers and Digital Techniques, 152(2):148--166, 2005.
• 11: P. Krcal, L. Mokrushin, and W. Yi. A tool for compositional analysis of timed systems by abstraction (extended abstract). In Proc. of NWPT07, the 19th Nordic Workshop on Programming Theory, October 2007.
• 12: Simon Künzli , Arne Hamann , Rolf Ernst , Lothar Thiele, Combined approach to system level performance analysis of embedded systems, Proceedings of the 5th IEEE/ACM international conference on Hardware/software codesign and system synthesis, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289816.1289835]
• 13: Modular Performance Analysis Framework and Matlab Toolbox. www.mpa.ethz.ch.
• 14: Christer Norström , Anders Wall , Wang Yi, Timed Automata as Task Models for Event-Driven Systems, Proceedings of the Sixth International Conference on Real-Time Computing Systems and Applications, p.182, December 13-15, 1999
• 15: Linh T. X. Phan , Samarjit Chakraborty , P. S. Thiagarajan, A Multi-mode Real-Time Calculus, Proceedings of the 2008 Real-Time Systems Symposium, p.59-69, November 30-December 03, 2008 [doi>10.1109/RTSS.2008.47]
• 16: Linh T. X. Phan , Samarjit Chakraborty , P. S. Thiagarajan , Lothar Thiele, Composing Functional and State-Based Performance Models for Analyzing Heterogeneous Real-Time Systems, Proceedings of the 28th IEEE International Real-Time Systems Symposium, p.343-352, December 03-06, 2007 [doi>10.1109/RTSS.2007.16]
• 17: L. Thiele, S. Chakraborty, and M. Naedele. Real-time calculus for scheduling hard real-time systems. In Proc. Intl. Symposium on Circuits and Systems, volume 4, pages 101--104, 2000.
• 18: The Uppaal timed model checker. www.uppaal.com.
• 19: Ernesto Wandeler , Lothar Thiele , Marcel Verhoef , Paul Lieverse, System architecture evaluation using modular performance analysis: a case study, International Journal on Software Tools for Technology Transfer (STTT), v.8 n.6, p.649-667, October 2006 [doi>10.1007/s10009-006-0019-5]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Modeling techniques

General Terms:
Design, Performance, Verification

Keywords:
hard real-time systems, performance analysis, real-time calculus, timed automata