Cyclic dependencies in modular performance analysis

ABSTRACT

The Modular Performance Analysis based on Real-Time Calculus (MPA-RTC), developed by Thiele et al., is an abstraction for the analysis of component-based real-time systems. The formalism uses an abstract stream model to characterize both workload and availability of computation and communication resources. Components can then be viewed as stream transformers. The Real-Time Calculus has been used successfully on systems where dependencies between components, via either workload or resource streams, are acyclic. For systems with cyclic dependencies the foundations and performance of the formalism are less well understood.

In this paper, we develop a general operational semantics underlying the Real-Time Calculus, and use this to show that the behavior of systems with cyclic dependencies can be analyzed by fixpoint iterations. We characterize conditions under which such iterations give safe results, and also show how precise the results can be.

REFERENCES

• 1: M. Fekete. Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten. Mathematische Zeitschrift, 17:228--249, 1923.
• 2: M. Jersak, K. Richter, and R. Ernst. Performance analysis for complex embedded applications. Int. J. of Embedded Systems, 1(1/2):33--49, 2005.
• 3: G. Kahn. The semantics of a simple language for parallel programming. In IFIP 74, pages 471--475. North-Holland, 1974.
• 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: H. Schiøler, J. Jessen, J. Dalsgaard, and K. Larsen. Network calculus for real time analysis of embedded systems with cyclic task dependencies. In G. Hu, editor, Proc. 20th International Conference on Computers and Their Applications, CATA 2005, March 16-18, 2005, Louisiana, pages 326--332. ISCA, 2005.
• 6: L. Thiele, S. Chakraborty, M. Gries, and S. Künzli. Design space exploration of network processor architectures. In Network Processor Design: Issues and Practices, Volume 1, pages 55--89. 2002.
• 7: Lothar Thiele , Samarjit Chakraborty , Matthias Gries , Simon Künzli, A framework for evaluating design tradeoffs in packet processing architectures, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514136]
• 8: E. Wandeler. Modular Performance Analysis and Interface-Based Design for Embedded RealTime Systems. PhD thesis, ETH Zürich, 2006.
• 9: Quantitative Characterization of Event Streams in Analysis of Hard Real-Time Applications, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium, p.450, May 25-28, 2004
• 10: 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]
• 11: Robert Kim Yates, Networks of Real-Time Processes, Proceedings of the 4th International Conference on Concurrency Theory, p.384-397, August 23-26, 1993

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

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

General Terms:
Design, Performance, Theory

Keywords:
fixpoint iteration, performance analysis, real-time calculus