Providing accurate event models for the analysis of heterogeneous multiprocessor systems

ABSTRACT

This paper proposes a new method for deriving quantitative event information for compositional multiprocessor performance analysis. This procedure brakes down the complexity into the analysis of individual components (tasks mapped to resources) and the propagation of the timing information with the help of event models. This paper improves previous methods to derive event models in a multiprocessor system by providing tighter bounds and allowing arbitrarily shaped event models. The procedure is based on a a simple yet expressive resource model called the multiple event busy time which can be derived on the basis of classical scheduling theory -- it can therefore be provided for a large domain of scheduling policies. Our experiments show that overestimation by previous methods can be reduced significantly.

REFERENCES

• 1: Rafik Henia, Arne Hamann, Marek Jersak, Razvan Racu, Kai Richter, and Rolf Ernst. System level performance analysis - the symta/s approach. In IEE Proceedings Computers and Digital Techniques, 2005.
• 2: 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
• 3: K. W. Tindell , A. Burns , A. J. Wellings, An extendible approach for analyzing fixed priority hard real-time tasks, Real-Time Systems, v.6 n.2, p.133-151, March 1994 [doi>10.1007/BF01088593]
• 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 , Lothar Thiele, A New Task Model for Streaming Applications and Its Schedulability Analysis, Proceedings of the conference on Design, Automation and Test in Europe, p.486-491, March 07-11, 2005 [doi>10.1109/DATE.2005.26]
• 6: Ernesto Wandeler. Modular Performance Analysis and Interface-based Design of Embedded Systems. PhD thesis, Swiss Federal Institute of Technology, 2006.
• 7: Kai Richter. Compositional Scheduling Analysis Using Standard Event Models. PhD thesis, Technical University of Braunschweig, 2004.
• 8: Simon Perathoner, Ernesto Wandeler, and Lothar Thiele et al. Influence of different system abstractions on the performance analysis of distributed real-time systems. Design Automation for Embedded Systems, 2008.
• 9: Jonas Rox , Rolf Ernst, Construction and Deconstruction of Hierarchical Event Streams with Multiple Hierarchical Layers, Proceedings of the 2008 Euromicro Conference on Real-Time Systems, p.201-210, July 02-04, 2008 [doi>10.1109/ECRTS.2008.13]
• 10: S. Schliecker, M. Ivers, and R. Ernst. Memory Access Patterns for the Analysis of MPSoCs. IEEE North-East Workshop on Systems, 2006.
• 11: Karsten Albers , Frank Bodmann , Frank Slomka, Hierarchical Event Streams and Event Dependency Graphs: A New Computational Model for Embedded Real-Time Systems, Proceedings of the 18th Euromicro Conference on Real-Time Systems, p.97-106, July 05-07, 2006 [doi>10.1109/ECRTS.2006.12]
• 12: M. Joseph and P. Pandya. Finding Response Times in a Real-Time System. The Computer Journal, 29(5):390, 1986.
• 13: J. C. Palencia , M. González Harbour, Schedulability Analysis for Tasks with Static and Dynamic Offsets, Proceedings of the IEEE Real-Time Systems Symposium, p.26, December 02-04, 1998
• 14: Aloysius K. Mok , Deji Chen, A Multiframe Model for Real-Time Tasks, IEEE Transactions on Software Engineering, v.23 n.10, p.635-645, October 1997 [doi>10.1109/32.637146]
• 15: Jan Staschulat , Simon Schliecker , Rolf Ernst, Scheduling Analysis of Real-Time Systems with Precise Modeling of Cache Related Preemption Delay, Proceedings of the 17th Euromicro Conference on Real-Time Systems, p.41-48, July 06-08, 2005 [doi>10.1109/ECRTS.2005.26]
• 16: Traian Pop , Paul Pop , Petru Eles , Zebo Peng , Alexandru Andrei, Timing Analysis of the FlexRay Communication Protocol, Proceedings of the 18th Euromicro Conference on Real-Time Systems, p.203-216, July 05-07, 2006 [doi>10.1109/ECRTS.2006.31]
• 17: Chengzhi Li , Riccardo Bettati , Wei Zhao, Response Time Analysis for Distributed Real-Time Systems with Bursty Job Arrivals, Proceedings of the 1998 International Conference on Parallel Processing, p.432-440, August 10-14, 1998
• 18: Razvan Racu , Li Li , Rafik Henia , Arne Hamann , Rolf Ernst, Improved response time analysis of tasks scheduled under preemptive Round-Robin, 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.1289861]
• 19: Simon Schliecker , Matthias Ivers , Rolf Ernst, Integrated analysis of communicating tasks in MPSoCs, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176325]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Performance, Verification

Keywords:
compositional performance analysis, multiprocessor, real-time