Accurately Estimating Worst-Case Execution Time for Multi-core Processors with Shared Direct-Mapped Instruction Caches
- 1 August 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23251271,p. 455-463
- https://doi.org/10.1109/rtcsa.2009.55
Abstract
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.Keywords
This publication has 14 references indexed in Scilit:
- WCET Analysis for Multi-Core Processors with Shared L2 Instruction CachesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- A Hybrid Real-Time Scheduling Approach for Large-Scale Multicore Platforms19th Euromicro Conference on Real-Time Systems (ECRTS'07), 2007
- Efficient detection and exploitation of infeasible paths for software timing analysisProceedings of the 39th conference on Design automation - DAC '02, 2006
- Adding instruction cache effect to schedulability analysis of preemptive real-time systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- MediaBench: a tool for evaluating and synthesizing multimedia and communications systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Integrating the timing analysis of pipelining and instruction cachingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Automatic detection and exploitation of branch constraints for timing analysisIEEE Transactions on Software Engineering, 2002
- Bounding cache-related preemption delay for real-time systemsIEEE Transactions on Software Engineering, 2001
- Efficient longest executable path search for programs with complex flows and pipeline effectsPublished by Association for Computing Machinery (ACM) ,2001
- An efficient search algorithm to find the elementary circuits of a graphCommunications of the ACM, 1970