程序代写代做代考 go clock L10_1 Finite-State- Machines_Implementation

L10_1 Finite-State- Machines_Implementation
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 1 The material in this presentation cannot be copied in any form without written permission

Learning Objectives
• Be able to identify the components and trade-offs relevant to a finite state machine.
• Identify the course-granularity operation of the implementation for an FSM.
EECS 370 – Introduction to Computer Organization
2

FSM for Vending Machine
Refund
0 coins
1 coin
3 coins
Ran out of specific drink selection
2 coins
Coin trigger Refund button Drink Select
Is this a Mealy or Moore Machine?
Mealy ~ output is based on current state AND input
EECS 370 – Introduction to Computer Organization
3
Vend drink Refund Refund

Implementing a FSM
Outputs
Inputs
Implement transition functions
(using a ROM and combinational circuits)
Current state
D
Q
D
Q
2-bit state
Next state
EECS 370 – Introduction to Computer Organization
4

Implementing Combinational Logic (1)
• If I have a truth table:
• I can either implement this using
combinational logic:
A
BC0
• …or I could literally just store the entire truth table in a memory and just “address” it using the input!
ABCO
000 0 001 1 010 0 011 1 100 0 101 1 110 1 111 1
{A,B,C}
addr_in
3
0
1
0
1
0
1
1
1
EECS 370 – Introduction to Computer Organization
5
{O}

Implementing Combinational Logic (2)
• Custom logic • Pros:
• Can optimize the number of gates used • Cons:
• Can be expensive / time consuming to make custom logic circuits
• Lookup table:
ABC O
000 0 001 1 010 0 011 1 100 0 101 1 110 1 111 1
Add one more input… ABCDO
0
0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 1
•Pros: 0100
• Programmable ROMs (Read-Only Memories) are very cheap and can be programmed very quickly
• Cons:
• Size requirement grows exponentially with number of inputs
(adding one just more bit doubles the storage requirements!)
EECS 370 – Introduction to Computer Organization
1
0
1
0
1
0
1
0
1
1
6
0000 0001 0010 0011
0
1
0
1

ROMs and PROMs
• Read Only Memory
• Array of memory values that are constant • Non-volatile
• Programmable Read Only Memory
• Array of memory values that can be written exactly once
(destructive writes)
• You can use ROMs to implement FSM transition functions
• ROM inputs (i.e., ROM address): current state, primary inputs
• ROM outputs (i.e., ROM data): next state, primary outputs EECS 370 – Introduction to Computer Organization
Outputs
Inputs
ROM and combinational circuits
D
Q
D
Q
2-bit state
Next state
Current state
7

8-entry 4-bit ROM
address
1
A0 A1 A2
0
3
3×8 Decoder
7
1
0
• A diode only allows current to flow in one direction.
• It prevents a ‘1’ from propagating to other lines.
D1D0D0D1 0123
data
EECS 370 – Introduction to Computer Organization
8

ROM for Vending Machine Controller
• Use current state and inputs as address • 2 state bits + 22 inputs = 24 bits (address)
• Coin, refund, 10 drink selectors, 10 sensors
• Read next state and outputs from ROM • 2 state bits + 11 outputs = 13 bit (memory) • Refund release, 10 drink latches
• We need 224 entry, 13 bit ROM memories
• 218,103,808 bits of ROM seems excessive for our cheap controller
EECS 370 – Introduction to Computer Organization
9

Reducing the ROM Needed
• Idea: let’s do a hybrid between combinational logic and a lookup table
• Use basic hardware (AND / OR) gates where we can, and a ROM for everything more
complicated
• Replace 10 selector inputs and 10 pressure inputs with a single bit input (drink selected)
• Use drink selection input to specify which drink release latch to activate
• Only allow trigger if pressure sensor indicates that there is a bottle in that selection.
(10 2-bit ANDs)
• Now:
• 2 current state bits + 3 input bits (5 bit ROM address)
• 2 next state bits + 2 control trigger bits (4 bit memory)
• 32 × 4 = 128 bit ROM (good!)
EECS 370 – Introduction to Computer Organization
10

