WCET analysis of instruction cache hierarchies

With the advent of increasingly complex hardware in real-time embedded systems (processors with performance enhancing features such as pipelines, caches, multiple cores), most embedded processors use a hierarchy of caches. While much research has been devoted to the prediction of Worst-Case Execution Times (WCETs) in the presence of a single level of cache (instruction caches, data caches, impact of cache replacement policies), very little research has focused on WCET estimations in the presence of cache hierarchies.In this paper, we propose a safe static instruction cache analysis method for multi-level caches. Variations of the method are presented to model different cache hierarchy management policies between cache levels: non-inclusive, inclusive and exclusive cache hierarchies. The method supports multiple replacement policies.The proposed method is experimented on medium-size benchmarks and a larger application. We show that the method is tight in the case of non-inclusive caches hierarchies and exclusive caches hierarchies, provided that all cache levels use the Least Recently Used (LRU) replacement policy. We further evaluate the additional pessimism when inclusion is enforced or when a non-LRU replacement policy is used.