COMPUTER ORGANIZATION AND DESIGN

The Hardware/Software Interface

Chapter 2

Instructions:
Language of the Computer
The Classic Components of a Computer

2
 What Is Computer Architecture?

▪ Computer Architecture
▪ Instruction Set Architecture + Computer Organization

▪ Instruction Set Architecture (ISA)

▪ WHAT the computer does (logical view)

▪ Computer Organization
▪ HOW the ISA is implemented (physical view)

3
 §2.1 Introduction
Instruction Set
◼ Instruction set: The vocabulary of commands
understood by a given architecture.
◼ Different computers have different
instruction sets
◼ But with many aspects in common
◼ Early computers had very simple
instruction sets
◼ Simplified implementation
◼ Many modern computers also have simple
instruction sets
Chapter 2 — Instructions: Language of the Computer — 4
 Instruction Set
User Level

Interfacing

Stored-program
The idea that instructions
and data of many types
can be stored in memory
as numbers, leading to the
stored-program computer.
Hardware Level
5
The MIPS Instruction Set
◼ Used as the example throughout the course
◼ Stanford MIPS commercialized by MIPS
Technologies (www.mips.com)
◼ Typical of many modern ISAs
◼ See MIPS Reference Data tear-out card, and
Appendixes B and E
◼ Similar ISAs have a large share of embedded
core market
◼ Applications in consumer electronics, network/storage
equipment, cameras, printers, …

Chapter 2 — Instructions: Language of the Computer — 6

Computer Components: Top Level View

7
 §2.2 Operations of the Computer Hardware
Arithmetic Operations
▪ Every computer must be able to perform arithmetic and
logical operations.

▪ Arithmetic operations: add, subtract, multiply & divide

are the building blocks for any arithmetic operation.

▪ The MIPS assembly language: (a, b, and c are variables)

Instruction Operands
add a, b, c

One destination & two sources

▪ All arithmetic operations have this form. 8
 Arithmetic Operations
▪ The MIPS assembly language: (a, b, and c are variables)

add a, b, c

One destination & two sources

▪ Example: place the sum of variables b, c, d, and e into

variable a.
▪ Computer performs this arithmetic operation as a set of add
instructions sequentially.

9
 Arithmetic Operations
▪ The MIPS assembly language: (a, b, and c are variables)

add a, b, c

One destination & two sources

▪ Example: Compiling Two C Assignment Statements into
MIPS
a = b + c;
d = a – e;
MIPS instructions:
b-c →a
add a, b, c
Sub d, a, e
a-e→d 10
 Arithmetic Operations
▪ Example: Compiling a Complex C Assignment into MIPS

f = ( g + h ) – ( i + j );

MIPS instructions: a set of instructions in a sequential order

11
 Design Principles

Simplicity favors regularity

▪ Regularity makes implementation simpler

▪ Simplicity enables higher performance at lower cost

12
 Operands
Instruction Operands
Ins Des, Src1, Src2

One destination & two sources

In general, operands can be:

▪ Register Operands
▪ Memory Operands
▪ Immediate Operands
▪ Constant Zero
13
 §2.3 Operands of the Computer Hardware
Register Operands
◼ Arithmetic instructions use register operands
◼ MIPS has a 32 × 32-bit register file
◼ Use for frequently accessed data
◼ Numbered 0 to 31
◼ 32-bit data called a “word”
◼ The word is the natural unit of access in a computer,
usually a group of 32 bits; corresponds to the size of
a register in the MIPS architecture.
◼ Assembler names
◼ $t0, $t1, …, $t9 for temporary values
◼ $s0, $s1, …, $s7 for saved variables

Chapter 2 — Instructions: Language of the Computer — 14

 §2.3 Operands of the Computer Hardware
Register Operands
◼ Resister names (or numbers):

Chapter 2 — Instructions: Language of the Computer — 15

 Design Principles

Smaller is faster

▪ A very large number of registers may increase the