Putting It All Together
Drink selector Pressure Sensor
10 input OR gate
DQ
DQ
2-bit state
32
Drink Release Latches
Coin release
Clock/Event
refund
coin
EECS 370 – Introduction to Computer Organization
11
Drink Release
5×32 decoder

Some of the ROM Contents
Refund
Coin trigger Refund button Drink Select
0 coins
1 coin
3 coins
Ran out of specific drink selection
2 coins
0000 0000
0000 0100 1000 1100 0001 0010
ROM address (current state, inputs)
ROM contents (next state, outputs)
EECS 370 – Introduction to Computer Organization
12
Vend drink Refund Refund

Limitations of the Controller
• What happens if we make the price $1.00?, or what if we want to accept nickels, dimes and quarters?
• Must redesign the controller (more state, different transitions) • A programmable processor only needs a software upgrade.
• If you had written software anticipating a variable price, perhaps no change is even needed
• Next Topic – Our first processor!
EECS 370 – Introduction to Computer Organization
13

LC2Kx Processor as FSM
Outputs
Inputs
Implement transition functions (using a ROM and combinatorial circuits)
Memory
Next state 65,53632 + 9 32 bits
Current state 65,53632 + 932 bits
Far more states than atoms in the Universe!
EECS 370 – Introduction to Computer Organization
14
Register file

Logistics
• There are 3 videos for lecture 10
• L10_1 – Finite-State-Machines_Implementation
• L10_2 – Single-Cycle-Processor • L10_3 – LC2K_Datapath
• There is one worksheet for lecture 10
1. Finite state machine – you can do this now
EECS 370 – Introduction to Computer Organization
15

L10_2 Single-Cycle-Processor
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 16 The material in this presentation cannot be copied in any form without written permission

Learning Objectives
• To identify the components used to implement a processor for LC-2K and understand the mapping from these components to LC-2K instructions.
EECS 370 – Introduction to Computer Organization
17

Single-Cycle Processor Design
General-Purpose Processor Design
• Fetch Instructions
• Decode Instructions
• Instructions are input to control ROM
• ROM data controls movement of data
• Incrementing PC, reading registers, ALU control
• Clock drives it all
• Single-cycle datapath: Each instruction completes in one clock cycle
EECS 370 – Introduction to Computer Organization
18

Building Blocks for the LC2K
Control
memory
memory
Register file
reg
MMMM UUUU XXXX
ROM
A L+ U
Very easy!
Just a few wires
+
Sign extend
State
Compute
Here are the pieces, go build yourself a processor!
EECS 370 – Introduction to Computer Organization
19
3to8

Control Building Blocks (1)
Connect one of the inputs to OUT based on the value of select
2 to 1 MUX
IN1 IN2
select
M U X
OUT
EECS 370 – Introduction to Computer Organization
20
If (! select) OUT = IN1
Else
OUT = IN2

Control Building Blocks (2)
Decoder activates one of the output lines based on the input
IN OUT
210 76543210
000 00000001
001 00000010
010 00000100
011 00001000
etc.
ROM stores preset
data in each location.
Give address to access data.
3 to 8 decoder
OUT 7:0
3×8 decoder
Read-only Memory
IN2 IN1 IN0
Addr ROM
Data
EECS 370 – Introduction to Computer Organization
21

Compute Building Blocks (1)
Perform basic arithmetic functions
OUT = f(IN1, IN2)
EQ = (IN1 == IN2)
For LC2K:
f=0 is add
f=1 is nor
For other processors, there are many more functions.
Just adds
Arithmetic Logic Unit
EQ
A L U
function
Adder
IN1
IN2
OUT
IN1 IN2
+ OUT
EECS 370 – Introduction to Computer Organization
22

Compute Building Blocks (2)
Sign extend input by replicating the MSB to width of output
OUT(31:0) = SE(IN(15:0))
OUT(31:16) = IN(15) OUT(15:0) = IN(15:0)
Useful when compute unit is wider than data
Sign Extension Unit
IN Sign extend OUT
EECS 370 – Introduction to Computer Organization
23

