As demand for computational power of embedded applications has increased, their architectures have become more complex. One result of this increased complexity are real-time embedded systems with set-associative multi-level caches. Multi-level caches complicate the process of program analysis techniques such as worst case execution time (WCET). To address this need we have developed a sound cache behavior analysis that handles multi-level instruction and data caches. Our technique relies on a new abstraction, live caches, which models relationships between cache levels to improve accuracy. Our analysis improves upon previous multi-level cache analysis in three ways. First, it handles write-back, a common feature of cache models, soundly. Second, it handles both instruction and data cache hierarchies, and third, it improves precision of cache analysis. For standard WCET benchmarks and a multi-level cache configuration analyzed by previous work, we observed that live caches improve WCET precision resulting in an average of 6.3% reduction in computed WCET.
Available at: http://works.bepress.com/hridesh-rajan/74/
This article is published as Sondag, Tyler, and Hridesh Rajan. "A more precise abstract domain for multi-level caches for tighter wcet analysis." In Real-Time Systems Symposium (RTSS), 2010 IEEE 31st, pp. 395-404. IEEE, 2010. 10.1109/RTSS.2010.8. Posted with permission.