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
