A Dynamic Instruction Cache Locking Approach for Minimizing Worst Case Execution Time of a Single Task

Abstract

In real time embedded system, the embedded software often consists of a set of concurrent tasks, and such tasks are generally subject to timing constraints. In order to satisfy all the timing constraints, precisely predicting the WCET of a task is essential for the task scheduler to construct a feasible schedule for a task set. Caches have been widely used to bridge the gap between high speed processors and relatively slower off-chip memory. However, caches make it extremely harder to predict precise WCET (Worst Case Execution Time) of a task for the simple reason that it is difficult to predict if each cache access is a cache hit or miss. Cache locking is a mechanism which disables the replacement policy of caches and locks some contents (instruction or data) in the caches, such that the accesses to those contents become fully predictable and the WCET of a task is easier to predict. Furthermore, cache locking is also an effective technique to reduce the WCET of a task by locking appropriate contents in the caches. In this paper, we investigate the WCET-aware I-cache (Instruction cache) locking problem and propose an ILP-based (Integer Linear Programming) dynamic I-cache locking approach for reducing the WCET of a task. Our approach not only select locking contents which have largest benefit for reducing WCET of a task, but also finds a good locking point for each locked instruction such that extra execution time spend on locking instructions is also minimized. We have implemented this approach and compared it with two state-of-the-art I-cache locking approaches, the longest path based dynamic cache locking approach proposed in and the min-cut based dynamic locking approach proposed in by using MRTC benchmark suite. The experimental results show that our approach performs better for each benchmark. Compared to the longest path based dynamic approach, our approach achieves the average improvements of 5.8%, 13.8%, 16.1% and 12.6% for the 256B, 512B, 1KB and 2KB caches, respectively. Compared to the min-cut based dynamic approach, our approach achieves the average improvements of 2.2%, 7.6%, 8.2% and 6.4% for the 256B, 512B, 1KB and 2KB caches, respectively.

Keywords

• Cache locking
• real-time systems
• worst-case-executing-time