• 검색 결과가 없습니다.

Computer Architecture

N/A
N/A
Protected

Academic year: 2024

Share "Computer Architecture"

Copied!
35
0
0

로드 중.... (전체 텍스트 보기)

전체 글

(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)

Computer Architecture & Network Lab

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)

Computer Architecture & Network Lab

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(5)

Computer Architecture & Network Lab

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)

Computer Architecture & Network Lab

6

Instruction Fetch Step

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

(7)

Computer Architecture & Network Lab

7

Instruction Fetch Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(8)

Computer Architecture & Network Lab

8

Instruction Decode/Register Fetch Step

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

(9)

Computer Architecture & Network Lab

9

Instruction Decode/Register Fetch Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(10)

Computer Architecture & Network Lab

10

R-format Execution Step

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

(11)

Computer Architecture & Network Lab

11

R-format Execution Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(12)

Computer Architecture & Network Lab

12

R-format Completion Step

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

(13)

Computer Architecture & Network Lab

13

R-format Completion Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(14)

Computer Architecture & Network Lab

14

Load/Store Address Computation Step

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

(15)

Computer Architecture & Network Lab

15

Load/Store Address Computation Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(16)

Computer Architecture & Network Lab

16

Load Memory Access Step

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

(17)

Computer Architecture & Network Lab

17

Load Memory Access Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(18)

Computer Architecture & Network Lab

18

Load Completion Step

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

(19)

Computer Architecture & Network Lab

19

Load Completion Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(20)

Computer Architecture & Network Lab

20

Store Memory Access Step

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

(21)

Computer Architecture & Network Lab

21

Store Memory Access Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(22)

Computer Architecture & Network Lab

22

Branch Completion Step

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

(23)

Computer Architecture & Network Lab

23

Branch Completion Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(24)

Computer Architecture & Network Lab

24

Jump Completion Step

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

(25)

Computer Architecture & Network Lab

25

Jump Completion Step

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

Shift left 2

Instruction [15-0]

Instruction [15-11]

16 32

26 28

PC[31-28]

Jump

address[31-0]

Instruction[25-0]

(26)

Computer Architecture & Network Lab

26

Summary of Multi-cycle Steps

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

(27)

Computer Architecture & Network Lab

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)

Computer Architecture & Network Lab

28

Multiple-cycle Implementation (with control signals added)

(29)

Computer Architecture & Network Lab

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)

Computer Architecture & Network Lab

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)

Computer Architecture & Network Lab

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)

Computer Architecture & Network Lab

32

Finite State Machine Controller

(33)

Computer Architecture & Network Lab

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)

Computer Architecture & Network Lab

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)

Computer Architecture & Network Lab

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)

참조

관련 문서