Supporting Timing Analysis by Automatic Bounding of Loop Iterations

Christopher Healy, Mikael Sjödin, V. Rustagi, David Whalley, Robert van Engelen · Real-time systems · 2000

Summary

Three complementary methods to support timing analysis by bounding the number of loop iterations are described and have been successfully integrated in an existing timing analyzer that predicts the performance for optimized code on a machine that exploits caching and pipelining.

Type: article
Published: 2000-05-01
Cited by: 141
References: 36
DOI: https://doi.org/10.1023/a:1008189014032
OpenAlex: https://openalex.org/W1797762004
Semantic Scholar: https://api.semanticscholar.org/CorpusID:2858536

Keywords

Bounding overwatch, Computer science, Algorithm, Loop (graph theory), Code (set theory)

References

Software pipelining: an effective scheduling technique for VLIW machinesMonica S. Lam — 1988
Symbolic Evaluation of Sums for Parallelising CompilersRizos Sakellariou — 1997
Compilers: Principles, Techniques, and ToolsAlfred V. Aho, Ravi Sethi, Jeffrey D. Ullman — 1986
Computer architecture (2nd ed.): a quantitative approachJohn L. Hennessy, David A. Patterson — 1996
Maple V Library Reference ManualBruce W. Char, K. O. Geddes, Gastón H. Gonnet — 1992
Computer Architecture: A Quantitative ApproachJohn L. Hennessy, David A. Patterson — 1969
On the Quest for Perfect Load Balance in Loop-Based Parallel ComputationsRizos Sakellariou — 1996
A portable global optimizer and linkerManuel E. Benitez, Jack W. Davidson — 1988
High-performance computer architecture (2nd ed.)Harold S. Stone — 1990
Calculating the maximum execution time of real-time programsPeter Puschner, C. Koza — 1989
Experiments with a program timing tool based on source-level timing schemaC.Y. Park, Alan Shaw — 1991
CTADEL: a generator of multi-platform high performance codes for PDE-based scientific applicationsRobert van Engelen, Lex Wolters, Gerard Cats — 1996
Combining static worst-case timing analysis and program proofRoderick Chapman, Alan Burns, Andy Wellings — 1996
High performance compilers for parallel computingMichael Wolfe, Carter Shanklin, Leda Ortega — 1995
Real-Time Euclid: A language for reliable real-time systemsEugene Kligerman, Alexander D. Stoyenko — 1989
Tighter timing predictions by automatic detection and exploitation of value-dependent constraintsChristopher Healy, Dan Whaley — 1999
Integrating the timing analysis of pipelining and instruction cachingChristopher Healy, David Whalley, Marion G. Harmon — 1995
Timing analysis for data caches and set-associative cachesRandall T. White, Frank Mueller, Christopher Healy — 1997
Efficient microarchitecture modeling and path analysis for real-time softwareY.-T.S. Li, Sharad Malik, A. Wolfe — 1995
Bounding worst-case instruction cache performanceArnold, Mueller, Whalley — 1994

Cited by

Techniques for Building Timing-Predictable Embedded SystemsNan Guan — 2016
Control-flow refinement and progress invariants for symbolic complexity boundsSumit Gulwani, Sagar Jain, Eric Koskinen — 2009
Exploiting hardware/software interactions for analyzing embedded systemsFrank Mueller, Sibin Mohan — 2008
Organizing Information for Execution Time Analysis in Real-Time Embedded SystemsYun-Kwan Kim, Won Shin, Tae Wan Kim — 2007
Tight Timing Estimation With the Newton-Gregory Formulae∗Robert van Engelen, Kyle A. Gallivan — 2002
Behavioral Intervals in Embedded SoftwareFabian Wolf — 2002
Contributions à l'analyse du comportement temporel de la hiérarchie mémoire pour l'estimation du pire temps d'exécutionJean-François Deverge — 2008
Cache and Compiler Interaction : How to analyze, optimize and time cache behaviorX. Vera — 2003
Worst-Case Execution Time Analysis of Parallel SystemsAndreas Gustavsson — 2011
TuBound - A Conceptually New Tool for Worst-Case Execution Time AnalysisAdrian Prantl, Markus Schordan, Jens Knoop — 2008
Combining Symbolic Execution and Path Enumeration in Worst-Case Execution Time AnalysisDjemaï Kebbal, Pascal Sainrat — 2006
A Modular Tool Architecture for Worst-Case Execution Time AnalysisAndreas Ermedahl — 2008
Comparing WCET and Resource Demands of Trigonometric Functions Implemented as Iterative Calculations vs. Table-LookupRaimund Kirner, Markus Grössing, Peter Puschner — 2006
Loop Bound Analysis based on a Combination of Program Slicing, Abstract Interpretation, and Invariant AnalysisAndreas Ermedahl, Christer Sandberg, Jan Gustafsson — 2007
Hybrid Cache Analysis in Running Time Verification of Embedded SoftwareFabian Wolf, Jan Staschulat, Rolf Ernst — 2002
Cache persistence analysis for embedded real-time systemsChristoph Cullmann — 2013
A WCET Analysis Method for Pipelined Microprocessors with Cache MemoriesThomas Lundqvist — 2002
Integer Range Analysis for Whiley on Embedded SystemsDavid J. Pearce — 2015
Execution-Time Analysis for Embedded Real-Time SystemsJakob Engblom, Andreas Ermedahl, Mikael Sjödin — 2003
Computing time as a program variable: a way around infeasible pathsNiklas Holsti — 2008

Supporting Timing Analysis by Automatic Bounding of Loop Iterations

Summary

Keywords

References

Cited by

Related papers