Data-flow graph

The model functions are deflned in two stages. First, formal models according to usual representations of hardware behaviour at the speciflc levels are introduced (data flow graph and register transfers, resp.). Second, it is deflned how values are computed from these representations. After that, we deflne when a register transfer model correctly implements a data flow model the execution of the two models must result in the same values for corresponding output objects (data flow variables and registers, resp.). 

The value of an assigned variable is computed by applying the binary function of the assigning operation to the values of the operand variables. The value of an input variable is symbolically defined using the function varinit VARS dfvalue. The recursion is well founded because the DAG property of data flow graphs prevents cyclic data dependencies. 

Correctness is defined with respect of the final results of evaluating a data flow graph and executing register transfers. cs max is the control step of the last completion of a register transfer (cs-max is part of rtm). After this control step the values of the registers associated with output variables must implement the values of these output variables. 

Most of the current design models are not suitable for the real-time signal processing domain and do not deal with the above requirements. At the start of the Ascis project, there was a clear need to fill this gap. This has led to the Ascis data flow-graph (DFG) model described in chapter 2. It differs... 

Verification has also been performed directly on the DFG [17]. This is a highly interesting perspective, since data flow graphs are widely used as the starting point for synthesis. The verification here is a more global data-independent scope, allowing the verification of much larger systems at the cost of a reduced resolution detailed, data-dependent functional behavior is not modeled. 

Data flow graphs are a suitable starting point for architectural synthesis, since they allow maximal freedom in exploiting area/time tradeoffs and do not impose real restrictions towards different design styles. 

Unlike many designer-oriented specifications, data flow graphs are semantically clean and simple, thus forming an unambiguous behavioral definition suitable to interface to or exchange between synthesis packages, as well as to formal verification. 

Various optimization tools that perform manipulations at the data flow graph level become generally available in the synthesis projects. 

The next section will treat the data flow graph standard, as developed in the Ascis project, with topics like design criteria, allowed graph structures, semantics, syntax, and later extensions. Section 3 discusses designer-oriented specification languages. It will focus on the suitability of Vhdl and a newly developed Vhdl subset for high-level synthesis. 

The data flow graph model for the Ascis project [16] is based on earlier work at the Eindhoven University of Technology both theoretical work [17] and the application in synthesis [14]. The model was designed to combine a unique set of features, which set it apart from other approaches [5, 12, 19] ... 

The data flow graphs are allowed to contain conditionals as well as loop constructs. A token flow semantics is responsible for a concise behavioral model, without the need for additional external control information. Having conditionals and loops coherently represented in the data flow graph allows synthesis programs to perform several global optimizations, uninhibited by block boundaries, as are imposed by most other representations. 

A data flow graph is a graph where each node represents an operation, and the edges represent the transfer of values between the nodes. The edges attach at ports of the nodes. The ports are either input ports or output ports. The behavior of a node is defined as a behavior between its ports. A crucial property of the data flow graph is that each input port has precisely one edge attached to it, whereas the number of edges on an output port is left free. 

Figure 2 The swap algorithm and its data flow graph.

Figure 3 Simple expressions and their data flow graphs.

As explained in the previous section, the data flow graph has an executional... 

G. G. de Jong. Generalized data flow graphs theory and applications. To appear as PhD thesis, Eindhoven Univ. of Tech., Eindhoven, The Netherlands, 1993. 

J. T. J. van Eijndhoven, G. G. de Jong, and L. Stok. The ASCIS data flow graph semantics and textual format. Technical report 91-E-251, Eindhoven University of Technology, Jun 1991. 

Compilation of the source HDL into an internal representation, usually a data flow graph and/or a control flow graph. This step is very similar to the compilation of a programming language. 

The data-flow graph (DFG) is also a directed graph. The nodes represent the data (variables and signals) and the operations (shown as circles). The directed edges indicate the direction of the data flow. For example, operation 5 (an addition) reads IN2 and D as inputs, and writes A as its output. The given graph represents the complete data flow in later sections it will be shown that for certain applications it can be combined with the CFG and significantly simplified. Note that the DFG may be disconnected, as shown by operator 2. 

G. Borriello, "Combining Event and Data-Flow Graphs in Behavioral Synthesis, Proceedings of the ICCAD 88, pp. 56-59, Santa Clara, Ca, November 1988. 

Internal Behavioral Representation A data flow graph. 

The DSL language, mapping onto a data flow graph, data path synthesis, control step scheduling, a decoder example, a priority encoder example, and the MC6800iO. 

The Value Trace [Snow78] is an internal control and data-flow graph representation of ISPS. This graph represents behavior in terms of operators that correspond to ISPS operators and the values that pass between them. Operators are represented by nodes in the graph. They perform a function on their inputs and produce one or more outputs. Operator inputs and outputs are connected to other operator inputs and outputs by directed edges that represent values. Each value represents an individual value of an ISPS variable or intermediate expression. Since variables may be assigned several values in an ISPS description, there may be several values for each ISPS variable. 

In the absence of a static evaluation of the data flow graph, the probability of control passing through all clusters in a given procedure is simplified to be equivalent. Therefore the probability of any one cluster being activated at any time is approximated by the product of the probability that the procedure it is in is will be activated and the number of clusters in that procedure. Thus if cluster a is in procedure A, the probability of cluster a being activated is estimated by... 

---