Assembly Language Programming

Multiplication
CPSC 252 Computer
Organization
Ellen Walker, Hiram College
Multiplication
• Multiplication result needs twice as
many bits
– E.g. 7*7 = 49 (7 is 3 bits, 49 is 6 bits)
• Multiplication is more complex than
addition/subtraction
– Develop algorithm, implement using
simpler hardware
Multiplication Algorithms
• Repeated addition
– Easy to implement in software
– Can only multiply positive numbers directly
– Time depends on magnitude of operands
• Shift-and add
– Efficient use of hardware
– Time depends only on width of operands
– No special case for negative numbers
Shift and Add Algorithm
• For each bit in multiplier
– If bit = 1, add multiplicand to result
– Shift multiplicand left by 1
• This is the “usual” multiplication
algorithm you learned many years ago
(but simpler in binary)
Shift and Add example
10101
X 101
--------10101
000000
+ 1010100
-----------------1101001
21
5
(included for completeness)
105 (1+8+32+64)
Hardware to Multiply
• 64-bit register for multiplicand
– 32 bits for original value
– Option to shift left 32 times
• 64-bit ALU
– Add shifted multiplicand to product
• 32-bit register for multiplier
– Shift right after each step (low bits fall off)
• Control hardware
Multiplication: Implementation
Start
Multiplier0 = 1
1. Test
Multiplier0
Multiplier0 = 0
Multiplicand
Shift left
1a. Add multiplicand to product and
place the result in Product register
64 bits
Multiplier
Shift right
64-bit ALU
32 bits
Product
Write
2. Shift the Multiplicand register left 1 bit
Control test
64 bits
3. Shift the Multiplier register right 1 bit
No: < 32 repetitions
32nd repetition?
Datapath
Control
Yes: 32 repetitions
Done
How Long Does it Take?
• 32 shift/add cycles
• Each cycle has 3 steps (add, shift left,
shift right)
• Without parallelism, that’s 96 cycles per
multiply
Improvements
• Save hardware by using 1 64-bit register for
the product and multiplier
– Left part is product (so far)
– Right part is unused multiplier
– Add a bit to the product and lose a bit from the
multiplier each cycle
– Shift product right & add instead of shift
multiplicand left & add!
• Shift and add in the same cycle (in parallel)
• This revision requires only 32 cycles
Final Version
•Multiplier starts in right half of product
Product0 = 1
Start
1. Test
Product0
Product0 = 0
Multiplicand
32 bits
32-bit ALU
Product
Shift right
Write
Control
test
3. Shift the Product register right 1 bit
64 bits
No: < 32 repetitions
32nd repetition?
What goes here?
Yes: 32 repetitions
Done
Parallel Multiplication
• Instead of 32 cycles, use 32 adders
• Each adds 0 or multiplicand
• Arrange in tree so results cascade
properly
• Result pulls each bit from the
appropriate adder
Parallel Multiplication (cont)
010101 x 000101 (6 bits)
000000 000101
+010101
010101 000101
0010101 00010
00010101 0001
+010101
01101001 0001
001101001 000
0001101001 00
00001101001 0
000001101001
(initial product)
Rightmost bit is 1, add multiplicand
Shift product right
Shift product right
Rightmost bit is 1, add multiplicand
Shift product right
Shift product right
Shift product right
Shift product right, answer is 105
Negative numbers
• Convert to positive, multiply, then
negate if initial signs were different
• Or, consider 3 cases:
– Both negative: convert to positive and
multiply
– One negative: make multiplier positive,
multiplicand negative
– Negative multiplicand: when high bit is 1,
shift in 1’s (shift right arithmetic)
MIPS multiplication
• 2 32-bit registers: Hi and Lo
mflo $s0
mfhi $s0
move from lo (to $s0)
move from hi (to $s0)
• Multiplication Operations
mult $s0, $s1
multu $s0, $s1
{Hi,Lo}= $s0 x $s1
unsigned version

Download Report