Dataflow Process Networks

In dataflow, a program is specified by a directed graph where the nodes (called actors) represent computations and the arcs represent totally ordered sequences (called streams) of events (called tokens). In figure 4(a), the large circles represent actors, the small circle represents a token and the lines represent streams. The graphs are often represented visually and are typically hierarchical, in that an actor in a graph may represent another
directed graph. The nodes in the graph can be either language primitives or subprograms specified in another language, such as C or FORTRAN. In the latter case, we are mixing two of the models of computation from figure 2, where dataflow serves as the coordination language for subprograms written in an imperative host language.
Dataflow is a special case of Kahn process networks [13], [31]. In a Kahn process network, communication is by unbounded FIFO buffering, and processes are constrained to be continuous mappings from input streams to output streams. “Continuous” in this usage is a topological property that ensures that the program is determinate [13]. Intuitively, it implies a form of causality without time; specifically, a process can use partial information about its input streams to produce partial information about its output streams. Adding more tokens to the input stream will never result in having to change or remove tokens on the output stream that have already been produced. One way to ensure continuity is with blocking reads, where any access to an input stream results in suspension of the process if there are no tokens. One consequence of blocking reads is that a process cannot test an input channel for the availability of data and then branch conditionally to a point where it will read a different input. In dataflow, each process is decomposed into a sequence of firings, indivisible quanta of computation. Each firing consumes and produces tokens. Dividing processes into firings avoids the multitasking overhead of context switching in direct implementations of Kahn process networks. In fact, in many of the signal processing environments, a major objective is to statically (at compile time) schedule the actor firings, achieving an interleaved implementation of the concurrent model of computation. The firings are organized into a list (for one processor) or set of lists (for multiple processors). Figure 4(a) shows a dataflow graph, and Figure 4(b) shows a single processor schedule for it. This schedule is a list of firings that can be repeated indefi- nitely. One cycle through the schedule should return the graph to its original state (here, state is defined as the number of tokens on each arc). This is not always possible, but when it is, considerable simplification results [32]. In many existing environments, what happens within a firing can only be specified in a host language with imperative semantics, such as C or C++.
In the Ptolemy system [14], it can also consist of a quantum of computation specified with any of several models of computation, such as FSMs, a synchronous/reactive subsystem, or a discrete-event subsystem [33]. A useful formal device is to constrain the operation of a firing to be functional, i.e., a simple, stateless mapping from input values to output values. Note, however, that this does not constrain the process to be stateless, since it can maintain state in a self-loop: an output that is connected back to one of its inputs.An initial token on this self-loop provides the initial value for the state.
Many possibilities have been explored for precise semantics of dataflow coordination languages, including Karp andMiller’s computation graphs [34], Lee and Messerschmitt’s synchronous dataflow graphs [35], Lauwereins et al.’s cyclo-static dataflow model [36], [37], Kaplan et al.’s Processing Graph Method (PGM) [38], Granular Lucid [39], and others [40], [41], [42], [43]. Many of these limit expressiveness in exchange for formal properties (e.g., provable liveness and bounded memory).
Synchronous dataflow (SDF) and cyclo-static dataflow require processes to consume and produce a fixed number of tokens for each firing. Both have the useful property that a finite static schedule can always be found that will return the graph to its original state. This allows for extremely efficient implementations [32]. For more general dataflow models, it is undecidable whether such a schedule exists [10].
A looser model of dataflow is the tagged-token model, in which the partial order of tokens is explicitly carried with the tokens [44]. A significant advantage of this model is that while it logically preserves the FIFO semantics of the channels, it permits out-of-order execution. Some examples of graphical dataflow programming environments intended for signal processing (including image processing) are Khoros [45], and Ptolemy [14].

Languages

