Worst-case Execution Time Analysis Based On Abstract Analysis

Estimates of Worse-Case Execution Time (WCET) are required in providingguarantees for timing of programs used in computer controlled products and otherreal-time computer systems. They are used to ensure timely responses from interrupts,to guarantee the throughput of cyclic tasks, as input to scheduling and schedule analysisalgorithm, and in many other situations. To derive program WCET estimates, bothsoftware and hardware must be considered. Traditionally, such estimates have beenobtained either by measurement or labor-intensive manual analysis, which is both timeconsuming and error-prone. Static WCET analysis, on the other hand, is capable ofgenerating safe WCET estimates without actually running the program.The Worst-Case Execution Time (WCET) analysis attempts to determine an upperbound on the execution time of a program running on particular hardware platform.Static Analysis is one of important ways to obtains worst-case execution time, whichdoes not rely on executing code on real hardware or on a simulator. Generally, the staticanalysis consists of three phases, Flow analysis, Low-level analysis and Calculation.In this thesis, we present a method called Abstract Analysis for the static analysis.In the Flow Analysis, the control flow graph (CFG) is constructed for the measuredprogram firstly, combining with Data information. Then conducting abstract analysis forthe constructed CFG, basic abstract structures are generated. Using those abstractstructures and following their defined actions, the flow information can be generatedautomatically from the analysis. For Low-level analysis, we use the common methodproposed by papers previously to obtain the timing behavior of processor. And ourevaluation whether is accurate or not largely depends on the results. Regarding ofCalculation, a new path-based approach, based on abstract structures, is adopted tocalculate the WCET estimates, handling the flow information effectively. This methodovercomes the drawback of the common Path-based calculation, which has problemswith flow information stretching across loop-nesting levels. The experimentalevaluations show that our method is an efficient analysis measure having the quality forresolving problems in an uniform mode. And that is capable to obtain better results for some situations.