Unit - II

Programming in assembly language (ALP) vs High

Level Language

C Program Elements:- Macros and functions,

Use of Date Types, Structure, Pointers, Function Calls

Program Modeling Concepts – Program Models- DFG

Models – FSM Models – Modeling of Multiprocessor
Systems
Program Modeling Concepts - Program
Models
• Modeling
– A standard practice adopted by engineers in solving
design problems
• Program models
– Polling for events
– Sequential program model
– DFG model
– FSM model – Polling for events
– Concurrent processes model
• Modeling of Multiprocessor Systems
2. Sequential Program Model
 Programming using Sequential
functions
• Use of multiple
function calls
sequentially
 ACVM Example Sequential Program
Model
• Run function get_user_input ( ) for obtaining
input for choice of chocolate from child.
• Run function read_coins ( ) for reading the
coins inserted into ACVM for cost of
chocolate.
• Run function deliver_chocolate for delivering
the chocolate.
• Run function display_thanks for displaying
‘Collect the nice chocolate. Visit again!’
 3. Concurrent Process Model
• A programming model is that there are several
concurrent tasks and each task has the
sequential code in infinite loop.
• A task sends a message or signal for another
task.
• A task, which gets a message or signal, runs
and the remaining tasks remain in the blocked
state.
Concurrent Process Model
2. Data-Flow and control data
flow Models
 Data Flow Model
• A data-flow means that a program flow such
that specifically the data only determines all
the program execution steps and program
flows are determined specifically only by the
data.
• Programmer predetermines the data inputs
and designs the programming steps to
generate the data output
 DFG Model
• A set of data-input generates a set of data-
output and another set of input will generate
another output.
Example of Data Flow graph (DFG)
• A program for finding an average of grades in
various subjects will have the data inputs of
grades and data output of the average.
• Program executes a function to generate the
appropriate output.
• The data flow graph model is appropriate to
model the program for the average.
 Data Flow graph (DFG) Modeling
• A circle represents each process (set of
program steps) in DFG.
• An arrow directed towards the circle
represents the data input (or set of inputs)
and an arrow originating from the circle
represents a data output (or a set of outputs).
• Data input along an input edge is considered
as token.
• An input edge has at least one token.
Example – Quadratic root
−𝑏 ± 𝑏 2 − 4𝑎𝑐
𝛾=
2𝑎
 ADFG – Acrylic Data Flow Graph
• When there is only one set of values of each
of the inputs and only one of values of the
outputs, a DFG is known as ADFG.

• Examples of Non-Acrylic DFG – an event,

status flag, output of the previous process
acting as the input.
DFG - Example
DFG for a process for the sixth FIR
filter response
DFG for a set of processes of the same sequence for
an FIR filter with 6 inputs and 7 co-efficients
 DFG – ADFG (ACRYLIC DATA FLOW
GRAPH)
• There is one input point to the process
represented by the circle.
• There is one output point for y6.
• There is only one memory address for each
co-efficient and each filter input. There is only
one value of each of the six inputs for ‘x’ and
there is only one value for each of the six co-
efficients ‘a’.
 DFG
• Data flow graph models help in a simple code
design.
• A simple code design can be defined as that in
which the program mostly breaks into DFGs.
• A DFG models a fundamental program
element having an independent path.
• A DFG gives that unit of a system, which has
no control conditions and thus a single path
for the program flow.
 CDFG – Control Data Flow Graph
• A control flow means that specifically only the
program determines all program execution
steps and the flow of a program
• The programmer predetermines these steps.
 CDFG
• The steps may have loops or condition
statements in-between.
• Data that is input generate the data output
after a control data-flow as per controlling
conditions.
• Output(s) and paths taken after the steps
depends on the control statements for various
decisions in a process.
 CDFG
• In the CDFG model, there is a diagram, which
graphically represents the conditions and the
program flow along a condition dependent
path.
• The CDFG diagram also represents the effect
of events among the processes and shows
which processes are activated on each specific
event.
 CDFG Modeling
• A circle also represents each process (called
node) in a CDFG.
• A directed arrow towards the circle represents
the data input (or set of inputs)
• A directed arrow from the circle represents a
data output (or a set of outputs).
• A box (square or rectangle with its diagonal
axes horizontal and vertical) may represent a
condition
 CDFG
