A Short Note on POLIS and timing semantics
by Ellen Sentovich
Background: system connectivity and communication
A system is typically modeled as a network of communicating modules. One must define the semantics of intra- and inter-module communciation.Communication can be summarized by two components: the data, which is stored in a common buffer (or register, wire, variable, or a set of these), and the timing, which gives information about when this data is read and written.
The synchronous hypothesis assumes that computations take zero time. That is, at a point in time called an instant, a synchronous module reads its inputs, performs its computation, and writes its outputs all at once. The time in between instants is infinite, since there is no interaction between instants (input n arrives an infinitely long time after input n-1). The behavior of a synchronous system is a stream of input/output pairs, where one pair is associated with each instant.
Communication in a synchronous system then implies that all modules read and write to a common shared memory. The time to read/write is zero, while the time between read/writes is infinite.
Implications of the model:
In a real implementation, computations do not really take zero time, nor is the delay between computations infinite. A computation takes negligible time with respect to the actions going on in its environment. Therefore, the environment sees a module that computes in zero time, and the module sees an environment that takes infinite time in between input values. This assumption on relative delays between module and environment must be checked on the synthesized implementation. In hardware, the global synchronous clock must be run slow enough for each module to complete its computation in between clock ticks. In software, a synchronous module that is called by the operating system must be allowed to complete its reaction before its inputs are changed (for example, by another module).
Ordering: There is no ordering of reading of inputs, computations, or writing of outputs (except that an output is only written after the computations upon which it depends have been performed, and a computation is only performed after the inputs upon which it depends have been read). An ordering can be imposed, but this is not part of the model.
Determinism: Implementation usually requires a determinate solution: each output must be able to be determined uniquely from the input. This is also not part of the model.
Causality: Interpretation (that is, construction of an interpreter for simulation) of a synchronous program requires in addition that the program be constructively causal. Causality is out of the scope of this document.
Esterel: Esterel is both a synchronous language and a compiler for that language. An Esterel system is composed of interacting synchronous modules. Inter-module communication is through signals. Each module has a set of input and output signals, which are read and written instantaneously and in no particular order (i.e., the senders and receivers of those signals cannot depend on a particular order). Intra-module communication is through internal signals and internal variables. Computations based on variables can be ordered, and hence information stored in variables cannot be communicated between concurrent blocks (exception: a variable can be read by several modules in the branches of a parallel statement). The operation of a system begins in a defined main module and begins executing statements, possibly branching and executing concurrently. At each instant, execution is carried out in each active concurrent branch until a halt statement is reached. Execution continues at the next statement. Execution always involves an instantaneous, unordered, read/compute/write cycle. A design may be specified as a set of modules, but all communication (intra- and inter-module) is synchronous, so a set of synchronous modules has an equivalent single module representation. Thus, any system can be thought of as a single finite state machine, though it may not be implemented as such.
In an asynchronous model, assumptions made about the timing, relative or absolute, of any signals, variables, or computations are more complex. In the purest form of asynchrony, called delay insensitive, the goal is to generate a correct design regardless of delays on computation elements (in hardware, gates) or communication channels (in hardware, wires). It has been proven that no circuits of practical interest can be designed without tighter restrictions to the mode or a proliferation of computational elements. Several sets of restrictions have been proposed, and synthesis techniques developed for these. These take the form of restrictions on the application of inputs by the environment and the timing of the access to shared information. In hardware, this latter form of delay may be pure or inertial, bounded or unbounded, integer or continuous, applied to feedback wires or non-feedback wires or gates. The most restrictive case is precisely that of synchrony: the delays are fixed and known for each gate and wire, and there is an infinite delay element on (at the least) each feedback wire.
Implications of the model:
A typical delay model in an asynchronous system assigns each gate and/or wire an up-bounded inertial delay: this allows a variable delay, and allows the modeling of lost event pulses, both of which are necessary to model real systems.
The notion of delay is completely loose. Communication is event-based since there is no global clock with which to synchronize different communicating modules. Thus, nothing happens in an asynchronous system or module until some event triggers a reaction. This reaction takes an unspecified amount of time, and outputs events which trigger further reactions.
Consider a synchronous system operating in its environment. At each synchronous instant, the system reacts "instantly", but note that this reaction could in fact be composed of a series of events or actions. These are called microsteps. For example, the new signal values may be written in several different orders. An implementation may be devised to take advantage of the ordering during microsteps. This is not part of the synchronous model, but can be used in addition to it for optimization purposes.
All correct implementations of a synchronous program a la Esterel are required to have the same instant-to-instant behavior, although the microstep behavior may be different. That is, the choice of ordering at the microstep level is not observable at the instant level.
With Statecharts, which is not a fully synchonous model, several correct implementations may have observable differences at the instant level that come from differences in microstep ordering.
The synchronous model deals with two types of delay: zero, where everything happens at once, and infinite, where actions are completely separate. The asynchronous model deals with one type of delay which is both non-zero and finite. It is typically up-bounded. Differences in simulations of two systems, where one is assuming synchronous communication and the other asynchronous, can be attributed to these three different notions of delay.
A synchronous system may be slower, since a "clock" must be run at the rate of the slowest module.
Why use synchrony? It is easier to design and verify modules, many systems are not time critical and can afford a synchronous implementation, and many systems are in fact naturally synchronous.
Why use asynchrony? The real world is asynchronous and thus any interface to it will be asynchronous, for time or power critical applications a single global clock is unacceptable, and for some systems, such as distributed heterogeneous systems, restrictions to synchrony are too cumbersome (e.g., the same control structure must be executed on all processors, and only data computations completely separate from control can be distributed).
POLIS uses the GALS model of timing and synchronization. That is, a POLIS network consists of nodes (called CFSMs) of synchronous modules that interact through an asynchronous network. Stated in another way the Globally Asynchronous part is the network, and the Locally Synchronous part is the set of synchronous nodes.
Implications of the model:
Local synchrony means that each module reads/computes/writes as though it were in a synchronous network: in zero time, and with an unordered input/output set. Global asynchrony means that as soon as a module stops to wait for a signal, the delay in waiting is completely indeterminate. In the fully synchronous world, an atomic delay is an instant, and all modules are delayed by the same amount. With global asynchrony, a module waits until it is again triggered by one of its inputs. This triggering could happen at any time in the future.
The operation of the GALS system proceeds as follows. The asynchronous network determines when to call each node to make a computation. This is event-driven. Once a node is called, its reaction is synchronous: it reads, computes, and writes at once, returning control to the asynchronous network. Seen from the network, this takes time: inputs are read over a period of time (so if they are changing the behavior is difficult to predict), computations are performed over a period of time, and outputs are written over a period of time (so if they are read too early by the network or some other module it calls, behavior is difficult to predict). Seen from the node, this takes no time: it computes based on a single atomic set of inputs (that it thinks occurred at once), and reacts instantaneously.
At the very moment a synchronous node communicates with its environment, which is the rest of the network, the communication is asynchronous. Even if that node is the only one in the network, if it communicates with itself through the asynchronous network, this will be an asynchronous communication. As a result, the simulation of a set of Esterel modules will usually differ in the Esterel simulator (which assumes synchronous communication between modules) and the POLIS simulator (which assumes asynchronous communication). Even with a single module, simulation results could be different.
One very nice property of Esterel synchronous systems and POLIS GALS systems is that they have finite state, and thus the rich set of tools for analysis and optimization of finite state systems can be applied. This is particularly important for verifying properties of the system.
In Esterel, the system state-to-state boundary is based on the clock tick: the system changes state at each tick, and any two synchronous programs are equivalent if they have the same tick-to-tick behavior. Properties can be verified based on state trajectories. Though two systems may have different micro-step or micro-state behavior, this is not visible outside according to the model.
In POLIS, the system state-to-state boundary is based on the event-based execution of CFSMs: every time a single CFSM in hardware or software is executed, it reads/computes/writes and thus changes the state of the system. This is a much finer level of granularity, resulting in systems with many more states. Furthermore, the behavior may be more difficult to predict and control, since there is no global clock that all CFSMs are slave to.
There is clearly more flexibility in implementation with the POLIS model, while the Esterel model provides a model that makes it easier to control and predict the behavior of the design. For this reason synchronous implementations have frequently been chosen for safety-critical applications. However, high-speed requirements, and heterogeneous distributed systems must use an asynchronous model.
Simulating Full Synchrony and GALS
We will compare POLIS and Esterel simulations of the same or similar systems to illustrate the differences between the models of fully synchronous communication and GALS . From here onward, we are effectively considering a particular implementation of a written synchronous program: a full software implementation with a particular semantics to the environment that is described below. Behavior will be different for other implementations.
We consider several single module (node) systems attached to a simple environment module. In POLIS, two C-files are generated for the system: one for the module itself and one for the operating system that is responsible for calling the module whenever it is triggered. Compiling these files results in an executable simulator. In Esterel, a single C-file is generated for the module (the same holds true if there is a set of modules). This file is compiled and linked to a simulation library which is responsible for reading user input, calling all modules for the execution, and writing user output at each instant.
To simulate the systems, the user provides a set of inputs and then reads the corresponding outputs. We call this a simulation reaction. In Esterel, this is equivalent to a single instant. In POLIS, reactions are event-triggered and there is no global notion of instant (since the term instant applies only to a single synchronous module, each module has its own schedule of instants). A simulation reaction then is the successive calling of all CFSMs that have been triggered, until there are no remaining runnable CFSMs. In other words, a simulation reaction is a set of instants of CFSMs, and in particular, it may include multiple instants or calls of a CFSM. (This is like a VHDL step.) It is important to keep this point in mind: the simulator interface requires that we create a rather artificial schedule of time points at which we observe the system.
In Esterel, all modules react at every instant, so new outputs can be produced without a triggering input. In POLIS, all reactions are event-triggered, so with no input events, no output events will be produced (except in the case where a module is self-triggering; this can be used, for example, to ensure that one event happens after another, to order events).
In our examples, we use the Esterel language as input for both Esterel and POLIS. Esterel has a well-defined set of constructs for writing a program describing a system, including convenient statements for sequencing, concurrency, and pre-emption. The most important family of statements in the Esterel language for our purposes are those relating to delay. Once again, an atomic delay in Esterel is a single instant, while an atomic delay in POLIS is undefined and depends on the system implementation. Thus, the statement await tick; in Esterel means wait until the next instant to continue executing. The same statement in POLIS also means wait until the next instant, though this may happen in the same simulation reaction, depending on the simulator (in our simulator, it will be in the same reaction). In other words, this statement means return control to the operating system, but make sure that control comes back to this CFSM eventually (this is self triggering). Similarly, the statement await SIG; in Esterel means wait until the next instant that SIG is present. In POLIS, it means return control to the operating system, and don't trigger this CFSM again until SIG is present (which again could be in the same simulation reaction).
Finally , note some simple differences between Esterel and POLIS:
Consider the following module with its surrounding network environment.
The POLIS system is composed of module NODE and net POLIS_NETWORK; the Esterel system is composed of module NODE and module ESTEREL_NETWORK. We enclose the behavior of interest in an await i, so we can explicitly trigger it, and an emit o, so we can explicitly observe the completion of computation. The network contains input i and output o, and an internal signal a that is used to connect a_in and a_out of NODE. This connection, because i is through the network, is asynchronous in POLIS and synchronous in Esterel.
The simulation of this system in a GALS model yields a completely different result than that of a synchronous simulation. Once the input i has been received, the synchronous implementation emits the internal signal a_out, and though it is connected to a_in through the network, the await a_in statement must wait until the next instant to check for a_out at which time the signal a_out is no longer available. The module then waits forever for a_in (there are no other emitters for this signal). In the GALS model, upon receiving the input i, the module NODE emits the signal a_out and returns control to the network. The network observes that a_out is present, that it is connected to a_in, and that a_in is a trigger for NODE. It schedules NODE to be executed with a_in present. NODE is then executed, and the output o is emitted.
The differences in the two simulations are then
Several other points to note on variations of this example:
In the following example, the await tick construct is used to order the emission of outputs o and p.
The await tick construct in both Esterel and POLIS is a simple direction to stop execution and continue at the next instant, i.e. it is a trigger to continue execution later. The difference is when the continuation takes place. In Esterel, continuation is at the next instant, which is the next simulation reaction. In POLIS, continuation is at the next instant, which is in the same simulation reaction. Therefore, during simulation, upon receiving input i, Esterel produces o immediately and p at the next instant, while POLIS produces o then p immediately. In both cases, NODE is called twice; in Esterel this takes place over two simulation reactions and in POLIS over one.
Conclusions and Hints for System Specification
It should be clear that while system specification for POLIS and Esterel can be done in the same way, via the synchronous language Esterel,
Thus, direct comparison of the two simulations is meaningless. Furthermore, while the behavior of the Esterel simulation mimics the behavior of its implementation (provided the synchronous hypothesis holds on the implementation, and modulo ordering on output signals), the behavior of the POLIS simulation only illustrates one in a set of acceptable behaviors, and thus one possible implementation. Consider the case of multiple modules executing simultaneously, some in hardware and some in software. The input/output behavior of the system can depend on the relative delays of the modules and the way in which they are scheduled. In Esterel, all modules are scheduled at every instant, and thus all modules wait for all others to compute. Of course, this restriction can be placed on a system in POLIS, but this will reduce the possible optimizations.
So is POLIS simulation useless as a verification technique? Certainly not, and lessons learned from comparing POLIS and Esterel simulation outputs can help in writing a specification for POLIS that has more predictable behavior. In general, one must keep in mind the delay model, and hence write a specification that is truly event driven and not based on a specific notion of time. Some general guidelines: