Please use this identifier to cite or link to this item:
Title: Modeling out-of-order processors for WCET analysis
Authors: Li, X.
Roychoudhury, A. 
Mitra, T. 
Keywords: Branch prediction
Instruction cache
Out-of-order superscalar processor
Worst-case execution time (WCET) analysis
Issue Date: 2006
Citation: Li, X., Roychoudhury, A., Mitra, T. (2006). Modeling out-of-order processors for WCET analysis. Real-Time Systems 34 (3) : 195-227. ScholarBank@NUS Repository.
Abstract: Estimating the Worst Case Execution Time (WCET) of a program on a given processor is important for the schedulability analysis of real-time systems. WCET analysis techniques typically model the timing effects of micro-architectural features in modern processors (such as pipeline, cache, branch prediction) to obtain safe and tight estimates. In this paper, we model out-of-order superscalar processor pipelines for WCET analysis. The analysis is, in general, difficult even for a basic block (a sequence of instructions with single-entry and single-exit points) if some of the instructions have variable latencies. This is because the WCET of a basic block on out-of-order pipelines cannot be obtained by assuming maximum latencies of the individual instructions. Our timing estimation technique for a basic block proceeds by a fixed-point analysis of the time intervals at which the instructions enter/leave a pipeline stage. To extend our estimation to whole programs, we use Integer Linear Programming (ILP) to combine the timing estimates for basic blocks. Timing effects of instruction cache and branch prediction are also modeled within our pipeline analysis framework. This forms a combined timing analysis framework that captures out-of-order pipeline, cache, branch prediction as well as the mutual interaction among these micro-architectural features. The accuracy of our analysis is demonstrated via tight estimates obtained for several benchmarks.
Source Title: Real-Time Systems
ISSN: 09226443
DOI: 10.1007/s11241-006-9205-5
Appears in Collections:Staff Publications

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


checked on Oct 18, 2018


checked on Oct 10, 2018

Page view(s)

checked on Aug 3, 2018

Google ScholarTM



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