• Helps in understanding all conditions and in
determining the number of paths a program
may take.
• Guides us how software to be tested for each
path starting from a decision node
• Helps in analyzing the program in terms of
complexity
 Data Flow Graph Model and CDFG
Assumptions
• A set of the outputs from a circle showing a
set of programming steps will be
simultaneously available as the inputs to the
next circle (next set of programming steps).
• At each circle computations take same time
for each output and there is no delay in any of
the inputs
 SDFG - Synchronous Data Flow Graph
• An SDF graph consists of nodes and arcs.
• Nodes represent operations which are called actors.
• Arcs represent data values called tokens which stored in first-
in first-out (FIFO) queues.
• The word token is used because each data values can
represent any data type (e.g. integer or real) or any data
structure (e.g. matrix or image).
 SDFG
• SDF graphs obey the following rules:
• An actor is enabled for execution when enough tokens
are available on all of the inputs, and source actors are
always enabled. (Node is said to be fired)
• When an actor executes (Fires), it always produces and
consumes the same fixed amount of tokens.
• The flow of data through the graph may not depend on
values of the data.
• Delay is a property of an arc, and a delay of n samples
means that n tokens are initially in the queue of that arc.
SDFG – Synchronous Data Flow Graph
• DFG assumptions not true in several cases
• SDFG models the delay in getting an input (s)
before the all or part of computation(s) fire at
a circle in the DFG
• Models the number of outputs from the
program steps at a circle and model the
number of inputs
 SDFG
• An SDFG model shows the delay(s) [expected due to a
previous process may not yet have been completed] as well as
shows the number of inputs and outputs.
• An arc (directed arrow) represents a buffer in physical
memory.
• The arc can contain one or more initial tokens with the delays.
• A token till received at the vertex (shown by a circle) does not
fire the computations (actors) at a vertex (circle).
 SDFG Model Example 1
• SDFG model of
computations (actors)
at the vertices shown
by circles) and memory
buffer by arcs in a
directed graph between
X and Y.
• The delay in the input is
shown by dot.
• Number of inputs and
outputs also marked
• Actors (Vertices
shown by circles) and
arcs in a directed
graph between X and
Y.
• The outputs are a, b
and c and and inputs
are a, c, i and j. The i is
with a delay (dot).
 Example - SDFG

The notation means that when A executes, it produces 20

tokens. When B executes, it consumes 10 tokens and
produces 20 tokens. When C executes, it consumes 10
tokens.

In the example SDF graph above,

we must
•Fire A 1 time
•Fire B 2 times
•Fire C 4 times
State Machine Models
 State Machine Model
• Assumed that there are states and state
transition functions, which produce the states.
• A state transition function is a function, which
changes a state to its next state .
 Examples of States
• Three states in a washing machine: ‘Washing,
‘Rinsing and Drying,
• A telephone process five states: Idle,
Receiving a ring, Dialing, Connected and
Exchanging messages.
 Examples of States
• States of a process (function or interrupt
service routine (ISR) or task: Idle, Running,
Blocked, Finished
A process modeled using the states
• When there are inputs to a process that
change the state of the process to a new state,
and generate outputs which may also be the
inputs for the next state.
• A program flow in system can be modeled
simply by an inter-state transition (from one
state to another).
 Steps in modeling state machine
• The steps to model and represent the states and inter-state
transitions are as follows:
1) A transition to a new state occurs from the previous state on an
event (input). The event may be setting a value of certain
parameter or the result of the execution of certain codes.
2) A transition may be also be interrupt flag driven (after a flag sets) or
semaphore driven or interrupt-source servicing need driven.
3) A state is identified by a flag condition or set of codes being
executed or set of values of certain parameters.
4) A state can receive multiple tokens (inputs, messages, flags
interrupts or semaphores) from another state (s). [A token (event)
is a general term that means either an input or event-input.]
5) A state can generate multiple tokens (outputs, messages, flags
interrupts or semaphores)
 Finite State Machine (FSM) Model for
Event Controlled or Response
Controlled Programs
In FSM model:
• A circle represents a state of a program
• A directed arc (or an arrow) represent the
program flow from a state to another.
 Example : Washing Machine
• Inputs: Timer signal T (T==1 when timer expires);
Commence/Start button pressed C; Double wash
requested D; Lid Open L (L==1 when lid is open).
• States:
– Idle
– Soak
– Wash
– Rinse
– Spin
– Lid Open
T T&