COMPUTER

ARCHITECTURE
Arithmetic Ops
MIPS Instruction Set
This chapter introduces the concept of a computer's instruction set, MIPS
which is the language a computer understands to command its hardware. Microprocessor without
Interlocked Pipeline Stages.
MIPS is used as the example throughout the book.

Arithmetic Operations
Arithmetic_Ops

add a, b, c # The sum of b and c is placed in a

add a, a, d # The sum of b, c, and d is now in a
add a, a, e # The sum of b, c, d, and e is now in a

Design Principle 1: Simplicity Favors Regularity

The strict requirement of three operands per operation follows the design principle of simplicity
and regularity in hardware. Hardware for variable operands would be more complex,
so using a fixed number of operands (three) makes the hardware design simpler and more efficient.
Page 65
Example 1
A somewhat complex statement contains the five variables f, g, h, i, and j:
f = (g + h) – (i + j);
What might a C compiler produce?

Answer

Arithmetic_Ops

add t0,g,h # temporary variable t0 contains g + h --> (temp t0 = g + h)

add t1,i,j # temporary variable t1 contains i + j --> (temp t1 = i + j)
sub f,t0,t1 # f gets t0 - t1, which is (g + h) - (i + j) --> (f = t0 – t1)
Register Operands
Operand: Input or Output values for an operation.
Operands for arithmetic instructions are restricted to registers, which are special hardware locations.
Registers in MIPS are 32 bits in size, and a group of 32 bits is called a word.
Design Principle 2: Smaller Is Faster Register
MIPS typically has 32 registers (Numbered 0 to 31). A special, small-sized, fast storage
This limitation is partly due to the hardware design principle: “Smaller is faster”. location in computer hardware used
A smaller number of registers helps keep the clock cycle fast to hold data for arithmetic operations.
because electronic signals don't need to travel as far.
Register Naming
MIPS uses symbolic names for registers, like $s0, $s1 for saved registers
(corresponding to C/Java variables) and $t0, $t1 for temporary registers.

Temporary Registers ($t0, $t1, …, $t7)

Saved Registers ($s0, $s1, …, $s7) These registers are used to store temporary values
These registers are used to hold values that during computation, particularly when performing
must be preserved across function calls. operations that don’t need to be preserved
after a function call.
Page 67
Example 2
It is the compiler’s job to associate program variables with registers.
Take, for instance, the assignment statement from our earlier example: f = (g + h) – (i + j);
The variables f, g, h, i, and j are assigned to the registers $s0, $s1, $s2, $s3, and $s4, respectively.
What is the compiled MIPS code?

Answer

Arithmetic_Ops

add $t0,$s1,$s2 # register $t0 contains g + h --> (temp t0 = g + h)

add $t1,$s3,$s4 # register $t1 contains i + j --> (temp t1 = i + j)
sub $s0,$t0,$t1 # f gets $t0 - $t1, which is (g + h) - (i + j) --> (f = t0 – t1)
Memory Operands Data Transfer Instructions
Memory A command that moves data between
memory and registers.
Memory is used to store larger data structures like arrays and structures,
which can hold more data than the available registers.
Word
Data Transfer The natural unit of access in a computer,
MIPS instructions operate only on registers, so data must be transferred usually a group of 32 bits; corresponds to
between memory and registers using data transfer instructions. the size of a register in the MIPS architecture.

Addressing
In memory, data is stored in a single-dimensional array, with the address acting as the index.
For instance, in a memory array, Memory[2] would represent the third element of the array.

Load Instruction
To access a word in memory, MIPS uses the lw (load word) instruction.
This instruction loads data from memory into a register.
The address for the memory location is computed by adding a constant
value to the contents of a register, forming the address.
Design Principle
CPU
Register 1 Register 2 Register 3
…

Memory

…
3 100
2 10
1 101
0 1
Byte
Address
Data
Page 69
Example 3
Assume variable h is associated with register $s2 and the base address of the array A is in $s3.
What is the MIPS assembly code for the C assignment statement below?
A[12] = h + A[8];

Answer

Arithmetic_Ops

lw $t0,32($s3) # Temporary reg $t0 gets A[8] --> (temp t0 = A[8])

add $t0,$s2,$t0 # Temporary reg $t0 gets h + A[8] --> (temp t0 = h + A[8])
sw $t0,48($s3) # Stores h + A[8] back into A[12] --> (A[12] = t0)
Immediate Operands
No Subtract Immediate
Use of Constants
Instruction
Programs often require constants for operations, such as incrementing an index.
Just use a negative constant.
In the MIPS architecture, many arithmetic instructions use constants as operands.

Improved Efficiency
Constants can be directly used in arithmetic instructions via the addi (add immediate) instruction.

Arithmetic_Ops

addi $s3,$s3,4 # $s3 = $s3 + 4

addi $s3,$s3,-1 # $s3 = $s3 + (-1)

Design Principle 3: Make the Common Case Fast

Including constants directly in instructions like addi is an example of optimizing for common use cases.
This makes frequently used operations (like adding small constants) faster and more energy-efficient.
The Constant Zero
MIPS register 0 ($zero) is the constant 0. Cannot be overwritten.
Useful for Common Operations
E.g., move between registers.

Arithmetic_Ops

add $t2, $s1, $zero # $t2 = $s1

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, register $zero always equals 0, and register $at is
$fp, $sp, $ra, $at reserved by the assembler to handle large constants.
Accessed only by data transfer instructions. MIPS uses byte
Memory[0], Memory[4], …,
2 30
memory words addresses, so sequential word addresses differ by 4. Memory holds
Memory[4294967292]
data structures, arrays, and spilled registers.
Category Instruction Example Meaning Comments
add add $s1,$s2,$s3 $s1 = $s2 + $s3 Three register operands

