Transcript CS 230 Chapter 3 Arithmetic for Computers

CS 230: Computer Organization
and Assembly Language
Aviral Shrivastava
Department of Computer Science and Engineering
School of Computing and Informatics
Arizona State University
Slides courtesy: Prof. Yann Hang Lee, ASU, Prof. Mary
Jane Irwin, PSU, Ande Carle, UCB
M
C L
Announcements
• Project 3
– MIPS Assembler
• Midterm
– Thursday, Oct 2009
•
•
•
•
•
MIPS ISA and Programming
Function calls and register conventions
Assembling MIPS Instructions
2’s complement number system
FP number system
• Finals
– Tuesday, Dec 08, 2009
M
C L
Computer Organization
software
Instruction Set Architecture
hardware
• We have leaned the ISA of the processor till now
– Given an algorithm, express it in terms of the processor ISA
M
C L
Below the Program

High-level language program (in C)
swap (int v[], int k)
. . .
Assembly
swap:

language program (for MIPS)
sll
add
lw
lw
sw
sw
jr
C - Compiler
$2, $5, 2
$2, $4, $2
$15, 0($2)
$16, 4($2)
$16, 0($2)
$15, 4($2)
$31
Machine (object) code (for MIPS)
000000
000000
100011
100011
101011
101011
000000
00000
00100
00010
00010
00010
00010
11111
00101
00010
01111
10000
10000
01111
00000
0001000010000000
0001000000100000
0000000000000000
0000000000000100
0000000000000000
0000000000000100
0000000000001000
Assembler
M
C L
Datapath & Control
• We're ready to look at an implementation of the MIPS
• Simplified to contain only:
– memory-reference instructions: lw, sw
– arithmetic-logical instructions: add, sub, and, or,
slt
– control flow instructions: beq, j
• Generic implementation:
– use the program counter (PC) to supply the instruction
address and fetch the instruction from memory (and update
the PC)
– decode the instruction (and read registers)
– execute the instruction
Fetch
PC = PC+4
Exec
Decode
• All instructions (except j) use the ALU after reading the
registers
– Why? memory-reference? arithmetic? control flow?
M
C L
Abstract Implementation View
• Two types of functional units:
– elements that operate on data values (combinational)
– elements that contain state (sequential)
Instruction
Memory
PC
Address
Instruction
Write Data
Register Read
Data
Reg Addr
File
Reg Addr
Read
Data
Reg Addr
Address
ALU
Data
Memory Read Data
Write Data
• Single cycle operation
• Split memory (Harvard) model - one memory for instructions and
one for data
M
C L
32-bit ALU
• Supports all the Arithmetic/Logic operations
operation
a
32
ALU
result
32
b
32
M
C L
op
ALU Design
add/subt
A0
result0
B0
+
less
A1
result1
...
B1
0
+
zero
less
. . .
A31
B31
0
set
+
less
result31
overflow
M
C L
Fetching Instructions
• Fetching instructions involves
– reading the instruction from the Instruction Memory
– updating the PC to hold the address of the next instruction
Add
4
Instruction
Memory
PC
Read
Address
Instruction
– PC is updated every cycle, so it does not need an explicit write control
signal
– Instruction Memory is read every cycle, so it doesn’t need an explicit
read control signal
M
C L
Decoding Instructions
• Decoding instructions involves
– sending the fetched instruction’s opcode and function field bits
to the control unit
Control
Unit
Instruction
Read Addr 1
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
Data 2
− reading two values from the Register File
•Register File addresses are contained in the instruction
M
C L
Executing R Format Operations
• R format operations (add, sub, slt, and, or)
31
R-type: op
25
rs
20
15
10
rt
rd
5
0
shamt funct
– perform the indicated (by op and funct) operation on values in rs and rt
– store the result back into the Register File (into location rd)
RegWrite
Instruction
Read Addr 1
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
ALU control
ALU
overflow
zero
Data 2
– Note that Register File is not written every cycle (e.g. sw), so we need an
explicit write control signal for the Register File
M
C L
Load and Store Operations
• Load and store operations
31
I-Type:
op
25
rs
20
rt
15
0
address offset
– compute a memory address by adding the base register (in rs) to
the 16-bit signed offset field in the instruction
• base register was read from the Register File during decode
• offset value in the low order 16 bits of the instruction must be sign
extended to create a 32-bit signed value
– store value, read from the Register File during decode, must be
written to the Data Memory
– load value, read from the Data Memory, must be stored in the
Register File
M
C L
Load and Store Operations
RegWrite
Instruction
ALU control
overflow
zero
Read Addr 1
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
16
Address
ALU
Data
Memory Read Data
Write Data
Data 2
Sign
Extend
MemWrite
MemRead
32
M
C L
Executing Branch Operations
• Branch operations have to
31
I-Type:
op
25
rs
20
rt
15
0
address offset
– compare the operands read from the Register File during
decode (rs and rt values) for equality (zero ALU output)
– compute the branch target address by adding the updated
PC to the sign extended16-bit signed offset field in the
instruction
• “base register” is the updated PC
• offset value in the low order 16 bits of the instruction must be
sign extended to create a 32-bit signed value and then shifted
left 2 bits to turn it into a word address
M
C L
Executing Branch Operations
Add
4
Add
Shift
left 2
Branch
target
address
ALU control
PC
Read Addr 1
Instruction
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
16
zero (to branch
control logic)
ALU
Data 2
Sign
Extend
32
M
C L
Executing Jump Operations
• Jump operations have to
31
25
0
J-Type: op
jump target address
– replace the lower 28 bits of the PC with the lower 26 bits of
the fetched instruction shifted left by 2 bits
Add
4
4
Instruction
Memory
PC
Read
Address
Shift
left 2
Jump
address
28
Instruction
26
M
C L
Adding the pieces together
Add
RegWrite
ALU control
4
ovf
zero
Instruction
Memory
PC
MemWrite
Read
Address
Instruction
Read Addr 1
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
Address
ALU
Write Data
Data 2
Sign
16 Extend
Data
Memory Read Data
MemRead
32
M
C L
Multiplexor Insertion
Add
RegWrite
ALUSrc ALU control
4
MemtoReg
ovf
zero
Instruction
Memory
PC
MemWrite
Read
Address
Instruction
Read Addr 1
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
Address
ALU
Write Data
Data 2
Sign
16 Extend
Data
Memory Read Data
MemRead
32
M
C L
Clock Distribution
System Clock
clock cycle
RegWrite
Add
MemWrite
ALUSrc ALU control
4
ovf
zero
Instruction
Memory
PC
MemtoReg
Read
Address
Instruction
Read Addr 1
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
Address
ALU
Write Data
Data 2
Sign
16 Extend
Data
Memory Read Data
MemRead
32
M
C L
Adding the Branch Portion
Add
4
Shift
left 2
RegWrite
Instruction
Memory
PC
Read
Address
Instruction
MemWrite
MemtoReg
Address
ALU
Data
Memory Read Data
Write Data
Data 2
Sign
16 Extend
PCSrc
ALUSrc ALU control
ovf
zero
Read Addr 1
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
Add
MemRead
32
M
C L
Adding the Jump Portion
26
Shift
left 2
Jump
32
28
1
PC+4[31-28]
0
Add
4
Shift
left 2
RegWrite
Instruction
Memory
PC
Read
Address
Instruction
MemWrite
MemtoReg
Address
ALU
Data
Memory Read Data
Write Data
Data 2
Sign
16 Extend
PCSrc
ALUSrc ALU control
ovf
zero
Read Addr 1
Register Read
Read Addr 2 Data 1
File
Write Addr
Read
Write Data
Add
MemRead
32
M
C L
MIPS Machine (with Controls)
Instr[25-0]
Shift
left 2
26
1
28
32
0
PC+4[31-28]
0
Add
Jump
ALUOp
Add
Shift
left 2
4
1
PCSrc
Branch
MemRead
MemtoReg
MemWrite
Instr[31-26] Control
Unit
ALUSrc
RegWrite
RegDst
Instruction
Memory
PC
Read
Address
Instr[31-0]
ovf
Instr[25-21] Read Addr 1
Register Read
Instr[20-16] Read Addr 2 Data 1
File
0
Write Addr
Read
1
Instr[15
-11]
Instr[15-0]
Write Data
zero
ALU
Address
Data
Memory Read Data
1
Write Data
0
0
Data 2
1
Sign
16 Extend
32
Instr[5-0]
ALU
control
M
C L
Yoda says…
Use your feelings, Obi-Wan, and find him you will
M
C L