Computer Architecture

Designing Single Cycle Control

The Big Picture: Where are We Now?

Processor
Input
Control
Memory

Datapath
Output

Lec 3.2
An Abstract View of the Implementation

Ideal Control
Instruction Control Signals Conditions
Instruction
Memory
Rd Rs Rt
5 5 5
Instruction
Address
A Data
Rw Ra Rb 32 Data
32 Address
Next Address

32 Ideal Out
32 32-bit

ALU
Data
PC

Registers Data Memory

B
In

Clk Clk
32
Clk

Datapath

Lec 3.3
 Recap: A Single Cycle Datapath

We have everything except control signals (underline)

Instruction<31:0>
nPC_sel Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
Clk
RegDst 1 Mux 0
Rs Rt Rt Rs Rd Imm16
RegWr 5 5 5 ALUctr Zero
busA MemWr MemtoReg
Rw Ra Rb
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32
Clk

Mux
32
Mux 32
WrEn Adr 1
Extender

1 Data In32
imm16 Data
32
16 Memory
Clk
ALUSrc

ExtOp

Lec 3.4
Recap: Meaning of the Control Signals

nPC_MUX_sel: 0 ⇒ PC <– PC + 4
1 ⇒ PC <– PC + 4 + SignExt(Im16) || 00

nPC_MUX_sel

Inst
Memory
Adr
4
Adder

00
Mux

PC
Adder
imm16

PC Ext

Clk

Lec 3.5
Recap: Meaning of the Control Signals

ExtOp: “zero”, “sign”
MemWr: 1 ⇒ write memory

MemtoReg: 0 ⇒ ALU; 1 ⇒ Mem

ALUsrc: 0 ⇒ regB; 1 ⇒ immed

RegDst: 0 ⇒ “rt”; 1 ⇒ “rd”

ALUctr: “add”, “sub”, “or”

RegWr: 1 ⇒ write register

Equal
Rd Rt ALUctr MemWr MemtoReg
RegDst
1 0
Rs Rt
RegWr 5 5 5
busA
Rw Ra Rb =
busW 32 32-bit 32

ALU
32 Registers busB 32 0
0

Mux
32
Mux

Clk 32 WrEn Adr

Extender

1 Data In 1
imm16 32 Data
16 Memory
Clk

ExtOp ALUSrc
Lec 3.6
RTL: The Add Instruction

31 26 21 16 11 6 0
op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

add rd, rs, rt

• mem[PC] Fetch the instruction

from memory

• R[rd] <- R[rs] + R[rt] The actual operation

• PC <- PC + 4 Calculate the next

instruction’s address

Lec 3.7
Instruction Fetch Unit at the Beginning of Add

Fetch the instruction from Instruction memory:

Instruction <- mem[PC]
Inst

Same for all instructions Memory Instruction<31:0>
Adr

nPC_MUX_sel

4
Adder

00
0

Mux

PC
1
Adder
imm16

Clk

Lec 3.8
 The Single Cycle Datapath During Add

R[rd] <- R[rs] + R[rt]

Instruction<31:0>
nPC_sel= +4
Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
RegDst = 1 Clk
1 Mux 0
Rs Rt ALUctr = Add Rt Rs Rd Imm16
RegWr = 1 5 5 5 MemtoReg = 0
busA Zero
Rw Ra Rb MemWr=0
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32
Clk

Mux
32
Mux
32
WrEn Adr 1
Extender

1 Data In 32
imm16 Data
32
16 Memory
Clk
ALUSrc=0

ExtOp = x

Lec 3.9
Instruction Fetch Unit at the End of Add

PC <- PC + 4
• This is the same for all instructions except: Branch and Jump

Inst
Memory Instruction<31:0>
Adr

nPC_MUX_sel

4
Adder

00
0
Mux

PC

1
Adder
imm16

Clk

Lec 3.10
 The Single Cycle Datapath During Or Immediate

R[rt] <- R[rs] or ZeroExt[Imm16]

Instruction<31:0>
nPC_sel =
Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
RegDst = Clk
1 Mux 0
Rs Rt ALUctr = Rt Rs Rd Imm16
RegWr = 5 5 5 MemtoReg =
busA Zero MemWr =
Rw Ra Rb
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32
Clk

Mux
32 Mux
32
WrEn Adr 1
Extender

