## Dani 1,665

ALU: Arithmetic Logic Unit

On 32-bits (MIPS architecture)
Hardware building blocks are AND gate, OR gate, Inverter, Multiplexor

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

Has CarryOut but no CarryIn
Only two inputs and two outputs

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
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)

shift smaller number right until exponent matches larger exponent
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

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
place the result in a place where the calling program can access it
return control to the point of origin

## maverick26

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

Thanks

he he
much more tutorialsa needed

## prithaghoshal

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?

## laosland

For what it's worth, how about splitting the result between two memory locations?

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?