Dynamic Reconfiguration of Two-Level Cache Hierarchy in Real-Time Embedded Systems

Weixun Wang, Prabhat MishraJ. low Power Electron 2011 · DOI

TL;DR

This paper tackles the challenge of dynamically reconfiguring two-level cache hierarchies in real-time embedded systems to optimize energy efficiency without compromising timing constraints. The authors propose a novel methodology combining static analysis with efficient exploration heuristics to identify optimal cache configurations for different task phases, achieving significant energy savings.

What Problem Does This Paper Address?

Real-time embedded systems, often battery-powered, face a critical trade-off between energy consumption and performance, especially concerning the memory hierarchy. Caches, while crucial for performance, are significant energy consumers. Dynamic reconfiguration of caches offers a promising avenue for energy savings by adapting cache parameters (size, associativity, line size) to the specific needs of running applications. However, applying this to real-time systems is challenging due to strict timing constraints. Existing approaches often focus on single-level caches or lack mechanisms to handle the complex interdependencies and vast configuration space of two-level hierarchies in a way that respects real-time deadlines. This paper aims to bridge this gap by providing a systematic approach to dynamically reconfigure two-level caches in soft real-time systems.

Methods

The core of the proposed methodology involves two main components:

  • Phase-Based Static Profiling: Each task is divided into "phases" based on potential preemption points. For each phase, the authors statically analyze and profile various cache configurations to determine their energy and performance impact. This profiling generates a "profile table" that stores optimal configurations for each phase.
  • Efficient Design Space Exploration Heuristics: The enormous configuration space of two-level caches (IL1, DL1, L2) makes exhaustive exploration infeasible. The paper introduces four heuristics to efficiently explore this space:
  • SLOT (Same Level One Cache Tuning): Explores all L2 configurations while keeping IL1 and DL1 caches at the same configuration.
  • TST (Two-Step Tuning): Iteratively tunes each cache level (IL1, DL1, L2) by considering Pareto-optimal configurations.
  • ILOT (Independent Level One Cache Tuning): Leverages the observed independence between IL1 and DL1 to reduce exploration by tuning them together while L2 is fixed.
  • ILT (Interlaced Tuning): Tunes cache parameters in an order of importance (size, line size, associativity), combining exploration of L2 size and associativity.
  • Scheduling-Aware Reconfiguration Algorithm: A runtime algorithm that uses the static profiling results to select the appropriate cache configuration based on the current task, its priority, and the schedulability of other tasks in the system. This algorithm ensures that energy-optimal configurations are chosen only when they do not violate real-time deadlines.

Datasets

The authors evaluated their approach using six benchmarks from MediaBench, MiBench, and EEMBC suites. These benchmarks were chosen for their suitability for embedded systems and cache configuration analysis. They were organized into seven task sets, with tasks within each set having comparable sizes to avoid dominance by a few large tasks. The paper does not introduce new benchmarks but uses existing ones.

Key Insights and Ideas

  • Two-level cache interdependence: While IL1 and DL1 might appear independent, their interactions through the L2 cache and their impact on overall execution time and static power consumption mean that optimizing them separately doesn't always guarantee a global optimum.
  • Heuristics are crucial for scalability: The vast configuration space of two-level caches necessitates efficient exploration heuristics. Exhaustive search is computationally prohibitive, making heuristics like SLOT, TST, ILOT, and ILT essential for practical application.
  • Trade-off between exploration efficiency and optimality: Heuristics offer significant speedups in exploration but may not always find the absolute optimal configuration. The choice of heuristic depends on the available design time and the desired balance between energy savings and performance.
  • Dynamic reconfiguration is viable for real-time systems: By carefully integrating static profiling with a scheduling-aware runtime algorithm, it's possible to dynamically reconfigure caches in real-time systems without jeopardizing deadlines.

Key Results

  • The proposed heuristics significantly reduce the design space exploration time compared to exhaustive search. For example, exhaustive exploration for "qsort" took over 5 days, while ILT took only 44 minutes.
  • The approach achieves substantial energy savings, with results showing up to 40-58% energy savings for the cache hierarchy compared to a base configuration.
  • On average, the heuristics achieved significant energy savings: SLOT (56%), TST (52%), ILOT (46%), and ILT (40%), all comparable to or better than the exhaustive approach in terms of energy savings.
  • In terms of performance, SLOT and TST consistently found performance-optimal or near-optimal configurations, while ILOT struggled in this aspect. ILT, despite its small exploration space, was also not as effective in finding performance-optimal configurations.

Limitations and Future Work

  • Assumption of independent Pareto-optimal sets: The TST heuristic assumes that the Pareto-optimal configuration sets for individual caches are independent. The paper acknowledges that this assumption doesn't always hold, as a less energy-efficient L1 cache might lead to fewer L2 accesses, potentially making a better L2 cache more beneficial.
  • Heuristic performance variation: The effectiveness of heuristics varies across benchmarks and for different objectives (energy vs. performance). For instance, ILOT performed poorly in finding performance-optimal configurations.
  • Future work: The authors suggest that their approach would be even more valuable in multi-core scenarios where the design space is even larger. Designers can choose heuristics based on their profiling time budget and expected energy savings.

Summary updated

BibTeX
@article{wang2011dynamic,
  author = {Weixun Wang and Prabhat Mishra},
  title = {{Dynamic Reconfiguration of Two-Level Cache Hierarchy in Real-Time Embedded Systems}},
  journal = {J. low Power Electron},
  year = {2011},
  doi = {10.1166/jolpe.2011.1113},
}
Figure