A tool for performance estimation of networked embedded end-systems

ABSTRACT

Networked embedded systems are expected to support adaptive streaming audio/video applications with soft real-time constraints. These systems can be designed in a cost efficient manner only if their architecture exploits the “leads” suggested by clever compile-time performance estimators. However, performance estimation of networked embedded systems is a non-trivial problem. The computational requirements of such systems show statistical variations that stem from several interacting factors. At the slowest time scale, applications can adapt to network bandwidth by configuring the processing functionality of their tasks (e.g. compression parameters). Also, there could be significant execution time variations within a task. Thus, it is tricky to compute the net processing demand of several such applications on a system architecture, especially if the system schedules these applications using prioritized run-time schedulers. In this paper, we describe an analytical tool called AsaP for fast performance estimation of such embedded systems. AsaP builds approximate models of these systems and characterizes the processing load on the system as a stochastic process. The output of AsaP is an exact distribution of the processing delay of each application. This is a powerful result that can be leveraged for efficient design of multimedia networked systems requiring soft real-time guarantees. It is also the first known framework that quantifies the effect of runtime schedulers (FCFS, RM, EDF) on the performance of such systems.

REFERENCES

• 1: PDA Buyer's Guide, Pen Computing Magazine, vol. 3, no. 11, July/ August 1996, pp. 84.
• 2: H. Schulzrinne, et al. "RTP: A Transport Protocol for Real-Time Applications'', RFC 1889, Audio/Video Transport WG, Jan. 1996.
• 3: I. Busse, et a/, "Dynamic QoS Control of Multimedia Applications based on RTP", Computer Communications 19:1, Jan. l OO6, pp.49-58.
• 4: J.-C. Bolot, A. Vega-Garcia, "Control Mechanisms for Packet Audio in the Intemet", Proc. IEEE Infocom '96, CA, April 1996, pp. 232-9.
• 5: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 6: Rajesh Kumar Gupta , Giovanni De Micheli, Co-Synthesis of Hardware and Software for Digital Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1995
• 7: Joerg Henkel , Rolf Ernst, The Interplay of Run-Time Estimation and Granularity in HW/SW Partitioning, Proceedings of the 4th International Workshop on Hardware/Software Co-Design, p.52, March 18-20, 1996
• 8: Jong Kim , Kang G. Shin, Execution Time Analysis of Communicating Tasks in Distributed Systems, IEEE Transactions on Computers, v.45 n.5, p.572-579, May 1996 [doi>10.1109/12.509908]
• 9: Y. A. Li , J. K. Antonio, Estimating the execution time distribution for a task graph in a heterogeneous computing system, Proceedings of the 6th Heterogeneous Computing Workshop (HCW '97), p.172, April 01-01, 1997
• 10: Ti-Yen Yen , Wayne Wolf, Performance estimation for real-time distributed embedded systems, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.64-71, October 02-04, 1995
• 11: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 12: K. Ramamritham et al., "Scheduling Algorithms and Operating Systems Support for Real-Time Systems", Proc. of the IEEE, vol. 82, no. 1, Jan. 1994, pp. 55-66.
• 13: David K. Y. Yau , Simon S. Lam, Adaptive rate-controlled scheduling for multimedia applications, Proceedings of the fourth ACM international conference on Multimedia, p.129-140, November 18-22, 1996, Boston, Massachusetts, United States [doi>10.1145/244130.244177]
• 14: Rajendra Yavatkar , K. Lakshman, A CPU Scheduling Algorithm for Continuous Media Applications, Proceedings of the 5th International Workshop on Network and Operating System Support for Digital Audio and Video, p.210-213, April 19-21, 1995
• 15: V. Mooney et al., "Run-Time Scheduler Synthesis for Hardware-Software Systems and Application to Robot Control Design", CODES 97.
• 16: Felice Balarin , Massimiliano Chiodo , Attila Jurecska , Luciano Lavagno , Bassam Tabbara , Alberto Sangiovanni-Vincentelli, Automatic Generation of a Real-Time Operating System for Embedded Systems, Proceedings of the 5th International Workshop on Hardware/Software Co-Design, p.95, March 24-26, 1997
• 17: Pai Chou , Gaetano Borriello, Software scheduling in the co-synthesis of reactive real-time systems, Proceedings of the 31st annual conference on Design automation, p.1-4, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196247]
• 18: E. Cinlar, Introduction to Stochastic Processes, Prentice-Hall, 1975.
• 19: S. Ross, Introduction to Probability Models, Academic Press., 1985.
• 20: V. L. Wallace, R. S. Rosenberg, "Markovian Models and Numerical Analysis of Computer System Behavior", AFIPS Spring Joint Computer Conf. Proceedings, pages 141-148, 1966.
• 21: Ptolemy at http://ptolemy, eecs. berkeley, edu
• 22: http ://bmrc. berkeley, edu/pr~jects/mpeg/mpeg-enc~de'html
• 23: Steven McCanne , Van Jacobson, vic: a flexible framework for packet video, Proceedings of the third ACM international conference on Multimedia, p.511-522, November 05-09, 1995, San Francisco, California, United States [doi>10.1145/217279.215315]

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.2 COMPUTER-COMMUNICATION NETWORKS

  J. Computer Applications

General Terms:
Design, Measurement, Performance, Theory

Keywords:
design methodology, microprocessor, timing, verification