Minimizing WCET for Real-Time Embedded Systems via Static Instruction Cache Locking
- 1 April 2009
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
Cache is effective in bridging the gap between processor and memory speed. It is also a source of unpredictability because of its dynamic and adaptive behavior. Worst-case execution time (WCET) of an application is one of the most important criteria for real-time embedded system design. The unpredictability of instruction miss/hit behavior in the instruction cache (I-Cache) leads to an unnecessary over-estimation of the real-time application's WCET. A lot of modern processors provide cache locking capability. Static I-Cache locking locks function/instruction blocks of a program into the I-Cache before program execution. In this way, a more precise estimation of WCET can be achieved. The selection of functions/instructions to be locked in the I-Cache has dramatic influence on the performance of the real-time application. This paper focuses on the static I-Cache locking problem to minimize WCET for real-time embedded systems. We formulate the problem using an Execution Flow Tree (EFT) and a linear programming model. For a subset of the problems with certain properties, corresponding polynomial time optimal algorithms are proposed. We prove that the general problem is an NP-Hard problem. We also show that for a subset of the general problem with certain patterns, optimal solutions can be achieved in polynomial time. Experimental results show that our algorithms can reduce the WCET of applications further compared to current best known techniques.Keywords
This publication has 6 references indexed in Scilit:
- Compile-time decided instruction cache locking using worst-case execution pathsPublished by Association for Computing Machinery (ACM) ,2007
- Cache Contents Selection for Statically-Locked Instruction Caches: An Algorithm ComparisonPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Improving WCET by applying a WC code-positioning optimizationACM Transactions on Architecture and Code Optimization, 2005
- A first look at the interplay of code reordering and configurable cachesPublished by Association for Computing Machinery (ACM) ,2005
- Low-complexity algorithms for static cache locking in multitasking hard real-time systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Timing Analysis for Instruction CachesReal-Time Systems, 2000