WCET analysis of multi-level non-inclusive set-associative instruction caches

With the advent of increasingly complex hardware in real-time embedded systems (processors with performance en-hancing features such as pipelines, cache hierarchy, multi-ple cores), many processors now have a set-associative L2 cache. Thus, there is a need for considering cache hierar-chies when validating the temporal behavior of real-time sys-tems, in particular when estimating tasks ’ worst-case execu-tion times (WCETs). In this paper, we propose a safe static in-struction cache analysis method for multi-level non-inclusive caches. The proposed method is experimented on medium-size and large programs. We show that the method is reasonably tight. We further show that in all cases WCET estimations are much tighter when considering the cache hierarchy than when considering only the L1 cache. An evaluation of the analy-sis time is conducted, demonstrating that analyzing the cache hierarchy has a reasonable computation time. 1