clock cycle time simply because it takes electronic
signals longer when they must travel farther.

▪ Main memory has millions of locations

16
Register Operand Example
◼ C code:
f = (g + h) - (i + j);
◼ f, …, j in $s0, …, $s4

◼ Compiled MIPS code:

add $t0, $s1, $s2
add $t1, $s3, $s4
sub $s0, $t0, $t1

Chapter 2 — Instructions: Language of the Computer — 17

Register Operand Example
◼ Compiling Two C Assignment Statements
into MIPS
a = b + c;
d = a – e;
a, b, c, d and e in registers $s0, $s1, $s2, $s3 and $s4

◼ Compiled MIPS code:

add $s0, $s1, $s2

sub $s3, $s0, $s4
Chapter 2 — Instructions: Language of the Computer — 18
 Memory Operands
▪ Main memory used for composite data
▪Arrays, structures, dynamic data

▪ To apply arithmetic operations

▪ Load values from memory into registers

▪ Store result from register to memory

Chapter 2 — Instructions: Language of the Computer — 19

 Memory Operands
◼ Memory is byte addressed
◼ Each address identifies an 8-bit (1 byte)
◼ Words are aligned in memory
◼ Address must be a multiple of 4 (i.e., 4 locations)

Word size is 32. Thus, each word

will take 4 locations in the memory

Chapter 2 — Instructions: Language of the Computer — 20

Memory Operands
◼ MIPS is Big Endian machine
◼ Most-significant byte at least address of a word
◼ Little Endian: least-significant byte at least address

Chapter 2 — Instructions: Language of the Computer — 21

Memory Operand Example 1
◼ C code:
g = h + A[8];
◼ g in $s1, h in $s2, base address of A in $s3

◼ Compiled MIPS code:

◼ Index 8 requires offset of 32
◼ 4 bytes per word
lw $t0, 32($s3) # load word
add $s1, $s2, $t0

Offset = 8*4=32 base register consists of the address of the first

element in A

Chapter 2 — Instructions: Language of the Computer — 22

Memory Operand Example 2
◼ C code:
A[12] = h + A[8];
◼ h in $s2, base address of A in $s3

◼ Compiled MIPS code:

◼ Index 8 requires offset of 32
lw $t0, 32($s3) # load word
add $t0, $s2, $t0
sw $t0, 48($s3) # store word

Chapter 2 — Instructions: Language of the Computer — 23

Registers vs. Memory
◼ Registers are faster to access than
memory

◼ Operating on memory data requires loads

and stores
◼ More instructions to be executed

◼ Compiler must use registers for variables

as much as possible

Chapter 2 — Instructions: Language of the Computer — 24

Immediate Operands

◼ Constant data specified in an instruction

addi $s3, $s3, 4

◼ No subtract immediate instruction

◼ Just use a negative constant
addi $s2, $s1, -1

Chapter 2 — Instructions: Language of the Computer — 25

The Constant Zero
◼ MIPS register 0 ($zero) is the constant 0
◼ Cannot be overwritten

◼ Useful for common operations

◼ E.g., move between registers
add $t2, $s1, $zero
$t1  $s1
◼ The move instruction (pseudo-instruction):
◼ move between registers
move $t2, $s1 $t1  $s1

Chapter 2 — Instructions: Language of the Computer — 26

Design Principles

Make the common case fast

▪ Small constants are common

▪ Immediate operand avoids a load instruction

27
MIPS Instructions

28
 MARS simulator
▪ MARS (MIPS Assembler and Runtime Simulator): An
IDE for MIPS Assembly Language Programming

▪ MARS is a lightweight interactive development

environment (IDE) for programming in MIPS assembly
language, intended for educational-level use with
Patterson and Hennessy's Computer Organization and
Design.

▪ Features:
▪ GUI with point-and-click control and integrated editor
▪ Easily editable register and memory values, similar to a spreadsheet
▪ Display values in hexadecimal or decimal
▪ And many others 29
 MARS simulator

