loading...
Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns
San Francisco, CA March 07-March 10
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/RTAS.2005.1211th IEEE Real Time and Embedded Tech ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Harini Ramaprasad, North Carolina State University
Frank Mueller, North Carolina State University
While caches have become invaluable for higher-end architectures due to their ability to hide, in part, the gap between processor speed and memory access times, caches (and particularly data caches) limit the timing predictability for data accesses that may reside in memory or in cache. This is a significant problem for real-time systems.
The objective our work is to provide accurate predictions of data cache behavior of scalar and non-scalar references whose reference patterns are known at compile time. Such knowledge about cache behavior provides the basis for significant improvements in bounding the worst-case execution time (WCET) of real-time programs, particularly for hard-to-analyze data caches.
We exploit the power of the Cache Miss Equations (CME) framework but lift a number of limitations of traditional CME to generalize the analysis to more arbitrary programs. We further devised a transformation, coined "forced" loop fusion, which facilitates the analysis across sequential loops. Our contributions result in exact data cache reference patterns - in contrast to approximate cache miss behavior of prior work. Experimental results indicate improvements on the accuracy of worst-case data cache behavior up to two orders of magnitude over the original approach. In fact, our results closely bound and sometimes even exactly match those obtained by trace-driven simulation for worst-case inputs. The resulting WCET bounds of timing analysis confirm these findings in terms of providing tight bounds. Overall, our contributions lift analytical approaches to predict data cache behavior to a level suitable for efficient static timing analysis and, subsequently, real-time schedulability of tasks with predictable WCET.
Citation:
Harini Ramaprasad, Frank Mueller, "Bounding Worst-Case Data Cache Behavior by Analytically Deriving Cache Reference Patterns," rtas, pp.148-157, 11th IEEE Real Time and Embedded Technology and Applications Symposium (RTAS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions