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, don’t
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, don’t
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, don’t
shift product register right 1 bit
repeat 32 times (on 32 bits)

Booth’s 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 it’s 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