▪ Download the MARS simulator. On the MARS

download page, select the "Download MARS" button.

▪ For detailed directions, refer to the MARS tutorial ,

this website or watch this video on YouTube

▪ Here are a few example MIPS assembly programs you

may download and try:
area_triangle.asm, arith_exmpl.asm, sum_1to100.asm.

30
 §2.4 Signed and Unsigned Numbers
Unsigned Binary Integers
◼ Given an n-bit number
n −1 n−2
x = x n−1 2 + x n−2 2 +  + x1 2 + x 0 2
1 0

◼ Range: 0 to +2n – 1
◼ Example
◼ 0000 0000 0000 0000 0000 0000 0000 10112
= 0 + … + 1×23 + 0×22 +1×21 +1×20
= 0 + … + 8 + 0 + 2 + 1 = 1110
◼ Using 32 bits
◼ 0 to +4,294,967,295

Chapter 2 — Instructions: Language of the Computer — 31

2s-Complement Signed Integers
◼ Given an n-bit number
n −1 n−2
x = − x n−1 2 + x n−2 2 +  + x1 2 + x 0 2
1 0

◼ Range: –2n – 1 to +2n – 1 – 1

◼ Example
◼ 1111 1111 1111 1111 1111 1111 1111 11002
= –1×231 + 1×230 + … + 1×22 +0×21 +0×20
= –2,147,483,648 + 2,147,483,644 = –410
◼ Using 32 bits
◼ –2,147,483,648 to +2,147,483,647

Chapter 2 — Instructions: Language of the Computer — 32

2s-Complement Signed Integers
◼ Bit 31 is sign bit
◼ 1 for negative numbers
◼ 0 for non-negative numbers

◼ Non-negative numbers have the same unsigned

and 2s-complement representation
◼ Some specific numbers
◼ 0: 0000 0000 … 0000
◼ –1: 1111 1111 … 1111
◼ Most-negative: 1000 0000 … 0000
◼ Most-positive: 0111 1111 … 1111

Chapter 2 — Instructions: Language of the Computer — 33

Signed Negation

◼ Complement and add 1

◼ Complement means 1 → 0, 0 → 1

◼ Example: negate +2
◼ +2 = 0000 0000 … 00102
◼ –2 = 1111 1111 … 11012 + 1
= 1111 1111 … 11102

Chapter 2 — Instructions: Language of the Computer — 34

Sign Extension
◼ Representing a number using more bits
◼ Preserve the numeric value
◼ In MIPS instruction set
◼ addi: extend immediate value
◼ lb, lh: extend loaded byte/halfword
◼ beq, bne: extend the displacement
◼ Replicate the sign bit to the left
◼ c.f. unsigned values: extend with 0s
◼ Examples: 8-bit to 16-bit
◼ +2: 0000 0010 => 0000 0000 0000 0010
◼ –2: 1111 1110 => 1111 1111 1111 1110

Chapter 2 — Instructions: Language of the Computer — 35

MIPS Instructions

36
 §2.6 Logical Operations
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
Chapter 2 — Instructions: Language of the Computer — 37
 Shift Operations

Shift left operation

R format instruction 38
Shift Operations
op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

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

Chapter 2 — Instructions: Language of the Computer — 39

AND Operations
◼ Useful to mask bits in a word
◼ Select some bits, clear others to 0
and $t0, $t1, $t2

$t2 0000 0000 0000 0000 0000 1101 1100 0000

$t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 0000 0000 0000 0000 0000 1100 0000 0000

Chapter 2 — Instructions: Language of the Computer — 40

OR Operations
◼ Useful to include bits in a word
◼ Set some bits to 1, leave others unchanged
or $t0, $t1, $t2

$t2 0000 0000 0000 0000 0000 1101 1100 0000

$t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 0000 0000 0000 0000 0011 1101 1100 0000

Chapter 2 — Instructions: Language of the Computer — 41

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 Register 0: always
read as zero

