Computational models

Computational Models used in Embedded System Design

1. Computational Models
In Embedded Design
1
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

2. •Data Flow Graph/Diagram (DFG) Model
•Control Data Flow Graph/Diagram (CDFG)
Model
•State Machine Model
•Sequential Program Model
•Concurrent/Communicating Process Model
•Object Oriented Model


Definition: a model is a formal system consisting of objects & composition rules.
It is hard to make a decision on which model should be followed in particular
system design.
Most often designers switch between variety of models from requirement
specification to implementation.
2
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

3. Data Flow Graph/Diagram (DFG)
Model
•Translates the data processing requirements into a data
flow graph.
•It is data driven model in which program execution is
determined by data.
•It emphasizes on data and operation on data which
transform the input data to output data.
•It is visual model in which operation on data(Process) is
represented using a block(Circle) and data flow is
represented by arrows(inward arrow => i/p to process
and outward arrow=> o/p of process)
3
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

4. Data Flow Graph/Diagram (DFG)
Model cont…
•Embedded application which are computational intensive &
data driven are modeled using DFG Eg.: DSP
•For example suppose computation x = a + b & y = x - c needs
to be carried out, then




4
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
• Acyclic DFG: doesn’t contain
multiple values for i/p variables
and multiple values for o/p
variables.

5. Control Data Flow Graph (CDFG)
Model
•Is used for applications involving control
program execution.
•Contains both data operation and control
operation.
Data nodes-> elements
control nodes-> decision makers
•For example, if Flag=1, x=a+b else y=a-b. This
requires decision making
5
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

6. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
6
Control node is represented by a Diamond
Block
X
y

7. State Machine Model
•Used for modeling reactive or event-driven embedded
systems, whose behavior are dependent on state
transistions.
•State machine model describes the system behavior
with ‘State’, ‘Event’, ‘Action’ & ‘Transistion’.

State -> representation of current situation.
Event -> i/p to state, acts as stimuli for state transistion.
Action ->activity to be performed by state machine.
Transistion -> movement from one state to another.
7
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

8. State Machine Model cont.
Example-1: SEAT BELT WARNING SYSTEM
Requirements:
1.When vehicle ignition is turned ON & seat belt is
not fastened within 10 secs of Ignition ON, the
system generates an alarm signal for 5 secs.
2.The alarm is turned OFF when the seat belt is
fastened / alarm time expires / the ignition is
off== whichever happens first.
8
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

9. SEAT BELT WARNING SYSTEM:
Events:
‘Ignition_Key_ON’
‘Ignition_Key_OFF’,
‘Time Expire’,
‘Alarm Time Expire’ and
‘Seat_Belt_ON’.
States:
‘Alarm_OFF’,
‘Waiting’, and
’Alarm_ON’.
9
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

10. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
10

11. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
11

12. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
12

13. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
13

14. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
14

15. SEAT BELT WARNING SYSTEM: cont..

The timer used in Seat Belt Warning System can also be
modeled as a Finite State Machine

States: ‘Idle’,
‘Ready’, and
’Running’.

Events: ‘Load Timer’
‘Start Timer’,
‘Stop Timer’ and
‘Timer Expire’

15
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

16. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
16

17. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
17

18. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
18

19. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
19

20. State Machine Model cont.
Example-2: Automatic Tea/Coffee vending
Machine
Requirements:
1.Tea/Coffee vending machine is initiated by
user by inserting 5 Rs. Coin.
2.After inserting Coin, user can select either
coffee /tea / press cancel order and take back
the coin.
20
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

21. Automatic Tea/Coffee vending Machine:
Events:
‘Insert Coin’
‘Tea Button Pressed’,
‘Coffee Button Pressed’,
‘Cancel Button Pressed’,
‘Coffee Dispensed’ and
‘Tea Dispensed’
States:
A= ‘OFF/wait for coin’,
B= ‘wait for user i/p’,
C= ’Dispense Tea’ and
D= ’Dispense Coffee’.
21
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

22. Automatic Tea/Coffee vending Machine:
22
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

23. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
23

24. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
24

25. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
25

26. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
26

27. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
27

28. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
28

29. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
29

