CSE141-s121-L3
Week 1 — Thursday July 1
MIPS ISA
CSE-141 Summer Session I 2021
Many slides adapted from Dean Tullsen
Administrative
• Weekly Check-In is due midnight
• Do not forget
• Homework 1 Will be posted tonight
• Due next Thursday 11:59 pm
Be a human …
• 2 min breakout rooms
• Talk about your long weekend plans
• Feel free to not join and hang out in the
main room…
Previously on CSE-141…
The Instruction Set Architecture
I/O systemInstr. Set Proc.
Compiler
Operating
System
Application
Digital Design
Circuit Design
Instruction Set
Architecture
• An ISA is “the agreed-upon interface between all the software that runs on the
machine and the hardware that executes it.”
Hardware
Software
The Instruction Set Architecture
I/O systemInstr. Set Proc.
Compiler
Operating
System
Application
Digital Design
Circuit Design
Instruction Set
Architecture
• An ISA is “the agreed-upon interface between all the software that runs on the
machine and the hardware that executes it.”
Hardware
Software
Key ISA decisions
y = x + b
how does the computer know what
0001 0101 0001 0010 means?
Key ISA decisions
y = x + b
operation
how does the computer know what
0001 0101 0001 0010 means?
Key ISA decisions
y = x + b
operation
source operands
how does the computer know what
0001 0101 0001 0010 means?
Key ISA decisions
y = x + b
operation
source operands
Destination operand
how does the computer know what
0001 0101 0001 0010 means?
Key ISA decisions
y = x + b
operation
source operands
Destination operand
how does the computer know what
0001 0101 0001 0010 means?
add r5, r1, r2
Key ISA decisions
• operations
– how many?
– which ones?
y = x + b
operation
source operands
Destination operand
how does the computer know what
0001 0101 0001 0010 means?
add r5, r1, r2
Key ISA decisions
• operations
– how many?
– which ones?
• operands
– how many?
– location
– types
– how to specify?
y = x + b
operation
source operands
Destination operand
how does the computer know what
0001 0101 0001 0010 means?
add r5, r1, r2
Key ISA decisions
• operations
– how many?
– which ones?
• operands
– how many?
– location
– types
– how to specify?
• instruction format
– size
– how many formats?
y = x + b
operation
source operands
Destination operand
how does the computer know what
0001 0101 0001 0010 means?
add r5, r1, r2
Key ISA decisions
• operations
– how many?
– which ones?
• operands
– how many?
– location
– types
– how to specify?
• instruction format
– size
– how many formats?
y = x + b
operation
source operands
Destination operand
how does the computer know what
0001 0101 0001 0010 means?
add r5, r1, r2
Key ISA decisions
• operations
– how many?
– which ones?
• operands
– how many?
– location
– types
– how to specify?
• instruction format
– size
– how many formats?
y = x + b
operation
source operands
Destination operand
how does the computer know what
0001 0101 0001 0010 means?
Syntax choice Design choice
add r5, r1, r2 add r5, r1– r4
add [r1, r2], r5
add r5, r1, r2
Instruction Length
Variable: …
Fixed:
Hybrid:
Load-store architectures
– more instructions
Why else? (hint – fixed instruction length)
Load-store architectures
can do:
add r1=r2+r3
and
load r3, M(address)
⇒ forces heavy dependence on registers, which is exactly what you want in today’s CPUs
– more instructions
+ fast implementation (e.g., easy pipelining)
Why else? (hint – fixed instruction length)
Load-store architectures
can do:
add r1=r2+r3
and
load r3, M(address)
⇒ forces heavy dependence on registers, which is exactly what you want in today’s CPUs
– more instructions
+ fast implementation (e.g., easy pipelining)
can’t do
add r1 = r2 + M(address)
Why else? (hint – fixed instruction length)
Addressing Modes
how do we specify the operand we want?
Addressing Modes
how do we specify the operand we want?
• Register direct R3
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
• Register indirect M[R3]
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
• Register indirect M[R3]
• Base+Displacement M[R3 + 10000]
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
• Register indirect M[R3]
• Base+Displacement M[R3 + 10000]
• Base+Index M[R3 + R4]
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
• Register indirect M[R3]
• Base+Displacement M[R3 + 10000]
• Base+Index M[R3 + R4]
• Scaled Index M[R3 + R4*d + 10000]
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
• Register indirect M[R3]
• Base+Displacement M[R3 + 10000]
• Base+Index M[R3 + R4]
• Scaled Index M[R3 + R4*d + 10000]
• Autoincrement M[R3++]
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
• Register indirect M[R3]
• Base+Displacement M[R3 + 10000]
• Base+Index M[R3 + R4]
• Scaled Index M[R3 + R4*d + 10000]
• Autoincrement M[R3++]
• Autodecrement M[R3 – -]
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
• Register indirect M[R3]
• Base+Displacement M[R3 + 10000]
• Base+Index M[R3 + R4]
• Scaled Index M[R3 + R4*d + 10000]
• Autoincrement M[R3++]
• Autodecrement M[R3 – -]
Addressing Modes
how do we specify the operand we want?
• Register direct R3
• Immediate (literal) #25
• Direct (absolute) M[10000]
• Register indirect M[R3]
• Base+Displacement M[R3 + 10000]
• Base+Index M[R3 + R4]
• Scaled Index M[R3 + R4*d + 10000]
• Autoincrement M[R3++]
• Autodecrement M[R3 – -]
• Memory Indirect M[ M[R3] ]
ISA Design
Case Study: MIPS ISA
MIPS Instruction Formats
opcode
opcode
opcode
rs rt rd sa funct
rs rt immediate
target
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
R-type
I-type
J-type
MIPS Instruction Formats
• the opcode tells the machine which format
opcode
opcode
opcode
rs rt rd sa funct
rs rt immediate
target
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
R-type
I-type
J-type
MIPS Instruction Formats
• the opcode tells the machine which format
opcode
opcode
opcode
rs rt rd sa funct
rs rt immediate
target
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
R-type
I-type
J-type
MIPS Instruction Formats
• the opcode tells the machine which format
• so add r1, r2, r3 has
• opcode=0, funct=32, rs=2, rt=3, rd=1, sa=0
• 000000 00010 00011 00001 00000 100000
opcode
opcode
opcode
rs rt rd sa funct
rs rt immediate
target
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits
R-type
I-type
J-type
MIPS addressing modes
register direct
add $1, $2, $3
immediate
add $1, $2, #35
base + displacement
lw $1, disp($2)
OP rs rt rd sa funct
OP rs rt immediate
rt
rs
immediate
(R1 = M[R2 + disp])
MIPS addressing modes
register direct
add $1, $2, $3
immediate
add $1, $2, #35
base + displacement
lw $1, disp($2)
OP rs rt rd sa funct
OP rs rt immediate
rt
rs
immediate register indirect ! disp = 0
absolute ! (rs) = 0
(R1 = M[R2 + disp])
Is this sufficient?
Is this sufficient?
• measurements on the VAX (super complex ISA) show that these addressing
modes (immediate, direct, register indirect, and base+displacement) represent
88% of all addressing mode usage.
• similar measurements show that 16 bits is enough for the immediate 75 to
80% of the time
• and that 16 bits is enough of a displacement 99% of the time.
• (and when these are not sufficient, it typically means we need one more instruction)
Memory Organization (digression)
• Viewed as a large, single-dimension array,
with an address.
• A memory address is an index into the array
• “Byte addressing” means that the index
(address) points to a byte of memory.
0
1
2
3
4
5
6
…
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
8 bits of data
Memory Organization
• Bytes are nice, but most data items use larger “words”
• For MIPS32, a word is 32 bits or 4 bytes.
• If addresses are 32 bits, then we can think of memory as
• 232 bytes with byte addresses from 0, 1, to 232-1
• 230 words with byte addresses 0, 4, 8, … 232-4
• Words are aligned i.e., what are the least 2 significant bits of a word address?
0
4
8
12
32 bits of data
32 bits of data
32 bits of data
32 bits of data
The MIPS ISA, so far
• fixed 32-bit instructions
• 3 instruction formats
• 3-operand, load-store architecture
• 32 general-purpose registers (integer, floating point)
• R0 always equals 0.
• 2 special-purpose integer registers, HI and LO, because multiply and divide produce more
than 32 bits.
• registers are 32-bits wide (word)
• register, immediate, and base+displacement addressing modes
What’s left
• which instructions?
• how to handle control flow
• odds and ends
Which instructions?
• arithmetic
• logical
• data transfer
• conditional branch
• unconditional jump
Which instructions (integer)
• arithmetic
• add, subtract, multiply, divide
• logical
• and, or, shift left, shift right
• data transfer
• load word, store word
Control Flow
• Jumps
• Procedure call (jump subroutine)
• Conditional Branch
• Used to implement, for example, if-then-else logic, loops, etc.
Control Flow
• Jumps
• Procedure call (jump subroutine)
• Conditional Branch
• Used to implement, for example, if-then-else logic, loops, etc.
• A conditional branch must specify two things
• Condition under which the branch is taken
• Location that the branch jumps to if taken (target)
Conditional branch
• How do you specify the destination (target) of a branch/jump?
Conditional branch
• How do you specify the destination (target) of a branch/jump?
• studies show that almost all conditional branches go short distances from the
current program counter (loops, if-then-else).
Conditional branch
• How do you specify the destination (target) of a branch/jump?
• studies show that almost all conditional branches go short distances from the
current program counter (loops, if-then-else).
• we can specify a relative address in much fewer bits than an absolute address
• e.g., beq $1, $2, 100 => if ($1 == $2) PC = (PC+4) + 100 * 4
Conditional branch
• How do you specify the destination (target) of a branch/jump?
• studies show that almost all conditional branches go short distances from the
current program counter (loops, if-then-else).
• we can specify a relative address in much fewer bits than an absolute address
• e.g., beq $1, $2, 100 => if ($1 == $2) PC = (PC+4) + 100 * 4
• How do we specify the condition of the branch?
MIPS conditional branches
MIPS conditional branches
• beq, bne beq r1, r2, addr => if (r1 == r2) goto addr
MIPS conditional branches
• beq, bne beq r1, r2, addr => if (r1 == r2) goto addr
• slt $1, $2, $3 => if ($2 < $3) $1 = 1; else $1 = 0 MIPS conditional branches • beq, bne beq r1, r2, addr => if (r1 == r2) goto addr
• slt $1, $2, $3 => if ($2 < $3) $1 = 1; else $1 = 0 • these, combined with $0, can implement all fundamental branch conditions Always, never, !=, = =, >, <=, >=, <, >(unsigned), <= (unsigned), ... MIPS conditional branches • beq, bne beq r1, r2, addr => if (r1 == r2) goto addr
• slt $1, $2, $3 => if ($2 < $3) $1 = 1; else $1 = 0
• these, combined with $0, can implement all fundamental branch conditions
Always, never, !=, = =, >, <=, >=, <, >(unsigned), <= (unsigned), ...
if (i
Jumps
• need to be able to jump to an absolute address sometimes
• need to be able to do procedure calls and returns
• jump — j 10000 => PC = 10000
• jump and link — jal 100000 => $31 = PC + 4; PC = 10000
Jumps
• need to be able to jump to an absolute address sometimes
• need to be able to do procedure calls and returns
• jump — j 10000 => PC = 10000
• jump and link — jal 100000 => $31 = PC + 4; PC = 10000
• used for procedure calls
OP target
Jumps
• need to be able to jump to an absolute address sometimes
• need to be able to do procedure calls and returns
• jump — j 10000 => PC = 10000
• jump and link — jal 100000 => $31 = PC + 4; PC = 10000
• used for procedure calls
• jump register — jr $31 => PC = $31
• used for returns, but can be useful for lots of other things.
OP target
Branch and Jump Addressing Modes
• Branch (e.g., beq) uses PC-relative addressing mode (uses few bits if address
typically close). That is, it uses base+displacement mode, with the PC being
the base. If opcode is 6 bits, how many bits are available for displacement?
How far can you jump?
Branch and Jump Addressing Modes
• Branch (e.g., beq) uses PC-relative addressing mode (uses few bits if address
typically close). That is, it uses base+displacement mode, with the PC being
the base. If opcode is 6 bits, how many bits are available for displacement?
How far can you jump?
• Jump uses pseudo-direct addressing mode. 26 bits of the address is in the
instruction, the rest is taken from the PC.
Branch and Jump Addressing Modes
• Branch (e.g., beq) uses PC-relative addressing mode (uses few bits if address typically
close). That is, it uses base+displacement mode, with the PC being the base. If opcode
is 6 bits, how many bits are available for displacement? How far can you jump?
• Jump uses pseudo-direct addressing mode. 26 bits of the address is in the instruction,
the rest is taken from the PC.
instruction program counter
jump destination address
| |00
6 | 26 4 | 28
To summarize:
MIPS operands
Name Example Comments
$s0-$s7, $t0-$t9, $zero, Fast locations for data. In MIPS, data must be in registers to perform
32 registers $a0-$a3, $v0-$v1, $gp, arithmetic. MIPS register $zero always equals 0. Register $at is
$fp, $sp, $ra, $at reserved for the assembler to handle large constants.
Memory[0], Accessed only by data transfer instructions. MIPS uses byte addresses, so
230 memory Memory[4], …, sequential words differ by 4. Memory holds data structures, such as arrays,
words Memory[4294967292] and spilled registers, such as those saved on procedure calls.
MIPS assembly language
Category Instruction Example Meaning Comments
add add $s1, $s2, $s3 $s1 = $s2 + $s3 Three operands; data in registers
Arithmetic subtract sub $s1, $s2, $s3 $s1 = $s2 – $s3 Three operands; data in registers
add immediate addi $s1, $s2, 100 $s1 = $s2 + 100 Used to add constants
load word lw $s1, 100($s2) $s1 = Memory[$s2 + 100] Word from memory to register
store word sw $s1, 100($s2) Memory[$s2 + 100] = $s1 Word from register to memory
Data transfer load byte lb $s1, 100($s2) $s1 = Memory[$s2 + 100] Byte from memory to register
store byte sb $s1, 100($s2) Memory[$s2 + 100] = $s1 Byte from register to memory
load upper
immediate
lui $s1, 100 $s1 = 100 * 2 16 Loads constant in upper 16 bits
branch on equal beq $s1, $s2, 25 if ($s1 == $s2 ) go to
PC + 4 + 100
Equal test; PC-relative branch
Conditional
branch on not equal bne $s1, $s2, 25 if ($s1 != $s2 ) go to
PC + 4 + 100
Not equal test; PC-relative
branch set on less than slt $s1, $s2, $s3 if ($s2 < $s3 ) $s1 = 1; else $s1 = 0 Compare less than; for beq, bne set less than immediate slti $s1, $s2, 100 if ($s2 < 100 ) $s1 = 1; else $s1 = 0 Compare less than constant jump j 2500 go to 10000 Jump to target address Uncondi- jump register jr $ra go to $ra For switch, procedure return tional jump jump and link jal 2500 $ra = PC + 4; go to 10000 For procedure call Review -- Instruction Execution in a CPU Memory2 20000 20004 80000 Address10 10001100010000110100111000100000 00000000011000010010100000100000 00000000000000000000000000111001 Registers10 R0 R1 R2 R3 R4 R5 ... 0 36 60000 45 198 12 ... Program Counter10 20000 Instruction Buffer op rtrs rd shamt immediate/disp in1 in2 out ALUoperation Load/Store Unit addr data C P U M e m o r y MIPS ISA Tradeoffs What if? • 64 registers • 20-bit immediates • 4 operand instruction (e.g. Y = AX + B) opcode opcode opcode rs rt rd sa funct rs rt immediate target 6 bits 5 bits 5 bits 5 bits 5 bits 6 bits R-type I-type J-type RISC Architectures • MIPS, like SPARC, PowerPC, and Alpha AXP, is a RISC (Reduced Instruction Set Computer) ISA. • fixed instruction length • few instruction formats • load/store architecture • RISC architectures worked because they enabled pipelining. They continue to thrive because they enable parallelism. Alternative Architectures Alternative Architectures • Design alternative: • provide more powerful operations • goal is to reduce number of instructions executed • danger is a slower cycle time and/or a higher CPI (cycles per instruction) Alternative Architectures • Design alternative: • provide more powerful operations • goal is to reduce number of instructions executed • danger is a slower cycle time and/or a higher CPI (cycles per instruction) • Sometimes referred to as “RISC vs. CISC” • CISC = Complex Instruction Set Computer (as alt to RISC) • virtually all new instruction sets since 1982 have been RISC • VAX: minimize code size, make assembly language easy instructions from 1 to 54 bytes long! Alternative Architectures • Design alternative: • provide more powerful operations • goal is to reduce number of instructions executed • danger is a slower cycle time and/or a higher CPI (cycles per instruction) • Sometimes referred to as “RISC vs. CISC” • CISC = Complex Instruction Set Computer (as alt to RISC) • virtually all new instruction sets since 1982 have been RISC • VAX: minimize code size, make assembly language easy instructions from 1 to 54 bytes long! • We’ll look (briefly!) at 80x86 Alternative Architectures • Design alternative: • provide more powerful operations • goal is to reduce number of instructions executed • danger is a slower cycle time and/or a higher CPI (cycles per instruction) • Sometimes referred to as “RISC vs. CISC” • CISC = Complex Instruction Set Computer (as alt to RISC) • virtually all new instruction sets since 1982 have been RISC • VAX: minimize code size, make assembly language easy instructions from 1 to 54 bytes long! • We’ll look (briefly!) at 80x86 • What is ARM? 80x86 • 1978: The Intel 8086 is announced (16 bit architecture) • 1980: The 8087 floating point coprocessor is added • 1982: The 80286 increases address space to 24 bits, +instructions • 1985: The 80386 extends to 32 bits, new addressing modes • 1989-1995: The 80486, Pentium, Pentium Pro add a few instructions (mostly designed for higher performance) • 1997: MMX is added • 1999: Pentium III (same architecture) • 2001: Pentium 4 (144 new multimedia instructions), simultaneous multithreading (hyperthreading) • 2005: dual core Pentium processors • 2006: quad core (sort of) Pentium processors • 2009: Nehalem – eight-core multithreaded processors • 2015: Skylake – 4-core, multithreaded, added hw security features, transactional memory, … 80x86 • Complexity: • Instructions from 1 to 17 bytes long • one operand must act as both a source and destination • one operand can come from memory • complex addressing modes e.g., “base or scaled index with 8 or 32 bit displacement” • Saving grace: • the most frequently used instructions are not too difficult to build • compilers avoid the portions of the architecture that are slow • Some other tricks we’ll talk about later. Key Points Key Points • MIPS is a general-purpose register, load-store, fixed-instruction-length architecture. Key Points • MIPS is a general-purpose register, load-store, fixed-instruction-length architecture. • MIPS is optimized for fast pipelined performance, not for low instruction count Key Points • MIPS is a general-purpose register, load-store, fixed-instruction-length architecture. • MIPS is optimized for fast pipelined performance, not for low instruction count • Historic architectures favored code size over parallelism. Key Points • MIPS is a general-purpose register, load-store, fixed-instruction-length architecture. • MIPS is optimized for fast pipelined performance, not for low instruction count • Historic architectures favored code size over parallelism. • MIPS most complex addressing mode, for both branches and loads/stores is base + displacement.