The distinction between a language and its underlying model of computation is important. The same model of computation can give rise to fairly different languages (e.g., the imperative Algol-like languages C, C++, Pascal, and FORTRAN). Some languages, such as VHDL and Verilog, support two or more models of computation7.
The model of computation affects the expressiveness of a language — which behaviors can be described in the language, whereas the syntax affects compactness, modularity, and reusability. Thus, for example, object-oriented properties of imperative languages like C++ are more a matter of syntax than a model of computation. The expressiveness of a language is an important issue. At one extreme, a language that is not expressive enough to specify a particular behavior is clearly unsuitable, but the other extreme also raises problems. A language that is too expressive often raises the complexity of analysis and synthesis. In fact, for very expressive languages, many analysis and synthesis problems become undecidable: no algorithmwill solve all problem instances in finite time. A language in which a desired behavior cannot be represented succinctly is also problematic. The difficulty of solving analysis and synthesis problems is at least linear in the size of the problem description, and can be as bad as several times exponential, so choosing a language in which the desired behavior of the system is compact can be critical. A language may be very incomplete and/or very abstract. For example, it may specify only the interaction between computational modules, and not the computation performed by the modules. Instead, it provides an interface to a host language that specifies the computation, and is called a coordination language (examples include Linda [41], Granular Lucid [39], and Ptolemy domains [14]). Or the language may specify only the causality constraints of the interactions without detailing the interactions themselves nor providing an interface to a host language. In this case, the language is used as a tool to prove properties of systems, as done, for example, in process calculi [46], [47] and Petri nets [48], [49]. In still more abstract modeling, components in the system are replaced with nondeterminate specifica- 7They directly support the Imperative model within a process, and the Discrete Event model among processes. They can also support Extended Finite State Machines under suitable restrictions known as the “synthesizable subset”. tions that give constraints on the behavior, but not the behavior itself. Such abstraction provides useful simplifications that help formal verification.
C. Languages

Heterogeneous Models of Computation

The variety of models of computation that have been developed is only partially due to immaturity in the field. It appears that differentmodels fundamentally have different strengths and weaknesses, and that attempts to find their common features result in models that are very low level, difficult to use. These low level models (such as Dijkstra’s P/V systems [52]) provide a good theoretical foundation, but not a good basis for design. Thus we are faced with two alternatives in designing complex, heterogeneous systems. We can either use a single unified approach and suffer the consequences, or we can mix approaches. To use the unified approach today we could choose between VHDL and C for a mixed hardware and software design, doing the entire design in one or the other (i.e. specifying the software in VHDL or the hardware in C). Or worse, we could further bloat the VHDL language by including a subset designed for software specification (e.g. by making Ada a subset of VHDL). In the alternative that we advocate, we mix approaches while keeping them conceptually distinct, for example by using both
VHDL and C in a mixed hardware/software design. The key problem in the mixed approach, then, is to define the semantics of the interaction of fundamentally different models of computation. It is not simply a problem of interfacing languages. It is easy, for example, to provide a mechanism for calling C procedures from VHDL. But what does it mean if two concurrent VHDL entities call C procedures that interact? The problem is exacerbated by the lack of agreed-upon semantics for C or VHDL. Studying the interaction semantics of mixed models of computation is the main objective of the Ptolemy project [14]. There, a hierarchical framework is used, where a specification in one model of computation can contain a primitive that is internally implemented using another model of computation. The object-oriented principle of information hiding is used to isolate the models from one another as much as possible.

VALIDATION

Validation loosely refers to the process of determining that a design is correct. Simulation remains the main tool to validate a model, but the importance of formal verification is growing, especially for safety-critical embedded systems. Although still in its infancy, it shows more promise than verification of arbitrary systems, such as generic software programs, because embedded systems are often specified in a more restricted way. For example, they are often finite-state. Many safety properties (including deadlock detection) can be detected in a time-independentway using existing model checking and language containment methods (see, e.g., Kurshan [53] and Burch et al. [54]). Unfortunately, verifying most temporal properties is much more difficult (Alur and Henzinger [55] provide a good summary). Much more research is needed before this is practical.

Simulation

