Fundamentals of Computer Systems
A Single Cycle MIPS Processor
Stephen A. Edwards
and
Martha A. Kim
Columbia University
Spring 2012
Illustrations Copyright © 2007 Elsevier
Let s Build a Simple Processor
Supported instructions:
R-type: and, or, addu, subu, slt
Memory instructions: lw, sw
Branch instructions: beq
Version 2.0:
I-type: addiu
J-type: j
MIPS State Elements
This is the programmer-visible state in the ISA
CLK
CLK CLK
PC'
PC WE3 WE
A1 RD1
32 32 5 32
A RD
32 32
A2 RD2
A RD
5 32
Instruction 32 32
Data
Memory
A3 Memory
5
Register
WD3 WD
32 32
File
ALU Interface and Implementation
A B
A B
N N
N N
F
3
ALU
N
N
F2
Y
N
F2 F1 F0 Func.
0 0 0 A & B
Cout
0 0 1 A | B +
[N-1] S
0 1 0 A + B
0 1 1
1 0 0 A & B
N N N N
1 0 1 A | B
F1:0
2
1 1 0 A - B
N
1 1 1 A < B (slt)
Y
1
0
Extend
Zero
1
0
3
2
Datapath Elements for thelwInstruction
Fetch instruction from instruction memory:
Send the PC to the instruction memory s address
CLK CLK
CLK
WE3 WE
PC Instr
A1 RD1
PC'
A RD
A RD
Instruction
A2 RD2
Data
Memory
A3 Memory
Register
WD3 WD
File
lw rt, offset(base)
LW
base rt offset
1 0 0 0 1 1
Datapath Elements for thelwInstruction
Read the base register
CLK CLK
CLK
25:21
WE3 WE
A1 RD1
PC' PC Instr
A RD
A RD
Instruction
A2 RD2
Data
Memory
A3 Memory
Register
WD3 WD
File
lw rt, offset(base)
LW
base rt offset
1 0 0 0 1 1
Datapath Elements for thelwInstruction
Sign-extend the immediate
CLK CLK
CLK
WE3 WE
25:21
A1 RD1
PC' PC Instr
A RD
A RD
Instruction
A2 RD2
Data
Memory
A3 Memory
Register
WD3 WD
File
SignImm
15:0
Sign Extend
lw rt, offset(base)
LW
base rt offset
1 0 0 0 1 1
Datapath Elements for thelwInstruction
Add the base register and the sign-extended immediate
to compute the data memory address
ALUControl2:0
010
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
A1 RD1
PC' PC Instr
A RD
ALUResult
A RD
Instruction
A2 RD2
SrcB
Data
Memory
A3 Memory
Register
WD3 WD
File
SignImm
15:0
Sign Extend
lw rt, offset(base)
LW
base rt offset
1 0 0 0 1 1
ALU
Datapath Elements for thelwInstruction
Read data from memory and write it back to rt in the
register file
RegWrite ALUControl2:0
1 010
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
A1 RD1
PC' PC Instr
A RD
ALUResult ReadData
A RD
Instruction
A2 RD2
SrcB
Data
Memory 20:16
A3 Memory
Register
WD3 WD
File
SignImm
15:0
Sign Extend
lw rt, offset(base)
LW
base rt offset
1 0 0 0 1 1
ALU
Datapath Elements for thelwInstruction
Add four to the program counter to determine address
of the the next instruction to execute
RegWrite ALUControl2:0
1 010
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
PC' A1 RD1
PC Instr
A RD
ALUResult ReadData
A RD
Instruction
A2 RD2
SrcB
Data
Memory
20:16
A3 Memory
Register
WD3 WD
File
PCPlus4
SignImm
4 15:0
Sign Extend
Result
lw rt, offset(base)
LW
base rt offset
1 0 0 0 1 1
ALU
+
Additional Elements forsw
Read rt from the register file and write it to data
memory
RegWrite ALUControl2:0 MemWrite
0 010 1
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
A1 RD1
PC' PC Instr
A RD
ALUResult ReadData
A RD
20:16
Instruction
A2 RD2
SrcB
Data
Memory
20:16
A3 Memory
WriteData
Register
WD3 WD
File
PCPlus4
SignImm
4 15:0
Sign Extend
Result
sw rt, offset(base)
SW
base rt offset
1 0 1 0 1 1
ALU
+
Additional Elements for R-Type Instructions
Read from rs and rt
Write ALUResult to rd (instead of rt)
RegWrite RegDst ALUSrc ALUControl2:0 MemWrite MemtoReg
1 1 0 varies 0
0
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
A RD 1
Instruction
20:16
SrcB
A2 RD2 0
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
4 15:0
Sign Extend
Result
addu rd, rs, rt
SPECIAL ADDU
rs
rt rd
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
ALU
+
Additional Elements forbeq
Determine whether rs and rt are equal
Calculate branch target address
PCSrc
RegWrite RegDst ALUSrc ALUControl2:0 Branch MemWrite MemtoReg
0 x 0 110 1 x
0
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
PC'
0 A1 RD1
PC Instr
0
A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
beq rs, rt, offset
BEQ
rs
rt offset
0 0 0 1 0 0
ALU
+
+
Add a controller to complete it
MemtoReg
Control
MemWrite
Unit
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
Op rs
Funct
ALU
+
+
R-Type Instruction Encoding
addu rd, rs, rt
SPECIAL ADDU
rs
rt rd
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
subu rd, rs, rt
SPECIAL SUBU
rs
rt rd
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1
and rd, rs, rt
SPECIAL AND
rs
rt rd
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0
or rd, rs, rt
SPECIAL OR
rs
rt rd
0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1
slt rd, rs, rt
SPECIAL SLT
rs
rt rd
0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0
The ALU Decoder
Control Part of the control unit
Unit
MemtoReg
responsible for
MemWrite
implementing the opcode
Branch
Funct field.
Opcode5:0 Main
ALUSrc
Decoder
ALU Funct ALU ALU
RegDst
Op Ctrl. Function
RegWrite
00  010 Add
ALUOp1:0
-1  110 Subtract
1- 100001 010 Add
ALU
1- 100011 110 Subtract
Funct5:0 ALUControl2:0
Decoder
1- 100100 000 AND
1- 100101 001 OR
1- 101010 111 Slt
The Main Decoder
Inst. OP RegWrite RegDst ALUSrc Branch MemWrite MemToReg ALUOp
R-type 000000
lw 100011
sw 101011
beq 000100
MemtoReg
Control
MemWrite
Unit
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
ALU
+
+
The Main Decoder
Inst. OP RegWrite RegDst ALUSrc Branch MemWrite MemToReg ALUOp
R-type 000000 1 1 0 0 0 0 1-
lw 100011
sw 101011
beq 000100
MemtoReg
Control
MemWrite
Unit
0
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
1 0
CLK
0 001
0
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
0 A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
1
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
ALU
+
+
The Main Decoder
Inst. OP RegWrite RegDst ALUSrc Branch MemWrite MemToReg ALUOp
R-type 000000 1 1 0 0 0 0 1-
lw 100011 1 0 1 0 0 1 00
sw 101011
beq 000100
MemtoReg
Control
MemWrite
Unit
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
ALU
+
+
The Main Decoder
Inst. OP RegWrite RegDst ALUSrc Branch MemWrite MemToReg ALUOp
R-type 000000 1 1 0 0 0 0 1-
lw 100011 1 0 1 0 0 1 00
sw 101011 0 - 1 0 1 - 00
beq 000100
MemtoReg
Control
MemWrite
Unit
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
ALU
+
+
The Main Decoder
Inst. OP RegWrite RegDst ALUSrc Branch MemWrite MemToReg ALUOp
R-type 000000 1 1 0 0 0 0 1-
lw 100011 1 0 1 0 0 1 00
sw 101011 0 - 1 0 1 - 00
beq 000100 0 - 0 1 0 - 01
MemtoReg
Control
MemWrite
Unit
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
ALU
+
+
The Main Decoder
Inst. OP RegWrite RegDst ALUSrc Branch MemWrite MemToReg ALUOp
R-type 000000 1 1 0 0 0 0 1-
lw 100011 1 0 1 0 0 1 00
sw 101011 0 - 1 0 1 - 00
beq 000100 0 - 0 1 0 - 01
addiu 001001 Can we do this with our datapath?
MemtoReg
Control
MemWrite
Unit
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
ALU
+
+
The Main Decoder
Inst. OP RegWrite RegDst ALUSrc Branch MemWrite MemToReg ALUOp
R-type 000000 1 1 0 0 0 0 1-
lw 100011 1 0 1 0 0 1 00
sw 101011 0 - 1 0 1 - 00
beq 000100 0 - 0 1 0 - 01
addiu 001001 1 0 1 0 0 0 00
MemtoReg
Control
MemWrite
Unit
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
CLK
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
ALU
+
+
Additional Elements for thejInstruction
Inst. OP RegWrite RegDst ALUSrc Branch MemWrite MemToReg ALUOp Jump
R-type 000000 1 1 0 0 0 0 1- 0
lw 100011 1 0 1 0 0 1 00 0
sw 101011 0 - 1 0 1 - 00 0
beq 000100 0 - 0 1 0 - 01 0
addiu 001001 1 0 1 0 0 0 00 0
j 000010 0 - - - 0 - -- 1
Jump
MemtoReg
Control
MemWrite
Unit
Branch
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
CLK
0 WE3 Zero WE
SrcA
PC' 25:21
0 A1 RD1
PC Instr
0
Result
1 A RD
ALUResult ReadData
1
A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
20:16
0
PCJump
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
27:0 31:28
25:0
<<2
ALU
+
+
Processor Performance
Seconds Instructions Clock Cycles Seconds
= × ×
Program Program Instruction Clock Cycle
Seconds
How long you have to wait
Program
Instructions
Number that must execute to complete the task
Program
Clock Cycles
CPI: Cycles per instruction
Instruction
Seconds
The clock period (1/frequency)
Clock Cycle
The Critical Path Here: Load from Memory
MemtoReg
Control
MemWrite
Unit
0
Branch
0
PCSrc
ALUControl2:0
31:26
Op
ALUSrc
5:0
Funct
RegDst
RegWrite
CLK CLK
1 0
CLK
010
1
WE3 Zero WE
SrcA
25:21
0 A1 RD1
PC' PC Instr
0
A RD
ALUResult ReadData
1
1 A RD 1
Instruction
20:16
A2 RD2 0
SrcB
Data
Memory
A3 1 Memory
WriteData
Register
WD3 WD
File
0
20:16
0
15:11
1
WriteReg4:0
PCPlus4
SignImm
<<2
4 15:0
Sign Extend
PCBranch
Result
Instruction Memory to Register File to ALU to Data
Memory to Register File
ALU
+
+
The Critical Path Dictates the Clock Period
Element Delay
MemtoReg
Control
MemWrite
Unit
Register clk-to-Q tpcq-PC 30 ps Branch 0
0
PCSrc
ALUControl2:0
31:26
Op ALUSrc
5:0
Funct RegDst
Register setup tsetup 20
RegWrite
CLK CLK
CLK 1 0
Multiplexer tmux 25 010
1
WE3
25:21 SrcA Zero WE
0 PC' PC Instr A1 RD1
0
A RD
ALUResult ReadData
1
1 A RD 1
Instruction 20:16
A2 RD2 0
ALU tALU 200 SrcB Data
Memory
A3 1 Memory
Register WriteData
WD3 WD
File
0
Memory Read tmem 250 20:16
0
15:11
1
WriteReg4:0
PCPlus4
Register file read tRFread 150 SignImm
<<2
4 15:0
Sign Extend
PCBranch
Register file setup tRFsetup 20
Result
TC = tpcq-PC + tmem-I + tRFread + tALU + tmem-D + tmux + tRFsetup
= (30 + 250 + 150 + 200 + 250 + 25 + 20) ps
= 925 ps
= 1.08 GHz
ALU
+
+
Execution Time for Our Single-Cycle Processor
For a 100 billion-instruction task on our single-cycle
processor with a 925 ps clock period,
Seconds Instructions Clock Cycles Seconds
= × ×
Program Program Instruction Clock Cycle
= 100 × 109 × 1 × 925 ps
= 92.5 seconds