L03.ppt

CS1103 電機資訊工程實習

What Is State? Prof. Chung-Ta King Department of Computer Science National Tsing Hua University (Contents from http://ai-depot.com/FiniteStateMachines/FSM-Background.html, www.dcs.shef.ac.uk/~ahw/comp_arch/L3.ppt )

How many “states” can a motorcycle have?

這是什麼爛問題 ? State 有不同的類型 ! • 新、舊

• 運作良好、堪用、待修、報廢 • 停止、行進、牽行 • ...

A Better Question

機車的「運作狀態」有幾種 ?

熄火靜止、熄火行進、 發動靜止、發動行進

不同「運作狀態」之間如何轉換 ? 

State transition 熄火 行進

推動

熄火 靜止

停止

發動 熄火

啟動

發動 行進

發動 熄火

發動 靜止

煞車停止

Finite state machine 5

Outline  

What is finite state machine? Finite state machine for program modeling 

   

The important concept of “state”

Finite state machine for circuit control Finite state machine for embedded control Finite state machine for recognition Modeling with finite state machine

6

Finite State Machines (FSM) 

or Finite State Automation (FSA) 



4 main elements:    



Models of behaviors of a system or object, with a limited number of defined conditions or modes, where modes change with circumstance

States: define behavior and may produce actions State transitions: move from one state to another Rules (or conditions): must be met to allow a state transition Input events: externally or internally generated; may trigger rules and lead to state transitions

An initial state and a current state Good for representation and 7 modeling sequences of behaviors

Outline  

What is finite state machine? Finite state machine for program modeling 

   

The important concept of “state”

Finite state machine for circuit control Finite state machine for embedded control Finite state machine for recognition Modeling with finite state machine

8

Consider the Program main() { i=5; j=6; k=0; k=i+j; if (k>0) i=0; else j=0; } 

Can this program be modeled with a FSM? What is its “state”? 9

Initial State main() { i=5; j=6; k=0; k=i+j; if (k>0) i=0; else j=0; }

Memory

CPU

6

j

5

i

0

k

10

State 1 main() { i=5; j=6; k=0; k=i+j; if (k>0) i=0; else j=0; }

Memory

CPU

6

j

5

i

11

k

11

State 2 main() { i=5; j=6; k=0; k=i+j; if (k>0) i=0; else j=0; }

Memory

CPU

6

j

0

i

11

k

12

State 3 main() { i=5; j=6; k=0; k=i+j; if (k>0) i=0; else j=0; }

Memory

CPU

0

j

5

i

11

k

13

FSM Representing the Program

V

k=i+j

1

2

k<=0

4

k>0

3 14

Compare with Flow Chart

k=i+j yes

i=0

k>0

no

j=0

15

Some Questions 



Can FSM be used to represent any program? Any algorithm? What is the “state” of a program/process? Or a computer?     



Why is this important? 系統更新的回復點 電腦休眠之後回復原來畫面 Context switch Interrupt and resume

Is there a machine that can model any computation?  Turing machine 16

State of a Procedure? 

Fibonacci number (iterative version) unsigned int fib(unsigned int n) { unsigned int i=1, j=0, k, t; for (k=1; k<=n; k++) { t=i+j; i=j; j=t; } return j; } What need to be stored when the procedure is suspended and later resumed (as if nothing had happened)? 17

Why Is It Important? 

Fibonacci number (recursive version) unsigned int fib(unsigned int n) { unsigned int i=n-1, j=n-2; if (n<2) return n; else return fib(i) + fib(j); }

What happens when n, i, and j each refer to the same memory location across procedure calls? 18

How to Solve for Recursion? 



If we could save the “state” of the calling procedure in a safe/separate place that the called procedure will not overwrite, then the recursion can be executed correctly Big idea: “procedure state” in run-time stack    

Allocate the “state” of each called procedure in the run-time stack procedure frame All references to the “state” go to the stack Each invocation will push “state” down the stack How to write assembly code to do that?  Memory reference relative to stack pointer  Chapter 8 of CS2422 19

Summary: A View of a “State” 

Storage contents of the code/system that must be saved away when the code/system is suspended and resumed later, as if nothing had happened      

State of a procedure on procedure calls State of a thread/process on context switch  make time-sharing possible State of a process on migration to another PC State of a computer on error recovery State of a computer on hibernation ... 20

Implication of the View 

We can do anything as long as we do not disturb the “state” z = x * 3.1412; if (z > 10) j = j + k; 

Since FP multiplication takes a long time, can we execute the addition at the same time?  out-of-order, speculative

21

Outline  

What is finite state machine? Finite state machine for program modeling 

   

The important concept of “state”

Finite state machine for circuit control Finite state machine for embedded control Finite state machine for recognition Modeling with finite state machine

22

FSM Also Good for Hardware Processor AX BX

Register …

Memory x a

data 01 0000001 1000010 11 0000001 1000110 01 1000011 0000001

Controller

ALU

b MOV AX, a ADD AX, b MOV x, AX

…

clock

IR

PC address

PC: program counter IR: instruction register

23

Step 1: Fetch (MOV AX, a) Register AX BX

…

Memory x a

data 01 0000001 1000010 11 0000001 1000110 01 1000011 0000001

Controller

ALU

b MOV AX, a ADD AX, b MOV x, AX

…

clock

IR

PC

01 0000001 1000010

0000111

address

24

Step 2: Decode (MOV AX,a) Register AX BX

…

Memory x a

data 01 0000001 1000010 11 0000001 1000110 01 1000011 0000001

Controller

ALU

b MOV AX, a ADD AX, b MOV x, AX

…

clock

IR

PC

01 0000001 1000010

0000111

address

25

Step 3: Execute (MOV AX,a) Register AX BX

Memory

00000000 00000001

…

data

x 00000000 000000001 a

01 0000001 1000010 11 0000001 1000110 01 1000011 0000001

Controller

ALU

b MOV AX, a ADD AX, b MOV x, AX

…

clock

IR

PC

01 0000001 1000010

0000111

address

26

Concept of the State Machine Computer Hardware = Datapath + Control

Registers Combinational Functional Units (e.g., ALU) Busses

Qualifiers

Control

FSM generating sequences of control signals Instructs datapath what to do next

Control State Control Signal Outputs

Qualifiers and Inputs

Datapath

27

FSM of the Computer 

For this highly simplified computer, the controller can be described by a FSM Decode

Fetch if (ADD)

ADD

if (MOV)

MOV

if (JNG)

...

JNG

Each state will generate certain control signals to control the datapath 28

Internal Structure of Controller Next state (state transition) State Register Combinational circuit Clk

Output

To datapath

Controller Instruction Reg

EFLAGS ALU zero,carry,overflow,...

29

Combinational & Sequential Logic  





Combinational logic does not have memory It generates output solely according to the input and does not care about history Often, we need a different reaction on the same input depending on the current state E.g.   

Current state is 7 and input is 1, the new state and output are 8 Current state is 15 and input is 1, the new state and output are To make the new state depends on the previous state, we need memory 30

Sequential Logic and FSM 

Computers are made of sequential logic blocks 

 

Truth tables are used to design combinational logic, but can’t be used for sequential logic

Finite state machines (FSM) are used instead FSM describes a sequential logic block in terms of:   

Set of states, State transition function (defined on current state and input), and Output function (defined on current state and input, or on current state only) 31

Two Types of FSMs Differ in how outputs are produced  Moore Machine: 



Mealy Machine: 



Outputs are independent of the inputs, i.e. outputs are produced from within the state of the state machine Outputs can be determined by the present state alone, or by the present state and the present inputs, i.e. outputs are produced as the machine makes a transition from one state to another

Any Moore machine can be turned into a Mealy machine (and vice versa) 32

Moore Machine The Moore State Machine output remains the same as long as the state machine remains in that state. The output can be arbitrarily complex but must be the same every time the machine enters that state.

Output condition that results from being in a particular present state

State 1 q,r i,j

State 2 x,y

a,b Input condition that must exist in order to execute these transitions from State 1

33

Mealy Machine The Mealy State Machine generates outputs based on:  The Present State, and  The Inputs to the M/c. So, same state can generate many different patterns of output signals, depending on the inputs. Outputs are shown on transitions since they are determined in the same way as is the next state. Output condition that results from being in a particular present state

State 1 i,j x,y

a,b q,r Input condition that must exist in order to execute these transitions from State 1

State 2 34

Outline  

What is finite state machine? Finite state machine for program modeling 

   

The important concept of “state”

Finite state machine for circuit control Finite state machine for embedded control Finite state machine for recognition Modeling with finite state machine

35

Safety Belt Control 

We want to design a controller for safety belt 

  

If the seat is seated and the belt is not buckled within a set time, a buzzer will sound until the belt is buckled  event driven Inputs: seat sensor, timer, belt sensor Output: buzzer, timer System: specialized computer for reacting according to events sensed by the sensors

36

FSM for Event-driven Systems no seat/no seat/ buzzer off

idle

seat/timer on

no seat/buzzer

Belt/buzzer on

belt/ buzzer off

belted

no belt and no timer/-

seated belt/no belt/timer on

37

C Code Structure  

Current state is kept in a variable State table is implemented as a switch  

Cases define states States can test inputs and produce outputs

while (TRUE) { switch (state) { case state1: … } } 

Switch is repeatedly evaluated by while-loop 38

C Implementation #define IDLE 0 #define SEATED 1 #define BELTED 2 #define BUZZER 3 switch (state) { case IDLE: if (seat) { state = SEATED; timer_on = TRUE; } break; case SEATED: if (belt) state = BELTED; else if (timer) state = BUZZER; break; … }

39

Another Example in1=1/x=a A

B

r=0/out2=1

r=1/out1=0 in1=0/x=b

s=0/out1=0

C

D s=1/out1=1

40

C State Table switch (state) { case A: if (in1==1) { x = a; state = B; } else { x = b; state = D; } break; case B: if (r==0) { out2 = 1; state = B; } else { out1 = 0; state = C; } break; case C: if (s==0) { out1 = 0; state = C; } else { out1 = 1; state = D; } break; 41

Outline  

What is finite state machine? Finite state machine for program modeling 

   

The important concept of “state”

Finite state machine for circuit control Finite state machine for embedded control Finite state machine for recognition Modeling with finite state machine

42

FSM as Recognizer/Translator 



Outputs a ‘0’ if an even # of 1’s is received and outputs a ‘1’ otherwise What is state? 

Two states: whether an even # of 1s have been received, or an odd # of 1s have been received Moore Machine Mealy Machine 0/0 Even

Odd

Even

Input

1/1

1/0

0

Output

Output

[0]

1

1

Input

Odd [1]

0/1

0

43

Finite State Machines 

Language recognizer (acceptor) y



recognizer of L

yes, y in L no

Problem solver

problems

strings (languages)

machines

answers

44

FSM as Recognizer/Translator 

How to recognize words in a document?  

Assume characters in the document are input sequentially What is state? others/[word] State 2

State 1

[a-z, A-Z]

[a-z, A-Z]

others 45

Example 



A FSM that outputs a ‘1’ whenever it receives a multiple of 3 # of 1’s on a serial input Relevant information to solve the problem: (A) A multiple of 3 # is received (B) A non-multiple of 3 # is received



Questions to consider: (1) How do we go from (A)(B) Ans.: If a ‘0’ is received (2) How do we go from (B)(A) Ans.: Not clear; need to consider (B1): 3y+1 # of 1’s received. y is an integer  0 (B2): 3y+2 # of 1’s received. 46

Example 

Transitions between 3 classes of information: (A)  (B1)  (B2)  (A) 1 received



1 received 1 received

They can be considered states of the FSM: 00

Reset

0/1

i=0

Output

Input

0

Reset i=0 [1]

0/0

1/0 1/1

10

01

i=1

1/0

i=2

0/0

Mealy Machine

1

1

0 i=1 [0]

i=2 [0]

1

0

Moore Machine

47

Outline  

What is finite state machine? Finite state machine for program modeling 

   

The important concept of “state”

Finite state machine for circuit control Finite state machine for embedded control Finite state machine for recognition Modeling with finite state machine

48

Scenario 1 入侵偵測系統：  某一房間的麥克風偵測到有不正常的聲音，即 提高偵測頻率，並通知房間內的攝影機追蹤聲 音的來源，且將影像傳到管理員手機。  同時，通知走廊及其他房間內的麥克風提高偵 測頻率，攝影機追蹤移動物體。

What are the states? What is the FSM?

49

Scenario 2 大富翁：  What are the states?  How states transit? Are the transitions deterministic?  What are the expected outcomes? Markov chain, stochastic process, ...

50

Quiz 



 

每天早上小明的爸爸開車送他到學校，然後到 公司上班。小明的媽媽處理家務。 每天下午下課時，小明的媽媽用機車來接他， 並送他去補習。 小明補完習，媽媽再來接他回家。 爸爸下班時間比較不固定，他直接開車回家。

What are the states? What is the FSM? What are the states for 小明？ hierarchy 51