Formulating and implementing profiling over adaptive ranges

ABSTRACT

Modern computer systems are called on to deal with billions of events every second, whether they are executed instructions, accessed memory locations, or forwarded packets. This presents a serious challenge to those who seek to quantify, analyze, or optimize such systems, because important trends and behaviors may easily be lost in a sea of data. We present range-adaptive profiling (RAP) as a new and general-purpose profiling method capable of hierarchically efficiently classifying streams of data in hardware. Through the use of RAP, events in an input stream are dynamically classified into increasingly precise categories, based on the frequency with which they occur. The more important a class, or range of events, the more precisely it is quantified. Despite the dynamic nature of our technique, we build upon tight theoretic bounds covering both worst-case error, as well as the required memory. In the limit, it is known that error and the memory bounds can be independent of the stream size and grow only linearly with the level of precision desired. Significantly, we expose the critical constants in these algorithms and through careful engineering, algorithm redesign, and use of heuristics, we show how a high-performance profile system can be implemented for range-adaptive profiling. RAP can be used on various profiles, such as PCs, load values, and memory addresses, and has a broad range of uses, from hot-region profiling to quantifying cache miss value locality. We propose two methods of implementation of RAP, one in software and the other with specialized hardware, for which we also describe our prototype FPGA implementation. We show that with just 8KB of memory, range profiles can be gathered with an average accuracy of 98%.

REFERENCES

