Abstract
This paper describes a method to predict guaranteed and tight deterministic execution time bounds of a sequential program. The basic prediction technique is a static analysis based on simple timing schema for source-level language constructs, which gives accurate predictions in many cases. Using powerful user-provided information, dynamic path analysis refines looser predictions by eliminating infeasible paths and decomposing the possible execution behaviors in a pathwise manner. Overall prediction cost is scalable with respect to desired precision, controlling the amount of information provided. We introduce a formal path model for dynamic path analysis, where user execution information is represented by a set of program paths. With a well-defined practical high-level interface language, user information can be used in an easy and efficient way. We also introduce a method to verify given user information with known program verification techniques. Initial experiments with a timing tool show that safe and tight predictions are possible for a wide range of programs. The tool can also provide predictions for interesting subsets of program executions.
Similar content being viewed by others
References
Avrunin, G., Dillon, L., Wileden, J., and Riddle, W. 1986. Constrained expressions: Adding analysis capabilities to design methods for concurrent software systems.IEEE Transactions on Software Engineering. 12:278–291.
Callison, H., and Shaw, A. 1991. Building a real-time kernel: First step in validating a pure process/Adt model.Software — Practice and Experience. 21:337–354.
Chen, M. 1987. TAL — A language for timing analysis. Department of Computer Science, University of Texas, Austin.
Dijkstra, E. 1976.A Discipline of Programming. Englewood Cliffs, NJ: Prentice-Hall.
Hoare, C. 1969. An axiomatic basis for computer programming.Communications of ACM. 12:576–580.
Huang, J. 1990. State constraints and pathwise decomposition of programs.IEEE Transactions on Software Engineering. 16:880–896.
Gehani, N. and Ramamritham, K. 1991. Real-time concurrent C: A language for programming dynamic real-time systems.The Journal of Real-Time Systems. 3:377–405.
Gries, D. 1981.The Science of Programming. Berlin/New York: Springer-Verlag. Chapter 12, pp. 149–162.
Kim, J. and Shaw, A. 1990. An experiment on predicting and measuring the deterministic execution times of parallel programs on a multiprocessor. Tech. Report #90-09-01, Dept. of Computer Science and Engineering, Univ. of Washington, Seattle, WA.
Korel, R. 1990. Automated software test data generation.IEEE Transactions on Software Engineering. 16:870–879.
Lin, K., Kenny, K., Natarajan, S., and Liu, J. 1990. FLEX: A language for real-time systems programming.Foundations of Real-Time Computing: Formal Specifications and Methods. (ed. A. Tilborg and G. Koob), Kluwer Academic Publishers. pp. 251–290.
McNaughton, R. and Yamada, H. 1960. Regular expressions and state graphs for automata.IRE Transactions on Electronic Computers. 9:39–47.
Mok, A., Amerasinghe, P., Chen, M., and Tantisirivat, K. 1989. Evaluating tight execution time bounds of programs by annotations.Proceedings of 6th IEEE Workshop on Real-Time Operating Systems and Software. pp. 74–80.
Niehaus, M. 1991. Program representation and translation for predictable real-time systems.Proceedings on 12th IEEE Real-Time Systems Symposium, pp. 43–52.
Nirkhe, V. and Pugh, W. 1991. A partial evaluator for the Maruti hard real-time system.Proceedings on 12th IEEE Real-Time Systems Symposium, pp. 64–73.
Olender, K. and Osterweil, L. 1990. Cecil: A sequencing constraint language for automatic static analysis generation.IEEE Transactions on Software Engineering. 16:268–280.
Park, C. and Shaw, A. 1990. Experiments with a program timing tool based on source-level timing schema.Proceedings on 11th IEEE Real-Time Systems Symposium. pp. 72–81. (A revised version is also inIEEE Computer, 24:48–57.)
Park, C. 1992. Predicting deterministic execution times of real-time programs. Ph.D. Thesis, University of Washington, Department of Computer Science.
Puschner, P. and Koza, Ch. 1989. Calculating the maximum execution time of real-time programs.The Journal of Real-Time Systems. 1:159–176.
Shaw, A. 1989. Reasoning about time in higher-level language software.IEEE Transactions on Software Engineering. 15:875–889.
Shaw, A. 1991. Deterministic timing schema for parallel programs.Proceedings of 5th International Parallel Processing Symposium. pp. 56–63.
Stoyenko, A. 1987. A real-time language with a schedulability analyzer. Ph.D. Thesis, Univ. of Toronto, Computer Systems Research Institute, Tech. Report CSRI-206, Toronto.
Stoyenko, A. and Marlowe, T. 1992. Polynomial-time transformation and schedulability analysis of parallel real-time programs with restricted resource contention.Real-Time Systems, 4:307–330.
Woodward, M., Hedley, D., and Hennell, M. 1980. Experience with path analysis and testing of programs.IEEE Transactions on Software Engineering. 6:278–286.
Young, M. and Taylor, R. 1988. Combining static concurrency analysis with symbolic execution.IEEE Transactions on Software Engineering, 14:1499–1511.
Author information
Authors and Affiliations
Additional information
This research was supported in part by the Office of Naval Research under grant number N00014-89-J-1040.
Rights and permissions
About this article
Cite this article
Park, C.Y. Predicting program execution times by analyzing static and dynamic program paths. Real-Time Syst 5, 31–62 (1993). https://doi.org/10.1007/BF01088696
Issue Date:
DOI: https://doi.org/10.1007/BF01088696