Determining average program execution times and their variance

Abstract

This paper presents a general framework for determining average program execution times and their variance, based on the program's interval structure and control dependence graph. Average execution times and variance values are computed using frequency information from an optimized counter-based execution profile of the program.

References

1. ABC*87 Frances Allen, Michael Burke, Philippe Charles, Ron Cytron, and Jeanne Ferrante. An overview of the ptran analysis system for multiprocessing. Proceedings of the 1987 international Conference on $upercomputing, 1987. Also pub!ished in The Journal of Parallel and Distributed Computing, Oct., 1988, Vol. 5, No. 5, pp. 617-640.
2. ASU86 A.V. Aho, R. Sethi, and J.D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.
3. Bur87 Michael Burke. An IntervakBased Approach to Exhaustive and Incremental Interpvocedural Dala Flow Analysis. Technical Report, IBM Research, August 1987. Research report RC12702, submitted to ACM Transactions on Programming Languages and Systems.
4. CF87 Ron Cytron and Jeanne Ferrante. An Improved Control Dependence Algorithm. Technical Report, IBM, 1987. Tech. Report RC 13291.
5. CFR*89 Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. An efficient method for computing static single assignment form. $i~teenlh Annual A CM Symposium on Principles of Programming Languages, 25-35, January 1989.
6. CHH89 Ron Cytron, Michael Hind, and Wilson Hsieh. Automatic generation of dag parallelism. Proceedings of the 1989 $IGPLAN Conference on Programming Language De. sign and Implementation, 1989. To appear.
7. CHR78 W.P. Crowley, C. P. Hendrickson, and T. E. Rudy. The SIMPLE code. Technical Report, Lawrence Livermore Laboratory, 1978. UCID 17715.
8. CK74 John Cocke and Ken Kennedy. Profitability Computations on Program Flow Graphs. Technical Report, IBM, 1974. Tech. Report RC 5123.
9. FERN84 J. A. Fisher, J. R. Ellis, J. C. Ruttenberg, and A. Nicolau. Parallel processing: a smart compiler and a dumb machine. Proceedings of the A CM Symposium on Compiler Construction, 37- 47, June 1984.
10. FOW87 J. Ferrante, K. Ottenstein, and J. Warren. The program dependence graph and its use in optimization. A CM TransacIions on Programming Languages and Systems, 319-349, July 1987.
11. FS87 Philippe Flajolet and Jean-Marc Steyaert. A complexity calculus for recursive tree algorithms. Math. Systems Theory, 19:301-331, 1987.
12. GKM82 Susan L. Graham, Peter B. Kessler, and Marshall K. McKusick. Gprof: a call graph execution profiler. A CM SIGPLAN '82 Symposium on Compiler Construction, 17(6):120-126, June 1982.
13. HC88 Timothy Hickey and Jacques Cohen. Automating program analysis. JACM, 35(1):185-220, 1988.
14. Hsi88 Wilson C. Hsieh. Exlracting Parallelism from Sequential Programs. Technical Report, Massachusetts Institute of Technology, May 1988. Master's thesis.
15. Knu71 D.E. Knuth. An empirical study of fortran programs. Software - Practice and Experience, 1:105-133, 1971.
16. KW85 Clyde Kruskal and Alan Weiss. Allocating independent subtasks on parallel processors. IEEE Transactions on Software Engineering, SE-11(10), October 1985.
17. McM86 F. I/. McMahon. L.L.N.L. FORTRAN Kernels: MFLOPS. Technical Report, Lawrence Livermore National Laboratory, March 1986.
18. MH86 S. McFarling and J. Hennessy. Reducing the cost of branches. Proceedings of the Sigplan '86 Symposium on Compiler Construction, 21(7), July 1986.
19. Sar87 Vivek Sarkar. Partitioning and Scheduling Parallel Programs for Execution on Muliiprocessors. PhD thesis, Stanford University, April 1987. Tech. Report CSL-TR-87-328.
20. Sar89 Vivek Saxkar. Partitioning and Scheduling Parallel Programs for Multiprocessors. Pitman, London and The MIT Press, Cambridge, Massachusetts, 1989. In the series, Research Monographs in Parallel and Distributed Computing.
21. SH86a V. Sarkar and J. Hennessy. Compile-time partitioning and scheduling of parallel programs. Proceedings of the Sigplan '86 Symposium on Compiler Construction, 21(7):17- 26, July 1986.
22. SH86b V. Sarkar and J. Hennessy. Partitioning parallel programs for macro-dataflow. A CM Conference on Lisp and Functional Programming, 202-211, August 1986.
23. SS79 J.T. Schwartz and M. Sharir. A Design for Optimizations of the Bitvectoring Class. Technical Report, Courant Institute of Mathematical Sciences, New York University, September 1979. Courant Computer Science Report No. 17.
24. Wal86 D.W. Wall. Global register allocation at link time. Proceedings of the Sigplan '86 Symposium on Compiler Construction, 21(7), July 1986.
25. Weg75 Ben Wegbreit. Mechanical program analysis. CACM, 18(9):528-539, 1975.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Performance

• Social and professional topics

  • Professional topics

    • Management of computing and information systems

      • Software management

        • Software selection and adaptation

• Software and its engineering

  • Software notations and tools

    • Compilers

  • Software organization and properties

    • Extra-functional properties

      • Software performance

• Theory of computation

  • Randomness, geometry and discrete structures