Minimizing Cache Usage for Real-time Systems

Cache partitioning is a technique to reduce interference among tasks accessing the shared caches. To make this technique effective, cache segments must be given to the tasks that can benefit most from having their data and instructions cached for faster execution. The existing partitioning schemes for real-time systems divide the available cache among the tasks to guarantee their schedulability which is the sole optimization criterion. However, it is also preferable, especially in systems with power constraints or mixed criticalities, to reduce the total cache usage for real-time tasks. In this paper, we develop optimization algorithms for cache partitioning that, besides ensuring schedulability, also minimize cache usage. We consider both preemptive and non-preemptive scheduling policies on single-processor systems. For preemptive scheduling, we formulate the problem as an integer quadratically constrained program and propose an efficient heuristic achieving near-optimal solutions. For non-preemptive scheduling, we combine linear and binary search techniques with different schedulability tests. Our experiments based on synthetic task sets with parameters from real-world embedded applications show that the proposed heuristic: (i) achieves an average optimality gap of 0.79% within 0.1x run time of a mathematical programming solver and (ii) reduces average cache usage by 39.15% compared to existing cache partitioning approaches. Besides, we find that for large task sets with high utilization, non-preemptive scheduling can use less cache than preemptive to guarantee schedulability.