Digital System Design 4
Digital System Design 4
Lecture 7 – Instruction Sets 2
Computer Architecture
Chang Liu
Course Outline
Week Lecture Topic Chapter Tutorial
1 1 Introduction
1 2 A Historical Perspective
2 3 Modern Technology and Types of Computer
2 4 Computer Perfomance 1
3 5 Digital Logic Review C
3 6 Instruction Set Architecture 1 2
4 7 Instruction Set Architecture 2 2
4 8 Processor Architecture 1 4
5 9 Instruction Set Architecture 3 2
5 10 Processor Architecture 2 4
Festival of Creative Learning
6 11 Processor Architecture 3 4
6 12 Processor Architecture 4 4Instruction Sets 2 – Chang Liu 2
This Lecture
•Representing Instructions in the Computer
–R Format & I Format
•Logical Operations
•Instructions for making decisions
Instruction Sets 2 – Chang Liu 3
Representing Instructions
• Instructions are encoded in binary
– Called machine code
• MIPS instructions
– Encoded as 32-bit instruction words
– Small number of formats encoding operation code
(opcode), register numbers, …
– Regularity!
• Register numbers
– $t0 – $t7 are reg’s 8 – 15
– $t8 – $t9 are reg’s 24 – 25
– $s0 – $s7 are reg’s 16 – 23
Instruction Sets 2 – Chang Liu 4
MIPS R-format Instructions
• Instruction fields
– op: operation code (opcode)
– rs: first source register number
– rt: second source register number
– rd: destination register number
– shamt: shift amount (00000 for now)
– funct: function code (extends opcode)
op rs rt rd shamt funct
6 bits 6 bits5 bits 5 bits 5 bits 5 bits
Instruction Sets 2 – Chang Liu 5
R-format Example
add $t0, $s1, $s2
special $s1 $s2 $t0 0 add
0 17 18 8 0 32
000000 10001 10010 01000 00000 100000
000000100011001001000000001000002 = 0232402016
op rs rt rd shamt funct
6 bits 6 bits5 bits 5 bits 5 bits 5 bits
Instruction Sets 2 – Chang Liu 6
Hexadecimal
• Base 16
– Compact representation of bit strings
– 4 bits per hex digit
0 0000 4 0100 8 1000 c 1100
1 0001 5 0101 9 1001 d 1101
2 0010 6 0110 a 1010 e 1110
3 0011 7 0111 b 1011 f 1111
• Example: eca8 6420
– 1110 1100 1010 1000 0110 0100 0010 0000
Instruction Sets 2 – Chang Liu 7
MIPS I-format Instructions
• Immediate arithmetic and load/store instructions
– rt: destination or source register number
– Constant: –215 to +215 – 1
– Address: offset added to base address in rs
op rs rt constant or address
6 bits 5 bits 5 bits 16 bits
lw $t0, 32($s3)
35 19 8 32
Instruction Sets 2 – Chang Liu 8
Translation
Assembly Language Machine Language
A[300]=h+A[300];
C++
Instruction Sets 2 – Chang Liu 9
Logical Operations
• Instructions for bitwise manipulation
Operation C Java MIPS
Shift left << << sll Shift right >> >>> srl
Bitwise AND & & and, andi
Bitwise OR | | or, ori
Bitwise NOT ~ ~ nor
• Useful for extracting and inserting groups
of bits in a word
Instruction Sets 2 – Chang Liu 10
Shift Operations
• shamt: how many positions to shift
• Shift left logical
– Shift left and fill with 0 bits
– sll by i bits multiplies by 2i
• Shift right logical
– Shift right and fill with 0 bits
– srl by i bits divides by 2i (unsigned only)
op rs rt rd shamt funct
6 bits 6 bits5 bits 5 bits 5 bits 5 bits
Instruction Sets 2 – Chang Liu 11
AND Operations
• Useful to mask bits in a word
– Select some bits, clear others to 0
and $t0, $t1, $t2
0000 0000 0000 0000 0000 1101 1100 0000
0000 0000 0000 0000 0011 1100 0000 0000
$t2
$t1
0000 0000 0000 0000 0000 1100 0000 0000$t0
Instruction Sets 2 – Chang Liu 12
OR Operations
• Useful to include bits in a word
– Set some bits to 1, leave others unchanged
or $t0, $t1, $t2
0000 0000 0000 0000 0000 1101 1100 0000
0000 0000 0000 0000 0011 1100 0000 0000
$t2
$t1
0000 0000 0000 0000 0011 1101 1100 0000$t0
Instruction Sets 2 – Chang Liu 13
NOT Operations
• Useful to invert bits in a word
– Change 0 to 1, and 1 to 0
• MIPS has NOR 3-operand instruction
– a NOR b == NOT ( a OR b )
nor $t0, $t1, $zero
0000 0000 0000 0000 0011 1100 0000 0000$t1
1111 1111 1111 1111 1100 0011 1111 1111$t0
Register 0: always
read as zero
Instruction Sets 2 – Chang Liu 14
Conditional Operations
• Branch to a labeled instruction if a condition is
true
– Otherwise, continue sequentially
• beq rs, rt, L1
– if (rs == rt) branch to instruction labeled L1;
• bne rs, rt, L1
– if (rs != rt) branch to instruction labeled L1;
• j L1
– unconditional jump to instruction labeled L1
Instruction Sets 2 – Chang Liu 15
Compiling If Statements
• C code:
if (i==j) f = g+h;
else f = g-h;
– f, g, … in $s0, $s1, …
• Compiled MIPS code:
bne $s3, $s4, Else
add $s0, $s1, $s2
j Exit
Else: sub $s0, $s1, $s2
Exit: … Assembler calculates addresses
Instruction Sets 2 – Chang Liu 16
Compiling Loop Statements
• C code:
while (save[i] == k) i += 1;
– i in $s3, k in $s5, address of save in $s6
• Compiled MIPS code:
Loop: sll $t1, $s3, 2
add $t1, $t1, $s6
lw $t0, 0($t1)
bne $t0, $s5, Exit
addi $s3, $s3, 1
j Loop
Exit: …
Instruction Sets 2 – Chang Liu 17
More Conditional Operations
• Set result to 1 if a condition is true
– Otherwise, set to 0
• slt rd, rs, rt
– if (rs < rt) rd = 1; else rd = 0; • slti rt, rs, constant – if (rs < constant) rt = 1; else rt = 0; • Use in combination with beq, bne slt $t0, $s1, $s2 # if ($s1 < $s2) bne $t0, $zero, L # branch to L Instruction Sets 2 - Chang Liu 18 Branch Instruction Design • Why not blt, bge, etc? • Hardware for <, ≥, … slower than =, ≠ – Combining with branch involves more work per instruction, requiring a slower clock – All instructions penalized! • beq and bne are the common case • This is a good design compromise • More on Jump and Branch in Lecture 9 – Instruction Sets 3 Instruction Sets 2 - Chang Liu 19 Basic Blocks • A basic block is a sequence of instructions with – No embedded branches (except at end) – No branch targets (except at beginning) • A compiler identifies basic blocks for optimization • An advanced processor can accelerate execution of basic blocks Instruction Sets 2 - Chang Liu 20 Some Points to Consider • Design principles 1. Simplicity favors regularity 2. Smaller is faster 3. Make the common case fast 4. Good design demands good compromises • Layers of software/hardware – Compiler, assembler, hardware • MIPS: typical of RISC ISAs – c.f. x86 (CISC) Instruction Sets 2 - Chang Liu 21 Next Lecture • Basic function blocks for Processor Architecture • Chapter 4 Instruction Sets 2 - Chang Liu 22