Accurately Estimating Worst-Case Execution Time for Multi-core Processors with Shared Direct-Mapped Instruction Caches

In a multicore processor, different cores typically share the last level cache, and threads running on different cores may interfere with each other in accessing the shared cache. Therefore, multicore WCET (worst case execution time) analyzer must be able to safely and accurately estimate the worst case interthread cache interferences, which is not supported by current WCET analysis techniques that mainly focus on analyzing uniprocessors. This paper proposes a novel approach to analyzing the worst case cache interferences and bounding the WCET for threads running on multicore processors with shared direct mapped L2 instruction caches. We propose to use an extended ILP (integer linear programming) to model all the possible interthread cache conflicts, based on which we can accurately calculate the worst case interthread cache interferences and derive the WCET. Compared to a recently proposed multicore static analysis technique based on control flow information alone, this approach improves the tightness of WCET estimation by 13.7% on average.