Precise micro-architectural modeling for WCET analysis via AI+SAT
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Hard real-time systems are required to meet critical deadlines. Worst case execution time (WCET) is therefore an important metric for the system level schedulability analysis of hard real-time systems. However, performance enhancing features of a processor (e.g. pipeline, caches) makes WCET analysis a very difficult problem. In this paper, we propose a novel approach to combine abstract interpretation (AI) and satisfiability (SAT) checking (hence the name AI+SAT) for different varieties of micro-architectural modeling. Our work in this paper is inspired by the research advances in program flow analysis(e.g. infeasible path analysis). We show that the accuracy of WCET estimates can be improved in a scalable fashion by using SAT checkers to integrate infeasible path analysis results into micro-architectural modeling. Our modeling is implemented on top of the Chronos WCET analysis tool and we improve the accuracy of WCET estimates for instruction cache, data cache, branch predictors and shared caches.Keywords
This publication has 10 references indexed in Scilit:
- Scope-Aware Data Cache Analysis for WCET EstimationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- JetBench: An Open Source Real-time Multiprocessor BenchmarkPublished by Springer Nature ,2010
- A Fast and Precise Static Loop Analysis Based on Abstract Interpretation, Program Slicing and Polytope ModelsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- WCET Analysis of Multi-level Non-inclusive Set-Associative Instruction CachesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Exploring locking & partitioning for predictable shared caches on multi-coresPublished by Association for Computing Machinery (ACM) ,2008
- Automatic Derivation of Loop Bounds and Infeasible Paths for WCET Analysis Using Abstract ExecutionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Modeling complex flows for worst-case execution time analysisPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fast and Precise WCET Prediction by Separated Cache and Path AnalysesReal-Time Systems, 2000
- Worst Case Execution Time Analysis for a Processor with Branch PredictionReal-Time Systems, 2000
- Performance estimation of embedded software with instruction cache modelingACM Transactions on Design Automation of Electronic Systems, 1999