System-level performance/power analysis for platform-based design of multimedia applications

ABSTRACT

The objective of this article is to introduce the use of Stochastic Automata Networks (SANs) as an effective formalism for application-architecture modeling in system-level average-case analysis for platform-based design. By platform, we mean a family of heterogeneous architectures that satisfy a set of architectural constraints imposed to allow re-use of hardware and software components. More precisely, we show how SANs can be used early in the design cycle to identify the best performance/power trade-offs among several application-architecture combinations. Having this information available not only helps avoid lengthy simulations for predicting power and performance figures, but also enables efficient mapping of different applications onto a chosen platform. We illustrate the benefits of our methodology by using the “Picture-in-Picture” video decoder as a driver application.

REFERENCES

• 1: Felice Balarin , Massimiliano Chiodo , Paolo Giusto , Harry Hsieh , Attila Jurecska , Luciano Lavagno , Claudio Passerone , Alberto Sangiovanni-Vincentelli , Ellen Sentovich , Kei Suzuki , Bassam Tabbara, Hardware-software co-design of embedded systems: the POLIS approach, Kluwer Academic Publishers, Norwell, MA, 1997
• 2: Brooks, D., Tiwari, V., and Martonosi, M. 2000. Wattch: A framework for architectural-level power analysis and optimizations. In Proceedings of the International Symposium on High-Performance Computer Architecture.
• 3: Buck, J., Ha, S., Lee, E. A., and Messerschmitt, D. G. 1994. Ptolemy: A framework for simulating and prototyping heterogeneous systems. Int. J. Comput. Simul. 4, 2, 55--182.
• 4: Joseph Buck , Radha Vaidyanathan, Heterogeneous modeling and simulation of embedded systems in El Greco, Proceedings of the eighth international workshop on Hardware/software codesign, p.142-146, May 2000, San Diego, California, United States [doi>10.1145/334012.334042]
• 5: Steven M. Burns , Henrik Hulgaard , Tod Amon , Gaetano Borriello, An Algorithm for Exact Bounds on the Time Separation of Events in Concurrent Systems, IEEE Transactions on Computers, v.44 n.11, p.1306-1317, November 1995 [doi>10.1109/12.475126 ]
• 6: Henry Chang , Larry Cooke , Merrill Hunt , Grant Martin , Andrew J. McNelly , Lee Todd, Surviving the SOC revolution: a guide to platform-based design, Kluwer Academic Publishers, Norwell, MA, 1999
• 7: Xi Chen , Harry Hsieh , Felice Balarin , Yosinori Watanabe, Automatic trace analysis for logic of constraints, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775952]
• 8: Edwards, S., Lavagno, L., Lee, E. A., and Sangiovanni-Vincentelli, A. 1997. Design of embedded systems: Formal models, validation, and synthesis. Proceedings of the IEEE 85, 3, 366--390.
• 9: Paulo Fernandes , Brigitte Plateau , William J. Stewart, Efficient descriptor-vector multiplications in stochastic automata networks, Journal of the ACM (JACM), v.45 n.3, p.381-414, May 1998 [doi>10.1145/278298.278303]
• 10: System Design: Traditional Concepts and New Paradigms, Proceedings of the 1999 IEEE International Conference on Computer Design, p.2, October 10-13, 1999
• 11: Rajesh Kumar Gupta , Giovanni De Micheli, Co-Synthesis of Hardware and Software for Digital Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1995
• 12: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470 ]
• 13: Asawaree Kalavade , Pratyush Moghé, A tool for performance estimation of networked embedded end-systems, Proceedings of the 35th annual conference on Design automation, p.257-262, June 15-19, 1998, San Francisco, California, United States [doi>10.1145/277044.277116]
• 14: Keutzer, K., Malik, S., Newton, A. R., Rabaey, J. M., and Sangiovanni-Vincentelli, A. 2000. System-Level Design: Orthogonalization of concerns and platform-based design. IEEE Trans. Comput.-Aid. Des. 19, 12, 1523--1543.
• 15: Bart Kienhuis , Ed Deprettere , Kees Vissers , Pieter van der Wolf, An Approach for Quantitative Analysis of Application-Specific Dataflow Architectures, Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures and Processors, p.338, July 14-16, 1997
• 16: 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
• 17: Lieverse, P., van der Wolf, P., Deprettere, E., and Vissers, K. 1999. A methodology for architecture exploration of heterogeneous signal Processing Systems. In Proceedings of the Workshop on Signal Processing Systems.
• 18: Yanhong Liu , Samarjit Chakraborty , Wei Tsang Ooi, Approximate VCCs: a new characterization of multimedia workloads for system-level MpSoC design, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065645]
• 19: Sharad Malik , Margaret Martonosi , Yau-Tsun Steven Li, Static timing analysis of embedded software, Proceedings of the 34th annual conference on Design automation, p.147-152, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266052]
• 20: R. Marculescu , A. Nandi, Probabilistic application modeling for system-level perfromance analysis, Proceedings of the conference on Design, automation and test in Europe, p.572-579, March 2001, Munich, Germany
• 21: Radu Marculescu , Amit Nandi , Luciano Lavagno , Alberto Sangiovanni-Vincentelli, System-level power/performance analysis of portable multimedia systems communicating over wireless channels, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 22: Anmol Mathur , Ali Dasdan , Rajesh K. Gupta, Rate analysis for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.3, p.408-436, July 1998 [doi>10.1145/293625.293631]
• 23: Alexander Maxiaguine , Simon Künzli , Samarjit Chakraborty , Lothar Thiele, Rate analysis for streaming applications with on-chip buffer constraints, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.131-136, January 27-30, 2004, Yokohama, Japan
• 24: Metropolis. 2006. http://www.gigascale.org/metropolis/.
• 25: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 26: Sorin Manolache , Petru Eles , Zebo Peng, Schedulability analysis of applications with stochastic task execution times, ACM Transactions on Embedded Computing Systems (TECS), v.3 n.4, p.706-735, November 2004 [doi>10.1145/1027794.1027797]
• 27: Sorin Manolache , Petru Eles , Zebo Peng, Schedulability analysis of multiprocessor real-time applications with stochastic task execution times, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.699-706, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774675]
• 28: Amit Nandi , Radu Marculescu, System-level power/performance analysis for embedded systems design, Proceedings of the 38th conference on Design automation, p.599-604, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379032]
• 29: Chang Yun Park, Predicting deterministic execution times of real-time programs, University of Washington, Seattle, WA, 1992
• 30: Kihong Park , Walter Willinger, Self-Similar Network Traffic and Performance Evaluation, John Wiley & Sons, Inc., New York, NY, 2000
• 31: James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 32: Brigitte Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, Proceedings of the 1985 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.147-154, August 1985, Austin, Texas, United States
• 33: Brigitte Plateau , Jean-Michel Fourneau, A methodology for solving Markov models of parallel systems, Journal of Parallel and Distributed Computing, v.12 n.4, p.370-387, Aug. 1991 [doi>10.1016/0743-7315(91)90007-V]
• 34: P. Puschner , Ch. Koza, Calculating the maximum, execution time of real-time programs, Real-Time Systems, v.1 n.2, p.159-176, Sep. 1989 [doi>10.1007/BF00571421]
• 35: Kai Richter , Marek Jersak , Rolf Ernst, A Formal Approach to MpSoC Performance Verification, Computer, v.36 n.4, p.60-67, April 2003 [doi>10.1109/MC.2003.1193230 ]
• 36: Sangiovanni-Vincentelli, A. 2002. Defining platform-based design. EE. Design, http://www.eedesign.com/.
• 37: Youngsoo Shin , Daehong Kim , Kiyoung Choi, Schedulability-driven performance analysis of multiple mode embedded real-time systems, Proceedings of the 37th conference on Design automation, p.495-500, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337556]
• 38: Simplescalar. 2006. http://www.cs.wisc.edu/~mscalar/simplescalar.html.
• 39: Tajana Šimunić , Luca Benini , Giovanni De Micheli, Cycle-accurate simulation of energy consumption in embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.867-872, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310090]
• 40: Stewart, W. J. 1994. An Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton, NJ.
• 41: Kei Suzuki , Alberto Sangiovanni-Vincentelli, Efficient software performance estimation methods for hardware/software codesign, Proceedings of the 33rd annual conference on Design automation, p.605-610, June 03-07, 1996, Las Vegas, Nevada, United States [doi>10.1145/240518.240633]
• 42: Filip Thoen , Francky Catthoor, Modeling, Verification, and Exploration of Task-Level Concurrency of Real-Time Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 2000
• 43: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 44: Girish V. Varatkar , Radu Marculescu, On-chip traffic modeling and synthesis for MPEG-2 video applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.1, p.108-119, January 2004 [doi>10.1109/TVLSI.2003.820523]
• 45: Wolf, W. 1994. Hardware-software co-design of embedded systems. Proceedings of IEEE 82, 7, 967--989.
• 46: 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
• 47: Tao Zhou , Xiaobo (Sharon) Hu , Edwin H.-M. Sha, A probabilistic performance metric for real-time system design, Proceedings of the seventh international workshop on Hardware/software codesign, p.90-94, March 1999, Rome, Italy [doi>10.1145/301177.301494]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**

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

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes; Stochastic processes

General Terms:
Design, Performance, Theory

Keywords:
Markov chains, average-case analysis, design space exploration, hardware/software codesign, performance models, platform-based design, stochastic automata networks (SANs)