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

could someone please give me an explanation of n's complement?

Thanks

he he
much more tutorialsa needed

Hi,

We are working on an ALU Architecture in VHDL including instructions of Multiply and Divide. We are confused about how exactly the results from Multiplication or Division are sent outside the ALU. The adder subtractor have 8 bit results, but multiplication will have 16 bit and Division will have 8 bits quotient, and 8 bits remainder. So how exactly do we configure the outputs to send the whole information when we have a C as output from ALU of size 8 bits? Do we use 2 statements one after a specific time delay assigning the second half of the result, or is it some other way?