JCSE, vol. 3, no. 4, pp.195-215, December, 2009

DOI:

Bounding Worst-Case Data Cache Performance by Using Stack Distance

Yu Liu, Wei Zhang
Department of Electrical and Computer Engineering, Southern Illinois University Carbondale, USA

Abstract: Worst-case execution time (WCET) analysis is critical for hard real-time systems to ensure thatdifferent tasks can meet their respective deadlines. While significant progress has been madefor WCET analysis of instruction caches, the data cache timing analysis, especially for set-associative data caches, is rather limited. This paper proposes an approach to safely and tightlybounding data cache performance by computing the worst-case stack distance of data cacheaccesses. Our approach can not only be applied to direct-mapped caches, but also be used forset-associative or even fully-associative caches without increasing the complexity of analysis.Moreover, the proposed approach can statically categorize worst-case data cache misses intocold, conflict, and capacity misses, which can provide useful insights for designers to enhancethe worst-case data cache performance. Our evaluation shows that the proposed data cachetiming analysis technique can safely and accurately estimate the worst-case data cacheperformance, and the overestimation as compared to the observed worst-case data cache missesis within 1% on average.

Keyword: No keyword

Full Paper:   185 Downloads, 3818 View