Automatic Distribution of Synchronous Programs

by Alain Girault

Synchronous languages have recently emerged as a very elegant, safe, and efficient solution for programming embedded systems. The success with which they have been implemented in safety-critical industries is impressive (eg Airbus planes, nuclear plants etc). Scientists at INRIA Rhone-Alpes are currently performing research in the field of automatic distribution of synchronous programs.

Reactive systems are computer systems that react continuously to their environment at a speed determined by the latter. This class of systems contrasts with transformational systems on the one hand (classical programs whose inputs are available at the beginning of their execution, and which deliver their outputs when terminating; eg compilers), and interactive systems on the other (programs which react continuously to their environment, but at their own speed; eg operating systems). Reactive systems include most industrial embedded real-time systems, such as control, supervision, signal-processing, etc.

The synchronous approach has been proposed to ease the design of reactive systems. It is based on the so-called synchronous abstraction. Without entering into details, this is similar to the abstraction made when designing synchronous circuits at the gate level. Concerning the implementation, synchronous programs are embedded in a periodic execution loop, where inputs are read at the beginning of each cycle, before the next state, and the outputs are computed.

There are numerous languages based upon the synchronous abstraction, including data-flow languages (Lustre, Signal, and Lucid Synchrone), imperative languages (Esterel), and graphical languages (Argos and SyncCharts).

Our work deals with the automatic distribution of Esterel programs. The purpose of automatic distribution is, given a centralised source program and some distribution specifications, to build as many programs as required by the distribution specifications. These programs must be able to communicate harmoniously, such that their combined behaviour will be functionally equivalent to the behaviour of the initial centralised source program.

To achieve automatically a distributed implementation of an Esterel program, we first compile it into some intermediate format, and then distribute it according to the user's specifications. The main advantage of this approach is that directly designing a distributed system is always more difficult and error-prone. This explains the recent success of automatic distribution methods. The other advantage of this approach is the ability to debug and formally verify the centralised program before its distribution, which is always easier and faster than debugging a distributed program.

Over the years, a number of compiling methods have been invented for Esterel. These methods vary according to the successive language semantics and the target. More than the compiling method, we are interested here in the format of the target code. Three of these exist, as summarised in the Table above.

In the automaton format, the target program generated by the compiler is a deterministic finite state automaton. This state graph can be cyclic, but in each state there is sequential acyclic code, represented by a directed acyclic graph of actions. With these actions, the program manipulates input, output, and local variables. This internal format is quite general since programs written with a classical imperative programming language can be compiled into it.

In the circuit format, the target program is a sequential circuit, with Boolean gates and registers connected by wires. Some wires are tied to an action in order to manipulate the input, output, and local variables of the program. This control structure is dual to the automaton structure, the internal state being implicitly stored in the registers. Furthermore, it is parallel in the sense that there are several control paths, and dynamic in the sense that the control depends on the data.

In the control points format, the target program is an ordered list of blocks, each block being a sequence of C instructions linked to one control point. The program maintains two ordered lists of control points, one for the current instant and one for the next instant. At the beginning, a number of control points are true, and the first of those is executed. This execution can modify the status of other control points, either later in the same instant, or anywhere in the next instant. The next true control point is then executed, and so on until the end of the list. Finally, the list of control points of the next instant is copied into the list of the current instant. This control structure is parallel in the sense that each block contains C code enhanced with parallel constructs.

We have developed three distribution algorithms for the three target formats of Esterel. They all share a common structure that involves the following steps:

1. Assign a unique computing location to each sequential action, thanks to the designer's specifications. These specifications are a partition of the set of inputs and outputs of the program into N subsets, one for each computing location of the final parallel program.
2. Replicate the program on each location.
3. Prune from the program of each location the actions not belonging to the considered location.
4. Insert send actions in order to solve the data dependencies between any two distinct locations. These data-dependencies were created by pruning the actions during the previous step.
5. Insert receive actions in order to match the sending actions.

The algorithms involved in each of these steps vary according to the control structure of the program (automaton, circuit, or control points).

The communications take place through a fully connected network of FIFO queues. Queues allow send actions to be advanced, and receive actions to be postponed, thereby minimising the waiting time induced by the communication network. The send and receive actions perform both the data-transfer and the synchronisation between the source and the destination locations: when the queue is empty, the receive action is blocking (in contrast, the send action is never blocking). The only requirement on the network is that it must preserve the integrity and the ordering of messages.

These three distribution methods have been successfully implemented and tested:

• The ocrep tool automatically distributes Esterel programs compiled into the automaton format (it also works for Lustre). It acts as a post-processor of the standard Esterel compiler. The user must specify the desired distribution in a separate file.
• The screp tool automatically distributes Esterel programs compiled into the circuit format. It acts as a post-processor of the standard Esterel compiler. The user must specify the desired distribution in a separate file.
• The Saxo-RT tool compiles Esterel programs into the control point format, distributes them automatically, and finally generates one C file for each computing location specified in the distribution.

Links:
Synchronous languages: http://www.synalp.org
Esterel: http://www.esterel-technologies.com

Please contact:
Alain Girault, INRIA
Tel: +33 476 61 53 51
E-mail: Alain.Girault@inrialpes.fr