Frequent loop detection using efficient non-intrusive on-chip hardware

ABSTRACT

Dynamic software optimization methods are becoming increasingly popular for improving software performance and power. The first step in dynamic optimization consists of detecting frequently executed code, or "critical regions." Previous critical region detectors have been targeted to desktop processors. We introduce a critical region detector targeted to embedded processors, with the unique features of being very size and power efficient, and being completely non-intrusive to the software's execution - features needed in timing-sensitive embedded systems. Our detector not only finds the critical regions, but also determines their relative frequencies, a potentially important feature for selecting among alternative dynamic optimization methods. Our detector uses a tiny cache coupled with a small amount of logic. We provide results of extensive explorations across seventeen embedded system benchmarks. We show that highly accurate results can be achieved with only a 0.02% power overhead and acceptable size overhead. Our detector is currently being used as part of a dynamic hardware/software partitioning approach, but is applicable to a wide-variety of situations.

REFERENCES

• 1: Jennifer M. Anderson , Lance M. Berc , Jeffrey Dean , Sanjay Ghemawat , Monika R. Henzinger , Shun-Tak A. Leung , Richard L. Sites , Mark T. Vandevoorde , Carl A. Waldspurger , William E. Weihl, Continuous profiling: where have all the cycles gone?, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.1-14, October 05-08, 1997, Saint Malo, France
• 2: Artisan, http://www.artisan.com.
• 3: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 4: Energy and Performance Improvements in Microprocessor Design Using a Loop Cache, Proceedings of the 1999 IEEE International Conference on Computer Design, p.378, October 10-13, 1999
• 5: Burger, D., Austin, T., Bennet, S. Evaluating future microprocessors: the simplescalar toolset. University of Wisconsin-Madison. Computer Science Department Tech. Report CS-TR-1308, July 2000.
• 6: Brad Calder , Peter Feller , Alan Eustace, Value profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.259-269, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 7: Robert F. Cmelik, SpixTools: Introduction and User's Manual, Sun Microsystems, Inc., Mountain View, CA, 1993
• 8: Jeffrey Dean , James E. Hicks , Carl A. Waldspurger , William E. Weihl , George Chrysos, ProfileMe: hardware support for instruction-level profiling on out-of-order processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.292-302, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 9: Ann Gordon-Ross , Susan Cotterell , Frank Vahid, Exploiting Fixed Programs in Embedded Systems: A Loop Cache Example, IEEE Computer Architecture Letters, v.1 n.1, p.2, January 2006 [doi>10.1109/L-CA.2002.4]
• 10: Subash Chandar G , Mahesh Mehendale , R. Govindarajan, Area and power reduction of embedded DSP systems using instruction compression and re-configurable encoding, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 11: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• 12: IEEE, IEEE 1149.1 Standard Test Access Port and Boundary-Scan Architecture, http://standards .ieee.org, 2001.
• 13: Tohru Ishihara , Hiroto Yasuura, A power reduction technique with object code merging for application specific embedded processors, Proceedings of the conference on Design, automation and test in Europe, p.617-623, March 27-30, 2000, Paris, France [doi>10.1145/343647.343871]
• 14: David A. Patterson , John L. Hennessy, Computer architecture: a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 15: Kiefendorff, K.. Transistor Budgets Go Ballistic. Microprocessor Report, Volume 12, Number 10, August 1998, pp. 34--43.
• 16: Klaiber, A. The technology behind crusoe processors. Transmeta Technical Brief. January 2000.
• 17: 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
• 18: Lea Hwang Lee , Bill Moyer , John Arends, Instruction fetch energy reduction using loop caches for embedded applications with small tight loops, Proceedings of the 1999 international symposium on Low power electronics and design, p.267-269, August 16-17, 1999, San Diego, California, United States [doi>10.1145/313817.313944]
• 19: Roman Lysecky , Frank Vahid, A codesigned on-chip logic minimizer, 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.944677]
• 20: Roman Lysecky , Frank Vahid, On-chip logic minimization, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775918]
• 21: Afzal Malik , Bill Moyer , Dan Cermak, A low power unified cache architecture providing power and performance flexibility (poster session), Proceedings of the 2000 international symposium on Low power electronics and design, p.241-243, July 25-27, 2000, Rapallo, Italy [doi>10.1145/344166.344610]
• 22: Matthew C. Merten , Andrew R. Trick , Christopher N. George , John C. Gyllenhaal , Wen-mei W. Hwu, A hardware-driven profiling scheme for identifying program hot spots to support runtime optimization, Proceedings of the 26th annual international symposium on Computer architecture, p.136-147, May 01-04, 1999, Atlanta, Georgia, United States
• 23: MIPS Technologies, http://www.mips.com/content/Products/Cores/32BitCores/MIPS324KFamily/ProductCatalog/P_MIPS324KFamily/productBrief
• 24: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 25: Ann Chin, Designing the M·CORE^TM M3 CPU Architecture, Proceedings of the 1999 IEEE International Conference on Computer Design, p.94, October 10-13, 1999
• 26: Greg Stitt , Roman Lysecky , Frank Vahid, Dynamic hardware/software partitioning: a first approach, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA [doi>10.1145/775832.775896]
• 27: Dinesh C. Suresh , Walid A. Najjar , Frank Vahid , Jason R. Villarreal , Greg Stitt, Profiling tools for hardware/software partitioning of embedded applications, Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems, June 11-13, 2003, San Diego, California, USA
• 28: Synopsys Inc., http://www.synopsys.com.
• 29: J. Tubella , A. González, Control Speculation in Multithreaded Processors through Dynamic Loop Detection, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.14, January 31-February 04, 1998
• 30: Vtune Environment, Intel Corp., http://developer.intel.com/vtune
• 31: Jun Yang , Rajiv Gupta, Energy efficient frequent value data cache design, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 32: Marco Zagha , Brond Larson , Steve Turner , Marty Itzkowitz, Performance analysis using the MIPS R10000 performance counters, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.16-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States [doi>10.1145/369028.369059]
• 33: Xiaolan Zhang , Zheng Wang , Nicholas Gloy , J. Bradley Chen , Michael D. Smith, System support for automatic profiling and optimization, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.15-26, October 05-08, 1997, Saint Malo, France

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Design

Keywords:
dynamic optimization, frequent loop detection, frequent value profiling, hardware profiling, hot spot detection, on-chip profiling, runtime profiling