Q. Write a note on Program models. i) DFG; ii) FSM; iii) Petri-net; i) UML. (Include this in unit 3)

i) Data Flow Graph (DFG):

• The Data Flow Graph (DFG) model translates the data processing requirements into a data flow graph.

• The Data Flow Graph (DFG) is a data driven model in which the program execution is determined by data. This model emphasizes on the data and operations on the data which transforms the input data to output data.

• Indeed DFG is a visual model in which the operation on the data (process) is represented using a block (circle) and data flow is represented using arrows. An inward arrow to the process (circle) represents input data and an outward arrow from the process (circle) represents output data in DFG notation.

• Embedded applications which are computational intensive and data driven are modeled using the DFG model. DSP applications are typical examples for it.

• Suppose one of the functions in our application contains the computational requirement x=a+b; and y=x-c. Following figure shows the implementation of a DFG model for implementing these requirements.

• In a DFG model, a data path is the data flow path from input to output. A DFG model is said to be acyclic DFG if it doesn't contain multiple values for the input variable and multiple output values for a given set of inputs. A DFG model translates the program as a single sequential process execution.

ii) FSM:

• A finite state machine is a model of discrete behavior, which consists of: a finite number of states, transitions between two of those states, and actions.

• A state represents a certain behavior. A transition indicates a state change and is guarded by a condition. An action is a description of an activity that is to be performed.

• If this action depends on the state, it’s called a Moore machine. If the action is performed when a transition occurs, so when the state and condition are satisfied, it’s called a Mealy machine. Most machines are both a Moore and Mealy machine at the same time.

• Some integrated development environments (IDE) allow a designer to draw a FSM diagram on screen, and then the IDE automatically translates the diagram into a software or FPGA or ASIC implementation. This allows the designer to use a natural way of representation of the system.

iii) Petri-net:

• Petri Net (PN) is an abstract model to show the interaction between asynchronous processes. It is only one of the many ways to represent these interactions.

• Asynchronous means that the designer doesn't know when the processes start and in which sequence they'll take place.

• A common manner to visualize the concepts is with the use of places, tokens, transitions and arcs.

• We refer to the basics of Petri Net for a first introduction in notations. We want to mention that a transition can only fire when there are tokens in every input- place. When it fires, one token is taken from every input-place and every output-place from the transition gets an (extra) token.

• Places can play the following role of a geographical location or the environment of a robot, i.e a place he has to go to. Tokens can be a physical object: a robot. Transitions can be a transformation of an object: a robot which changes his role.

• In a PN, situations can occur where two or more systems wait for each other before an action can take place. This is called a deadlock.

• It can also occur that a single system has to wait forever at the beginning of a transition because another process has always higher priority. This problem is called starvation.

• In the mathematical model a transition takes no time. In the real world executing a transition takes some time and the sequence or timing of events becomes important. This problem relates to race conditions or race hazards. When the PN is rather big, these problems are hard to find.

iv) UML:

• FSM is limited in a way. It cannot have two states active at the same moment, next to each other.

• The UML statechart is an attempt to overcome this limitation while retaining its good features.

• UML (Unified Modeling Language) is designed to specify, visualize, construct and document software-intensive systems.

• The essential syntax of statecharts is very much like FSM's.

• In a statechart, it is possible that there are states within states, so there is a kind of a hierarchical structure. They are called substates and superstates or parentstates.

• Another possibility is concurrent states. By using branching, a state can be followed by more than one other state. Each transition can be guarded with its own condition.

• When more than one condition is satisfied, two states can be active at the same moment.