1 Data In 32
imm16 Data
32
16 Memory
Clk
ALUSrc =

ExtOp =
Lec 3.11
 The Single Cycle Datapath During Or Immediate

Instruction<31:0>
nPC_sel= +4
Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
RegDst = 0 Clk
1 Mux 0
Rs Rt ALUctr = Or Rt Rs Rd
Imm16
RegWr = 1 5 5 5 MemtoReg = 0
busA Zero MemWr = 0
Rw Ra Rb
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32
Clk

Mux
32

Mux
32
WrEn Adr 1
Extender

1 Data In 32
imm16 Data
32
16 Memory
Clk
ALUSrc = 1

ExtOp = 0

Lec 3.12
The Single Cycle Datapath During Load

R[rt] <- Data Memory [ R[rs] + SignExt[imm16] ]

Instruction<31:0>
nPC_sel= +4
Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
RegDst = 0 Clk
1 Mux 0
Rs Rt ALUctr=Add Rt Rs Rd Imm16
RegWr = 1 5 5 5 MemtoReg = 1
busA Zero MemWr = 0
Rw Ra Rb
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32
Clk

Mux
32
Mux 1
WrEn Adr
Extender

1 Data In 32
imm16 Data 32
32
16 Memory
Clk
ALUSrc = 1

ExtOp = 1
Lec 3.13
 The Single Cycle Datapath During Store

Data Memory [ R[rs] + SignExt[imm16] ] <- R[rt]

Instruction<31:0>
nPC_sel =
Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
RegDst = Clk
1 Mux 0
Rs Rt ALUctr = Rt Rs Rd Imm16
RegWr = 5 5 5 MemtoReg =
busA Zero MemWr =
Rw Ra Rb
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32

Mux
Clk
32 Mux 32
WrEn Adr 1
Extender

1 Data In 32
imm16 Data
32
16 Memory
Clk
ALUSrc =

ExtOp =

Lec 3.14
 The Single Cycle Datapath During Store

Instruction<31:0>
nPC_sel= +4
Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
RegDst = x Clk
1 Mux 0
Rs Rt ALUctr= Add Rt Rs Rd Imm16
RegWr = 0 5 5 5 MemtoReg = x
busA Zero
Rw Ra Rb MemWr = 1
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32
Clk

Mux
32

Mux
32
WrEn Adr 1
Extender

1 Data In 32
imm16 Data
32
16 Memory
Clk
ALUSrc = 1

ExtOp = 1

Lec 3.15
 The Single Cycle Datapath During Branch

if (R[rs] - R[rt] == 0) then Zero <- 1 ; else Zero <- 0

Instruction<31:0>
nPC_sel= “Br”
Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
RegDst = x Clk
1 Mux 0
Rs Rt ALUctr= Sub Rt Rs Rd
Imm16
RegWr = 0 5 5 5 MemtoReg = x
busA Zero MemWr = 0
Rw Ra Rb
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32
Clk

Mux
32 Mux
32
WrEn Adr 1
Extender

1 Data In 32
imm16 Data
32
16 Memory
Clk
ALUSrc = 0

ExtOp = x
Lec 3.16
 Instruction Fetch Unit at the End of Branch

Inst
Memory
Instruction<31:0>
nPC_sel Adr
Zero

nPC_MUX_sel
What is encoding of nPC_sel?

• Direct MUX select?
4
• Branch / not branch
Adder

00

0
nPC_sel zero? MUX
Mux

PC

0 x 0
1 0 0
1
Adder

1 1 1
imm16

Clk

Lec 3.17
Step 4: Given Datapath: RTL -> Control

Instruction<31:0>

<21:25>
Inst

<21:25>

<16:20>

<11:15>

<0:15>
Memory
Adr
Op Fun Rt Rs Rd Imm16

Control

nPC_sel RegWr RegDst ExtOp ALUSrcALUctr MemWr MemtoReg Zero

DATA PATH

Lec 3.18
Summary of Control Signals

inst Register Transfer

