Minimizing Cache Usage for Real-time Systems

Binqi Sun, Tomasz Kloda, Sergio Arribas García, Giovani Gracioli, Marco CaccamoRTNS 2023 · DOI

Introduction

In modern real-time systems, multiple tasks frequently share a processor's cache, leading to inter-task interference. This phenomenon occurs when one task evicts the data of another, resulting in unpredictable execution times. For systems with strict deadlines, this unpredictability is a significant hurdle. Cache partitioning has emerged as a solution, providing each task or core with a dedicated slice of the cache to ensure deterministic behavior.

Cache partitioning in a mixed-criticality system, where real-time tasks (RTOS) and best-effort tasks (GPOS) share L2 cache.

The Problem: Beyond Schedulability

Traditionally, cache partitioning research has focused on "schedulability"—ensuring that every task finishes on time by distributing the entire available cache. However, this approach is often wasteful. Caches can account for up to 50% of a processor's energy consumption in embedded systems. Furthermore, in mixed-criticality environments, any cache saved from high-priority real-time tasks can be reallocated to "best-effort" tasks, such as user interfaces or background logging, thereby improving overall system performance. The objective of this research is to find the absolute minimum cache required to maintain system schedulability.

Methodology

The authors propose optimization algorithms for two primary scheduling policies on single-core systems:

  1. Preemptive Scheduling: Tasks can interrupt each other, and each is assigned a private cache partition.
  2. Integer Quadratically Constrained Program (IQCP): A mathematical formulation to find the optimal solution, though computationally intensive.
  3. Guided Local Search (GLS): A heuristic that alternates between "decrease" and "increase" phases to find a near-optimal configuration efficiently.
  4. Baselines: Adapted Branch-and-Bound (BB) and Dynamic Programming (DP) algorithms.
  5. Non-preemptive Scheduling: Tasks run to completion without interruption, allowing them to share a single cache partition. The authors utilized Linear and Binary Search strategies combined with non-preemptive Response Time Analysis (NP-RTA) to identify the smallest viable shared partition.

Key Insights: The Corner Point Phenomenon

A critical observation in this study is that the relationship between cache size and Worst-Case Execution Time (WCET) is not a smooth curve but a staircase. Execution time decreases only when the cache size reaches a "corner point"—a threshold large enough to accommodate a significant data structure.

The relationship between WCET and cache size follows a staircase pattern, with 'corner points' indicating significant performance gains.

By exploiting these corner points, the proposed algorithms can skip redundant calculations, significantly speeding up the search for the optimal cache size. Additionally, the research highlights a trade-off: for large task sets with high utilization, non-preemptive scheduling often requires less total cache because tasks can safely share the same partition without data eviction.

Results and Discussion

The study evaluated these methods using the CortexSuite benchmark and synthetic task sets. Key findings include:

  • Efficiency: The GLS heuristic reduced average cache usage by 39.15% compared to traditional "all-available-cache" partitioning.
  • Optimality: The gap between the GLS heuristic and the mathematical optimum (IQCP) was a negligible 0.79%.
  • Performance: For systems with 64 tasks, GLS and BB methods were ten times faster than the IQCP solver.

While currently focused on single-core architectures, the principles lay the groundwork for multi-core systems where shared cache interference is more complex. Future research will explore hybrid scheduling models and the integration of memory bandwidth constraints to further optimize hardware resource utilization.

Summary updated

BibTeX
@inproceedings{sun2023minimizing,
  author = {Binqi Sun and Tomasz Kloda and Sergio Arribas García and Giovani Gracioli and Marco Caccamo},
  title = {{Minimizing Cache Usage for Real-time Systems}},
  booktitle = {RTNS},
  year = {2023},
  doi = {10.1145/3575757.3593651},
}
Figure