Platform-Specific Code Generation from Platform-Independent Timed Models

BaekGyu Kim, Lu Feng, Oleg Sokolsky, Insup Lee

TL;DR

This paper tackles the challenge of generating code from timed system models that reliably meets strict timing constraints when deployed on real-world embedded platforms. They propose a model transformation technique that uses Integer Linear Programming (ILP) to automatically adjust timing parameters, compensating for platform-specific processing delays and ensuring the implemented system behaves as intended.

What Problem Does This Paper Address?

Developing safety-critical real-time embedded systems, like those in automotive or medical devices, requires strict adherence to timing constraints. These systems often use model-based development, where a system's behavior is first modeled and then automatically translated into code. A major hurdle is that the generated code, when run on a specific hardware platform (including its operating system and drivers), can exhibit different timing behavior than the original model predicted. This is because platforms introduce their own processing delays for handling inputs and outputs, which are often not accounted for in the initial, platform-independent models. Consequently, timing constraints verified at the modeling stage might be violated in the final implementation, potentially leading to catastrophic failures. The paper aims to bridge this gap by ensuring that the generated code, when deployed, respects the timing guarantees established during the modeling phase.

Methods

The core of the paper's contribution is a model transformation approach that adjusts timing parameters within the system model to account for platform delays. This process involves two main steps:

  1. Delay Analysis: The authors first define methods to compute the minimum and maximum delays between input/output (I/O) events within the original system model ($f_M$) and how these delays would manifest in the final implementation ($f_{IMP}$), considering platform processing delays ($P$).
  2. Integer Linear Programming (ILP) for Compensation: They then formulate an ILP problem to find optimal timing parameter assignments for a software model ($M_C$). This software model is derived from the original system model ($M_S$) but explicitly compensates for the platform's processing delays. The ILP solver determines these parameters by satisfying a set of linear constraints that enforce the "delay-bound inclusion constraint" – ensuring that the implementation's timing bounds are within the system model's verified bounds. The objective function of the ILP is designed to maximize the "room" for computation within the code, thus allowing for more robust timing behavior.

The approach handles different model structures (sequential, alternative, cyclic) and different I/O event patterns.

Datasets

The paper does not introduce new datasets for training. Instead, it uses a case study of infusion pump systems to demonstrate the effectiveness of their approach. The platform-specific processing delays for the Baxter II Syringe PCA infusion pump platform were measured using an oscilloscope, providing real-world data for the platform delay parameters ($P$).

Key Insights and Ideas

  • Platform-Independent Models are Insufficient for Timing Guarantees: The paper strongly argues that models designed without considering platform-specific delays cannot guarantee timing constraints in the final implementation. The "ideal" infinite speed of I/O processing assumed in many models is unrealistic.
  • Model Transformation is Key: Simply generating code from a model that mentions platform delays isn't enough. A proactive transformation of the model itself is needed to compensate for these delays.
  • ILP as a Powerful Tool for Timing Parameter Optimization: The authors demonstrate that ILP is a suitable mathematical framework for finding optimal timing parameter adjustments that satisfy complex delay-bound constraints across various system components and platform characteristics.
  • Maximizing Computational "Room": The objective of the ILP is not just to meet constraints but to maximize the uncertainty range of the implementation ($Δ_{IMP}$) to be as close as possible to the system model's range ($Δ_M$). This allows for more flexibility and computation time within the generated code.

Key Results

The paper's primary result is the successful demonstration of their model transformation approach on an infusion pump system.

  • Preservation of Timing Constraints: Experimental results showed that systems implemented with code generated from the transformed software models ($M_C$) significantly better preserved the timing constraints compared to code generated directly from the original system models ($M_S$). Figures 10, 11, and 12 visually depict this, showing that the adjusted implementation delays fall within the model's bounds, while the unadjusted ones often exceed them.
  • Feasibility Check: The ILP formulation can also determine if it's possible to meet the timing constraints for a given platform. In some examples, the solver found no feasible parameter assignment, indicating that the platform's delays were too extreme for the system's requirements.

Limitations and Future Work

  • Scope of Models: The current ILP formalization is primarily detailed for acyclic models, with extensions discussed for cyclic models. Future work aims to study a broader scope of modeling patterns.
  • Distributed Systems: The current approach focuses on single platforms. Future work plans to extend the framework to distributed systems, which involves more complex platform-processing delays (e.g., network delays) and requires new transformation strategies.
  • Refined Optimality Notions: The paper acknowledges that more sophisticated optimality criteria could be defined beyond maximizing uncertainty range, potentially leading to more complex objective functions.
  • Generalization of Metrics: The authors suggest that their delay-bound inclusion constraint could be complemented by more refined metrics for reasoning about model-implementation mismatches, which they leave for future work.

Summary updated

Abstract

Many safety-critical real-time embedded systems need to meet stringent timing constraints such as preserving delay bounds between input and output events. In model-based development, a system is often implemented by using a code generator to automatically generate source code from system models, and integrating the generated source code with a platform. It is challenging to guarantee that the implemented systems preserve required timing constraints, because the timed behavior of the source code and the platform is closely intertwined. In this paper, we address this challenge by proposing a model transformation approach for the code generation. Our approach compensates the platform-processing delays by adjusting the timing parameters in system models, based on an Integer Linear Programming problem formulation. We demonstrate the usefulness of our approach via a case study of infusion pump systems. Experimental results show that the code generated using our approach can better preserve the timing constraints.
BibTeX
@inproceedings{kim2015platform,
  author = {BaekGyu Kim and Lu Feng and Oleg Sokolsky and Insup Lee},
  title = {{Platform-Specific Code Generation from Platform-Independent Timed Models}},
  booktitle = {RTSS},
  year = {2015},
  doi = {10.1109/rtss.2015.15},
}

Loading related content...

Figure