L11

25/03/2020

CS104: Computer Organization

25th March, 2020
Manojit Ghose
Computer Organization (IS F242)
Dip Sankar
Lecture Banerjee
1 : Introductory Thoughts

Dip Sankar Banerjee

dsb@hyderabad.bits-pilani.ac.in
Department
Indian Institute of CS &Technology,
of Information IS Guwahati
Jan-Apr 2020
 L11
25/03/2020

Control Design

Processor
Input
Control
Memory

Datapath Output

• Next: Designing the Control for the Single Cycle

Datapath
 L11
25/03/2020

Adding Control
• Analyze datapath and RTLs for control
– Identify control points for pieces of the datapath
• Instruction Fetch Unit
• Integer function units
• Memory
– Categorize type of control signal
• Flow of data through multiplexors
• Writes of state information
– Derive control signal values for each instruction
• Design and implement control with logic/PLA/ROM (for
single cycle & pipelined)
 L11
25/03/2020

Instruction Fetch (first part)

• Always fetch next instruction
Mem[PC];
30
Addr[31:2]
PC[31:28] 30
Addr[1:0]
4 “00”
1 Instruction
Target 30

MUX
Instruction[25:0] 26 Memory
PC

0
Adder

30 0 32
MUX
30
“1”
Adder

1 Jump = previous Instruction[31:0]

Clk 30
SignExt

imm16 30
Branch = Zero =
Instruction[15:0] 16
previous previous
 L11
25/03/2020

Control for Arithmetic

Branch = 0 Instruction[31:0]
Instruction

[21:25]

[16:20]

[11:15]

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

ALU
32 32-bit
32 Registers busB 32 0

MUX
Clk 0
32
MUX

32
Extender

WrEn Adr 1
1 Data In32
imm16 32 Data
16 Memory
Clk
ALUSrc = 0

ExtOp = X
 L11
25/03/2020

Instruction Fetch at End

• Increment PC: PC = PC+4; (for all but Branch/Jump)

30
Addr[31:2]
PC[31:28] 30
Addr[1:0]
4 “00”
1 Instruction
Target 30

MUX
Instruction[25:0] 26 Memory
PC

0
Adder

30 0 32
MUX
30
“1”
Adder

1 Jump = 0 Instruction[31:0]
Clk 30
SignExt

imm16 30
Instruction[15:0] 16
Branch = 0 Zero = X
 L11
25/03/2020

Control for Immediate (ori)

Branch = 0 Instruction[31:0]
Instruction

[21:25]

[16:20]

[11:15]

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

ALU
32 32-bit
32 Registers busB 32 0

MUX
Clk 0
32
MUX

32
Extender

WrEn Adr 1
1 Data In32
imm16 32 Data
16 Memory
Clk
ALUSrc=1

ExtOp=0
 L11
25/03/2020

Control for Load (lw)

Branch = 0 Instruction[31:0]
Instruction

[21:25]

[16:20]

[11:15]

[0:15]
Jump = 0
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
Rw Ra Rb MemWr = 0
busW 32

ALU
32 32-bit
32 Registers busB 32 0

MUX
Clk 0
32
MUX

32
Extender

WrEn Adr 1
1 Data In32
imm16 32 Data
16 Memory
Clk
ALUSrc = 1

ExtOp = 1
 L11
25/03/2020

Control for Store (sw)

Branch = 0 Instruction[31:0]
Instruction

[21:25]

[16:20]

[11:15]

[0:15]
Jump = 0
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

ALU
32 32-bit
32 Registers busB 32 0

MUX
Clk 0
32
MUX

32
Extender

WrEn Adr 1
1 Data In32
imm16 32 Data
16 Memory
Clk
ALUSrc = 1

ExtOp = 1
 L11
25/03/2020

Control for Branch (beq)

Branch = 1 Instruction[31:0]
Instruction

[21:25]

[16:20]

[11:15]

[0:15]
Jump = 0
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
Rw Ra Rb MemWr = 0
busW 32

ALU
32 32-bit
32 Registers busB 32 0

MUX
Clk 0
32
MUX

32
Extender

WrEn Adr 1
1 Data In32
imm16 32 Data
16 Memory
Clk
ALUSrc = 0

ExtOp = X
 L11
25/03/2020

Instruction Fetch (beq)

Consider the interesting case where we branch (Zero = 1)

30
Addr[31:2]
PC[31:28] 30
Addr[1:0]
4 “00”
1 Instruction
Target 30

MUX
Instruction[25:0] 26 Memory
PC

0
Adder

30 0 32
MUX
30
“1”
Adder

1 Jump = 0 Instruction[31:0]
Clk 30
SignExt

imm16 30
Instruction[15:0] 16
Branch = 1 Zero = 1
 L11
25/03/2020

Control for Jump (j)

Branch = 0 Instruction[31:0]
Instruction

[21:25]

[16:20]

[11:15]

[0:15]
Jump = 1
Rd Rt Fetch Unit
RegDst = X Clk
1 Mux 0
Rs Rt ALUctr = X Rt Rs Rd Imm16
RegWr = 0 5 5 5 MemtoReg = X
busA Zero
Rw Ra Rb MemWr = 0
busW 32

ALU
32 32-bit
32 Registers busB 32 0

MUX
Clk 0
32
MUX

32
Extender

WrEn Adr 1
1 Data In32
imm16 32 Data
16 Memory
Clk
ALUSrc = X

ExtOp = X
 L11
25/03/2020

Instruction Fetch (j)

30
Addr[31:2]
PC[31:28] 30
Addr[1:0]
4 “00”
1 Instruction
Target 30

MUX
Instruction[25:0] 26 Memory
PC

0
Adder

30 0 32
MUX
30
“1”
Adder

1 Jump = 1 Instruction[31:0]
Clk 30
SignExt

imm16 30
Instruction[15:0] 16
Branch = 0 Zero = X
 L11
25/03/2020

Control Path
Branch Instruction[31:0]
Instruction

[21:25]

[16:20]

[11:15]

[0:15]
Jump
Rd Rt Fetch Unit
RegDst Clk
1 Mux 0
Rs Rt ALUctr Rt Rs Rd Imm16
RegWr 5 5 5 Zero MemtoReg
busA
Rw Ra Rb MemWr
busW 32

ALU
32 32-bit
32 Registers busB 32 0

MUX
Clk 0
32
MUX

32
Extender

WrEn Adr 1
1 Data In32
imm16 32 Data
16 Memory
Clk
ALUSrc

ExtOp
 L11
25/03/2020

Summary of Control Signals

coding from func 10 0000 10 0010 Not Important

green card op 00 0000 00 0000 00 1101 10 0011 10 1011 00 0100 00 0010
add sub ori lw sw beq jump
RegDst 1 1 0 0 x x x
ALUSrc 0 0 1 1 1 0 x
MemtoReg 0 0 0 1 x x x
RegWrite 1 1 1 1 0 0 0
MemWrite 0 0 0 0 1 0 0
Branch 0 0 0 0 0 1 0
Jump 0 0 0 0 0 0 1
ExtOp x x 0 1 1 x x
ALUctr<2:0> Add Sub Or Add Add Sub xxx
 L11
25/03/2020

Multilevel Decoding
• 12-input control will be very large (212 = 4096)
• To keep decoder size smaller, decode some control
lines in each stage
• Since only R-type instructions (with op = 000000)
need function field bits, give these to ALU control

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

ALU
 L11
25/03/2020

Multilevel Decoding: Main

Control Table
op 00 0000 00 1101 10 0011 10 1011 00 0100 00 0010
R-type ori lw sw beq jump
RegDst 1 0 0 x x x
ALUSrc 0 1 1 1 0 x
MemtoReg 0 0 1 x x x
RegWrite 1 1 1 0 0 0
MemWrite 0 0 0 1 0 0
Branch 0 0 0 0 1 0
Jump 0 0 0 0 0 1
ExtOp x 0 1 1 x x
ALUop<N:0> “R-type” Or Add Add Subtract xxx
 L11
25/03/2020

The 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 wide to
represent:
– (1) “R-type” instructions
– “I-type” instructions that require the ALU to perform:
• (2) Or, (3) Add, (4) Subtract, and (5) And (e.g. andi)

R-type ori lw sw beq jump

ALUop (Symbolic) “R-type” Or Add Add Subtract xxx
ALUop<2:0> 1 00 0 10 0 00 0 00 0 01 xxx
 L11
25/03/2020

The Decoding of the “func” Field

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

R-type ori lw sw beq jump

ALUop (Symbolic) “R-type” Or Add Add Subtract xxx
ALUop<2:0> 1 00 0 10 0 00 0 00 0 01 xxx
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 Add
10 0010 subtract 001 Subtract
ALU