$t1 0000 0000 0000 0000 0011 1100 0000 0000

$t0 1111 1111 1111 1111 1100 0011 1111 1111

Chapter 2 — Instructions: Language of the Computer — 42

MIPS Instructions

43
 §2.7 Instructions for Making Decisions
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

Chapter 2 — Instructions: Language of the Computer — 44

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

Chapter 2 — Instructions: Language of the Computer — 45

Compiling If Statements
C code MIPS Instructions

temp = a;
if ( a != b )
temp =(a+b)/2;
temp += c;

Assume that $s0 = a, $s1 = b, $s2 = c, $t0 = temp.

Chapter 2 — Instructions: Language of the Computer — 46

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: …

Chapter 2 — Instructions: Language of the Computer — 47

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

Chapter 2 — Instructions: Language of the Computer — 48

Signed vs. Unsigned
◼ Signed comparison: slt, slti
◼ Unsigned comparison: sltu, sltui
◼ Example
◼ $s0 = 1111 1111 1111 1111 1111 1111 1111 1111
◼ $s1 = 0000 0000 0000 0000 0000 0000 0000 0001
◼ slt $t0, $s0, $s1 # signed
◼ –1 < +1  $t0 = 1
◼ sltu $t0, $s0, $s1 # unsigned
◼ +4,294,967,295 > +1  $t0 = 0

Chapter 2 — Instructions: Language of the Computer — 49

Example 1
◼ The following C code:
int i;
for ( i = 0; i < numVals; i++ )
{ int x = A[i];
x *= 2;
A[i] = x;
}
$s6 = A ; $s7 = numVals ;
$t0 = I ; $t4 = x
Chapter 2 — Instructions: Language of the Computer — 50
Example 1
◼ MIPS Instructions:
addi $t0, $zero, 0
LOOP: slt $t1, $t0, $s7
beq $t1, $zero, ENDLOOP
sll $t1, $t0, 2
add $t1, $s7, $t1
lw $t4, 0($t1)
sll $t4, $t4, 1
sw $t4, 0($t1)
addi $t0, $t0, 1
j LOOP
ENDLOOP:
⋮
Chapter 2 — Instructions: Language of the Computer — 51
 Example 2
◼ The following C code:
sum = 0;
for ( i = 0; i < n; i++ )
{
sum += A[i];
}

Assume that $s0 = i, $s1 = n, $s2 = A, $s3 =

sum, and that A is an array of int.

Chapter 2 — Instructions: Language of the Computer — 52

Example 2
◼ MIPS Instructions:

Chapter 2 — Instructions: Language of the Computer — 53

MIPS Instructions

54
 §2.5 Representing Instructions in the Computer
Representing Instructions
User Level

Interfacing

Hardware Level

Chapter 2 — Instructions: Language of the Computer — 55

 Representing Instructions

▪ The binary digit (called binary bit), One of the two numbers
in base 2, 0 or 1, that are the components of information.

▪ Machine language: A binary representation used for

communication within a computer system.

• Instruction format: A form of representation of an

instruction composed of fields of binary numbers.

56
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, …

◼ Register numbers
◼ $t0 – $t7 are reg’s 8 – 15
◼ $t8 – $t9 are reg’s 24 – 25
◼ $s0 – $s7 are reg’s 16 – 23

Chapter 2 — Instructions: Language of the Computer — 57

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

Chapter 2 — Instructions: Language of the Computer — 58

MIPS R-format Instructions
op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

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

Chapter 2 — Instructions: Language of the Computer — 59

R-format Example
op rs rt rd shamt funct
6 bits 5 bits 5 bits 5 bits 5 bits 6 bits

add $t0, $s1, $s2

special $s1 $s2 $t0 0 add

0 17 18 8 0 32

000000 10001 10010 01000 00000 100000

000000100011001001000000001000002 = 0232402016

Chapter 2 — Instructions: Language of the Computer — 60

MIPS I-format Instructions
op rs rt constant or address
6 bits 5 bits 5 bits 16 bits