Arithmetic subtract sub $s1,$s2,$s3 $s1 = $s2 – $s3 Three register operands

MIPS Assembly Language

add immediate addi $s1,$s2,20 $s1=$s2 + 20 Used to add constants

load word lw $s1,20($s2) $s1 = Memory[$s2 + 20] Word from memory to register

store word sw $s1,20($s2) Memory[$s2 + 20] = $s1 Word from register to memory

load half lh $s1,20($s2) $s1 = Memory[$s2+ 20] Halfword memory to register

load half unsigned lhu $s1,20($s2) $s1 = Memory[$s2+ 20] Halfword memory to register

store half sh $s1,20($s2) Memory[$s2+ 20] = $s1 Halfword register to memory

Data transfer load byte lb $s1,20($s2) $s1 = Memory[$s2+ 20] Byte from memory to register

load byte unsigned lbu $s1,20($s2) $s1 = Memory[$s2+ 20] Byte from memory to register

store byte sb $s1,20($s2) Memory[$s2+ 20] = $s1 Byte from register to memory

load linked word ll $s1,20($s2) $s1 = Memory[$s2+ 20] Load word as 1st half of atomic swap

store condition. word sc $s1,20($s2) Memory[$s2+20]=$s1;$s1=0 or 1 Store word as 2nd half of atomic swap

load upper immed. lui $s1,20 $s1 = 20 * 2 16

Loads constant in upper 16 bits

and and $s1,$s2,$s3 $s1 = $s2 & $s3 Three reg. operands; bit-by-bit AND

or or $s1,$s2,$s3 $s1 = $s2 | $s3 Three reg. operands; bit-by-bit OR

nor nor $s1,$s2,$s3 $s1 = ~ ($s2 | $s3) Three reg. operands; bit-by-bit NOR

Logical and immediate andi $s1,$s2,20 $s1 = $s2 & 20 Bit-by-bit AND reg with constant

or immediate ori $s1,$s2,20 $s1 = $s2 | 20 Bit-by-bit OR reg with constant

shift left logical sll $s1,$s2,10 $s1 = $s2 << 10 Shift left by constant

shift right logical srl $s1,$s2,10 $s1 = $s2 >> 10 Shift right by constant

branch on equal beq $s1,$s2,25 if ($s1 == $s2) go to PC + 4 + 100 Equal test; PC-relative branch

branch on not equal bne $s1,$s2,25 if ($s1!= $s2) go to PC + 4 + 100 Not equal test; PC-relative

set on less than slt $s1,$s2,$s3 if ($s2 < $s3) $s1= 1; else $s1 = 0 Compare less than; for beq, bne
Conditional branch
set on less than unsigned sltu $s1,$s2,$s3 if ($s2 < $s3) $s1= 1; else $s1 = 0 Compare less than unsigned

set less than immediate slti $s1,$s2,20 if ($s2 < 20) $s1= 1; else $s1= 0 Compare less than constant

set less than immediate unsigned sltiu $s1,$s2,20 if ($s2 < 20) $s1= 1; else $s1= 0 Compare less than constant unsigned

jump j 2500 go to 10000 Jump to target address

Unconditional jump jump register jr $ra go to $ra For switch, procedure return

jump and link jal 2500 $ra = PC + 4; go to 10000 For procedure call
Unsigned Numbers
x = xn−1 2n−1 + xn−2 2n−2 + ⋯ + x1 21 + x0 20
Range: 0 to +2n – 1. Using 32 bits 0 to +4,294,967,295
0000 0000 0000 0000 0000 0000 0000 0000two = 0ten 0000 0000 0000 0000 0000 0000 0000 0010two = 2ten

Signed Numbers x = −xn−1 2n−1 + xn−2 2n−2 + ⋯ + x1 21 + x0 20

Range: −2n−1 to +2n−1 – 1.

1111 1111 1111 1111 1111 1111 1111 1111two = −1ten 1111 1111 1111 1111 1111 1111 1111 1110two = −2ten

0111 1111 1111 1111 1111 1111 1111 1111two = 2,147,483,647ten

1000 0000 0000 0000 0000 0000 0000 0000two = −2,147,483,648ten

1000 0000 0000 0000 0000 0000 0000 0001two = −2,147,483,647ten

Two’s Complement
The most common method of representing signed integers on computers.
1. Apply one’s complement: Inverting all bits – changing every 0 to 1, and every 1 to 0.
2. Adding 1 to the entire inverted number, ignoring any overflow.
Negate 2ten , and then check the result by negating −2ten .
0000 0000 0000 0000 0000 0000 0000 0010two = 2ten
1111 1111 1111 1111 1111 1111 1111 1101two
+
1two

1111 1111 1111 1111 1111 1111 1111 1110two = −2ten

Sign Extension
A technique used to convert a smaller binary number into a larger binary number, while preserving its value.
Context of Use
This is necessary when an immediate field (like a 16-bit two's complement number)
needs to be added to a 32-bit register.

Sign Extension Process

• The most significant bit (MSB) of the smaller binary number, which is the sign bit,
is replicated to fill the new higher-order bits of the larger number.
• The remaining bits are copied directly from the smaller binary number into the lower portion of the new larger number.

Examples
The 16-bit representation of 2ten is 0000 0000 0000 0010two .
To convert this to 32 bits, the 0 is replicated 16 times, and the rest of the original bits are placed in the right half:
0000 0000 0000 0000 0000 0000 0000 0010two = 2ten

The 16-bit representation of −2ten is 1111 1111 1111 1110two .

To convert this to a 32-bit number, the 1s in the sign bit (for a negative number) are replicated 16 times:
1111 1111 1111 1111 1111 1111 1111 1110two = −2ten