Computer Architecture

(1)

Computer Architecture

Multi-cycle Implementation

(2)

Computer Architecture & Network Lab

2

Outline



Disadvantages of the Single-cycle implementation



Long cycle time, too long for all instructions except for the slowest (lw instruction)



Inefficient hardware utilization with unnecessarily duplicated resources



Multi-cycle implementation



Partition execution into small steps



Process each step in one cycle



Different numbers of cycles for different instructions

−

Example



R-format instruction (4 cycles): (1) Instruction fetch (2) Instruction decode/register fetch (3) ALU operation (4) Register write



Load instruction (5 cycles): (1) Instruction fetch (2) Instruction decode/register fetch

(3) address computation (4) memory read (5) Register write

(3)

3

Multiple-cycle Concept

 Reduce resource requirements by using the same resource for different purposes during different cycles



Single memory unit for instructions and data



Single ALU

 Use temporary registers to store intermediate results during execution



Instruction register (IR), A register, B register, ALUOut register, Memory data register (MDR)

 Partition criteria: at most one of the following operations



Memory access



Register file access



ALU operation

(4)

4

Multiple-cycle Datapath

PC

Address

MemData memory

Read data 1

Read data 2 Registers 0

M U X 1

Write data

ALU Zero ALU result 0

M U X 1

Write data

0 M U X 1

Shift left 2

M U X 0 1 2 3 0 M U X 1

A

B

Memory Data Register

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Instruction register

Sign extend

ALUOut

M U X 0 1 2

Read register1 Read register2 Write register

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(5)

5

Overview of Multi-cycle Execution

Step name

Action for R-type instructions

Action for memory-reference instructions

Action for branches

Action for jumps

Instruction fetch IR = Memory[PC]

PC = PC + 4

Instruction A = Reg [IR[25-21]]

decode/register fetch B = Reg [IR[20-16]]

ALUOut = PC + (sign-extend (IR[15-0]) << 2)

Execution, address ALUOut = A op B ALUOut = A + sign-extend if (A ==B) then PC = PC [31-28] II

computation, branch/ (IR[15-0]) PC = ALUOut (IR[25-0]<<2)

jump completion

Memory access or R-type Reg [IR[15-11]] = Load: MDR = Memory[ALUOut]

completion ALUOut or

Store: Memory [ALUOut] = B

Memory read completion Load: Reg[IR[20-16]] = MDR

(6)

6

Instruction Fetch Step

Step name

PC = PC + 4

jump completion

(7)

7

Instruction Fetch Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(8)

8

Instruction Decode/Register Fetch Step

Step name

PC = PC + 4

jump completion

(9)

9

Instruction Decode/Register Fetch Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(10)

10

R-format Execution Step

Step name

PC = PC + 4

jump completion

(11)

11

R-format Execution Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(12)

12

R-format Completion Step

Step name

PC = PC + 4

jump completion

(13)

13

R-format Completion Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(14)

14

Load/Store Address Computation Step

Step name

PC = PC + 4

jump completion

(15)

15

Load/Store Address Computation Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(16)

16

Load Memory Access Step

Step name

PC = PC + 4

jump completion

(17)

17

Load Memory Access Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(18)

18

Load Completion Step

Step name

PC = PC + 4

jump completion

(19)

19

Load Completion Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(20)

20

Store Memory Access Step

Step name

PC = PC + 4

jump completion

(21)

21

Store Memory Access Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(22)

22

Branch Completion Step

Step name

PC = PC + 4

jump completion

(23)

23

Branch Completion Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(24)

24

Jump Completion Step

Step name

PC = PC + 4

jump completion

(25)

25

Jump Completion Step

PC

Address

MemData memory

Read data 1

M U X 1

Write data

M U X 1

Write data

0 M U X 1

M U X 0 1 2 3 0 M U X 1

A

B

Instruction [31-26]

Instruction [25-21]

Instruction [20-16]

Instruction [15-0]

Sign extend

ALUOut

M U X 0 1 2

4

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(26)