ADD R[rd] <– R[rs] + R[rt]; PC <– PC + 4
ALUsrc = RegB, ALUctr = “add”, RegDst = rd, RegWr, nPC_sel = “+4”
SUB R[rd] <– R[rs] – R[rt]; PC <– PC + 4
ALUsrc = RegB, ALUctr = “sub”, RegDst = rd, RegWr, nPC_sel = “+4”
ORi R[rt] <– R[rs] + zero_ext(Imm16); PC <– PC + 4
ALUsrc = Im, Extop = “Z”, ALUctr = “or”, RegDst = rt, RegWr, nPC_sel = “+4”
LOAD R[rt] <– MEM[ R[rs] + sign_ext(Imm16)]; PC <– PC + 4
ALUsrc = Im, Extop = “Sn”, ALUctr = “add”, MemtoReg,
RegDst = rt, RegWr, nPC_sel = “+4”
STORE MEM[ R[rs] + sign_ext(Imm16)] <– R[rt]; PC <– PC + 4
ALUsrc = Im, Extop = “Sn”, ALUctr = “add”, MemWr, nPC_sel = “+4”
BEQ if ( R[rs] == R[rt] ) then PC <– [PC + sign_ext(Imm16)] || 00 else PC <– PC + 4
nPC_sel = “Br”, ALUctr = “sub”

Lec 3.19
Summary of the Control Signals

See func 10 0000 10 0010 We Don’t Care :-)

Appendix A op 00 0000 00 0000 00 1101 10 0011 10 1011 00 0100
add sub ori lw sw beq
RegDst 1 1 0 0 x x
ALUSrc 0 0 1 1 1 0
MemtoReg 0 0 0 1 x x
RegWrite 1 1 1 1 0 0
MemWrite 0 0 0 0 1 0
nPCsel 0 0 0 0 0 1

ExtOp x x 0 1 1 x

ALUctr<2:0> Add Sub Or Add Add Sub

Lec 3.20
Concept of Local Decoding

op 00 0000 00 1101 10 0011 10 1011 00 0100

R-type ori lw sw beq
RegDst 1 0 0 x x
ALUSrc 0 1 1 1 0
MemtoReg 0 0 1 x x
RegWrite 1 1 1 0 0
MemWrite 0 0 0 1 0
Branch 0 0 0 0 1

ExtO x 0 1 1 x
p
ALUop<N:0> “R-type” Or Add Add Sub

func
ALU ALUctr
op Main 6
ALUop Control 3
6 Control
(Local)
N

ALU
Lec 3.21
Encoding of ALUop
func
op 6 ALU ALUctr
Main
ALUop Control
6 Control 3
(Local)
N

In this exercise, ALUop has to be 2 bits wide to represent:

• (1) “R-type” instructions
• “I-type” instructions that require the ALU to perform:
- (2) Or, (3) Add, and (4) Subtract

To implement the full MIPS ISA, ALUop has to be 3 bits to represent:

• (1) “R-type” instructions
• “I-type” instructions that require the ALU to perform:
- (2) Or, (3) Add, (4) Subtract, (5) And, and (6) Xor

R-type ori lw sw beq

ALUop (Symbolic) “R-type” Or Add Add Sub
ALUop<2:0> 1 00 0 10 0 00 0 00 0 01

Lec 3.22
 Decoding of the “func” Field
func
op 6 ALU ALUctr
Main
ALUop Control
6 Control 3
(Local)
N

R-type ori lw sw beq

ALUop (Symbolic) “R-type” Or Add Add Sub
ALUop<2:0> 1 00 0 10 0 00 0 00 0 01

31 26 21 16 11 6 0
R-type op rs rt rd shamt funct

funct<5:0> Instruction Operation ALUctr ALUctr<2:0> ALU Operation

10 0000 add 000 And
10 0010 subtract ALU 001 Or
10 0100 and 010 Add
10 0101 or 110 Subtract
10 1010 set-on-less-than 111 Set-on-less-than

Lec 3.23
Truth Table for ALUctr
funct<3:0> Instruction Op.
0000 add
ALUop R-type ori lw sw beq 0010 subtract
(Symbolic) “R-type” Or Add Add Sub 0100 and
ALUop<2:0> 1 00 0 10 0 00 0 00 0 01 0101 or
1010 set-on-less-than

ALUop func ALU ALUctr

