/ Home page of Thomas Lundqvist / Publications / unknown-tr02-11

Data Cache Timing Analysis with Unknown Data Placement

[tr02-11]Thomas Lundqvist: "Data Cache Timing Analysis with Unknown Data Placement," Technical Report No. 02-11, Dept. of Computer Engineering, Chalmers, February 2002.


This paper presents a method to estimate the worst-case number of data cache misses for a single subroutine where data objects have an unknown placement in memory. This is motivated by the need for a worst-case execution time estimate for parts of a program, e.g., a single library subroutine. The first step is to identify all data objects that are accessed in a predictable manner but have an unknown placement. Then, a conflict analysis is made and we show how this analysis can be made arbitrarily accurate. Our experimental evaluation of two benchmarks and different cache configurations shows that it is indeed possible to get tight estimates of the worst-case number of misses for a single subroutine with an acceptable analysis effort.

Download copy: