Automated energy/performance macromodeling of embedded software

ABSTRACT

Efficient energy and performance estimation of embedded software is a critical part of any system-level design flow. Macromodeling based estimation is an attempt to speed up estimation by exploiting reuse that is inherent in the design process. Macromodeling involves pre-characterizing reusable software components to construct high-level models, which express the execution time or energy consumption of a sub-program as a function of suitable parameters. During simulation, macromodels can be used instead of detailed hardware models, resulting in orders of magnitude simulation speedup. However, in order to realize this potential, significant challenges need to be overcome in both the generation and use of macromodels--- including how to identify the parameters to be used in the macromodel, how to define the template function to which the macromodel is fitted, em etc. This paper presents an automatic methodology to perform characterization-based high-level software macromodeling, which addresses the aforementioned issues. Given a sub-program to be macromodeled for execution time and/or energy consumption, the proposed methodology automates the steps of parameter identification, data collection through detailed simulation, macromodel template selection, and fitting. We propose a novel technique to identify potential macromodel parameters and perform data collection, which draws from the concept of bf data structure serialization used in distributed programming. We utilize bf symbolic regression techniques to concurrently filter out irrelevant macromodel parameters, construct a macromodel function, and derive the optimal coefficient values to minimize fitting error. Experiments with several realistic benchmarks suggest that the proposed methodology improves estimation accuracy and enables wide applicability of macromodeling to complex embedded software, while realizing its potential for estimation speedup. We describe a case study of how macromodeling can be used to rapidly explore algorithm-level energy tradeoffs, for the tt zlib data compression library.

REFERENCES

• 1: Massoud Pedram , Jan M. Rabaey, Power Aware Design Methodologies, Kluwer Academic Publishers, Norwell, MA, 2002
• 2: Anand Raghunathan , Niraj K. Jha , Sujit Dey, High-Level Power Analysis and Optimization, Kluwer Academic Publishers, Norwell, MA, 1998
• 3: V. Zivojnvic, S. Tjiang, and H. Meyr, "Compiled simulation of programmable DSP architectures," in Proc. IEEE Wkshp. VLSI Signal Processing, May 1995, pp. 73--80.
• 4: Achim Nohl , Gunnar Braun , Oliver Schliebusch , Rainer Leupers , Heinrich Meyr , Andreas Hoffmann, A universal technique for fast and flexible instruction-set architecture simulation, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.513927]
• 5: Mehrdad Reshadi , Nikhil Bansal , Prabhat Mishra , Nikil Dutt, An efficient retargetable framework for instruction-set simulation, 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.944649]
• 6: Venkata Syam P. Rapaka , Diana Marculescu, Pre-Characterization Free, Efficient Power/Performance Analysis of Embedded and General Purpose Software Applications, Proceedings of the conference on Design, Automation and Test in Europe, p.10504, March 03-07, 2003
• 7: Jie Liu , Marcello Lajolo , Alberto Sangiovanni-Vincentelli, Software timing analysis using HW/SW cosimulation and instruction set simulator, Proceedings of the 6th international workshop on Hardware/software codesign, p.65-69, March 15-18, 1998, Seattle, Washington, United States
• 8: Marcello Lajolo , Anand Raghunathan , Sujit Dey, Efficient power co-estimation techniques for system-on-chip design, Proceedings of the conference on Design, automation and test in Europe, p.27-34, March 27-30, 2000, Paris, France [doi>10.1145/343647.343691]
• 9: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 10: W. Ye , N. Vijaykrishnan , M. Kandemir , M. J. Irwin, The design and use of simplepower: a cycle-accurate energy estimation tool, Proceedings of the 37th conference on Design automation, p.340-345, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337436]
• 11: Gang Qu , Naoyuki Kawabe , Kimiyoshi Usami , Miodrag Potkonjak, Function-level power estimation methodology for microprocessors, Proceedings of the 37th conference on Design automation, p.810-813, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337786]
• 12: T. K. Tan, A. Raghunathan, G. Lakshminarayana, and N. K. Jha, "High-level energy macro-modeling of embedded software," IEEE Trans. Computer-Aided Design, vol. 21, pp. 1037--1050, Sept. 2002.
• 13: C. Brandolese , W. Fornaciari , F. Salice , D. Sciuto, Library Functions Timing Characterization for Source-Level Analysis, Proceedings of the conference on Design, Automation and Test in Europe, p.11132, March 03-07, 2003
• 14: Amit Sinha , Anantha P. Chandrakasan, JouleTrack: a web based tool for software energy profiling, Proceedings of the 38th conference on Design automation, p.220-225, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378467]
• 15: T. K. Tan, A. Raghunathan, and N. K. Jha, "A simulation framework for energy-consumption analysis of OS-driven embedded applications," IEEE Trans. Computer-Aided Design, vol. 22, pp. 1284--1294, Sept. 2003.
• 16: John Bloomer, Power programming with RPC, O'Reilly & Associates, Inc., Sebastopol, CA, 1992
• 17: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 18: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 19: G. R. Raidl, "A hybrid GP approach for numerically robust symbolic regression," in Proc. Annual Conf. Genetic Programming, July 1998, pp. 323--328.
• 20: P. Long, "Metre v2.3." {Online}. Available: urlhttp://www.lysator.liu.se/c/metre-v2-3.htmlBIBentrySTDinterwordspacing
• 21: A. Fraser and T. Weinbrenner, "The Genetic Programming Kernel." {Online}. Available: http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/weinbenner/gp.html
• 22: C. Bauer, A. Frink, and R. Freckel, "GiNaC is not a CAS," http://www.ginac.de.
• 23: The GNU Free Software Foundation, "The GNU Scientific Library," http://www.gnu.org/software/gsl/.
• 24: K. Clarkson, "2dch.c." {Online}. Available: http://www.math.niu.edu/ rusin/known-math/96/convhul
• 25: B. Chapman and W. Naylor, "wnlib." {Online}. Available: urlhttp://www.willnaylor.com/wnlib.html
• 26: R. Anderson, "Bipm." {Online}. Available: urlhttp://www.cs.sunysb.edu/ algorith/implement/bipm/distrib/
• 27: W. Qin, "The SimIt-ARM simulator." {Online}. Available: urlhttp://www.ee.princeton.edu/~wqin/armsim.htm
• 28: J. Flinn, K. I. Farkas, and J. Anderson, "Power and energy characterization of the ITSY pocket computer (version 1.5)," Compaq Western Research Laboratory, Tech. Rep., Feb. 2000.
• 29: J-L Gailly and M. Adler, "zlib-1.1.14." {Online}. Available: urlhttp://www.gzip.org/zlib/

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

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

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures

General Terms:
Design, Measurement

Keywords:
data serialization, embedded software, genetic programming, macromodeling, regression, symbolic