Analysis of input-dependent program behavior using active profiling

ABSTRACT

Utility programs, which perform similar and largely independent operations on a sequence of inputs, include such common applications as compilers, interpreters, and document parsers; databases; and compression and encoding tools. The repetitive behavior of these programs, while often clear to users, has been difficult to capture automatically. We present an active profiling technique in which controlled inputs to utility programs are used to expose execution phases, which are then marked, automatically, through binary instrumentation, enabling us to exploit phase transitions in production runs with arbitrary inputs. We demonstrate the effectiveness and programmability of active profiling via experiments with six utility programs from the SPEC benchmark suite; compare to code and interval phases; and describe applications of active profiling to memory management and memory leak detection.

REFERENCES

• 1: Dong H. Ahn , Jeffrey S. Vetter, Scalable analysis techniques for microprocessor performance counter metrics, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-16, November 16, 2002, Baltimore, Maryland
• 2: F. E. Allen , J. Cocke, A program data flow analysis procedure, Communications of the ACM, v.19 n.3, p.137, March 1976 [doi>10.1145/360018.360025]
• 3: Rajeev Balasubramonian , David Albonesi , Alper Buyuktosunoglu , Sandhya Dwarkadas, Memory hierarchy reconfiguration for energy and performance in general-purpose processor architectures, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.245-257, December 2000, Monterey, California, United States [doi>10.1145/360128.360153]
• 4: Rajeev Balasubramonian , Sandhya Dwarkadas , David H. Albonesi, Dynamically managing the communication-parallelism trade-off in future clustered processors, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 5: Vasanth Balasundaram , Geoffrey Fox , Ken Kennedy , Ulrich Kremer, A static performance estimator to guide data partitioning decisions, Proceedings of the third ACM SIGPLAN symposium on Principles and practice of parallel programming, p.213-223, April 21-24, 1991, Williamsburg, Virginia, United States
• 6: A. P. Batson , A. W. Madison, Measurements of major locality phases in symbolic reference strings, Proceedings of the 1976 ACM SIGMETRICS conference on Computer performance modeling measurement and evaluation, p.75-84, March 29-31, 1976, Cambridge, Massachusetts, United States [doi>10.1145/800200.806184]
• 7: Michael D. Bond , Kathryn S. McKinley, Bell: bit-encoding online memory leak detection, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 8: Richard B. Bunt , Jennifer M. Murphy , Shikharesh Majumdar, A measure of program locality and its application, Proceedings of the 1984 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.28-40, January 1984
• 9: D. Buytaert, K. Venstermans, L. Eeckhout, and K. D. Bosschere. Garbage collection hints. In Proceedings of The HiPEAC International Conference on High Performance Embedded Architectures and Compilation, November 2005.
• 10: Matthias Hauswirth , Trishul M. Chilimbi, Low-overhead memory leak detection using adaptive statistical profiling, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 11: Mark E. Crovella , Thomas J. LeBlanc, Parallel performance using lost cycles analysis, Proceedings of the 1994 conference on Supercomputing, p.600-609, December 1994, Washington, D.C., United States
• 12: Mark E. Crovella , Thomas J. LeBlanc, The Search for Lost Cycles: A New Approach to Parallel Program Performance Evaluation, University of Rochester, Rochester, NY, 1993
• 13: F. Darema-Rogers , G. F. Pfister , K. So, Memory access patterns of parallel scientific programs, Proceedings of the 1987 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.46-58, May 11-14, 1987, Banff, Alberta, Canada
• 14: Ashutosh S. Dhodapkar , James E. Smith, Managing multi-configuration hardware via dynamic working set analysis, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 15: Chen Ding , Chengliang Zhang , Xipeng Shen , Mitsunori Ogihara, Gated memory control for memory monitoring, leak detection and garbage collection, Proceedings of the 2005 workshop on Memory system performance, June 12-12, 2005, Chicago, Illinois [doi>10.1145/1111583.1111593]
• 16: Evelyn Duesterwald , Calin Cascaval , Sandhya Dwarkadas, Characterizing and Predicting Program Behavior and its Variability, Proceedings of the 12th International Conference on Parallel Architectures and Compilation Techniques, p.220, September 27-October 01, 2003
• 17: Andy Georges , Dries Buytaert , Lieven Eeckhout , Koen De Bosschere, Method-level phase behavior in java workloads, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 18: John L. Henning, SPEC CPU2000: Measuring CPU Performance in the New Millennium, Computer, v.33 n.7, p.28-35, July 2000 [doi>10.1109/2.869367]
• 19: Chung-Hsing Hsu , Ulrich Kremer, The design, implementation, and evaluation of a compiler algorithm for CPU energy reduction, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 20: 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
• 21: E. Ipek, B. R. de Supinski, M. Schulz, and S. A. McKee. An approach to performance prediction for parallel applications. In Proceedings of the Euro-Par Conference, pages 196--205, 2005.
• 22: Adeline Jacquet , Vincent Janot , Clement Leung , Guang R. Gao , R. Govindarajan , Thomas L. Sterling, An Executable Analytical Performance Evaluation Approach for Early Performance Prediction, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.268.1, April 22-26, 2003
• 23: Jeremy Lau , Erez Perelman , Brad Calder, Selecting Software Phase Markers with Code Structure Analysis, Proceedings of the International Symposium on Code Generation and Optimization, p.135-146, March 26-29, 2006 [doi>10.1109/CGO.2006.32]
• 24: Wei Liu , Michael C. Huang, EXPERT: expedited simulation exploiting program behavior repetition, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006228]
• 25: Grigorios Magklis , Michael L. Scott , Greg Semeraro , David H. Albonesi , Steven Dropsho, Profile-based dynamic voltage and frequency scaling for a multiple clock domain microprocessor, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 26: Priya Nagpurkar , Chandra Krintz , Michael Hind , Peter F. Sweeney , V. T. Rajan, Online Phase Detection Algorithms, Proceedings of the International Symposium on Code Generation and Optimization, p.111-123, March 26-29, 2006 [doi>10.1109/CGO.2006.26]
• 27: G. Rodríguez, R. M. Badia, and J. Labarta. Generation of simple analytical models for message passing applications. In Proceedings of the Euro-Par Conference, pages 183--188, 2004.
• 28: Xipeng Shen , Yutao Zhong , Chen Ding, Locality phase prediction, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 29: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 30: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

General Terms:
Algorithms, Measurement, Performance

Keywords:
active profiling, dynamic optimization, memory management, program phase analysis and prediction