PolyGraph: a data flow model with frequency arithmetic
- PDF / 1,526,406 Bytes
- 29 Pages / 595.276 x 790.866 pts Page_size
- 15 Downloads / 157 Views
STTT Special Issue: FASE 2019
PolyGraph: a data flow model with frequency arithmetic Paul Dubrulle1
· Nikolai Kosmatov1,2
· Christophe Gaston1
· Arnault Lapitre1
© Springer-Verlag GmbH Germany, part of Springer Nature 2020, corrected publication 2020
Abstract Data flow formalisms are commonly used to model systems in order to solve problems of buffer sizing and task scheduling. A prerequisite for static analysis of a modeled system is the existence of a periodic schedule in which the sizes of communication channels can be bounded for an unbounded execution (consistency), and that communication dependencies do not introduce a deadlock in such an execution (liveness). In the context of Cyber-Physical Systems, components are often interfaced with the physical world and have frequency constraints. The existing data flow formalisms lack expressiveness to fully cover the expected behavior of these components. We propose an extension to static data flow paradigms, called PolyGraph, that includes frequency constraints and adjustable communication rates. We show that with these extensions, the conditions for a model to be consistent and live are no longer sufficient, and we extend the corresponding theorems with necessary and sufficient conditions to preserve these properties. We illustrate how PolyGraph can be used in practice on a realistic Advanced Driver Assistance System, and present a framework to check PolyGraph properties in the tool DIVERSITY, along with experiments on realistic and random models. Keywords Dataflow · Real-time · Performance analysis · Formal semantic · Consistency · Liveness · Cyber-Physical System · Data fusion · Advanced Driver Assistance System
1 Introduction Context Cyber-Physical Systems (CPS) are increasingly present in everyday life. In these systems, the components require a certain amount of input data to produce a known amount of output data, and some of them must do so in synchrony with a reference time scale. For example, the next generation of autonomous vehicles will heavily rely on sensor fusion systems to operate the car. Sensors and actuators have specified frequencies. To produce its output, the fusion
B
Paul Dubrulle [email protected]; [email protected] Nikolai Kosmatov [email protected]; [email protected] Christophe Gaston [email protected] Arnault Lapitre [email protected]
1
CEA List, 91191 Gif-sur-Yvette, France
2
Thales Research and Technology, 91120 Palaiseau, France
kernel requires a certain number of samples from several sources, with a temporal correlation between them. Often, when implementing this kind of system, the prediction of its performance is important to the system designers. The performance prediction covers different characteristics of the system, including its throughput, memory footprint, and latency. In distributed implementations of such systems, an analysis of the communications between the components is necessary to configure a network capable of respecting the application’s real-time requirements. Data fl
Data Loading...
