Abstract
Static timing analyzers, which are used to analyze real-time systems, need to know the minimum and maximum number of iterations associated with each loop in a real-time program so accurate timing predictions can be obtained. This paper describes three complementary methods to support timing analysis by bounding the number of loop iterations. First, an algorithm is presented that determines the minimum and maximum number of iterations of loops with multiple exits. Even when the number of iterations cannot be exactly determined, it is desirable to know the lower and upper iteration bounds. Second, when the number of iterations is dependent on unknown values of variables, the user is asked to provide bounds for these variables. These bounds are used to determine the minimum and maximum number of iterations. Specifying the values of variables is less error prone than specifying the number of loop iterations directly. Finally, a method is given to tightly predict the execution time of inner loops whose number of iterations is dependent on counter variables of outer level loops. This is accomplished by formulating the total number of iterations of a loop in terms of summations and solving the resulting equation. These three methods have been successfully integrated in an existing timing analyzer that predicts the performance for optimized code on a machine that exploits caching and pipelining. The result is tighter timing analysis predictions and less work for the user.
Similar content being viewed by others
References
Aho, A. V., Sethi, R., and Ullman, J. D. 1986. Compilers Principles, Techniques, and Tools. Reading, MA: Addison-Wesley.
Arnold, R., Mueller, F., Whalley, D., and Harmon, M. 1994. Bounding worst-case instruction cache performance. Proceedings of the Fifteenth IEEE Real-Time Systems Symposium San Juan, Puerto Rico, pp. 172–181.
Benitez, M. E., and Davidson, J. W. 1988. A portable global optimizer and kinker. Proceedings of the SIGPLAN '88 Symposium on Programming Language Design and Implementation Atlanta, GA, pp. 329–338.
Burns, A., Chapman, R., and Wellings, A. 1996. Combining static worst-case timing analysis and program proof. Real-Time Systems Journal 11: 145–171.
Char, B., Geddes, K., Gonnet, G., Monagan, M., and Watt, S. 1988. MAPLE Reference Manual. Waterloo, Canada.
Ermedahl, A., and Gustafsson, J. 1997. Deriving annotations for tight calculation of execution time. Proceedings of European Conference on Parallel Processing: 1298–1307.
Healy, C., Arnold, R., Mueller, F., Whalley, D., and Harmon, M. 1999. Bounding pipeline and instruction cache performance. IEEE Transactions on Computers 48(1): 53–70.
Healy, C. A., and Whalley, D. B. 1999. Tighter timing predictions by automatic detection and exploitation of value-dependent constraints. Proceedings of the IEEE Real-Time Technology and Applications Symposium Vancouver, Canada, pp. 79–88.
Healy, C. A., Whalley, D. B., and Harmon, M. G. 1995. Integrating the timing analysis of pipelining and instruction caching. Proceedings of the Sixteenth IEEE Real-Time Systems Symposium Pisa, Italy, pp. 288–297.
Hennessy, J., and Patterson, D. 1996. Computer Architecture: A Quantitative Approach, Second Edition. San Francisco: Morgan Kaufmann.
Hur, Y., Bae, Y., Lim, S., Kim, S., Rhee, B., Min, S., Park, C., Lee, M., Shin, H., and Kim, C. 1995. Worst case timing analysis of RISC processors: R3000/R3010 case study. Proceedings of the IEEE Real-Time Systems Symposium Pisa, Italy.
Kligerman, E., and Stoyenko, A. 1986. Real-time Euclid: A language for reliable real-time systems. IEEE Transactions on Software Engineering 12(9): 941–949.
Lam, M. 1998. Software pipelining: An effective scheduling technique for VLIW machines. Proceedings of the SIGPLAN '88 Symposium on Programming Language Design and Implementation Atlanta, GA, pp. 318–328.
Li, Y. S., Malik, S., and Wolfe, A. 1995. Efficient microarchitecture modeling and path analysis for real-time software. Proceedings of the Sixteenth IEEE Real-Time Systems Symposium Pisa, Italy, pp. 298–307.
Liu, Y., and Gomez, G. 1998. Automatic accurate time-bound analysis for high-level languages. ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems: 31–40.
Lundqvist, T., and Stenström, P. 1998. Integrating path and timing analysis using instruction-level simulation techniques. ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems: 1–15.
Park, C. Y., and Shaw, A. C. 1991. Experiments with a program timing tool based on a source-level timing schema. Computer 24(5): 48–57.
Puschner, P., and Koza, C. 1989. Calculating the maximum execution time of real-time programs. Real-Time Systems 1(2): 159–176.
Sakellariou, R. 1996. On the Quest for Perfect Load Balance in Loop-Based Parallel Computations. Department of Computer Science, University of Manchester, Manchester, England.
Sakellariou, R. 1997. Symbolic evaluation of sums for parallelising compilers. Proceedings of the 15th IMACS World Congress on Scientific Computation, Modelling and Applied Mathematics, Volume 2, Wissenschaft & Technik Verlag, pp. 685-690.
Stone, H. S. 1990. High-Performance Computer Architecture, Second Edition. Reading, MA: Addison Wesley. Texas Instruments, Inc. 1993. Product Preview of the TMS390S10 Integrated SPARC Processor. Dallas, TX
van Engelen, R., Wolters, L., and Cats, G. 1996. Ctadel: Agenerator of multi-platform high performance codes for PDE-based scientific applications. Proceedings of the 10th ACM International Conference on Supercomputing Philadelphia, PA, pp. 86-93.
van Engelen, R., Wolters, L., and Cats, G. 1997. Tomorrow's weather forecast: Automatic code generation for atmospheric modeling. IEEE Journal of Computational Science and Engineering 4(3): 22–31.
White, R. T., Mueller, F., Healy, C. A., Whalley, D. B., and Harmon, M. G. 1997. Timing analysis for data caches and set-associative caches. Proceedings of the IEEE Real-Time Technology and Applications Symposium Montreal, Canada, pp. 192–202.
Wolfe, M. J. 1996. High Performance Compilers for Parallel Computers. Redwood City, CA: Addison-Wesley.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Healy, C., Sjödin, M., Rustagi, V. et al. Supporting Timing Analysis by Automatic Bounding of Loop Iterations. Real-Time Systems 18, 129–156 (2000). https://doi.org/10.1023/A:1008189014032
Issue Date:
DOI: https://doi.org/10.1023/A:1008189014032