30. State Machine Model cont.
Example-3: Coin Operated Public Telephone Unit
Requirements:
1.Call is initiated by lifting the receiver.
2.After lifting user needs to insert 1 Rs. Coin
3.If line is busy, coin is returned on placing the receiver back.
4.If line is through/free user is allowed to talk for 60 secs & at the end of
45
th
sec prompt for inserting another if want to continue call.
5.If doesn’t insert coin, call is terminated after completing 60 secs .
6.The system is ready to take up new call when receiver is placed back on
hook.
7.The system goes Out of order state when there is line fault.
30
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

31. Coin Operated Public Telephone Unit :
Events:
‘Rceiver lifted’
‘Coin inserted’,
‘Valid Number’,
’Line available’,
’Line busy’,
‘Time out’,
‘Place Receiver’,
‘Invalid Number’,
‘Line fault’ and
‘Line OK’
States:
A= ‘Ready’,
B=‘wait for coin’,
C=‘wait for number’,
D=’Dialing’
E=’Call in Progress’
F=’Call Terminated’
G=’Unable to make call’
H=’Invalid Number’ and
I=’Out of Order’.
31
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

32. Coin Operated Public Telephone Unit :
32
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

33. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
33

34. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
34

35. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
35

36. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
36

37. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
37

38. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
38

39. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
39

40. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
40

41. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
41

42. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
42

43. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
43

44. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
44

45. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
45

46. Sequential Program Model
•The functions or processing requirements are executed in
sequence.
•Program instructions are iterated and executed
conditionally and data gets transformed through a series of
operations.
•FSMs are good choice for sequential Program modeling.

•Flow charts are also good tool for modeling sequential
program.


46
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
FSMs represents States, events, transistions and actions
Flow charts model the execution flow

47. Example: Seat Belt Warning System
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
47
#define ON 1
#define OFF 0
#define YES 1
#define ON 0
Void Seat_belt_warn()
{
Wait_10sec();
If (Check_ignition_key()==ON)
{
If (Check_seat_belt()==OFF)
{
Set_timer(5);
Start_alarm;
While (Check_seat_belt() == ON || Check_ignition_key() == OFF || Timer_expire()==YES)
Stop_alarm();
}
}
}

48. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
48

49. Concurrent/Communicating Process
Model
•Models concurrently executing tasks/processes
•Sequential models leads to poor utilization of
processor, when the tasks waits for I/O
Sleeping.
•here a task is subdivided into multiple sub tasks &
CPU is effectively used.
•but requires additional overhead like task
scheduling, task synchronization &
communication
49
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru

50. Tasks can be split into:
•1.) timer task for waiting 10 secs
Wait_timer_task
•2.) tasks for checking the ignition key status
Ignition_status_monitoring task
•3.) tasks for checking the seat belt status
seat_belt_status_monitoring task
•4.) task for starting & stopping of alarm
alarm_control_task
•5.) alarm timer task for waiting 5 sec
alarm_timer_task

Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
50
Example: Seat Belt Warning System

51. These tasks cannot be executed randomly or sequentially instead
they need to be synchronized through some mechanism 
events

Events associated with tasks are:
•Wait_timer_task  wait_timer_expire
•Ignition_status_monitoring task  Ignition key ON
 Ignition key OFF
•seat_belt_status_monitoring task  Seat belt ON
 Seat belt OFF
•Alarm_timer_task  alarm_timer_start
alarm_timer_stop

Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
51
Set & Reset by
alarm_control_task

52. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
52

53. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
53

54. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
54

55. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
55

56. Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
56

57. Object Oriented Model
•Complex overall program/software requirement is
divided into simple well defined pieces called
objects.
•A class is abstract description of a set of objects &
can be considered as blueprint of objects.
•State of object=member variable
•Object behavior= member function
57
Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
Private, Public or
Protected
Private= ->accessible only within the class
Public-> accessible within as well as outside the class
Protected-> external access is prohibited

58. Reference

•Shibu K V, “Introduction to Embedded
Systems”, First Edition, Tata McGraw Hill
Education Private Limited, 2009

Computational Models prepared by
Anand H. D. Dr. AIT,Bengaluru
58

59. Prof. Anand H. D.
M. Tech. (PhD.)
Assistant Professor,
Department of Electronics & Communication Engineering
Dr. Ambedkar Institute of Technology, Bengaluru -56
Email: [email protected]
Phone: [phone]