Please use this identifier to cite or link to this item:
Title: Modeling control speculation for timing analysis
Authors: Li, X.
Mitra, T. 
Roychoudhury, A. 
Keywords: Branch prediction
Instruction cache
Micro-architectural modeling
Schedulability analysis
Worst case execution time
Issue Date: 2005
Citation: Li, X., Mitra, T., Roychoudhury, A. (2005). Modeling control speculation for timing analysis. Real-Time Systems 29 (1) : 27-58. ScholarBank@NUS Repository.
Abstract: The schedulability analysis of real-time embedded systems requires worst case execution time (WCET) analysis for the individual tasks. Bounding WCET involves not only language-level program path analysis, but also modeling the performance impact of complex micro-architectural features present in modern processors. In this paper, we statically analyze the execution time of embedded software on processors with speculative execution. The speculation of conditional branch outcomes (branch prediction) significantly improves a program's execution time. Thus, accurate modeling of control speculation is important for calculating tight WCET estimates. We present a parameterized framework to model the different branch prediction schemes. We further consider the complex interaction between speculative execution and instruction cache performance, that is, the fact that speculatively executed blocks can generate additional cache hits/misses. We extend our modeling to capture this effect of branch prediction on cache performance. Starting with the control flow graph of a program, our technique uses integer linear programming to estimate the program's WCET. The accuracy of our method is demonstrated by tight estimates obtained on realistic benchmarks.
Source Title: Real-Time Systems
ISSN: 09226443
DOI: 10.1023/B:TIME.0000048933.15922.f9
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.


checked on Mar 20, 2019


checked on Mar 20, 2019

Page view(s)

checked on Jan 26, 2019

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.