A recursive approach to end-to-end path latency computation in heterogeneous multiprocessor systems

ABSTRACT

This paper proposes a method for the derivation of end-to-end delays of applications that involve processing on multiple components in a heterogeneous multiprocessor system. The rocedure precisely captures the pipelined and parallel processing of multiple events along an application path by accurately capturing the resource timing and avoiding the pay-bursts-only-once problem. Both time-triggered and event-triggered task activation schemes with arbitrary event patterns are supported. In contrast to previous work, complex application topologies are allowed: The approach considers path forking and merging, as well as functional cycles and non-functional cyclic dependencies. The basis for the proposed method is an iterative compositional performance analysis, that allows computing event models in such systems. Based on the event models and local performance abstractions we propose a recursive approach to the derivation of the worst-case latency.

REFERENCES

• 1: N. Audsley, A. Burns, M. Richardson, K. Tindell, and A. Wellings. Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5):284--292, 1993.
• 2: F. Baccelli, G. Cohen, G. Olsder, and J. Quadrat. Synchronization and linearity. Wiley New York, 1992.
• 3: M. Bekooij, O. Moreira, P. Poplavko, B. Mesman, M. Pastrnak, and J. van Meerbergen. Predictable embedded multiprocessor system design. Proceeding of the SCOPES workshop, September, 2004.
• 4: S. Chakraborty, S. Kunzli, and L. Thiele. A general framework for analysing system properties in platform-based embedded system designs. Proc. 6th Design, Automation and Test in Europe (DATE), pages 190--195, 2003.
• 5: J. Gutierrez, J. Garcia, and M. Harbour. On the Schedulability Analysis for Distributed Hard Real-Time Systems. Proceedings of the 9th Euromicro Workshop on Real-Time Systems, Toledo, Spain, pages 136--143, 1997.
• 6: R. Henia, A. Hamann, M. Jersak, R. Racu, K. Richter, and R. Ernst. System level performance analysis -- the symta/s approach. In IEE Proceedings Computers and Digital Techniques, 2005.
• 7: P. Jayachandran and T. Abdelzaher. A Delay Composition Theorem for Real-Time Pipelines. Euromicro Conference on Real-Time Systems (ECRTS), pages 29--38, 2007.
• 8: M. Jersak, K. Richter, and R. Ernst. Performance analysis for complex embedded applications. International Journal of Embedded Systems, 1(1):33--49, 2005.
• 9: B. Jonsson, S. Perathoner, L. Thiele, and W. Yi. Cyclic dependencies in modular performance analysis. In Proceedings of the 8th ACM international conference on Embedded software (EMSOFT), pages 179--188, New York, NY, USA, October 2008. ACM.
• 10: M. Joseph and P. Pandya. Finding Response Times in a Real-Time System. The Computer Journal, 29(5):390, 1986.
• 11: J. Le Boudec and P. Thiran. Network Calculus: A Theory of Deterministic Queuing Systems for the Internet. Springer, 2001.
• 12: A. Mok and D. Chen. A multiframe model for real-time tasks. IEEE Transactions on Software Engineering, 23(10):635--645, 1997.
• 13: J. Palencia and M. Harbour. Schedulability analysis for tasks with static and dynamic o sets. In Proc. 19th IEEE Real-Time Systems Symposium (RTSS98), 1998.
• 14: S. Perathoner, E. Wandeler, L. Thiele, A. Hamann, S. Schliecker, R. Henia, R. Racu, R. Ernst, and M. G. Harbour. Influence of di erent abstractions on the performance analysis of distributed hard real-time systems. Design Automation for Embedded Systems, pages 1{23, April 2008.
• 15: P. Pop, P. Eles, and Z. Peng. Schedulability analysis and optimization for the synthesis of multi-cluster distributed embedded systems. Design Automation and Test in Europe Conference and Exhibition (DATE), pages 184--189, 2003.
• 16: T. Pop, P. Pop, P. Eles, Z. Peng, and A. Andrei. Timing Analysis of the FlexRay Communication Protocol. Euromicro Conference on Real-Time Systems (ECRTS), pages 203--213, 2006.
• 17: K. Richter and R. Ernst. Event Model Interfaces for Heterogeneous System Analysis. In Proc. Design Automation and Test in Europe (DATE), 2002.
• 18: K. Richter, D. Ziegenbein, M. Jersak, and R. Ernst. Model composition for scheduling analysis in platform design. In Proceedings of the 39th conference on Design automation (DAC), pages 287--292. ACM New York, NY, USA, 2002.
• 19: S. Schliecker, J. Rox, M. Ivers, and R. Ernst. Providing accurate event models for the analysis of heterogeneous multiprocessor systems. In Proc. Intl. Conference on Hardware/Software codesign and system synthesis (CODES+ISSS), pages 185--190. ACM New York, NY, USA, 2008.
• 20: J. Staschulat, S. Schliecker, and R. Ernst. Scheduling Analysis of Real-Time Systems with Precise Modeling of Cache Related Preemption Delay. Real-Time Systems, 2005.(ECRTS 2005). Proceedings. 17th Euromicro Conference on, pages 41--48, 2005.
• 21: S. Stein, J. Diemer, M. Ivers, S. Schliecker, and R. Ernst. On the convergence of the symta/s analysis. Technical report, Technische Universität Braunschweig, Braunschweig, Germany, November 2008.
• 22: J. Sun and J. Liu. Bounding the end-to-end response time in multiprocessor real-time systems. Proceedings of the 3rd Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), 1995.
• 23: L. Thiele, S. Chakraborty, and M. Naedele. Real-time calculus for scheduling hard real-time systems. Circuits and Systems, 2000. Proceedings. ISCAS 2000 Geneva. The 2000 IEEE International Symposium on, 4, 2000.
• 24: K. Tindell, A. Burns, and A. Wellings. An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Systems, 6(2):133--151, 1994.
• 25: K. Tindell and J. Clark. Holistic schedulability analysis for distributed hard real-time systems. Microprocessing and Microprogramming, 40(2-3):117--134, 1994

INDEX TERMS

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

General Terms:
Performance, Verification

Keywords:
multiprocessor, path latency, real-time