Real Time Spent on Real Time

Worst-Case Execution-Time (WCET) Analysis is the first phase of Timing Analysis, which attempts to verify that a set of real-time tasks can be executed on an execution platform such that all tasks respect their deadlines. WCET analysis determines upper bounds on execution times, which are then passed on to a Schedulability Analysis, the second phase of Timing Analysis. This clean separation into the two phases holds for single-core execution platforms. Multi-core platforms require a more complex interaction between WCET analysis and schedulability analysis. We have solved the WCET-analysis problem for single-core platforms. Key to our success was the use of Abstract Interpretation for the static analysis of the behavior of architectural components such as caches, pipelines, buses, and peripheries. The Program-Analyzer Generator (PAG), which is based on Abstract Interpretation, allowed us to quickly develop and experiment with abstract domains, to arrive at sound, precise, and scalable solutions.