26

Summary of Multi-cycle Steps

Step name

PC = PC + 4

jump completion

(27)

27

CPI of the Multi-cycle Implementation

 Number of clock cycles



Loads : 5



Stores : 4



R-format instructions : 4



Branches : 3



Jumps : 3

 Instruction mix



22% loads, 11% stores, 49% R-format instructions, 16%

branches, and 2% jumps



CPI = 0.22 x 5 + 0.11 x 4 + 0.49 x 4 + 0.16 x 3 + 0.02 x 3 = 4.04

(28)

28

Multiple-cycle Implementation (with control signals added)

(29)

29

Finite State Machine

 Finite state machine



There are a finite set of possible machine states



The machine has two functions

−

next state function dependent on current state and input values

−

output function dependent on current state and input values



Two kinds of state machines

−

Moore machine has output based only on current state

−

Mealy machine has output based on current state and input values

−

We use a Moore machine

Current state Next-state function

Output function

Next state

Inputs

Outputs Clock

(30)

30

High-Level Control Flow



Common 2-clock sequence to fetch/decode any instruction



Separate sequence of 1 to 3 clocks to execute specific types

of instruction

(31)

31

Finite State Machine Diagram

PCWrite PCSource = 10 ALUSrcA = 1

ALUSrcB = 00 ALUOp = 01 PCWriteCond PCSource = 01 ALUSrcA =1

ALUSrcB = 00 ALUOp= 10

RegDst = 1 RegWrite MemtoReg = 0 MemWrite

IorD = 1 MemRead

IorD = 1 ALUSrcA = 1 ALUSrcB = 10 ALUOp = 00

RegDst = 0 RegWrite MemtoReg=1

ALUSrcA = 0 ALUSrcB = 11 ALUOp = 00 MemRead

ALUSrcA = 0 IorD = 0

IRWrite ALUSrcB = 01

ALUOp = 00 PCWrite PCSource = 00

Instruction fetch Instruction decode/

register fetch

Jump completion Branch

completion Execution

Memory address computation

Memory access

Memory

access R-type completion

Write-back step

(Op='J')

(Op='LW')

4

0 1

9 8

6 2

7 5

3

Start

(32)

32

Finite State Machine Controller

(33)

33

PLA Implementation



Outputs and next state are

calculated by sum of products of inputs and current state



Columns in AND plane form products



one column per unique product term



Rows in OR plane form sum



Programmed by placing transistors at intersection of row and column according to logic function



When the inputs are fully decoded (2

^N

columns), a PLA is logically equivalent to a ROM



Optimization can be automated

Op5 Op4 Op3 Op2 Op1 Op0 S3 S2 S1 S0

IorD

IRWrite MemRead MemWrite PCWrite PCWriteCond

MemtoReg PCSource1 ALUOp1

ALUSrcB0 ALUSrcA RegWrite RegDst NS3 NS2 NS1 NS0 ALUSrcB1 ALUOp0 PCSource0

AND Plane

OR

Plane

(34)

34

Exceptions and Interrupts



Exception: an unexpected event from within the processor that traps into an operating system service routine



Arithmetic overflow



Undefined instruction



System call



Interrupt: an event that comes from outside of the processor that also traps into an operating system service routine



I/O device request (I/O completion)



Handling of exceptions and interrupts in MIPS



Saves PC (the address of the offending instruction) in EPC (exception program counter)



Records the reason for the exception or interrupt in the CAUSE register



Jumps to the operating system service routine



rfe (return from exception) instruction restores the PC from EPC

(35)

35

Summary



Disadvantages of the Single-cycle implementation



Long cycle time, too long for all instructions except for the slowest



Inefficient hardware utilization with unnecessarily duplicated resources



Multiple-cycle implementation



Partition execution into small steps of comparable duration



Process each step in one cycle



Three general forms of control implementation



Random logic



PLA



Microcode Clock

cycle time

CPI

Single-cycle implementation

Multi-cycle implementation Pipelined implementation

(next class)