10 0100 and 010 And

10 0101 or 110 Or
10 1010 set-on-less-than 111 Set-on-less-than
 L11
25/03/2020

Truth Tables funct<3:0> Instruction Op.

0000 add
0010 subtract
ALUop R-type ori lw sw beq 0100 and
(Symbolic) “R-type” Or Add Add Subtract 0101 or
ALUop<2:0> 1 00 0 10 0 00 0 00 0 01 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
 L11
25/03/2020

The 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>
 L11
25/03/2020

The 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> & !func<2> & !func<0>
 L11
25/03/2020

The ALU Control Logic

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<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>
 L11
25/03/2020

Main Control Truth Table

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 00 0010
R-type ori lw sw beq jump
RegDst 1 0 0 x x x
ALUSrc 0 1 1 1 0 x
MemtoReg 0 0 1 x x x
RegWrite 1 1 1 0 0 0
MemWrite 0 0 0 1 0 0
Branch 0 0 0 0 1 0
Jump 0 0 0 0 0 1
ExtOp x 0 1 1 x x
ALUop (Symbolic) “R-type” Or Add Add Subtract xxx
ALUop <2> 1 0 0 0 0 x
ALUop <1> 0 1 0 0 0 x
ALUop <0> 0 0 0 0 1 x
 L11
25/03/2020

Truth Table for RegWrite

op 00 0000 00 1101 10 0011 10 1011 00 0100 00 0010
R-type ori lw sw beq jump
RegWrite 1 1 1 0 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> .. op<5> ..
<0> <0> <0> <0> <0> op<0>

R-type ori lw sw beq jump

RegWrite
 L11
25/03/2020
PLA Implementation
op<5> .. op<5> .. op<5> .. op<5> .. op<5> .. op<5> ..
<0> <0> <0> <0> <0> op<0>

R-type ori lw sw beq jump

RegWrite

ALUSrc
RegDst
MemtoReg
MemWrite
Branch
Jump
ExtOp
ALUop<2>
ALUop<1>
ALUop<0>
 L11
25/03/2020

Implementing Control
• Programmable Logic Array (PLA) vs.
“Random Logic”
– Design Changes
• Validation changes are common
• PLA is less work to change; area/timing impact is predictable
– Area
• Tradeoff depends on complexity of logic (# of gates)
– Timing and Power
• Random logic generally better since individual paths can be tuned
• Alternative approach is Read Only Memory
(ROM/PROM)
– Also combinational, but size makes it slow
– used for microcoded control with more than one state/cycle per
instruction
 L11
25/03/2020
Putting It All Together
ALUop
ALU ALUctr
RegDst 3 func
op Control 3
Main Instr[5:0] 6
6 Control ALUSrc
Instr[31:26] : Branch Instruction[31:0]
Instruction

[21:25]

[16:20]

[11:15]

[0:15]
Jump
Rd Rt Fetch Unit
RegDst Clk
1 Mux 0
Rs Rt ALUctr Rt Rs Rd Imm16
RegWr 5 5 5 MemtoReg
busA Zero
Rw Ra Rb MemWr
busW 32

ALU
32 32-bit
32 Registers busB 32 0

MUX
Clk 0
32
MUX

32
Extender

WrEn Adr 1
1 Data In32
imm16 32 Data
16 Memory
Clk
ALUSrc
ExtOp
 L11
25/03/2020
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

RegisterWrite 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
Data Mem Address Old Value New Value
Data Memory Access Time
busW Old Value New
Sum of {Mux Delay+setup+skew}
 L11
25/03/2020

Single Cycle Processor

• Advantages
– Single cycle per instruction makes logic and clock simple
– All machines would have a CPI of 1
• Disadvantages
– Inefficient utilization of memory and functional units since different
instructions take different lengths of time
• Each functional unit is used only once per clock cycle
• e.g. ALU only computes values a small amount of the time
– Cycle time is the worst case path  long cycle times!
• Load instruction
– PC CLK-to-Q +
– instruction memory access time +
– register file access time +
– ALU delay +
– data memory access time +
– register file setup time +
– clock skew
– All machines would have a CPI of 1, with cycle time set by the
longest instruction!
 L11
25/03/2020

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
• Source registers always in same place Datapath Output
• Immediates same size, location
• Operations always on registers/immediates