21 June 2011 - 14h00
Modeling Synchronous Systems in BIP (Phd Defense)
by VASSILIKI SFYRLA from VERIMAG/UJF
Abstract: A central idea in systems engineering is that complex systems are built by assembling com-
ponents. Components have different characteristics, from a large variety of viewpoints, each
highlighting different dimensions of a system. A central problem is the meaningful composition
of heterogeneous components to ensure their correct interoperation. A fundamental source of
heterogeneity is the composition of subsystems with different execution and interaction seman-
tics. At one extreme of the semantic spectrum are fully synchronized components which proceed
in a lockstep with a global clock and interact in atomic transactions. At the other extreme
are completely asynchronous components, which proceed at independent speeds and interact
non-atomically. Between the two extremes a variety of intermediate models can be defined (e.g.
globally-asynchronous locally-synchronous models).
In this work, we study the combination of synchronous and asynchronous systems. To achieve
this, we rely on BIP (Behavior-Interaction-Priority), a general component-based framework en-
compassing rigorous design. We define an extension of BIP, called Synchronous BIP, dedicated
to model synchronous data-flow systems. Steps are described by acyclic Petri nets equipped
with data and priorities. Petri nets are used to model concurrent flow of computation. Priorities
are instrumental for enforcing run-to-completion in the execution of a step. We study a class of
well-triggered synchronous systems which are by construction deadlock-free and their computa-
tion within a step is confluent. For this class, the behavior of components is modeled by modal
flow graphs. These are acyclic graphs representing three different types of dependency between
two events p and q : strong dependency (p must follow q), weak dependency (p may follow q),
conditional dependency (if both p and q occur then p must follow q).
We propose translation of LUSTRE and discrete-time MATLAB/Simulink into well-triggered
synchronous systems. The translations are modular and exhibit data-flow connections between
components and their synchronization by using clocks. This allows for integration of synchronous
models within heterogeneous BIP designs. Moreover, they enable the application of validation
and automatic implementation techniques already available for BIP. Both translations are cur-
rently implemented and experimental results are provided.
For Synchronous BIP models we achieve efficient code generation. We provide two methods,
sequential implementation and distributed implementation. The sequential implementation pro-
duces endless single loop code. The distributed implementation transforms modal flow graphs
to a particular class of Petri nets, that can be mapped to Kahn Process Networks.
Finally, we study the theory of latency-insensitive design (LID) which deals with the problem
of interconnection latencies within synchronous systems. Based on the LID design, synchronous
systems can be “desynchronized” as networks of synchronous processes that might run with
increased frequency. We propose a model for LID design in Synchronous BIP by representing
specific LID interconnect mechanisms as synchronous BIP components.