Abstract
Real-time systems are characterized by the presence of timing constraints that a task must be completed within a given deadline. In this paper, we present a complete environment for determining best-case and worst-case execution time of a program when running on a given hardware. Our analysis technique is unique in that it allows user to annotate complex program path information and at the same time, models cache memory and pipeline accurately. This results in tight estimations even for complicated programs running on modern hardware. The technique has been implemented on a timing analysis tool — cinderella, which provides retargetable back-ends for analyzing programs written in different languages and executed on different hardware. We present some experimental results of using this tool.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
A. Aho, R. Sethi, and J. Ullman. Compilers Principles, Techniques, and Tools. Addison-Wesley, 1986.
R. Arnold, F. Mueller, D. Whalley, and M. Harmon. Bounding worst-case instruction cache performance. In Proc. of the 15th IEEE Real-Time Systems Symposium, Dec 1994.
S. Basumallick and K. Nilsen. Cache issues in real-time systems. In Proc. of ACM PLDI Workshop on Language, Compiler, and Tool Support for Real-Time Systems, Jun 1994.
S. Bharrat and K. Jeffay. Predicting worst case execution times on a pipelined RISC processor. Technical report, Dept of Computer Science, University of North Carolina at Chapel Hill, Apr 1994. TR94-072.
D. Bradlee. Retargetable Instruction Scheduling for Pipelined Processors. PhD thesis, University of Washington, 1991.
R. Gupta. Co-Synthesis of Hardware and for Digital Embedded Systems. PhD thesis, Stanford University, Dec 1993.
C. Healy, D. Whalley, and M. Harmon.Integrating the timing analysis of pipelining and instruction caching. In Proc. of 16th IEEE Real-Time Systems Symposium, Dec 1995.
J. Hennessy and D. Patterson. Computer Architecture: A Quantitative Approach, 2nd Ed. Morgan Kaufmann Publishers, Inc., 1996. ISBN 1-55860-329-8.
Y Hur, Y-H. Bae, S.-S. Lim, S.-K. Kim, B.-D. Rhee, S.-L. Min, C.-Y Park, M. Lee, H. Shin, and C.-S. Kim. Worst case timing analysis of RISC processors: R3000/R3010 case study. In Proc. of 16th IEEE Real-Time Systems Symposium, Dec 1995.
Intel Corp. QT960 User Manual, 1990. Order Number 270875-001.
E. Kligerman and A. Stoyenko. Real-time Euclid: A language for reliable real-time systems. IEEE Trans. on Software Engineering, Sep 1986.
Y-T. Li. Performance Analysis of Real-Time Embedded Software. PhD thesis, Princeton University, 1997.
S.-S. Lim, Y-H. Bae, G.-T. Jang, B.-D. Rhee, S.-L. Min, C.-Y Park, H. Shin, K. Park, and C.-S. Kim. An accurate worst case timing analysis technique for RISC processors. In Proc. of the 15th IEEE Real-Time Systems Symposium, Dec 1994.
J.-C. Liu and H.-J. Lee. Deterministic upperbounds of the worst-case execution times of cached programs. In Proc. of the 15th IEEE Real-Time Systems Symposium, Dec 1994.
A. Mok, P. Amerasinghe, M. Chen, and K. Tantisirivat. Evaluating tight execution time bounds of programs by annotations. In Proc. of the 6th IEEE Workshop on Real-Time Operating Systems and Software, May 1989.
K. Narasimhan and K. Nilsen. Portable execution time analysis for RISC processors. In Proc. of ACM PLDI Workshop on Language, Compiler, and Tool Support for Real-Time Systems, Jun 1994.
C.-Y Park. Predicting Deterministic Execution Times of Real-Time Programs. PhD thesis, University of Washington, Aug 1992.
P. Puschner and Ch. Koza. Calculating the maximum execution time of real-time programs. The Journal of Real-Time Systems, Sep 1989.
J. Rawat. Static analysis of cache performance for real-time programming. Master's thesis, Iowa State University of Science and Technology, Nov 1993. TR93-19.
A. Shaw. Reasoning about time in higher-level language software. IEEE Trans. on Software Engineering, Jul 1989.
N. Zhang, A. Burns, and M. Nicholson. Pipelined processors and worst-case execution times. Journal of Real-Time Systems, Oct 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, YT.S., Malik, S., Wolfe, A. (1997). Cinderella: A retargetable environment for performance analysis of real-time software. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002887
Download citation
DOI: https://doi.org/10.1007/BFb0002887
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive