JCSE, vol. 5, no. 2, pp.131-140, 2011

DOI: 10.5626/JCSE.2011.5.2.131/

An Interference Matrix Based Approach to Bounding Worst-Case Inter-Thread Cache Interferences and WCET for Multi-Core Processors

Jun Yan, Wei Zhang
Mathworks, Boston, MA, USA Department of Electrical and Computer Engineering, Virginia Commonwealth University, Richmond, VA, USA

Abstract: Different cores typically share the last-level cache in a multi-core processor. Threads running on different cores may interfere with each other. Therefore, the multi-core worst-case execution time (WCET) analyzer must be able to safely and accurately estimate the worst-case inter-thread cache interference. This is not supported by current WCET analysis techniques that manly focus on single thread analysis. This paper presents a novel approach to analyze the worst-case cache interference and bounding the WCET for threads running on multi-core processors with shared L2 instruction caches. We propose to use an interference matrix to model inter-thread interference, on which basis we can calculate the worst-case inter-thread cache interference. Our experiments indicate that the proposed approach can give a worst-case bound less than 1%, as in benchmark fib-call, and an average 16.4% overestimate for threads running on a dual-core processor with shared-L2 cache. Our approach dramatically improves the accuracy of WCET overestimatation by on average 20.0% compared to work.

Keyword: Worst-case execution time; Inter-thread cache interferences; Multicore computing

Full Paper:   149 Downloads, 2469 View