sdf.tex

\subsection{Synchronous Dataflow}\label{sec:sdf} % Guillaume

\begin{figure}[!h]
\begin{lstlisting}[morekeywords={node,int,bool,returns,var,when,let,tel,current}]
node tracker (speed, limit: int) returns (t: int);
var x: bool; cpt: int when x;
let
  x = (speed > limit);
  cpt = counter((0, 1) when x);
  t = current(cpt);
tel
\end{lstlisting}
\vspace*{-4mm}
\caption{\label{fig:lustre} Lustre code example.}
\end{figure}

Synchronous dataflow (SDF) languages were introduced to ease the design of
real-time embedded systems. They allow programmers to write a well-defined
deterministic specification of the system. It is then possible to
test, verify, and generate embedded code.
The first data\-flow synchronous languages \textsf{Lustre}~\cite{lustre_1987}
(Caspi and Halbwachs) and \textsf{Signal}~\cite{signal_1991} (Le Guernic,
Benveniste, and Gautier) were proposed in France in the late 1980s.
A dataflow synchronous program is a set of equations defining streams
of values. Time proceeds by discrete logical steps, and at each step,
the program computes the value of each stream depending on its inputs
and possibly previously computed values.
This approach is reminiscent of block diagrams, a popular notation to
describe control systems.
Figure~\ref{fig:lustre} presents a Lustre code example that tracks the
number of times the speed of a vehicle exceeds the speed limit. The
counter \lstinline{cpt} starts with~$0$ and is incremented by~$1$ each
time the current speed exceed the current limit (\lstinline{when x}).
The return value \lstinline{t} maintains the last computed value
of \lstinline{cpt} between two occurrences of~\lstinline{x}
(\lstinline{current(cpt)}).

Compared to the other languages presented here, SDF languages are
relatively low level and target embedded controllers. The focus is on
compiling efficient code that executes in bounded memory with a
predictable execution time.  In particular, this imposes that the
schedule and communication rates can be statically computed by the
compiler. Additional static analyses reject programs with potential
initialization or causality issues. Compilers produce imperative code
that can be executed in a control loop without communication buffers
triggered by external events or on a periodic signal (e.g., every
millisecond). The link between logical and real time is left to the
designer of the system.

The dataflow synchronous approach has inspired
multiple languages: \textsf{Lucid Synchrone}~\cite{lucid_2006} combines the
dataflow synchronous approach with functional features \`a la ML,
\textsf{StreamIt}~\cite{thies_et_al_2002} focuses on efficient parallel processing of large
streaming applications, and \textsf{Z\'elus}~\cite{zelus_2013} is a Lustre-like
language extended with ordinary differential equations to define
contin\-uous-time dynamics. Lustre is also the backbone of the
industrial language and compiler \textsf{Scade}~\cite{scade_2017} routinely
used to program embedded controllers in many critical applications.