◼ 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

Chapter 2 — Instructions: Language of the Computer — 61

 Representing Instructions (Example)
▪ Translating MIPS Assembly Language into Machine Language.
We can now take an example all the way from what the programmer writes
to what the computer executes. If $t1 has the base of the array A and $s2
corresponds to h, the assignment statement:

A[300] = h + A[300];
1) MIPS Instructions:

lw $t0,1200($t1) # Temporary reg $t0 gets A[300]

add $t0,$s2,$t0 # Temporary reg $t0 gets h + A[300]

sw $t0,1200($t1) # Stores h + A[300] back into A[300]

62
 Representing Instructions (Example)
▪ Translating MIPS Assembly Language into Machine Language.
We can now take an example all the way from what the programmer writes
to what the computer executes. If $t1 has the base of the array A and $s2
corresponds to h, the assignment statement:

A[300] = h + A[300];
2) MIPS machine code:

63
 Representing Instructions (Example)
▪ Translating MIPS Assembly Language into Machine Language.
We can now take an example all the way from what the programmer writes
to what the computer executes. If $t1 has the base of the array A and $s2
corresponds to h, the assignment statement:

A[300] = h + A[300];
2) MIPS machine code:

64
Branch Addressing
◼ Branch instructions specify
◼ Opcode, two registers, target address
◼ Most branch targets are near branch
◼ Forward or backward

op rs rt constant or address
6 bits 5 bits 5 bits 16 bits

◼ PC-relative addressing
◼ Target address = PC + offset × 4
◼ PC already incremented by 4 by this time
Chapter 2 — Instructions: Language of the Computer — 65
Jump Addressing
◼ Jump (j and jal) targets could be
anywhere in text segment
◼ Encode full address in instruction

op address
6 bits 26 bits

◼ (Pseudo)Direct jump addressing

◼ Target address = PC31…28 : (address × 4)

Chapter 2 — Instructions: Language of the Computer — 66

Target Addressing Example
◼ Loop code from earlier example
◼ Assume Loop at location 80000

Loop: sll $t1, $s3, 2 80000 0 0 19 9 4 0

add $t1, $t1, $s6 80004 0 9 22 9 0 32
lw $t0, 0($t1) 80008 35 9 8 0
bne $t0, $s5, Exit 80012 5 8 21 2
addi $s3, $s3, 1 80016 8 19 19 1
j Loop 80020 2 20000
Exit: … 80024

Chapter 2 — Instructions: Language of the Computer — 67

 Design Principles

Good design demands good compromises

▪ Different formats complicate decoding, but allow 32-

bit instructions uniformly

▪ Keep formats as similar as possible

68
 §2.12 Translating and Starting a Program
Translation and Startup

Many compilers produce

object modules directly

Static linking

Chapter 2 — Instructions: Language of the Computer — 69

 Role of Assembler
▪ Convert pseudo-instructions into actual hardware
instructions
▪ pseudo-instrs make it easier to program in
assembly
▪ examples: “move”, “blt”, 32-bit immediate
operands, etc.
▪ Convert assembly instrs into machine instrs
▪ a separate object file (x.o) is created for each C
file (x.c)
▪ compute the actual values for instruction labels
▪ maintain info on external references and
debugging information 70
 Assembler Pseudoinstructions
▪ Branch Pseudoinstructions (Branch if less than (blt))
The blt instruction compares 2 registers, treating them as signed
integers, and takes a branch if one register is less than another.

▪ Other Pseudoinstructions (Move (move))

The move pseudo instruction moves the contents of one register into
another register.

71
Stored Program Computers
The BIG Picture ◼ Instructions represented in
binary, just like data
◼ Instructions and data stored
in memory
◼ Programs can operate on
programs
◼ e.g., compilers, linkers, …
◼ Binary compatibility allows
compiled programs to work
on different computers
◼ Standardized ISAs

Chapter 2 — Instructions: Language of the Computer — 72