System-scenario-based design of dynamic embedded systems

ABSTRACT

In the past decade, real-time embedded systems have become much more complex due to the introduction of a lot of new functionality in one application, and due to running multiple applications concurrently. This increases the dynamic nature of today's applications and systems, and tightens the requirements for their constraints in terms of deadlines and energy consumption. State-of-the-art design methodologies try to cope with these novel issues by identifying several most used cases and dealing with them separately, reducing the newly introduced complexity. This article presents a generic and systematic design-time/run-time methodology for handling the dynamic nature of modern embedded systems, which can be utilized by existing design methodologies to increase their efficiency. It is based on the concept of system scenarios, which group system behaviors that are similar from a multidimensional cost perspective—such as resource requirements, delay, and energy consumption—in such a way that the system can be configured to exploit this cost similarity. At design-time, these scenarios are individually optimized. Mechanisms for predicting the current scenario at run-time, and for switching between scenarios, are also derived. This design trajectory is augmented with a run-time calibration mechanism, which allows the system to learn on-the-fly during its execution, and to adapt itself to the current input stimuli, by extending the scenario set, changing the scenario definitions, and both the prediction and switching mechanisms. To show the generality of our methodology, we show how it has been applied on four very different real-life design problems. In all presented case studies, substantial energy reductions were obtained by exploiting scenarios.

REFERENCES

