A single-cycle MIPS processor

 An instruction set architecture is an interface that defines the hardware

operations which are available to software

 Any ISA can be implemented in many different ways

 We will compare two important implementations:

— A basic single-cycle implementation: all operations take the same
amount of time — a single cycle (CPI = 1 in performance equation)

— A pipelined implementation: the processor overlaps the execution of

several instructions, potentially leading to big performance gains
• Slightly different formula for performance: N  CPI = total cycles

 A datapath contains all the functional units and connections necessary to

implement an instruction set architecture

1
 Single-cycle implementation

 We will implement a subset of MIPS supporting just these operations:

Arithmetic: add sub and or slt

Data Transfer: lw sw
Control: beq

 A computer is just a big fancy state machine

CPU
— registers, memory, hard disks and
other storage form the state
— processor keeps reading and updating
the state, according to the instructions State
in some program

 We will use a Harvard architecture: instructions stored in a separate

(read-only) memory, data stored in a read/write memory
2
 Instruction fetching

 The CPU is always in an infinite loop, fetching

instructions from memory and executing them
Add
 The program counter or PC register holds the 4

address of the current instruction PC

 MIPS instructions are each four bytes long, so

the PC should be incremented by four to read Read Instruction
address [31-0]
the next instruction in sequence
Instruction
memory

3
 Decoding instructions (R-type)

 A few weeks ago, we saw encodings of MIPS instructions as 32-bit values

 Example: R-type instructions

op rs rt rd shamt func
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

 Our register file stores thirty-two 32-bit values

— Each register specifier is 5 bits long ALU

— You can read from two registers at a time

— RegWrite is 1 if a register should be written RegWrite
ALUOp
— Opcode determines ALUOp Read Read
register 1 data 1
Read
register 2 Read
data 2
Write
register
Registers
Write
data

4
 Executing instructions (R-type)
1. Read an instruction from the instruction memory
2. The source registers, specified by instruction fields rs and rt, should be
read from the register file
3. The ALU performs the desired operation
4. Its result is stored in the destination register, which is specified by field
rd of the instruction word
RegWrite

Read Instruction I [25 - 21] Read Read ALU

address [31-0] register 1 data 1
Zero
I [20 - 16] Read Result
Instruction register 2 Read
memory data 2
I [15 - 11] Write
register
ALUOp
Registers
Write
data

op rs rt rd shamt func
31 26 25 21 20 16 15 11 10 6 5 0
5
 Decoding I-type instructions
 The lw, sw and beq instructions all use the I-type encoding
— rt is the destination for lw, but a source for beq and sw
— address is a 16-bit signed constant (can be ALU source, sign-extended)

op rs rt address
6 bits 5 bits 5 bits 16 bits

RegWrite
MemWrite MemToReg
Read Instruction I [25 - 21]
Read Read
address [31-0]
register 1 data 1
ALU Read Read 1
I [20 - 16]
Read Zero address data M
Instruction
register 2 Read 0 u
memory 0 Result Write
data 2 M x
M Write address
register u Data 0
u x Write
x Registers memory
I [15 - 11] Write 1 ALUOp data
1 data
MemRead
ALUSrc
RegDst
I [15 - 0] Sign
extend

6
 MemToReg

 Another mux needed for the register file’s “write data”: it must be able
to store either the ALU output of R-type instructions, or the data
memory output for lw

RegWrite
MemWrite MemToReg
Read Instruction I [25 - 21]
Read Read
address [31-0]
register 1 data 1
ALU Read Read 1
I [20 - 16]
Read Zero address data M
Instruction
register 2 Read 0 u
memory 0 Result Write
data 2 M x
M Write address
register u Data 0
u x Write
x Registers memory
I [15 - 11] Write 1 ALUOp data
1 data
MemRead
ALUSrc
RegDst
I [15 - 0] Sign
extend

7
 RegDst
 A final annoyance is the destination register of lw is in rt instead of rd

op rs rt address
lw $rt, address($rs)
 We’ll add one more mux, controlled by RegDst, to select the destination
register from either instruction field rt (0) or field rd (1)
RegWrite
MemWrite MemToReg
Read Instruction I [25 - 21]
Read Read
address [31-0]
register 1 data 1
ALU Read Read 1
I [20 - 16]
Read Zero address data M
Instruction
register 2 Read 0 u
memory 0 Result Write
data 2 M x
M Write address
register u Data 0
u x Write
x Registers memory
I [15 - 11] Write 1 ALUOp data
1 data
MemRead
ALUSrc
RegDst
I [15 - 0] Sign
extend

8
 Branches
 For branch instructions, the constant is not an address but an instruction
offset from the next program counter to the desired address

beq $at, $0, L

or $v1, $v0, $0
add $v1, $v1, $v1
j Somewhere
L: add $v1, $v0, $v0

 The target address L is three instructions past the or, so the encoding of
the branch instruction has 0000 0000 0000 0011 for the address field

000100 00001 00000 0000 0000 0000 0011

op rs rt address

 Instructions are four bytes long, so the actual memory offset is 12 bytes

9
 The steps in executing a beq

1. Fetch the instruction, like beq $at, $0, offset, from memory

2. Read the source registers, $at and $0, from the register file

3. Compare the values (e.g., by XORing them in the ALU)

4. If the XOR result is 0, the source operands were equal and the PC should
be loaded with the target address, PC + 4 + (offset x 4)

5. Otherwise the branch should not be taken, and the PC should just be
incremented to PC + 4 to fetch the next instruction sequentially

10
 Branching hardware

0
M
Add u
x
PC 4
Add 1
Shift
left 2
PCSrc
RegWrite
MemWrite MemToReg
Read Instruction I [25 - 21]
Read Read
address [31-0]
register 1 data 1
ALU Read Read 1
I [20 - 16]
Read Zero address data M
Instruction
register 2 Read 0 u
memory 0 Result Write
data 2 M x
M Write address
register u Data 0
u x Write
x Registers memory
I [15 - 11] Write 1 ALUOp data
1 data
MemRead
ALUSrc
RegDst
I [15 - 0] Sign
extend

11
 Datapath for a single-cycle MIPS implementation

0
M
Add u
x
PC 4
Add 1
Shift
left 2
PCSrc
RegWrite
MemWrite MemToReg
Read Instruction I [25 - 21]
Read Read
address [31-0]
register 1 data 1
ALU Read Read 1
I [20 - 16]
Read Zero address data M
Instruction
register 2 Read 0 u
memory 0 Result Write
data 2 M x
M Write address
register u Data 0
u x Write
x Registers memory
I [15 - 11] Write 1 ALUOp data
1 data
MemRead
ALUSrc
RegDst
I [15 - 0] Sign
extend

12
 Control

 The control unit is responsible for setting all the control signals so that
each instruction is executed properly
— control unit’s input is the 32-bit instruction word
— outputs are values for the blue control signals in the datapath
— most signals can be generated from the instruction opcode alone

 Our single-cycle implementation uses two separate memories, an ALU,

some extra adders, and lots of multiplexers

 Next week, we’ll see the performance limitations of this single-cycle

machine and discuss how to improve upon it

13