A design framework for real-time embedded systems with code size and energy constraints

ABSTRACT

Real-time embedded systems are typically constrained in terms of three system performance criteria: space, time, and energy. The performance requirements are directly translated into constraints imposed on the system's resources, such as code size, execution time, and energy consumption. These resource constraints often interact or even conflict with each other in a complex manner, making it difficult for a system developer to apply a well-defined design methodology in developing a real-time embedded system. Motivated by this observation, we propose a design framework that can flexibly balance the tradeoff involving the system's code size, execution time, and energy consumption. Given a system specification and an optimization criteria, the proposed technique generates a set of design parameters in such a way that a system cost function is minimized while the given resource constraints are satisfied. Specifically, the technique derives code generation decision for each task so that a specific version of code is selected among a number of different ones that have distinct characteristics in terms of code size and execution time. In addition, the design framework determines the voltage/frequency setting for a variable voltage processor whose supply voltage can be adjusted at runtime in order to minimize the energy consumption while execution performance is degraded accordingly. The proposed technique formulates this design process as a constrained optimization problem. We show that this optimization problem is NP-hard and then provide a heuristic solution to it. We show that these seemingly conflicting design goals can be pursued by using a simple optimization algorithm that works with a single optimization criteria. Moreover, the optimization is driven by an abstract system specification given by the system developer, so that the system development process can be automated. The results from our simulation show that the proposed algorithm finds a solution that is close to the optimal one with the average error smaller than 1.0&percent;.

REFERENCES

• 1: Chandrakasan, A. P., Sheng, S., and Brodersen, R. W. 1992. Low-power digital CMOS design. IEEE Journal of Solid State Circuits 27, 4 (Apr.), 473--484.
• 2: Naehyuck Chang , Kwanho Kim , Hyung Gyu Lee, Cycle-accurate energy measurement and characterization with a case study of the ARM7TDMI, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.10 n.2, p.146-154, April 2002 [doi>10.1109/92.994992]
• 3: Keith D. Cooper , Nathaniel McIntosh, Enhanced code compression for embedded RISC processors, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.139-149, May 01-04, 1999, Atlanta, Georgia, United States
• 4: Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.117-121, June 17-22, 1984, Montreal, Canada
• 5: Steve B. Furber, ARM System Architecture, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: Flavius Gruian, Hard real-time scheduling for low-energy using stochastic data and DVS processors, Proceedings of the 2001 international symposium on Low power electronics and design, p.46-51, August 2001, Huntington Beach, California, United States [doi>10.1145/383082.383092]
• 8: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 9: Tohru Ishihara , Hiroto Yasuura, Voltage scheduling problem for dynamically variable voltage processors, Proceedings of the 1998 international symposium on Low power electronics and design, p.197-202, August 10-12, 1998, Monterey, California, United States [doi>10.1145/280756.280894]
• 10: W. Kim , J. Kim , S. Min, A Dynamic Voltage Scaling Algorithm for Dynamic-Priority Hard Real-Time Systems Using Slack Time Analysis, Proceedings of the conference on Design, automation and test in Europe, p.788, March 04-08, 2002
• 11: Woonseok Kim , Jihong Kim , Sang Lyul Min, Dynamic voltage scaling algorithm for fixed-priority real-time systems using work-demand analysis, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871605]
• 12: Arvind Krishnaswamy , Rajiv Gupta, Profile guided selection of ARM and thumb instructions, Proceedings of the joint conference on Languages, compilers and tools for embedded systems: software and compilers for embedded systems, June 19-21, 2002, Berlin, Germany
• 13: Woo-Cheol Kwon , Taewhan Kim, Optimal voltage allocation techniques for dynamically variable voltage processors, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775867]
• 14: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 15: Lee, S., Lee, J., Min, S. L., Hiser, J., and Davidson, J. W. 2003. Code generation for a dual instruction set processor based on selective code transformation. In Proceedings of the 7th International Workshop on Software and Compilers for Embedded Systems (SCOPES), Vienna, Austria, 33--48.
• 16: Lee, S., Lee, J., Park, C. Y., and Min, S. L. 2004. A flexible tradeoff between code size and WCET using a dual instruction set processor. In Proceedings of the 8th International Workshop on Software and Compilers for Embedded Systems (SCOPES). Amsterdam, The Netherlands. 244--258.
• 17: 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]
• 18: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 19: Padmanabhan Pillai , Kang G. Shin, Real-time dynamic voltage scaling for low-power embedded operating systems, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 20: Gang Quan , Xiaobo Hu, Energy efficient fixed-priority scheduling for real-time systems on variable voltage processors, Proceedings of the 38th conference on Design automation, p.828-833, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379074]
• 21: Cosmin Rusu , Rami Melhem , Daniel Mossé, Maximizing the System Value while Satisfying Time and Energy Constraints, Proceedings of the 23rd IEEE Real-Time Systems Symposium (RTSS'02), p.246, December 03-05, 2002
• 22: Rusu, C., Melhem, R., and Mosse, D. 2003. Multi-version scheduling in rechargeable energy-aware real-time systems. In Proceedings of the 15th Euromicro Conference on Real-Time Systems (ECRTS), Porto, Portugal. 95--104.
• 23: Saowanee Saewong , Ragunathan (Raj) Rajkumar, Practical Voltage-Scaling for Fixed-Priority RT-Systems, Proceedings of the The 9th IEEE Real-Time and Embedded Technology and Applications Symposium, p.106, May 27-30, 2003
• 24: Kiran Seth , Aravindh Anantaraman , Frank Mueller , Eric Rotenberg, FAST: Frequency-Aware Static Timing Analysis, Proceedings of the 24th IEEE International Real-Time Systems Symposium, p.40, December 03-05, 2003
• 25: Shin, I., Lee, I., and Min, S. L. 2004. A design approach for real-time embedded systems with energy and code size constraints. In Proceedings of the 10th Real-time and Embedded Computing Systems and Applications Conference (RTCSA), Gothenburg, Sweden.
• 26: Youngsoo Shin , Kiyoung Choi , Takayasu Sakurai, Power optimization of real-time embedded systems on variable speed processors, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 27: SNU Real-Time Benchmark Suite. http://archi.snu.ac.kr/realtime/benchmark.
• 28: Bjorn De Sutter , Koen De Bosschere, Introduction, Communications of the ACM, v.46 n.8, August 2003 [doi>10.1145/859670.859694]
• 29: F. Yao , A. Demers , S. Shenker, A scheduling model for reduced CPU energy, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.374, October 23-25, 1995
• 30: Tuning the WCET of Embedded Applications, Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium, p.472, May 25-28, 2004

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design
          Subjects: Real-time systems and embedded systems

General Terms:
Algorithms, Design, Performance

Keywords:
Embedded, code size, energy, real-time, scheduling