L11_1 LC2K-Datapath
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
• 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
2
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
3
3/39
3
Instruction bits
Executing an SW 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
sw regA, regB, offset
M[regA + offset] = regB
PC = PC + 1
Control ROM
4
4/39
4
Instruction bits
Executing an SW Instruction 1
+
+
M U X
0…011001
Sign extend
001 010
M U
XM
A L U
M U X
X X 0
U X
sw 1 2 25
011
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
Instruction Memory
PC
0 05/39 1 1
5
5
Instruction bits
Executing a BEQ 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
beq regA, regB, offset
if (regA == regB)
PC = PC+1+offset
Register file
En
Data memory
En R/W
3×8 decoder
else PC = PC + 1
EECS 370 – Introduction to Computer Orga
PC
24-22
nization
Instruction Memory
Control ROM
6
6/39
6
Instruction bits
Executing “not taken” BEQ Instruction 1
+
+
Equal
A L U
M U X
0…011001
Sign extend
001 010
M U
XM 0MU
U X
X X 0
X
01 00
Eq
beq 1 2 25
100
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
Instruction Memory
PC
1 X7/39 0 X
7
7
Instruction bits
Executing “taken” BEQ Instruction 1
+
+
Equal
A L U
M U X
0…011001
Sign extend
001 011
M U
XM 1MU
U X
X X 0
X
11 00
Eq
beq 1 3 25
100
Register file
En
Data memory
En R/W
3×8 decoder
EECS 370 – Introduction to Computer Organization
Instruction Memory
PC
1 X8/39 0 X
8
8
Instruction bits
So Far, So Good
• Every architecture seems to have at least one ugly instruction. • JALR doesn’t fit into our nice clean datapath
• To implement JALR we need to • WritePC+1intoregB
• MoveregAintoPC
• Right now there is:
• No path to write PC+1 into a register • No path to write a register to the PC
EECS 370 – Introduction to Computer Organization
9
Executing a JALR 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
jalr regA, regB
regB = PC + 1
PC = regA
Control ROM
10
10/39
10
Instruction bits
Executing a JALR Instruction 1
+
to mux
Sign extend
001
+
Equal
A L
to mux
Instruction Memory
M U X
M 011 U
PC
1XMU 0MU
U X
0 01 1
X
1 01 11 01
Eq
jalr 1 3
EECS 370 – Introduction to Computer Organization
101
Register file
En
Data memory
En R/W
3×8 decoder
X X11/39 0 X
11
11
Instruction bits
What If regA = regB for a JALR ? 1
+
to mux
Sign extend
001 M 001
+
Equal
A L
M U X
U 1XMU
Instruction Memory
to mux
PC
0MU
U X
0 01 1
X
1 01
11 01
Eq
jalr 1 1
EECS 370 – Introduction to Computer Organization
101
Register file
En
Data memory
En R/W
3×8 decoder
X X12/39 0 X
12
12
Instruction bits
Changes for a JALR 1 1 Instruction 1
+
to mux
Sign extend
+
Equal
A L
Instruction Memory
M U X
M 001 U
PC
0XMU 0MU
01 0 1 11 01
Eq
jalr 1 1
EECS 370 – Introduction to Computer Organization
U X
0 01 1
X
NE
101
Register file
En
Data memory
En R/W
3×8 decoder
X X13/39 0 X
13
13
Instruction bits
What is Wrong with Single Cycle?
• All instructions run at the speed of the slowest instruction. • Adding a long instruction can hurt performance
• What if you wanted to include multiply?
• You cannot reuse any parts of the processor
• We have 3 different adders to calculate PC+1, PC+1+offset and the ALU
• No benefit in making the common case fast
• Since every instruction runs at the slowest instruction speed • This is particularly important for loads as we will see later
EECS 370 – Introduction to Computer Organization
14
Single Cycle Timing
Problem: What is latency for LC2K instruction execution?
Latencies:
1 ns – Register read/write time
2 ns – ALU/adder
2 ns – memory access (read or write)
0 ns – MUX, PC access, sign extend, ROM, wires
Inst.
get instr
read register
ALU operation
memory read/write
write register
total
add
beq
sw
lw
EECS 370 – Introduction to Computer Organization
15
Single Cycle Timing
Problem: What is latency for LC2K instruction execution?
Latencies:
1 ns – Register read/write time
2 ns – ALU/adder
2 ns – memory access (read or write)
0 ns – MUX, PC access, sign extend, ROM, wires
Inst.
get instr
read register
ALU operation
memory read/write
write register
total
add
2 ns
1 ns
2 ns
1 ns
6 ns
beq
2 ns
1 ns
2 ns
5 ns
sw
2 ns
1 ns
2 ns
2 ns
7 ns
lw
2 ns
1 ns
2 ns
2 ns
1 ns
8 ns
EECS 370 – Introduction to Computer Organization
16
Computing Execution Time
Assume: 100 instructions executed 25% of instructions are loads,
10% of instructions are stores,
45% of instructions are adds, and 20% of instructions are branches.
Single-cycle execution: ??
Optimal execution: ??
Inst.
total
add
6 ns
beq
5 ns
sw
7 ns
lw
8 ns
EECS 370 – Introduction to Computer Organization
17
Computing Execution Time
Assume: 100 instructions executed 25% of instructions are loads,
10% of instructions are stores,
45% of instructions are adds, and 20% of instructions are branches.
Single-cycle execution: 100 * 8ns = 800 ns
Optimal execution:
25*8ns + 10*7ns + 45*6ns + 20*5ns = 640 ns
Inst.
total
add
6 ns
beq
5 ns
sw
7 ns
lw
8 ns
EECS 370 – Introduction to Computer Organization
18
Logistics
• There are 3 videos for lecture 11
• L11_1 – LC2K-Datapath_Single-Cycle • L11_2 – Multi-Cycle_0
• L10_3 – Multi-Cycle_1
• There is one worksheet for lecture 10 1. L11 worksheet
EECS 370 – Introduction to Computer Organization
19
L11_2 Multi-Cycle
EECS 370 – Introduction to Computer Organization – Fall 2020
EECS 370 – Introduction to Computer Organization – © Bill Arthur 20 The material in this presentation cannot be copied in any form without written permission
Learning Objectives
• Identify the patterns seen in single-cycle LC2K processor.
• Mapping to the datapath to enable different execution times for
different instructions.
• Ability to trace and explain the flow of data in a multi-cycle processor diagram and the timing and operation of the control circuit for a multi-cycle processor.
EECS 370 – Introduction to Computer Organization
21
Multiple-Cycle Execution
• Each instruction takes multiple cycles to execute • Cycle time is reduced
• Slower instructions take more cycles
• Faster instruction take fewer cycles
• We can start next instruction earlier, rather than just waiting
• Can reuse datapath elements each cycle • What is needed to make this work?
• Since you are re-using elements for different purposes, you need more and/or wider MUXes.
• You may need extra registers if you need to remember an output for 1 or more cycles.
• Control is more complicated since you need to send new signals on each cycle. EECS 370 – Introduction to Computer Organization
22
Cycle 1
Cycle 2
Cycle 3
1
+
PC
Instructi on memory
3×8 decod er
M U X
Sign extend
Register file
En
A L U
+
M U X
Control ROM
M U X
Data memory
En R/W
add instruction will take 4 cycles (but cycles will be shorter). Only use the # of shorter cycles needed for the instruction
M U X
EECS 370 – Introduction to Computer Organization
23
Multicycle LC2K Datapath
M U X
M U X
M U X
A L U
PC
En
En
Con trol
M U X
M U X
addr
Memory
data
En R/W
Register file
En
1
0
Sign extend
MUXaddr
Memr/w
MUXdest
Regen
MUXalu2
Memen
IRen
MUXrdata
MUXalu1
ALUop
PCen
EECS 370 – Introduction to Computer Organization
24
Instruction Reg
ALU result
FSM – Multi-Cycle Control Signals
Finite State Machine
Control signals (transition functions)
add cycle 3
add cycle 4
nor cycle 3
State 0: Fetch cycle
State1: decode
lw sw beq
cycle3 cycle3
cycle3
2 4 6 9 11
nor lw sw beq cycle 4 cycle4 cycle4 cycle4
3 5 7 10 12
lw cycle5
8
EECS 370 – Introduction to Computer Organization
25
Implementing FSM
Outputs: 12 bits
Inputs: opcode
Outputs
Control lines for MUXs, ALU, Enable bits, R/W
Next state
Inputs
Opcode Current state
Implement transition functions (using a ROM and combinational circuits)
D
Q
4-bit state
Next state
Current state
EECS 370 – Introduction to Computer Organization
26
Building the Control ROM
Decoder Input: What happened to opcode???
Optimization using combinational logic. We will see it later, but opcode will not be input to the decoder
Current State
Output: Control Signals Next State
EECS 370 – Introduction to Computer Organization
27
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
First Cycle (State 0) Fetch Instruction
What operations need to be done in the first cycle of executing any instruction?
• Read memory[PC] and store into instruction register.
• Must select PC in memory address MUX (MUXaddr= 0) – B in diagram • Enable memory operation (Memen= 1) – C in diagram
• R/W should be (read) (Memr/w= 0) – D in diagram
• Enable Instruction Register write (IRen= 1) – H in diagram
• Calculate PC + 1
• Send PC to ALU (MUXalu1 = 0) – I in diagram
• Send 1 to ALU (MUXalu2 = 01) – J in diagram
• Select ALU add operation (ALUop = 0) – K in diagram
• PCen = 0; Regen = 0; MUXdest and MUXrdata= X • A, E, F, G in diagram, respectively
Next State: Decode Instruction
EECS 370 – Introduction to Computer Organization
28
First slide of L3_3
First Cycle (State 0) Operation
PC
En
M U X
M U X
M U X
M U X
M U X
A L U
En
Con trol
This is the same for all instructions, i.e., any opcode.
We do not know what the instruction is before decoding.
addr
Memory
data
En R/W
Register file
En
1
0
Sign extend
0
0
X
0
01
1
1
X
0
0
0
EECS 370 – Introduction to Computer Organization
29
Instruction Reg
ALU result
Building the Control ROM – State 0
1
1
1
1
1
Represents ROM memory for state.
Marks output lines (vertical) that will be 1 when that line in the decoder (horizontal) is selected by the input
Output: Control Signals Next State
EECS 370 – Introduction to Computer Organization
30
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
State 1: Instruction Decode
add cycle 3
add cycle 4
nor cycle 3
State 0: Fetch cycle
State1: decode
lw sw beq
cycle3 cycle3
2 4 6 9 11
nor lw sw beq cycle 4 cycle4 cycle4 cycle4
3 5 7 10 12 lw
cycle5
8
cycle3
EECS 370 – Introduction to Computer Organization
31
Update PC
Read registers (regA and regB)
Use opcode to determine next state
State 1: Output Function
P
C
En
M U X
M U X
X
M U
XA L
En
Con trol
M MU UX
U
addr
Memory
data
En R/W
Regist er file
En
1
0
Sign extend
X
X
X
0
XX
0
0
X
X
X
1
EECS 370 – Introduction to Computer Organization
32
Instruction Reg
ALU result
Building the Control ROM – State 1
1
1
1
1
?
?
?
1
?
Output: Control Signals Next State
EECS 370 – Introduction to Computer Organization
33
?
How will this be set?
We will revisit this later…
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
State 2: Add Cycle 3
add cycle 3
add cycle 4
nor cycle 3
State 0: Fetch cycle
State1: decode
lw sw beq
cycle3 cycle3
2 4 6 9 11
nor lw sw beq cycle 4 cycle4 cycle4 cycle4
3 5 7 10 12 lw
cycle5
8
cycle3
EECS 370 – Introduction to Computer Organization
34
State 2: Add Cycle 3 Operation
P
C
En
M U X
M U X
X
M U
XA L
En
Con trol
M MU UX
U
Send control signals to MUX to select values of regA and regB and control signal to ALU to add
addr
Memory
data
En R/W
Regist er file
En
1
0
Sign extend
X
X
X
0
00
0
0
X
1
0
0
EECS 370 – Introduction to Computer Organization
35
Instruction Reg
ALU result
Building the Control ROM – State 2
1
1
1
1
1
1
?
?
?
1
1
?
?
How will this be set?
We will revisit this later…
Output: Control Signals Next State
EECS 370 – Introduction to Computer Organization
36
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
State 3: Add Cycle 4
add cycle 3
add cycle 4
nor cycle 3
State 0: Fetch cycle
State1: decode
lw sw beq
cycle3 cycle3
cycle3
2 4 6 9 11
nor lw sw beq cycle 4 cycle4 cycle4 cycle4
3 5 7 10 12
lw cycle5
8
37
EECS 370 – Introduction to Computer Organization
State 3: Add Cycle 4 Operation
P
C
En
M U X
M U X
X
M U
XA L
En
M MU UX
U
Send control signal to address MUX to select dest and to data
MUX to select ALU output, then send write enable to register file.
Con trol
addr
Memory
data
En R/W
Regist er file
En
1
0
Sign extend
X
X
1
1
XX
0
0
1
X
X
0
EECS 370 – Introduction to Computer Organization
38
Instruction Reg
ALU result
Building the Control ROM – State 3
1
1
1
1
1
1
1
1
1
?
?
?
1
1
?
?
How will this be set?
We will revisit this later…
Output: Control Signals Next State
EECS 370 – Introduction to Computer Organization
39
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
Return to State 0
State 0:
add cycle 3 2
add cycle 4 3
nor cycle 3 4
nor cycle 4 5
lw cycle3 6
lw cycle4 7
Fetch cycle
State1: decode
sw cycle3 9
sw
cycle4 10
beq cycle3 11
beq cycle4 12
EECS 370 – Introduction to Computer Organization
40
lw cycle5
8
Fetch cycle to execute next instruction
What about nor?
Building the Control ROM – nor (States 4,5)
1 1
1
1
1
1
1
1
1
1
1
1
1
1
1
?
1
?
1
1
?
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
41
?
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
What About the Transition from State 1?
add cycle 3
add cycle 4
nor cycle 3
State 0: Fetch cycle
State1: decode
lw sw beq
cycle3 cycle3
2 4 6 9 11
nor lw sw beq cycle 4 cycle4 cycle4 cycle4
3 5 7 10 12 lw
cycle5
8
cycle3
EECS 370 – Introduction to Computer Organization
42
2 add 11 4nor
1
1
1
1
1
1
1
1
11
6lw 1
opcode
9 sw 11 beq
?? halt 0 noop
1
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
43
1
1
??
1
??
1
1
1
01
Next State
1
1
1 1
1
Next State
1
1
3 × 8 decoder
4 × 16 Decoder
Building the Control ROM
1
1
1
1
111
1
1
1
1
1
1
111 1
1
1
1
1
1
1
1111 state means “use the opcode to decide the next state”
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
44
2 add 4 nor 6 lw 9 sw 11 beq
?? halt 0 noop
opcode
1
1
1
1
1 1
1
Next State
1
1
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
3 × 8 decoder
4 × 16 Decoder
FSM – Multi-Cycle Clock
add
cycle 3 2
add cycle 4
3
State
0: State1:
nor
cycle 3 4
nor cycle 4
Fetch cycle
decode
5
lw lw lw
cycle3
sw cycle3
beq cycle3
cycle4 67
cycle5
8
9
11
sw cycle4
beq cycle4
10
12
clock
EECS 370 – Introduction to Computer Organization
45
State 6: LW Cycle 3
add cycle 3
add cycle 4
nor cycle 3
State 0: Fetch cycle
State1: decode
lw sw beq
cycle3 cycle3
cycle3
2 4 6 9 11 nor lw sw beq
cycle 4 cycle4 cycle4 cycle4
3 5 7 10 12 lw
cycle5
8
46
EECS 370 – Introduction to Computer Organization
State 6: LW Cycle 3 Operation
P
C
En
M U X
M U X
M U X
M U X
M U X
A L U
Con trol
addr
Memory
data
En R/W
Regist er file
En
1
0
Sign extend
X
X
X
0
11
0
0
X
1
0
EECS 370 – Introduction to Computer Organization
47
En
Calculate address for memory reference
0
Instruction Reg
ALU result
Building the Control ROM – State 6 lw
1
1
1
1
1
111 1
11
1
1
1
1
1
1
1
1
1
1
1
11
1
1
1
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
48
1
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
State 7: LW Cycle 4 Operation
P
C
En
M U X
M U X
X
M U
XA L
M MU UX
U
Con trol
addr
Memory
data
En R/W
Regist er file
En
1
0
Sign extend
1
0
X
0
XX
1
0
X
X
X
EECS 370 – Introduction to Computer Organization
49
En
Read memory location
0
Instruction Reg
ALU result
Building the Control ROM – State 7 lw
1
1
111 1
11 1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
11
1
1
1
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
50
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
State 8: LW Cycle 5 Operation
P
C
En
M U X
M U X
X
M U
XA L
M MU UX
U
Con trol
addr
Memory
data
En R/W
Regist er file
En
Sign extend
1
0
X
X
0
1
XX
0
0
0
X
X
EECS 370 – Introduction to Computer Organization
51
En
Write memory value to register file
0
data
Instruction Reg
ALU result
Building the Control ROM – State 8 lw
1
1
111 1
11 1
1
1
1
1
1
1
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
52
1
1
1
1
1
1
1
1
1
1
1
1
11
1
1
1
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
Return to State 0
State 0:
add cycle 3 2
add cycle 4 3
nor cycle 3 4
nor cycle 4 5
lw cycle3 6
lw cycle4 7
Fetch cycle
State1: decode
sw cycle3 9
sw
cycle4 10
beq cycle3 11
beq cycle4 12
EECS 370 – Introduction to Computer Organization
53
lw cycle5
8
Fetch cycle to execute next instruction
What about sw?
Building the Control ROM – sw (States 9,10)
111 1
11 1
11
1
1
1
1
1
1
1
1
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
54
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
11
1
1
1
1
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
Return to State 0
State 0:
add cycle 3 2
add cycle 4 3
nor cycle 3 4
nor cycle 4 5
lw cycle3 6
lw cycle4 7
Fetch cycle
State1: decode
sw cycle3 9
sw
cycle4 10
beq cycle3 11
beq cycle4 12
EECS 370 – Introduction to Computer Organization
55
lw cycle5
8
Fetch cycle to execute next instruction
What about beq?
State 11: BEQ Cycle 3 Operation
P
C
En
M U X
M U X
X
M U
XA L
M MU UX
U
Con trol
addr
Memory
data
En R/W
Regist er file
En
1
0
Sign extend
X
X
X
0
11
0
0
X
0
0
EECS 370 – Introduction to Computer Organization
56
En
Calculate target address for branch
0
Instruction Reg
ALU result
Building the Control ROM State 11 – beq
1
1
111 1
11 1
11
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
11
1
11
1
1
1
1
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
57
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
Write target address to PC if (dataregA == dataregB)
State 12: BEQ Cycle 4 Operation
P
C
En
M U X
M
U MX
U XM
eq?
A L U
M U X
U X
eq op
Con trol
addr
Memory
data
En R/W
En
Regist er file
En
1
0
Sign extend
X
X
X
0
00
0
0
X
1
X
0
EECS 370 – Introduction to Computer Organization
58
Instruction Reg
ALU result
Building the Control ROM State 12 – beq
1
1
111 1
11 1
11
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
11
1
11
1
1
1
1
Output: Control Signals
Next State
EECS 370 – Introduction to Computer Organization
59
PCen
MUXaddr Memen
Memr/w
IRen
MUXdest
MUXrdata Regen
MUXalu1
MUXalu2
MUXalu2 ALUop
4 × 16 Decoder
Logistics
• There are 3 videos for lecture 11
• L11_1 – LC2K-Datapath_Single-Cycle • L11_2 – Multi-Cycle_0
• L10_3 – Multi-Cycle_1
• There is one worksheet for lecture 10 1. L11 worksheet
EECS 370 – Introduction to Computer Organization
60