State Building Blocks (1)
Small/fast memory to store temporary values
n entries (LC2 = 8)
r read ports (LC2 = 2) w write ports (LC2 = 1)
* Ri specifies register number to read
* W specifies register
number to write
* D specifies data to write
Register File or Register
R1 R2
W D
OUT1 OUT2
Register file
reg
write enable
EECS 370 – Introduction to Computer Organization
24

State Building Blocks (2)
Addr DataIn
DataOut
Memory
Memory
En R/W
EECS 370 – Introduction to Computer Organization
25
Slower storage structure to hold large amounts of stuff.
Use 2 memories for LC2 * Instructions
* Data
* 65,536 total words

Review: LC2K Instruction Formats
• Tells you which bit positions mean what
• R-type instructions (opcodes add 000, nor 001)
31-25 24-22 21-19 18-16 15-3 2-0
• I-type instructions (opcodes lw 010, sw 011, beq 100) 31-25 24-22 21-19 18-16 15-0
unused
opcode
regA
regB
unused
destR
unused
opcode
regA
regB
offset
EECS 370 – Introduction to Computer Organization
26

Logistics
• There are 3 videos for lecture 10
• L10_1 – Finite-State-Machines_Implementation
• L10_2 – Single-Cycle-Processor • L10_3 – LC2K-Datapath
• There is one worksheet for lecture 10 1. Finite state machine
EECS 370 – Introduction to Computer Organization
27

L10_3 LC2K-Datapath
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 28 The material in this presentation cannot be copied in any form without written permission

Learning Objectives
• Ability to trace and explain the flow of data in a single-cycle processor diagram, using the blocks from the previous lecture.
• Identify the timing and operation of control circuit for a single-cycle processor.
EECS 370 – Introduction to Computer Organization
29

LC2Kx Datapath Implementation
1
+
+
15-0
21-19 18-16
XM
Sign extend
M U X
18-16 2-0
M U
A L U
M U X
U X
24-22
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
Instruction Memory
PC
Control ROM
30
30/39
30
Instruction bits

Executing an ADD Instruction 1
+
+
15-0
21-19 18-16
XM
Sign extend
M U X
18-16 2-0
M U
A L U
M U X
U X
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
PC
Instruction Memory
24-22
add regA, regB, destR
destR = regA + regB
PC = PC + 1
Control ROM
31
31/39
31
Instruction bits

Executing an ADD Instruction 1
+
+
15-0
001
010 011
XM
Sign extend
Instruction Memory
M U X
M U
A L U
PC
M U X
1 1 1
U X
000
add 1 2 3
EECS 370 – Introduction to Computer Organization
1 032/39 0 X
32
Register file
En
Data memory
En R/W
3×8 decoder
32
Instruction bits

Executing a NOR Instruction 1
+
+
15-0
21-19 18-16
XM
Sign extend
M U X
18-16 2-0
M U
A L U
M U X
U X
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
PC
Instruction Memory
24-22
nor regA, regB, destR destR = ~(regA | regB) PC = PC + 1
Control ROM
33
33/39
33
Instruction bits

Executing a NOR Instruction 1
+
+
15-0
001 010
Sign extend
M U X
M 011 U
XM
A L U
M U X
1 1 1
U X
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
Instruction Memory
PC
001
nor 1 2 3
1 134/39 0 X
34
34
Instruction bits

Executing an LW Instruction 1
+
+
15-0
21-19 18-16
XM
Sign extend
M U X
18-16 2-0
M U
A L U
M U X
U X
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
PC
Instruction Memory
24-22
lw regA, regB, offset
regB = M[regA + offset]
PC = PC + 1
Control ROM
35
35/39
35
Instruction bits

Executing an LW Instruction 1
+
+
0…011001
Sign extend
001
Instruction Memory
M U X
M 010 U
XM
A L U
PC
M U X
0 0 1
U X
010
lw 1 2 25
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
0 036/39 1 0
36
36
Instruction bits

More instructions to come…
Next lecture!
EECS 370 – Introduction to Computer Organization
37

Related Posts