Abstract
This paper describes a general approach for automatic and accurate time-bound analysis. The approach consists of transformations for building time-bound functions in the presence of partially known input structures, symbolic evaluation of the time-bound function based on input parameters, optimizations to make the overall analysis efficient as well as accurate, and measurements of primitive parameters, all at the source-language level. We have implemented this approach and performed a number of experiments for analyzing Scheme programs. The measured worst-case times are closely bounded by the calculated bounds.
This work was partially supported by NSF under Grant CCR-9711253.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
P. Altenbernd. On the false path problem in hard real-time programs. In Proceedings of the 8th EuroMicro Workshop on Real-Time Systems, pages 102–107, L’Aquila, June 1996.
B. BjØrner, A. P. Ershov, and N. D. Jones, editors. Partial Evaluation and Mixed Computation. North-Holland, Amsterdam, 1988.
Cadence Research Systems. Chez Scheme System Manual. Cadence Research Systems, Bloomington, Indiana, revision 2.4 edition, July 1994.
D. R. Chase, M. Wegman, and F. K. Zadeck. Analysis of pointers and structures. In Proceedings of the ACM SIGPLAN ’90 Conference on Programming Language Design and Implementation, pages 296–310. ACM, New York, June 1990.
J. Engblom, P. Altenbernd, and A. Ermedahl. Facilitating worst-case execution time analysis for optimized code. In Proceedings of the 10th EuroMicro Workshop on Real-Time Systems, Berlin, Germany, June 1998.
A. Ermedahl and J. Gustafsson. Deriving annotations for tight calculation of execution time. In In Proceedings of Euro-Par’97, volume 1300 of Lecture Notes in Computer Science, pages 1298–1307. Springer-Verlag, Berlin, Aug. 1997.
C. Ferdinand, F. Martin, and R. Wilhelm. Applying compiler techniques to cache behavior prediction. In Proceedings of the ACM SIGPLAN 1997 Workshop on Languages, Compilers, and Tools for Real-Time Systems, pages 37–46, 1997.
P. Flajolet, B. Salvy, and P. Zimmermann. Automatic average-case analysis of algorithms. Theoretical Computer Science, Series A, 79(1):37–109, Feb. 1991.
C. Healy, M. Sjödin, V. Rustagi, and D. Whalley. Bounding loop iterations for timing analysis. In Proceedings of the IEEE Real-Time Applications Symposium. IEEE CS Press, Los Alamitos, Calif., June 1998.
N. D. Jones, C. K. Gomard, and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice-Hall, Englewood Cliffs, N.J., 1993.
D. E. Knuth. The Art of Computer Programming, volume 1. Addison-Wesley, Reading, Mass., 1968.
D. Le Métayer. Ace: An automatic complexity evaluator. ACM Trans. Program. Lang. Syst., 10(2):248–266, Apr. 1988.
S.-S. Lim, Y. H. Bae, G. T. Jang, B.-D. Rhee, S. L. Min, C. Y. Park, H. Shin, K. Park, S.-M. Moon, and C.-S. Kim. An accurate worst case timing analysis for RISC processors. IEEE Trans. Softw. Eng., 21(7):593–604, July 1995.
Y. A. Liu and G. Gomezes. Automatic accurate time-bound analysis for high-level languages. Technical Report TR 508, Computer Science Department, Indiana University, Bloomington, Indiana, Apr. 1998.
Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. ACM Trans. Program. Lang. Syst., 20(3), May 1998.
Y. A. Liu and T. Teitelbaum. Systematic derivation of incremental programs. Sci. Comput. Program., 24(1):1–39, Feb. 1995.
T. Lundqvist and P. Stenström. Integrating path and timing analysis using instruction-level simulation techniques. Technical Report No. 98-3, Department of Computer Engineering, Chalmers University of Technology, Göteborg, Sweden, 1998.
C. Y. Park. Predicting program execution times by analyzing static and dynamic program paths. Real-Time Systems, 5:31–62, 1993.
C. Y. Park and A. C. Shaw. Experiments with a program timing tool based on source-level timing schema. IEEE Computer, 24(5):48–57, 1991.
M. Rosendahl. Automatic complexity analysis. In Proceedings of the 4th International Conference on Functional Programming Languages and Computer Architecture, pages 144–156. ACM, New York, Sept. 1989.
R. H. Saavedra and A. J. Smith. Analysis of benchmark characterization and benchmark performance prediction. ACM Transactions on Computer Systems, 14(4):344–384, Nov. 1996.
D. Sands. Complexity analysis for a lazy higher-order language. In Proceedings of the 3rd European Symposium on Programming, volume 432 of Lecture Notes in Computer Science, pages 361–376. Springer-Verlag, Berlin, May 1990.
A. Shaw. Reasoning about time in higher level language software. IEEE Trans. Softw. Eng., 15(7):875–889, July 1989.
P. Wadler. Strictness analysis aids time analysis. In Conference Record of the 15th Annual ACM Symposium on Principles of Programming Languages. ACM, New York, Jan. 1988.
B. Wegbreit. Mechanical program analysis. Commun. ACM, 18(9):528–538, Sept. 1975.
D. Weise, R. F. Crew, M. Ernst, and B. Steensgaard. Value dependence graphs: Representation without taxation. In Conference Record of the 21st Annual ACM Symposium on Principles of Programming Languages. ACM, New York, Jan. 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, Y.A., Gomez, G. (1998). Automatic accurate time-bound analysis for high-level languages. In: Mueller, F., Bestavros, A. (eds) Languages, Compilers, and Tools for Embedded Systems. LCTES 1998. Lecture Notes in Computer Science, vol 1474. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0057778
Download citation
DOI: https://doi.org/10.1007/BFb0057778
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65075-1
Online ISBN: 978-3-540-49673-1
eBook Packages: Springer Book Archive