**ALU: Arithmetic Logic Unit **

On 32-bits (MIPS architecture)

Hardware building blocks are AND gate, OR gate, Inverter, Multiplexor

**Single-Bit Full Adder**

operand a (input)

operand b (input)

CarryIn (= CarryOut from previous adder = input)

CarryOut (output)

Sum (output)

To subtract, add a multiplexor to choose between b and ~b for adder

**Single-Bit Half Adder**

Has CarryOut but no CarryIn

Only two inputs and two outputs

**Carry Lookahead**

For 32-bit ALU, ripple adder connects multiple 1-bit adders together

Takes too long to wait for sequential evaluation of adders, so anticipate the carry

Use abstraction to cope with complexity

**Multiplication **

Multiplicand = first operand

Multiplier = second operand

Product = final result

**1st Multiplication Algorithm**

1 0 0 0

X 1 0 0 1

________________________________

1 0 0 0

0 0 0 0

0 0 0 0 0 0

1 0 0 0 0 0 0

________________________________

1 0 0 1 0 0 0

n X m multiplication = n + m bits

1st multiplication algorithm implements traditional pencil and paper multiplication

32-bit multiplier register and 64-bit multiplicand register

Multiplicand register has 32-bit multiplicand in right half and initialized to 0 in left half

Multiplicand register shifted left 1 bit each step to align with sum

Sum is accumulated in 64-bit product register

*if least significant bit of multiplier is 1
add multiplicand to the product
else, dont
shift multiplicand register left 1 bit
shift multiplier register right 1 bit
repeat 32 times (on 32 bits)*

**2nd Multiplication Algorithm**

1st multiplication algorithm inefficient because half the multiplicand bits were always 0

instead of shifting multiplicand left, shift product right

*if least significant bit of multiplier is 1
add multiplicand to left half of product
place result in left half of product register
else, dont
shift product register right 1 bit
shift multiplier register right 1 bit
repeat 32 times (on 32 bits)*

**3rd Multiplication Algorithm**

2nd version still not optimized enough

product register had same amount of wasted space as size of multiplier

3rd algorithm combines rightmost half of product with multiplier

no multiplier register b/c instead is placed in right half of product register

*if least significant bit of multiplier is 1
add multiplicand to left half of product
place result in left half of product register
else, dont
shift product register right 1 bit
repeat 32 times (on 32 bits)*

**Booths Algorithm**

classify groups of bits into the beginning, middle, or end of a run of 1s

four cases depending on value of multiplier

o 10 = beginning of a run of 1s, subtract multiplicand from left half of product

o 01 = end of a run of 1s, add multiplicand to left half of product

o 11 = middle of a run of 1s, no operation

o 00 middle of a run of 0s, no operation

shift product register right 1 bit

extend sign when product shifted to right (arithmetic shift since dealing with signed numbers as opposed to logical shift)

**Floating Point Addition **

shift smaller number right until exponent matches larger exponent

add the significands

normalize the sum

round significand to appropriate number of bits

normalize and round again if necessary

**Floating Point Multiplication **

add biased exponents and subtract the bias from the sum so its only counted once

multiply the significands

normalize the product

round significand to appropriate number of bits

normalize and round again if necessary

**Assembly Programming for MIPS **

$s0, $s1, used for registers that correspond to variables in C/C++ programs

$t0, $t1, used for temporary registers needed to compile the program into MIPS instructions

memory addresses are multiples of 4

all MIPS instructions / words / etc are 32 bits long

**add** add $s1, $s2, $s3 s1 = s2 + s3**subtract** sub $s1, $s2, $s3 s1 = s2 s3**add immediate (constant)** addi $s1, $s2, 100 s1 = s2 + 100**load word** lw $s1, 100($s2) s1 = A[s2 + 100]**store word** sw $s1, 100($s2) A[s2 + 100] = s1**branch on equal** beq $s1, $s2, SOMEWHERE if (s1 == s2) go SOMEWHERE**branch on not equal** bne $s1, $s2, SOMEWHERE if (s1 != s2) go SOMEWHERE**set on less than** slt $s1, $s2, $s3 if (s2 < s3) s1 = 1 else s1 = 0**unconditional jump** j SOMEWHERE goto SOMEWHERE

**Procedures in Assembly**

place parameters in a place where procedure can access them

transfer control to the procedure

acquire storage resources needed for the procedure

perform the desired task

place the result in a place where the calling program can access it

return control to the point of origin