• 1: Arenaz, M., Touriño, J., and Doallo, R. 2004. An inspector-executor algorithm for irregular assignment parallelization. In Proceedings of the 2nd International Symposium on Parallel and Distributed Processing and Applications (ISPA). Hong Kong, China, 4--15.
• 2: Bruno Bougard , Sofie Pollin , Antoine Dejonghe , Francky Catthoor , Wim Dehaene, Cross-layer power management in wireless networks and consequences on system-level architecture, Signal Processing, v.86 n.8, p.1792-1803, August 2006 [doi>10.1016/j.sigpro.2005.09.035]
• 3: Burd, T., Pering, T., Stratakos, A., and Brodersen, R. 2000. A dynamic voltage scaled microprocessor system. IEEE J. Solid-State Circ. 35, 11, 1571--1580.
• 4: Calzarossa, M. and Serazzi, G. 1993. Workload characterization: a survey. Proc. IEEE 81, 8, 1136--1150.
• 5: John M. Carroll, Scenario-based design: envisioning work and technology in system development, John Wiley & Sons, Inc., New York, NY, 1995
• 6: Catthoor, F., Ed. 2000. Unified Low-Power Design Flow for Data-Dominated Multi-Media and Telecom Applications. Kluwer Academic Publishers, Boston, MA.
• 7: Kihwan Choi , Karthik Dantu , Wei-Chung Cheng , Massoud Pedram, Frame-based dynamic voltage and frequency scaling for a MPEG decoder, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.732-737, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774680]
• 8: Eui-Young Chung , Giovanni De Micheli , Luca Benini, Contents provider-assisted dynamic voltage scaling for low energy multimedia applications, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566420]
• 9: E. G. Daylight , S. Wuytack , C. Ykman-Couvreur , F. Catthoor, Analyzing energy friendly steady state phases of dynamic application execution in terms of sparse data structures, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566430]
• 10: Bjorn De Sutter , Bruno De Bus , Koen De Bosschere, Link-time binary rewriting techniques for program compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.27 n.5, p.882-945, September 2005 [doi>10.1145/1086642.1086645]
• 11: Saumya K. Debray , William Evans , Robert Muth , Bjorn De Sutter, Compiler techniques for code compaction, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.2, p.378-415, March 2000 [doi>10.1145/349214.349233]
• 12: Bruce Powel Douglass, Real Time UML: Advances in the UML for Real-Time Systems (3rd Edition), Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 2004
• 13: Dumont, G. A. and Huzmezan, M. 2002. Concepts, methods and techniques in adaptive control. In Proceedings of the American Control Conference (ACC). Vol. 2. IEEE, 1137--1150.
• 14: D. Ferrari, Workload charaterization and Selection in Computer Performance Measurement, Computer, v.5 n.4, p.18-24, July 1972 [doi>10.1109/C-M.1972.216939]
• 15: Martin Fowler, UML Distilled: A Brief Guide to the Standard Object Modeling Language, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2003
• 16: Marc Geilen , Twan Basten , Bart Theelen , Ralph Otten, An Algebra of Pareto Points, Fundamenta Informaticae, v.78 n.1, p.35-74, September 2007
• 17: Stefan Valentin Gheorghita , Twan Basten , Henk Corporaal, Intra-task scenario-aware voltage scheduling, Proceedings of the 2005 international conference on Compilers, architectures and synthesis for embedded systems, September 24-27, 2005, San Francisco, California, USA [doi>10.1145/1086297.1086321]
• 18: Gheorghita, S. V., Basten, T., and Corporaal, H. 2006. Application scenarios in streaming-oriented embedded system design. In Proceedings of the International Symposium on System-on-Chip (SoC). IEEE Press, Piscataway, NJ, 175--178. Revised version to appear as {Gheorghita et al. 2008a}.
• 19: Stefan Valentin Gheorghita , Twan Basten , Henk Corporaal, Application Scenarios in Streaming-Oriented Embedded-System Design, IEEE Design & Test, v.25 n.6, p.581-589, November 2008 [doi>10.1109/MDT.2008.158]
• 20: S. V. Gheorghita , T. Basten , H. Corporaal, Scenario selection and prediction for DVS-aware scheduling of multimedia applications, Journal of Signal Processing Systems, v.50 n.2, p.137-161, February 2008 [doi>10.1007/s11265-007-0086-1]
• 21: Stefan Valentin Gheorghita , Sander Stuijk , Twan Basten , Henk Corporaal, Automatic scenario detection for improved WCET estimation, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, Anaheim, California, USA [doi>10.1145/1065579.1065610]
• 22: Kees Goossens , John Dielissen , Jef van Meerbergen , Peter Poplavko , Andrei Rădulescu , Edwin Rijpkema , Erwin Waterlander , Paul Wielage, Guaranteeing the quality of services in networks on chip, Networks on chip, Kluwer Academic Publishers, Hingham, MA, 2003
• 23: Juan Hamers , Lieven Eeckhout, Resource prediction for media stream decoding, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 24: Hamers, J. and Eeckhout, L. 2008. Exploiting media stream similarity for energy-efficient decoding and resource prediction. ACM Transactions on Embedded Computing Systems. To appear.
• 25: Hamers, J., Eeckhout, L., and De Bosschere, K. 2007. Exploiting video stream similarity for energy-efficient decoding. In Proceedings of the 13th International Multimedia Modeling Conference, (MMM). Lecture Notes in Computer Science, vol. 4352. Springer, Berlin, Germany, 11--22. Extended version to appear as {Hamers and Eeckhout 2008}.
• 26: Andreas Hansson , Martijn Coenen , Kees Goossens, Undisrupted quality-of-service during reconfiguration of multiple applications in networks on chip, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 27: Michael C. Huang , Jose Renau , Josep Torrellas, Positional adaptation of processors: application to energy reduction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 28: Christopher J. Hughes , Jayanth Srinivasan , Sarita V. Adve, Saving energy with architectural and frequency adaptations for multimedia applications, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 29: IEEE. 2000. IEEE standard 1471: Recommended practice for architectural description of software-intensive systems.
• 30: Intel Corporation. 2003. Intel XScale microarchitecture for the PXA255 processor: Useris manual. Order No. 278796.
• 31: Ionita, M. T. 2005. Scenario-based system architecting: a systematic approach to developing future-proof system architectures. Ph.D. thesis, Technische Universiteit Eindhoven, The Netherlands.
• 32: Niraj K. Jha, Low power system scheduling and synthesis, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 33: David Kotz , Kobby Essien, Analysis of a campus-wide wireless network, Wireless Networks, v.11 n.1-2, p.115-133, January 2005 [doi>10.1007/s11276-004-4750-0]
• 34: Lee, R. 1991. An introduction to workload characterization. http://support.novell.com/techcenter/articles/ana19910503.html.
• 35: Sunghyun Lee , Kiyoung Choi , Sungjoo Yoo, An intra-task dynamic voltage scaling method for SoC design with hierarchical FSM and synchronous dataflow model, Proceedings of the 2002 international symposium on Low power electronics and design, August 12-14, 2002, Monterey, California, USA [doi>10.1145/566408.566432]
• 36: Stylianos Mamagkakis , Dimitrios Soudris , Francky Catthoor, Middleware design optimization of wireless protocols based on the exploitation of dynamic input patterns, Proceedings of the conference on Design, automation and test in Europe, April 16-20, 2007, Nice, France
• 37: Pierre Marchal , Chun Wong , Aggeliki Prayati , Nathalie Cossement , Francky Catthoor , Rudy Lauwereins , Diederik Verkest , Hugo De Man, Dynamic Memory Oriented Transformations in the MPEG4 IM1-Player on a Low Power Platform, Proceedings of the First International Workshop on Power-Aware Computer Systems-Revised Papers, p.40-50, November 12, 2000
• 38: Srinivasan Murali , Martijn Coenen , Andrei Radulescu , Kees Goossens , Giovanni De Micheli, Mapping and configuration methods for multi-use-case networks on chips, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan [doi>10.1145/1118299.1118344]
• 39: Srinivasan Murali , Martijn Coenen , Andrei Radulescu , Kees Goossens , Giovanni De Micheli, A methodology for mapping multiple use-cases onto networks on chips, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 40: Okabe, T., Jin, Y., and Sendhoff, B. 2003. A critical survey of performance indices for multi-objective optimisation. In Proceedings of the Congress on Evolutionary Computation. Vol. 2. IEEE Press, 878--885.
• 41: Palkovic, M., Brockmeyer, E., Vanbroekhoven, P., Corporaal, H., and Catthoor, F. 2006. Systematic preprocessing of data dependent constructs for embedded systems. J. Low Power Elect. 2, 1, 9--17.
• 42: Martin Palkovic , Henk Corporaal , Francky Catthoor, Global memory optimisation for embedded systems allowed by code duplication, Proceedings of the 2005 workshop on Software and compilers for embedded systems, p.72-79, September 29-October 01, 2005, Dallas, Texas [doi>10.1145/1140389.1140397]
• 43: Pareto, V. 1906. Manuale di Economia Politica. Piccola Biblioteca Scientifica, Milan. Translated into English by A.S. Schwier (1971), Manual of Political Economy, MacMillan, London.
• 44: Paul, J. M., Thomas, D. E., and Bobrek, A. 2006. Scenario-oriented design for single-chip heterogeneous multiprocessors. IEEE Trans. VLSI Syst. 14, 8, 868--880.
• 45: Peon-Quiros, M., Bartzas, A., Mamagkakis, S., Catthoor, F., Mendias, J., and Soudris, D. 2007. Direct memory access optimization in wireless terminals for reduced memory latency and energy consumption. In Proceedings of the 17th International Workshop in Power and Timing Modeling, Optimization and Simulation (PATMOS). Springer, 373--383.
• 46: Pollin, S., Mangharam, R., Bougard, B., Van der Perre, L., Moerman, I., Rajkumar, R., and Catthoor, F. 2007. MEERA: Cross-layer methodology for energy efficient resource allocation in wireless networks. IEEE Trans. Wirel. Comm. 6, 2, 617--628.
• 47: Peter Poplavko , Twan Basten , Jef van Meerbergen, Execution-time Prediction for Dynamic Streaming Applications with Task-level Parallelism, Proceedings of the 10th Euromicro Conference on Digital System Design Architectures, Methods and Tools, p.228-235, August 29-31, 2007 [doi>10.1109/DSD.2007.52]
• 48: Balaji Raman , Samarjit Chakraborty, Application-specific workload shaping in multimedia-enabled personal mobile devices, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176259]
• 49: Sachs, D. G., Adve, S. V., and Jones, D. L. 2003. Cross-layer adaptive video coding to reduce energy on general-purpose processors. In Proceedings of the IEEE International Conference on Image Processing. IEEE Press, 109--112.
• 50: Joel H. Salz , Ravi Mirchandaney , Kay Crowley, Run-Time Parallelization and Scheduling of Loops, IEEE Transactions on Computers, v.40 n.5, p.603-612, May 1991 [doi>10.1109/12.88484]
• 51: C. Sanz , M. Prieto , A. Papanikolaou , M. Miranda , F. Catthoor, System-level process variability compensation on memory organizations of dynamic applications: a case study, Proceedings of the 7th International Symposium on Quality Electronic Design, p.376-382, March 27-29, 2006 [doi>10.1109/ISQED.2006.129]
• 52: Ruchira Sasanka , Christopher J. Hughes , Sarita V. Adve, Joint local and global hardware adaptations for energy, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 53: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 54: Dongkun Shin , Jihong Kim, Optimizing intra-task voltage scheduling using data flow analysis, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120998]
• 55: Tack, K., Lafruit, G., Catthoor, F., and Lauwereins, R. 2006. Platform independent optimisation of multi-resolution 3D content to enable universal media access. Visual Computer 22, 8, 577--590.
• 56: Marijn Temmerman , Edgar G. Daylight , Francky Catthoor , Serge Demeyer , Tom Dhaene, Optimizing data structures at the modeling level in embedded multimedia, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.8, p.539-549, August, 2007 [doi>10.1016/j.sysarc.2006.11.008]
• 57: Theelen, B. D., Geilen, M. C. W., Basten, T., Voeten, J. P. M., Gheorghita, S. V., and Stuijk, S. 2006. A scenario-aware data flow model for combined long-run average and worst-case performance analysis. In Proceedings of the 4th ACM-IEEE International Conference on Formal Methods and Models for Codesign (MEMOCODE). IEEE Computer Society Press, 185--194.
• 58: Paul van der Mark , Lex Wolters , Gerard Cats, Using semi-lagrangian formulations with automatic code generation for environmental modeling, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus [doi>10.1145/967900.967950]
• 59: Vandeputte, F., Eeckhout, L., and De Bosschere, K. 2005a. A detailed study on phase predictors. In Proceedings of the 11th International Euro-Par Conference, J. Cunha and P. Medeiros, Eds. LNCS, vol. 3648. Springer, 571--581.
• 60: Frederik Vandeputte , Lieven Eeckhout , Koen De Bosschere, Exploiting program phase behavior for energy reduction on multi-configuration processors, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.8, p.489-500, August, 2007 [doi>10.1016/j.sysarc.2006.11.004]
• 61: Andreas Vogel , Brigitte Kerhervé , Gregor von Bochmann , Jan Gecsei, Distributed Multimedia and QOS: A Survey, IEEE MultiMedia, v.2 n.2, p.10-19, June 1995 [doi>10.1109/93.388195]
• 62: Ernesto Wandeler , Lothar Thiele, Characterizing Workload Correlations in Multi Processor Hard Real-Time Systems, Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, p.46-55, March 07-10, 2005 [doi>10.1109/RTAS.2005.13]
• 63: Wegener, I. 2000. Integer-Valued DDs. In Branching Programs and Binary Decision Diagrams: Theory and Applications. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics, Philadelphia, PA, Chapter 9.
• 64: Yang, P. 2004. Pareto-optimization based run-time task scheduling for embedded systems. Ph.D. thesis, Catholic University of Leuven, Belgium.
• 65: Peng Yang , Francky Catthoor, Pareto-optimization-based run-time task scheduling for embedded systems, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944680]
• 66: Peng Yang , Paul Marchal , Chun Wong , Stefaan Himpe , Francky Catthoor , Patrick David , Johan Vounckx , Rudy Lauwereins, Managing dynamic concurrent tasks in embedded real-time multimedia systems, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581226]
• 67: Peng Yang , Chun Wong , Paul Marchal , Francky Catthoor , Dirk Desmet , Diederik Verkest , Rudy Lauwereins, Energy-Aware Runtime Scheduling for Embedded-Multiprocessor SOCs, IEEE Design & Test, v.18 n.5, p.46-58, September 2001 [doi>10.1109/54.953271]
• 68: Ykman-Couvreur, C., Brockmeyer, E., Nollet, V., Marescaux, T., Catthoor, F., and Corporaal, H. 2005. Design-Time application exploration for MP-SoC customized run-time management. In Proceedings of the International Symposium on System-on-Chip (SoC). IEEE Press, 66--69.
• 69: Ykman-Couvreur, C., Nollet, V., Catthoor, F., and Corporaal, H. 2006. Fast multi-dimension multi-choice knapsack heuristic for MP-SoC run-time management. In Proceedings of the International Symposium on System-on-Chip (SoC). IEEE Press, 1--4.
• 70: Yokota, D., Chiba, S., and Itano, K. 2002. A new optimization technique for the inspector-executor method. In Proceedings of the International Conference on Parallel and Distributed Computing Systems (PDCS). Acta Press, 706--711.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques

General Terms:
Algorithms, Design, Performance

Keywords:
Design methodology, dynamic nature, embedded systems, energy reduction, real-time systems, system scenarios