Analyzing Throughput for Cyber-Physical Systems modeled with Synchronous Dataflow

Philippe Glanon, Selma Azaiez, Chokri MraidhaCPS Summer School, PhD Workshop 2019

TL;DR

This paper tackles the critical challenge of maximizing the performance (throughput) of Cyber-Physical Systems (CPS) by proposing a novel mathematical model for scheduling and mapping their computational tasks onto heterogeneous platforms. By transforming CPS applications into a specific graph representation (Linear Constraint Graph), the authors lay the groundwork for optimizing execution order and resource allocation to achieve the highest possible processing frequency.

What Problem Does This Paper Address?

Cyber-Physical Systems (CPS) are complex, distributed systems where components like sensors, controllers, and actuators are tightly integrated and communicate to interact with the physical world. A key performance metric for CPS is throughput, which essentially measures how much work the system can accomplish per unit of time. Ensuring high throughput is crucial for CPS to meet real-time deadlines and operate effectively.

However, analyzing and optimizing this throughput at design time is challenging due to several factors:

  • Heterogeneous Platforms: CPS often run on platforms with diverse processing units and communication links, each with different performance characteristics.
  • Complex Dependencies: The computational tasks within a CPS have intricate dependencies, often forming cyclic graphs.
  • Resource Allocation: Deciding when and where each task should execute on the available heterogeneous resources to maximize overall system speed is a complex optimization problem.

Existing methods often struggle with cyclic task graphs or assume homogeneous platforms, leaving a gap in analyzing and optimizing throughput for realistic, heterogeneous CPS.

Methods

The paper proposes a systematic approach to analyze CPS throughput:

  1. Modeling CPS Applications with Synchronous Dataflow Graphs (SDFGs): The authors leverage SDFGs, a formal model of computation well-suited for systems where performance is paramount. SDFGs represent computations as "actors" (nodes) and data flow between them as "channels" (arcs), with defined production and consumption rates.
  2. Transformation to Linear Constraint Graphs (LCGs): To handle the cyclic nature of many CPS task graphs, the SDFGs are transformed into equivalent LCGs. LCGs are a more compact representation that captures precedence constraints between task firings, even in the presence of cycles. This transformation is crucial because many scheduling algorithms are designed for Directed Acyclic Graphs (DAGs).
  3. Formalizing the Scheduling and Mapping Problem: The core contribution is a mathematical model that defines the problem of scheduling and mapping LCGs onto a heterogeneous CPS platform. This model includes:
  4. Variables: Defining task start times, resource assignments, and the minimal iteration period (which is inversely related to throughput).
  5. Constraints: Ensuring each task is mapped to exactly one device, respecting precedence relations, and limiting task completion times within the iteration period.
  6. Objective Function: Minimizing the iteration period (Y) to maximize throughput (λ = 1/Y).

Datasets

Not discussed in the paper. The paper focuses on a general modeling and formulation approach rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • SDFGs as a Foundation: Using SDFGs provides a robust, formal basis for analyzing the timing behavior of CPS applications, especially those with strict performance requirements.
  • LCGs for Cyclic Dependencies: The transformation of SDFGs into LCGs is a key step that allows the application of scheduling techniques to cyclic task graphs, which are common in real-world CPS.
  • Unified Scheduling and Mapping Model: The paper presents a unified mathematical model that simultaneously addresses both the scheduling (when tasks execute) and mapping (where tasks execute) problems on heterogeneous platforms. This integrated approach is essential for true optimization.
  • Throughput as Iteration Period Minimization: The insight that maximizing throughput is equivalent to minimizing the iteration period of the LCG provides a clear objective for the optimization problem.

Key Results

The paper does not present empirical results or quantitative performance improvements. Instead, its key contribution is the formalization of the problem and the proposed mathematical model for scheduling and mapping CPS tasks onto heterogeneous platforms to maximize throughput. The paper outlines the structure of the model, including objective function and constraints, and suggests a resolution method by splitting the problem into sub-problems.

Limitations and Future Work

The authors acknowledge that the proposed problem is NP-complete, meaning finding an optimal solution can be computationally very expensive for large systems.

Future work directions highlighted include:

  • Transforming LCGs to DAGs: Developing an efficient algorithm to convert cyclic LCGs into DAGs while preserving their semantics, enabling the use of existing DAG scheduling heuristics.
  • List-Scheduling Heuristics: Designing and implementing efficient list-scheduling heuristics for mapping the transformed DAGs onto heterogeneous CPS platforms.
  • Empirical Evaluation: Comparing different heuristic approaches to determine which ones provide the optimal throughput for various LCG instances.

Summary updated

BibTeX
@inproceedings{glanon2019analyzing,
  author = {Philippe Glanon and Selma Azaiez and Chokri Mraidha},
  title = {{Analyzing Throughput for Cyber-Physical Systems modeled with Synchronous Dataflow}},
  booktitle = {CPS Summer School, PhD Workshop},
  year = {2019},
}
Figure