Transcript longOldchapter5

CS/COE0447
Computer Organization &
Assembly Language
LECTURE NOTE
Chapter 5
CS/COE0447 Computer Organization and Assembly Language
A Simple MIPS
• Memory reference instructions
– lw (load word) and sw (store word)
• Arithmetic-logical instructions
– add, sub, and, or, and slt
• Control-transfer instructions
– beq (branch if equal)
– j (unconditional jump)
CS/COE0447 Computer Organization and Assembly Language
Implementation Overview
• Send program counter (PC) to code memory
and fetch an instruction
• Read one or two registers
– Depending on the instruction type, we need to do
different actions with the values read from the register
file
• Instructions of a same type (e.g., memory)
perform similar work
CS/COE0447 Computer Organization and Assembly Language
An Abstract Implementation
•
Combinational logic
–
•
ALU, adder
Sequential logic
–
Register file, instruction memory, data memory
CS/COE0447 Computer Organization and Assembly Language
Instruction Analysis
• lw (load word)
–
–
–
–
–
–
Fetch instruction
Read a base register
Sign-extend the immediate offset
Add two values to get address
Access data memory with the address
Store the memory data to the destination register
CS/COE0447 Computer Organization and Assembly Language
Instruction Analysis, cont’d
• add
–
–
–
–
Fetch instruction
Read two source registers
Add two values
Store the result to the destination register
CS/COE0447 Computer Organization and Assembly Language
Instruction Analysis, cont’d
• j
–
–
–
–
Fetch instruction
Take the 26-bit immediate field
Shift left by 2 (to make 28-bit immediate)
Get 4 bits from the current PC and attach to the left of
the immediate
– Assign the value to PC
• What about other instructions?
CS/COE0447 Computer Organization and Assembly Language
Components
• ALU
– We’ve already built this!
• Memory
– Instruction memory to supply instructions
– Data memory to supply data
– Data memory allows writing to it (store)
• PC
– Essentially a register
– Update logic (increment/jump address)
CS/COE0447 Computer Organization and Assembly Language
Components, cont’d
• Register file
– 32 32-bit registers
– 2 read ports, one write port
• Immediate
– Sometimes instruction contains immediate
– We may sign-extend it
• Support for branch and jump
CS/COE0447 Computer Organization and Assembly Language
Building Blocks
CS/COE0447 Computer Organization and Assembly Language
Instruction Fetch
Instruction width
is 4 bytes!
PC keeps the current
memory address
from which instruction
is fetched
CS/COE0447 Computer Organization and Assembly Language
Instruction memory
here is read-only!
Operand Fetch
For branches!
Two reads
at a time!
CS/COE0447 Computer Organization and Assembly Language
Handling Memory Instructions
Data to store!
Imm. offset
for address
To be in
a register!
CS/COE0447 Computer Organization and Assembly Language
Load data
from memory
Datapath so far
j instruction
not considered
so far!
CS/COE0447 Computer Organization and Assembly Language
Instruction Format
CS/COE0447 Computer Organization and Assembly Language
More Elaborated Design
Write register #
selection
ALU control bits
from I[5:0]
CS/COE0447 Computer Organization and Assembly Language
A First Look at Control
CS/COE0447 Computer Organization and Assembly Language
Control Signals Overview
• RegDst: which instr. field to use for dst. register specifier?
– instruction[20:16] vs. instruction[15:11]
• ALUSrc: which one to use for ALU src 2?
– immediate vs. register read port 2
•
•
•
•
•
•
MemtoReg: is it memory load?
RegWrite: update register?
MemRead: read memory?
MemWrite: write to memory?
Branch: is it a branch?
ALUop: what type of ALU operation?
CS/COE0447 Computer Organization and Assembly Language
Generic Control Sequence
• For each fetched instruction
–
–
–
–
–
–
–
(decoding)
Select two registers to read from register file
Select the 2nd register input
Select ALU operation
Select if data memory is to be accessed
Select if register file is updated
Select what to assign to PC
CS/COE0447 Computer Organization and Assembly Language
Example: lw r8, 32(r18)
I-Format
• Let’s assume r18 has 1,000
• Let’s assume M[1032] has 0x11223344
CS/COE0447 Computer Organization and Assembly Language
Example: lw r8, 32(r18)
(PC+4)
(PC+4)
Branch=0
35
RegWrite
(PC+4)
18
8
RegDest=0
8
0
0x11223344
1000
0x11223344
ALUSrc=1
32
1032
MemtoReg=1
32
32
CS/COE0447 Computer Organization and Assembly Language
MemRead
0x11223344
Control Sequence for lw
• OPcode = 35
–
–
–
–
–
–
–
–
RegDst = 0
ALUSrc = 1
MemtoReg = 1
RegWrite = 1
MemRead = 1
MemWrite = 0
Branch = 0
ALUop = 0
CS/COE0447 Computer Organization and Assembly Language
Control Signal Table
CS/COE0447 Computer Organization and Assembly Language
ALU Control
• Depending on instruction, we perform different ALU
operation
• Example
– lw or sw: ADD
– and: AND
– beq: SUB
• ALU control input (3 bits)
–
–
–
–
–
000: AND
001: OR
010: ADD
110: SUB
111: SET-IF-LESS-THAN (similar to SUB)
CS/COE0447 Computer Organization and Assembly Language
ALU Control, cont’d
• ALUop
– 00: lw/sw, 01: beq, 10: arithmetic, 11: jump
CS/COE0447 Computer Organization and Assembly Language
ALU Control Truth Table
CS/COE0447 Computer Organization and Assembly Language
ALU Control Logic Design
CS/COE0447 Computer Organization and Assembly Language
Datapath w/ Jump
CS/COE0447 Computer Organization and Assembly Language
Functional Unit Used
CS/COE0447 Computer Organization and Assembly Language
Register File Implementation
CS/COE0447 Computer Organization and Assembly Language
Reg. File Impl., cont’d
0
1
1
0x11223344
0
0
0x11223344
CS/COE0447 Computer Organization and Assembly Language
What We Have Now
CS/COE0447 Computer Organization and Assembly Language
Resource Usage
CS/COE0447 Computer Organization and Assembly Language
Single-Cycle Execution Timing
(in pico-seconds)
CS/COE0447 Computer Organization and Assembly Language
Single-Cycle Exe. Problem
• The cycle time depends on the most timeconsuming instruction
– What happens if we implement a more complex
instruction, e.g., a floating-point mult.
– All resources are simultaneously active – there is no
sharing of resources
• We’ll adopt a multi-cycle solution
– Use a faster clock
– Allow different number of clock cycles per instruction
CS/COE0447 Computer Organization and Assembly Language
A Multi-cycle Datapath
• A single memory unit for both instructions and data
• Single ALU rather than ALU & two adders
• Registers added after every major functional unit to hold the output
until it is used in a subsequent clock cycle
CS/COE0447 Computer Organization and Assembly Language
Multi-cycle Approach
• Reusing functional units
–
–
–
–
Break up instruction execution into smaller steps
Each functional unit is used for a specific purpose in any cycle
ALU is used for additional functions: calculation and PC increment
Memory used for instructions and data
• At the end of a cycle, keep results in registers
– Additional registers
• Now, control signals are NOT solely determined by the
instruction bits
• Controls will be generated by a FSM!
CS/COE0447 Computer Organization and Assembly Language
Finite State Machine (FSM)
• FSM
– Memory element to keep current
state
– Next state function
– Output function
CS/COE0447 Computer Organization and Assembly Language
Operations
CS/COE0447 Computer Organization and Assembly Language
Five Execution Steps
• Instruction fetch
• Instruction decode and register read
• Execution, memory address calculation, or
branch completion
• Memory access or R-type instruction completion
• Write-back
• Instruction execution takes 3~5 cycles!
CS/COE0447 Computer Organization and Assembly Language
Step 1: Instruction Fetch
• Access memory w/ PC to fetch instruction and
store it in Instruction Register (IR)
• Increment PC by 4 and put the result back in the
PC
– We can do this because ALU is not busy and we can
use it
– Actual PC Update is done at the next clock rising
edge
CS/COE0447 Computer Organization and Assembly Language
Step 2: Decode and Reg. Read
• Read registers rs and rt
– We read both of them regardless of necessity
• Compute the branch address in case the
instruction is a branch
– We can do this as ALU is not busy
– ALUOut will keep the target address
• We still don’t set any control signals based on
the instruction type
– Instruction is being decoded now in the control logic!
CS/COE0447 Computer Organization and Assembly Language
Step 3: Various Actions
• ALU performs one of three functions based on instruction type
• Memory reference
– ALUOut <= A + sign-extend(IR[15:0]);
• R-type
– ALUOut <= A op B;
• Branch:
– if (A==B) PC <= ALUOut;
• Jump:
– PC <= {PC[31:28],IR[25:0],2’b00};
CS/COE0447 Computer Organization and Assembly Language
// verilog notation
Step 4: Memory Access…
• If the instruction is memory reference
– MDR <= Memory[ALUOut]; // if it is a load
– Memory[ALUOut] <= B;
// if it is a store
– Store is complete!
• If the instruction is R-type
– Reg[IR[15:11]] <= ALUOut;
– Now the instruction is complete!
CS/COE0447 Computer Organization and Assembly Language
Step 5: Register Write Back
• Only memory load instruction reaches this step
– Reg[IR[20:16]] <= MDR;
CS/COE0447 Computer Organization and Assembly Language
A (Refined) Datapath
CS/COE0447 Computer Organization and Assembly Language
Datapath w/ Control Signals
CS/COE0447 Computer Organization and Assembly Language
Final Version w/ Control
CS/COE0447 Computer Organization and Assembly Language
State Diagram, Big Picture
CS/COE0447 Computer Organization and Assembly Language
Handling Memory Instructions
CS/COE0447 Computer Organization and Assembly Language
R-type Instruction
CS/COE0447 Computer Organization and Assembly Language
Branch and Jump
CS/COE0447 Computer Organization and Assembly Language
A FSM State Diagram
CS/COE0447 Computer Organization and Assembly Language
FSM Implementation
CS/COE0447 Computer Organization and Assembly Language
What We Have Now
CS/COE0447 Computer Organization and Assembly Language
Summary: R-type
• Instruction fetch
– IR <= Memory[PC];
– PC <= PC + 4;
• Decode/register read
– A <= Reg[IR[25:21]];
– B <= Reg[IR[20:16]];
– ALUOut <= PC + (sign-extend(IR[15:0])<<2);
• Execution
– ALUOut <= A op B;
• Completion
– Reg[IR[15:11]] <= ALUOut;
CS/COE0447 Computer Organization and Assembly Language
// done
Summary: Memory
• Instruction fetch
– IR <= Memory[PC];
– PC <= PC + 4;
• Decode/register read
– A <= Reg[IR[25:21]];
– B <= Reg[IR[20:16]];
– ALUOut <= PC + (sign-extend(IR[15:0])<<2);
• Execution
– ALUOut <= A + sign-extend(IR[15:0]);
• Memory Access
– Load: MDR <= Memory[ALUOut];
– Store: Memory[ALUOut] <= B;
• Write-back
– Load: Reg[IR[20:16]] <= MDR;
CS/COE0447 Computer Organization and Assembly Language
// done
Summary: Branch
• Instruction fetch
– IR <= Memory[PC];
– PC <= PC + 4;
• Decode/register read
– A <= Reg[IR[25:21]];
– B <= Reg[IR[20:16]];
– ALUOut <= PC + (sign-extend(IR[15:0])<<2);
• Execution
– if (A == B) then PC <= ALUOut;
CS/COE0447 Computer Organization and Assembly Language
// done
Summary: Jump
• Instruction fetch
– IR <= Memory[PC];
– PC <= PC + 4;
• Decode/register read
–
–
–
–
–
A <= Reg[IR[25:21]];
B <= Reg[IR[20:16]];
ALUOut <= PC + (sign-extend(IR[15:0])<<2);
Execution
PC <= {PC[31:28],IR[25:0],”00”}; // concatenation
CS/COE0447 Computer Organization and Assembly Language
Example: Load (1)
00
1
1
0
1 0
0
01
00
CS/COE0447 Computer Organization and Assembly Language
Example: Load (2)
0
11
00
CS/COE0447 Computer Organization and Assembly Language
Example: Load (3)
1
10
00
CS/COE0447 Computer Organization and Assembly Language
Example: Load (4)
1
1 0
CS/COE0447 Computer Organization and Assembly Language
Example: Load (5)
1
0
1
CS/COE0447 Computer Organization and Assembly Language
Example: Jump (1)
00
1
1
0
1 0
0
01
00
CS/COE0447 Computer Organization and Assembly Language
Example: Jump (2)
0
11
00
CS/COE0447 Computer Organization and Assembly Language
Example: Jump (3)
10
1
CS/COE0447 Computer Organization and Assembly Language
To Summarize…
• From several building blocks, we constructed a
datapath for a subset of the MIPS instruction set
• First, we analyzed instructions for functional
requirements
• Second, we connected buildings blocks in a way to
accommodate instructions
• Third, we are refining the datapath and will add
controls
CS/COE0447 Computer Organization and Assembly Language
To Summarize…
• We looked at how an instruction is executed on the
datapath in a pictorial way
• We looked at control signals connected to functional
blocks in our datapath
• We analyzed how execution steps of an instruction
change the control signals
• We looked at register file implementation
CS/COE0447 Computer Organization and Assembly Language
To Summarize…
• We compared a single-cycle implementation and a
multi-cycle implementation of our datapath
• We analyzed multi-cycle execution of instructions
• We refined multi-cycle datapath
• We designed multi-cycle control
CS/COE0447 Computer Organization and Assembly Language
To Summarize…
• We looked at the multi-cycle control scheme in
detail
• Multi-cycle control can be implemented using
FSM
• FSM is composed of some combinational logic
and memory element
CS/COE0447 Computer Organization and Assembly Language