Optimally profiling and tracing programs

ABSTRACT

This paper presents algorithms for inserting monitoring code to profile and trace programs. These algorithms greatly reduce the cost of measuring programs. Profiling counts the number of times each basic block in a program executes and has a variety of applications. Instruction traces are the basis for trace-driven simulation and analysis, and are also used in trace-driven debugging. The profiling algorithm chooses a placement of counters that is optimized—and frequently optimal—with respect to the expected or measured execution frequency of each basic block and branch in the program. The tracing algorithm instruments a program to obtain a subsequence of the basic block trace—whose length is optimized with respect to the program's execution—from which the entire trace can be efficiently regenerated. Both algorithms have been implemented and produce a substantial improvement over previous approaches. The profiling algorithm reduces the number of counters by a factor of two and the number of counter increments by up to a factor of four. The tracing algorithm reduces the file size and overhead of an already highly optimized tracing system by 20-40%.

REFERENCES

• 1: T. Ball and j. R. Larus, "'Optimally Profiling and Tracing Programs," Technical Report #1031, University of Wisconsin, Madison (July 1991).
• 2: Robert F. Cmelik , Shing I. Kong , David R. Ditzel , Edmund J. Kelly, An analysis of MIPS and SPARC instruction set utilization on the SPEC benchmarks, ACM SIGARCH Computer Architecture News, v.19 n.2, p.290-302, Apr. 1991
• 3: Systems Performance Evaluation Cooperative, SPEC Newsletter (K. Mendoza, editor) 1(1)(1989).
• 4: Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.37-47, June 17-22, 1984, Montreal, Canada
• 5: S.L. Graham, P. B. Kessler, and M. K. McKusick, "An Execution Profiler for Modular Programs," Software Practice and Experience 13 pp. 671-685 (1983).
• 6: Jeff L. Kennington , Richard V. Helgason, Algorithms for Network Programming, John Wiley & Sons, Inc., New York, NY, 1980
• 7: D.E. Knuth and F. R. Stevenson, "Optimal Measurement Points for Program Frequency Counts," BIT 13 pp. 313-322 (1973).
• 8: J. R. Larus, Abstract execution: a technique for efficiently tracing programs, Software—Practice & Experience, v.20 n.12, p.1241-1258, Dec. 1990 [doi>10.1002/spe.4380201205]
• 9: S. Maheshwari, "Traversal marker placement problems are NP-complete," Report No. CU-CS-092-76, Dept. of Computer Science, University of Colorado, Boulder, CO (1976).
• 10: Scott McFarling, Procedure merging with instruction caches, ACM SIGPLAN Notices, v.26 n.6, p.71-79, June 1991
• 11: B. P. Miller , Jong-Deok Choi, A mechanism for efficient debugging of parallel programs, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.135-144, June 20-24, 1988, Atlanta, Georgia, United States
• 12: W. G. Morris, CCG: a prototype coagulating code generator, ACM SIGPLAN Notices, v.26 n.6, p.45-58, June 1991
• 13: Karl Pettis , Robert C. Hansen, Profile guided code positioning, ACM SIGPLAN Notices, v.25 n.6, p.16-27, Jun. 1990
• 14: S. Pottle, private communication. October 1991.
• 15: R. L. Probert, "Optimal Insertion of Software Probes in Well-Delimited Programs," IEEE Transactions on Software Engineering SE-8(1) pp. 34-42 (January, 1975).
• 16: C.V. Ramamoorthy, K. H. Kim, and W. T. Chen, "Optimal Placement of Software Monitors Aiding Systematic Testing," IEEE Transactions on Software Engineering SE-I(4)pp. 403-410 (December, 1975).
• 17: Alan Dain Samples, Profile-driven compilation, University of California at Berkeley, Berkeley, CA, 1992
• 18: V. Sarkar, Determining average program execution times and their variance, ACM SIGPLAN Notices, v.24 n.7, p.298-312, July 1989
• 19: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 20: MIPS Computer Systems, inc., UMIPS-V Reference Manual (pixie and pixstats), MIPS Computer Systems, Sunnyvale, CA (1990).
• 21: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms, Performance