• 1: Agrawal, B. and Sherwood, T. 2006. Modeling tcam power for next generation network devices. In Proceedings of IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS), Austin, TX.
• 2: 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?, ACM Transactions on Computer Systems (TOCS), v.15 n.4, p.357-390, Nov. 1997 [doi>10.1145/265924.265925]
• 3: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 4: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 5: David Brooks , Margaret Martonosi, Dynamically Exploiting Narrow Width Operands to Improve Processor Power and Performance, Proceedings of the 5th International Symposium on High Performance Computer Architecture, p.13, January 09-12, 1999
• 6: 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
• 7: Bryan Buck , Jeffrey K. Hollingsworth, An API for Runtime Code Patching, International Journal of High Performance Computing Applications, v.14 n.4, p.317-329, November 2000 [doi>10.1177/109434200001400404]
• 8: Bruno De Bus , Dominique Chanet , Bjorn De Sutter , Ludo Van Put , Koen De Bosschere, The design and implementation of FIT: a flexible instrumentation toolkit, Proceedings of the 5th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA [doi>10.1145/996821.996833]
• 9: 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
• 10: Trishul M. Chilimbi, Efficient representations and abstractions for quantifying and exploiting data reference locality, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.191-202, June 2001, Snowbird, Utah, United States
• 11: Trishul M. Chilimbi , Martin Hirzel, Dynamic hot data stream prefetching for general-purpose programs, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 12: Thomas M. Conte , Burzin A. Patel , J. Stan Cox, Using branch handling hardware to support profile-driven optimization, Proceedings of the 27th annual international symposium on Microarchitecture, p.12-21, November 30-December 02, 1994, San Jose, California, United States [doi>10.1145/192724.192726]
• 13: Thomas M. Conte , Kishore N. Menezes , Mary Ann Hirsch, Accurate and practical profile-driven compilation using the profile buffer, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.36-45, December 02-04, 1996, Paris, France
• 14: Corporation, D. E. 1995. Alpha 21164 Microprocessor Hardware Reference Manual.
• 15: Corporation, I. 1997. Pentium(r) Pro Processor Developer's Manual. McGraw-Hill, New York.
• 16: 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
• 17: Evelyn Duesterwald , Vasanth Bala, Software profiling for hot path prediction: less is more, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.202-211, November 2000, Cambridge, Massachusetts, United States
• 18: Cristian Estan , Stefan Savage , George Varghese, Automatically inferring patterns of resource consumption in network traffic, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863972]
• 19: fs2. First Silicon Solutions. Home page. http://www.fs2.com.
• 20: Fung, W. W., and Sachdev, M. 2004. High performance priority encoder for content addressable memories. In Micronet R&D Annual Workshop.
• 21: Rajiv Gupta , David A. Berson , Jesse Z. Fang, Path Profile Guided Partial Redundancy Elimination Using Speculation, Proceedings of the 1998 International Conference on Computer Languages, p.230, May 14-16, 1998
• 22: Timothy Heil , James E. Smith, Relational profiling: enabling thread-level parallelism in virtual machines, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 2000, Monterey, California, United States [doi>10.1145/360128.360156]
• 23: Hershberger, J., Shrivastava, N., Suri, S., and Toth, C. 2004. Adaptive spatial partitioning for multidimensional data streams. In International Symposium on Algorithms and Computation (ISAAC).
• 24: Hewlett-Packard. 1994. PA-RISC 1.1 Architecture and Instruction Set Reference Manual.
• 25: Hirzel, M. and Chilimbi, T. 2001. Bursty tracing: A framework for low-overhead temporal profiling. In Proceedings of the 4th ACM Workshop on Feedback-Directed and Dynamic Optimization (FDDO-4).
• 26: Inc, M. T. 1995. Mips R10000 Microprocessor User's Manual.
• 27: Quinn Jacobson , Eric Rotenberg , James E. Smith, Path-based next trace prediction, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.14-23, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 28: A. Krall, Efficient JavaVM Just-in-Time Compilation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.205, October 12-18, 1998
• 29: Christopher Kruegel , Fredrik Valeur , Giovanni Vigna , Richard Kemmerer, Stateful Intrusion Detection for High-Speed Networks, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.285, May 12-15, 2002
• 30: Butler Lampson , Venkatachary Srinivasan , George Varghese, IP lookups using multiway and multicolumn search, IEEE/ACM Transactions on Networking (TON), v.7 n.3, p.324-334, June 1999 [doi>10.1109/90.779199]
• 31: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 32: Li, X., Liu, Z., Li, W., and Liu, B. 2004. SCP-TCAM: A power-efficient search engine for fast IP Lookup. In ISBN Proceedings.
• 33: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 34: Gabriel H. Loh, Exploiting data-width locality to increase superscalar execution bandwidth, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 35: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 36: Shashidhar Mysore , Banit Agrawal , Timothy Sherwood , Nisheeth Shrivastava , Subhash Suri, Profiling over Adaptive Ranges, Proceedings of the International Symposium on Code Generation and Optimization, p.147-158, March 26-29, 2006 [doi>10.1109/CGO.2006.30]
• 37: Satish Narayanasamy , Timothy Sherwood , Suleyman Sair , Brad Calder , George Varghese, Catching Accurate Profiles in Hardware, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.269, February 08-12, 2003
• 38: Pagiamtziz, K. and Sheikholeslami, A. 2004. A low-power content-addressable memory (CAM) using pipelined hierarchical search engine. IEEE J. Solid-State Circuits.
• 39: Pagiamtzis, K. and Sheikholeslami, A. 2006. Content-addressable memory (CAM) circuits and architectures: A tutorial and survey. IEEE J. Solid-State Circuits. 41.
• 40: Peri, R. V., Jinturkar, S., and Fajardo, L. 1999. A novel technique for profiling programs in embedded systems. In ACM Workshop on Feedback-Directed and Dynamic Optimization.
• 41: Shai Rubin , Rastislav Bodík , Trishul Chilimbi, An efficient profile-analysis framework for data-layout optimizations, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.140-153, January 16-18, 2002, Portland, Oregon
• 42: Sanchez, M., Biersack, E., and Dabbous, W. 2001. Survey and taxonomy of IP address lookup algorithms. IEEE Netw. Maga. 15, 2, 8--23.
• 43: S. Subramanya Sastry , Rastislav Bodík , James E. Smith, Rapid profiling via stratified sampling, Proceedings of the 28th annual international symposium on Computer architecture, p.278-289, June 30-July 04, 2001, Göteborg, Sweden
• 44: Shivakumar, P., and Jouppi, N. 2001/2. Cacti 3.0: An Integrated Cache Timing, Power and Area Model.
• 45: Amitabh Srivastava , Alan Eustace, ATOM: a system for building customized program analysis tools, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.196-205, June 20-24, 1994, Orlando, Florida, United States
• 46: V. Srinivasan , G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems (TOCS), v.17 n.1, p.1-40, Feb. 1999 [doi>10.1145/296502.296503]
• 47: V. Srinivasan , G. Varghese, Fast address lookups using controlled prefix expansion, ACM Transactions on Computer Systems (TOCS), v.17 n.1, p.1-40, Feb. 1999 [doi>10.1145/296502.296503]
• 48: Srivastava, A., Edwards, A., and Vo., H. 2001. Vulcan: Binary transformation in a distributed environment. Technical report msr-tr-2001-50. Microsoft Research., Redmond, Washington.
• 49: Hang-Sheng Wang , Xinping Zhu , Li-Shiuan Peh , Sharad Malik, Orion: a power-performance simulator for interconnection networks, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 50: Wang, J. and Huang, C. 2000. High-speed and low-power CMOS priority encoders. IEEE J. Solid-State Circuits 35, 10 (Oct.), 1511--1514.
• 51: Jun Yang , Rajiv Gupta, Frequent value locality and its applications, ACM Transactions on Embedded Computing Systems (TECS), v.1 n.1, p.79-105, November 2002 [doi>10.1145/581888.581894]
• 52: Jun Yang , Youtao Zhang , Rajiv Gupta, Frequent value compression in data caches, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.258-265, December 2000, Monterey, California, United States [doi>10.1145/360128.360154]
• 53: Cliff Young , Michael D. Smith, Better global scheduling using path profiles, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.115-123, November 1998, Dallas, Texas, United States
• 54: Youtao Zhang , Rajiv Gupta, Timestamped whole program path representation and its applications, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.180-190, June 2001, Snowbird, Utah, United States
• 55: Xiangyu Zhang , Rajiv Gupta, Whole Execution Traces, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.105-116, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.37]
• 56: Huiyang Zhou , Jill Flanagan , Thomas M. Conte, Detecting global stride locality in value streams, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 57: Pin Zhou , Feng Qin , Wei Liu , Yuanyuan Zhou , Josep Torrellas, iWatcher: Efficient Architectural Support for Software Debugging, Proceedings of the 31st annual international symposium on Computer architecture, p.224, June 19-23, 2004, München, Germany
• 58: Craig B. Zilles , Gurindar S. Sohi, A Programmable Co-processor for Profiling, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.241, January 20-24, 2001

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
Profiling hardware, range adaptive, value locality