METAMOC: Modular Execution Time Analysis using Model Checking

Andreas Engelbredt Dalsgaard, Mads Chr. Olesen, Martin Toft, René Rydhof Hansen, Kim Guldstrand LarsenWCET 2010 · DOI

TL;DR

This paper introduces METAMOC, a novel method for determining safe and tight Worst-Case Execution Times (WCETs) for embedded systems. By combining model checking with static analysis and modular hardware modeling, METAMOC effectively accounts for complex processor features like caching and pipelining, leading to significantly more accurate WCET estimates.

What Problem Does This Paper Address?

In safety-critical and time-critical embedded systems, guaranteeing that tasks complete within their deadlines is paramount. This requires accurate Worst-Case Execution Time (WCET) analysis. However, modern processors employ complex features like instruction and data caches, and multi-stage pipelines, which significantly complicate WCET analysis. Traditional methods struggle to precisely model these features without either sacrificing accuracy (e.g., overestimating WCETs) or becoming computationally intractable. The challenge is to develop a method that is both precise enough to capture the impact of these hardware features and efficient enough to be practical.

Methods

METAMOC employs a modular approach to WCET analysis, leveraging real-time model checking. The core idea is to build separate, reusable models for different components:

  • Program Model: A Control Flow Graph (CFG) of the program, annotated with information from an inter-procedural value analysis (specifically, constant propagation). This analysis helps determine memory accesses and loop bounds.
  • Hardware Models: Separate UPPAAL models are created for the processor's pipeline (e.g., fetch, decode, execute stages) and its caches (instruction and data).
  • Integration: These program and hardware models are combined into a single UPPAAL model.
  • Model Checking: The combined model is then model-checked to find the longest execution path, which corresponds to the WCET.

The modularity is a key aspect: to support a new processor or pipeline, only the specific hardware component models need to be updated or created, rather than re-analyzing the entire system from scratch. This approach uses UPPAAL, a model checker for real-time systems based on timed automata.

Datasets

The paper evaluates METAMOC using a suite of WCET benchmark programs from the Mälardalen Real-Time Research Centre. These benchmarks are standard for WCET analysis research. The authors specifically mention using 21 programs for the ARM architecture and 19 for the AVR architecture, after discarding programs with floating-point operations, dynamic jumps, or compilation issues.

Key Insights and Ideas

  • Modularity is Key: The paper strongly emphasizes that a modular approach, where program and hardware components are modeled separately, is crucial for retargeting WCET analysis to new processors and for managing complexity.
  • Model Checking for Precision: Contrary to some claims, model checking, when applied with appropriate models, can provide precise WCET estimates, especially when accounting for caching effects.
  • Caching Significantly Impacts WCET: The experiments clearly demonstrate that modeling caches (both instruction and data) leads to substantially tighter WCET bounds compared to analyses that ignore them.
  • Trade-offs Exist: METAMOC offers parameters that allow for trade-offs between analysis precision, memory usage, and analysis time.

Key Results

  • Tighter WCET Estimates: Modeling instruction caching improved WCET estimates by an average of 71.6%, and including data caching further increased this average improvement to 81.3% for the ARM9.
  • Performance: Analysis times were generally reasonable, with average successful analysis times for different configurations ranging from 44.8 seconds to 265.75 seconds.
  • Broad Applicability: METAMOC was successfully applied to 21 ARM benchmarks and 19 AVR benchmarks.
  • Modularity Demonstrated: The method was extended to support ARM7 and ATMEL AVR 8-bit processors with relatively little effort (less than a man-week for each), highlighting the effectiveness of the modular design.

Limitations and Future Work

  • State Space Explosion: For some benchmarks, especially on the AVR architecture, the model checker ran out of memory, indicating limitations in handling very large state spaces. Manual modifications were sometimes required for complex benchmarks on the ARM9 to avoid this.
  • Manual Annotations: Loops require manual annotation of loop bounds, which can be labor-intensive.
  • Future Work: The authors suggest improving model checker technology for parallelization to handle larger programs, exploring abstract cache models for better performance/precision trade-offs, and automatically deducing flow facts (beyond manual annotation) to further enhance the analysis. They also propose incorporating more sophisticated path analysis techniques.

Summary updated

BibTeX
@inproceedings{dalsgaard2010metamoc,
  author = {Andreas Engelbredt Dalsgaard and Mads Chr. Olesen and Martin Toft and René Rydhof Hansen and Kim Guldstrand Larsen},
  title = {{METAMOC: Modular Execution Time Analysis using Model Checking}},
  booktitle = {WCET},
  year = {2010},
  doi = {10.4230/oasics.wcet.2010.113},
}
Figure