Simulating embedded systems is challenging because they are heterogeneous. In particular, most contain both software and hardware components that must be simulated at the same time. This is the co-simulation problem. The basic co-simulation problem is reconciling two apparently conflicting requirements:
_ to execute the software as fast as possible, often on a host machine that may be faster than the final embedded CPU, and certainly is very different from it; and
_ to keep the hardware and software simulations synchronized, so that they interact just as they will in the target system. One approach, often taken in practice, is to use a generalpurpose software simulator (based, e.g., on VHDL or Verilog) to simulate a model of the target CPU, executing the software program on this simulation model. Different models can be employed, with a tradeoff between accuracy and performance:
_ Gate-level models These are viable only for small validation problems, where either the processor is a simple one, or very little code needs to be run on it, or both.
_ Instruction-set architecture (ISA) models augmented with hardware interfaces
An ISA model is a standard processor simulator (often written in C) augmented with hardware interface information for coupling to a standard logic simulator.
_ Bus-functional models These are hardware models only of the processor interface;
they cannot run any software. Instead, they are configured (programmed) to make the interface appear as if software were running on the processor. A stochastic model of the
processor and of the program can be used to determine the mix of bus transactions.
_ Translation-based models These convert the code to be executed on a processor into
code that can be executed natively on the computer doing the simulation. Preserving timing information and coupling the translated code to a hardware simulator are the major challenges.
When more accuracy is required, and acceptable simulation performance is not achievable on standard computers, designers sometimes resort to emulation. In this case, configurable hardware emulates the behavior of the system being designed. Another problem is the accurate modeling of a controlled electromechanical system, which is generally governed by a set of differential equations. This often requires interfacing to an
entirely different kind of simulator.
A. Simulation

Co-simulation Methods

Co-simulation Methods
In this section, we present a survey of some of the representative co-simulation methods, summarized in Table II. A unified approach, where the entire system is translated into a form suitable for a single simulator, is conceptually simple, but computationally inefficient. Making better use of computational resources often means distributing the simulation, but synchronization of the processes becomes a challenge. Themethod proposed by Gupta et al. [56] is typical of the unified approach to co-simulation. It relies on a single custom simulator for hardware and software that uses a single event queue and a high-level, bus-cycle model of the target CPU. Rowson [57] takes a more distributed approach that loosely links a hardware simulator with a software process, synchronizing them with the standard interprocess communication mechanisms offered by the host operating system. One of the problems with this approach is that the relative clocks of software and hardware simulation are not synchronized. This requires the use of handshaking protocols, which may impose an undue burden on the implementation. This may happen, for example, because hardware and software would not need such handshaking since the hardware part runs in reality much faster than in the simulation. Wilson [58] describes the use of a commercial hardware simulator. In this approach, the simulator and software compiled on the host processor interact via a bus-cycle emulator inside the hardware simulator. The software and hardware simulator execute in separate processes and the two communicate via UNIX pipes. Thomas et al. [59] take a similar approach. Another approach keeps track of time in software and hardware independently, using various mechanisms to synchronize them periodically. For example, ten Hagen et al. [60] describe a two-level co-simulation environment that combines a timed and untimed level. The untimed level is used to verify timeindependent properties of the system, such as functional correctness. At this level, software and hardware run independent of each other, passing messages whenever needed. This allows the simulation to run at the maximum speed, while taking full advantage of the native debugging environments both for software and for hardware. The timed level is used to verify timedependent properties, requiring the definition of time in hardware and software. In hardware, time can be measured either on the basis of clock cycles (cycle-based simulation, assuming synchronous operation) for maximum performance, or on the basis of estimated or extracted timing information for maximum precision. In software, on the other hand, time can be measured either by profiling or clock cycle counting information for maximum performance, or by executing a model of the CPU for maximum precision. The authors propose two basic mechanisms for synchronizing time in hardware and software.
1. Software is the master and hardware is the slave. In this case, software decides when to send a message, tagged with the current software clock cycle, to the hardware simulator.
Depending on the relation between software and hardware time, the hardware simulator can either continue simulation until software time or back-up the simulation to software time (this requires checkpointing capabilities, which fewhardware simulators currently have). 2. Hardware is themaster and software is the slave. In this case, the hardware simulator directly calls communication procedures which, in turn, call user software code. Kalavade and Lee [61] and Lee and Rabaey [63] take a similar approach. The simulation and design environment Ptolemy [14] is used to provide an interfacing mechanism between different domains. In Ptolemy, objects described at different levels of abstraction and using different semantic models are composed hierarchically. Each abstraction level, with its own semantic model, is a “domain” (e.g., dataflow, discrete-event).