bit<2> bit<1> bit<0> bit<3> bit<2> bit<1> bit<0> Operation bit<2> bit<1> bit<0>
0 0 0 x x x x Add 0 1 0
0 x 1 x x x x Subtract 1 1 0
0 1 x x x x x Or 0 0 1
1 x x 0 0 0 0 Add 0 1 0
1 x x 0 0 1 0 Subtract 1 1 0
1 x x 0 1 0 0 And 0 0 0
1 x x 0 1 0 1 Or 0 0 1
1 x x 1 0 1 0 Set on < 1 1 1

Lec 3.24
Logic Equation for ALUctr<2>

ALUop func
bit<2> bit<1> bit<0> bit<3> bit<2> bit<1> bit<0> ALUctr<2>
0 x 1 x x x x 1
1 x x 0 0 1 0 1
1 x x 1 0 1 0 1

This makes func<3> a don’t care

ALUctr<2> = !ALUop<2> & ALUop<0> +

ALUop<2> & !func<2> & func<1> & !func<0>

Lec 3.25
Logic Equation for ALUctr<1>

ALUop func
bit<2> bit<1> bit<0> bit<3> bit<2> bit<1> bit<0> ALUctr<1>
0 0 0 x x x x 1
0 x 1 x x x x 1
1 x x 0 0 0 0 1
1 x x 0 0 1 0 1
1 x x 1 0 1 0 1

ALUctr<1> = !ALUop<2> & !ALUop<1> +

!ALUop<2> & ALUop<0> +

ALUop<2> & !func<2> & !func<0>

Lec 3.26
Logic Equation for ALUctr<0>

ALUop func
bit<2> bit<1> bit<0> bit<3> bit<2> bit<1> bit<0> ALUctr<0>
0 1 x x x x x 1
1 x x 0 1 0 1 1
1 x x 1 0 1 0 1

ALUctr<0> = !ALUop<2> & ALUop<1>

+ ALUop<2> & !func<3> & func<2> & !func<1> & func<0>
+ ALUop<2> & func<3> & !func<2> & func<1> & !func<0>

Lec 3.27
ALU Control Block

func
6 ALU ALUctr
ALUop Control
3
(Local)
3

ALUctr<2> = !ALUop<2> & ALUop<0> +

ALUop<2> & !func<2> & func<1> & !func<0>

ALUctr<1> = !ALUop<2> & !ALUop<1> + !ALUop<2> & ALUop<0>

ALUop<2> & !func<2> & !func<0>

ALUctr<0> = !ALUop<2> & ALUop<1> + ALUop<2> & !func<3> &

func<2> & !func<1> & func<0> + ALUop<2> &
func<3> & !func<2> & func<1> & !func<0>

Lec 3.28
Step 5: Logic For Each Control Signal

nPC_sel <= if (OP == BEQ) then “Br” else “+4”

ALUsrc <= if (OP == “Rtype”) then “regB” else “immed”

ALUctr <= if (OP == “Rtype”) then funct

elseif (OP == ORi) then “OR”
elseif (OP == BEQ) then “sub”
else “add”

ExtOp <= _____________

MemWr <= _____________

MemtoReg <= _____________

RegWr: <=_____________

RegDst: <= _____________

Lec 3.29
Step 5: Logic for Each Control Signal

nPC_sel <= if (OP == BEQ) then “Br” else “+4”

ALUsrc <= if (OP == “Rtype”) then “regB” else “immed”

ALUctr <= if (OP == “Rtype”) then funct

elseif (OP == ORi) then “OR”
elseif (OP == BEQ) then “sub”
else “add”

ExtOp <= if (OP == ORi) then “zero” else “sign”

MemWr <= (OP == Store)

MemtoReg <= (OP == Load)

RegWr: <= if ((OP == Store) || (OP == BEQ)) then 0 else 1

RegDst: <= if ((OP == Load) || (OP == ORi)) then 0 else 1

Lec 3.30
“Truth Table” for the Main Control
RegDst
func
ALUSrc ALU ALUctr
op Main 6
6 Control
: Control 3
ALUop (Local)
3

op 00 0000 00 1101 10 0011 10 1011 00 0100

R-type ori lw sw beq
RegDst 1 0 0 x x
ALUSrc 0 1 1 1 0
MemtoReg 0 0 1 x x
RegWrite 1 1 1 0 0
MemWrite 0 0 0 1 0
nPC_sel 0 0 0 0 1

ExtOp x 0 1 1 x
ALUop (Symbolic) “R-type” Or Add Add Subtract
ALUop <2> 1 0 0 0 0
ALUop <1> 0 1 0 0 0
ALUop <0> 0 0 0 0 1
Lec 3.31
“Truth Table” for RegWrite
op 00 0000 00 1101 10 0011 10 1011 00 0100
R-type ori lw sw beq
RegWrite 1 1 1 0 0

RegWrite = R-type + ori + lw

= !op<5> & !op<4> & !op<3> & !op<2> & !op<1> & !op<0> (R-type)
+ !op<5> & !op<4> & op<3> & op<2> & !op<1> & op<0> (ori)
+ op<5> & !op<4> & !op<3> & !op<2> & op<1> & op<0> (lw)

op<5> .. op<5> .. op<5> .. op<5> .. op<5> ..

<0> <0> <0> <0> <0>

R-type ori lw sw beq

RegWrite

Lec 3.32
PLA Implementation of the Main Control
op<5> .
. op<5> .. op<5> .. op<5> .. op<5> ..
<0> <0> <0> <0> <0>

R-type ori lw sw beq

RegWrite

ALUSrc
RegDst
MemtoReg
MemWrite
Branch

ExtOp
ALUop<2>
ALUop<1>
ALUop<0>

Lec 3.33
 Putting it All Together: A Single Cycle Processor
ALUop
ALU ALUctr
Instr<31:26> RegDst 3 func Control
Main 3
op Instr<5:0> 6
6 Control ALUSrc
: Instruction<31:0>
nPC_sel
Instruction

<21:25>

<16:20>

<11:15>

<0:15>
Rd Rt Fetch Unit
RegDst Clk
1 Mux 0
Rs Rt Rt Rs Rd Imm16
RegWr 5 5 5 ALUctr
busA Zero MemWr MemtoReg
Rw Ra Rb
busW 32
32 32-bit

ALU
32 0
Registers busB 0 32
Clk

Mux
32 Mux
32
WrEn Adr 1
Extender

1 Data In32
imm16 Data
32
Instr<15:0> 16 Clk
Memory
ALUSrc

ExtOp
Lec 3.34
Recap: An Abstract View of the Critical Path (Load)

Critical Path (Load Operation) =

PC’s Clk-to-Q +
Instruction Memory’s Access Time +
Register File’s Access Time +
ALU to Perform a 32-bit Add +
Ideal Data Memory Access Time +
Instruction Setup Time for Register File Write +
Instruction Clock Skew
Memory
Rd Rs Rt Imm
5 5 5 16
Instruction
Address
A Data
Rw Ra Rb 32 Address
Next Address

32 32 Ideal
32 32-bit

ALU
Data
PC

Registers Data Memory

B
In

Clk Clk
32
Clk

Lec 3.35
 Worst Case Timing (Load)
Clk
Clk-to-Q
PC Old Value New Value
Instruction Memory Access Time
Rs, Rt, Rd, Old Value New Value
Op, Func
Delay through Control Logic
ALUctr Old Value New Value

ExtOp Old Value New Value

ALUSrc Old Value New Value

MemtoReg Old Value New Value Register

Write Occurs
RegWr Old Value New Value
Register File Access Time
busA Old Value New Value
Delay through Extender & Mux
busB Old Value New Value
ALU Delay
Address Old Value New Value
Data Memory Access Time
busW Old Value New
Lec 3.36
Drawback of this Single Cycle Processor

Long cycle time:

• Cycle time must be long enough for the load instruction:
PC’s Clock -to-Q +
Instruction Memory Access Time +
Register File Access Time +
ALU Delay (address calculation) +
Data Memory Access Time +
Register File Setup Time +
Clock Skew

Cycle time for load is much longer than needed for all other
instructions

Lec 3.37
 Summary

Single cycle datapath => CPI=1, CCT => long

5 steps to design a processor

• 1. Analyze instruction set => datapath requirements
• 2. Select set of datapath components & establish clock methodology
• 3. Assemble datapath meeting the requirements
• 4. Analyze implementation of each instruction to determine setting of control
points that effects the register transfer.
• 5. Assemble the control logic
Processor

Control is the hard part Input
Control

MIPS makes control easier Memory

• Instructions same size

Datapath Output
• Source registers always in same place
• Immediates same size, location
• Operations always on registers/immediates

Lec 3.38