29-03-2011, 04:36 PM
Presented by:
L.N. Bhuyan
[attachment=11280]
MIPS arithmetic instructions
° Instruction Example Meaning Comments
° add add $1,$2,$3 $1 = $2 + $3 3 operands; exception possible
° subtract sub $1,$2,$3 $1 = $2 – $3 3 operands; exception possible
° add immediate addi $1,$2,100 $1 = $2 + 100 + constant; exception possible
° add unsigned addu $1,$2,$3 $1 = $2 + $3 3 operands; no exceptions
° subtract unsigned subu $1,$2,$3 $1 = $2 – $3 3 operands; no exceptions
° add imm. unsign. addiu $1,$2,100 $1 = $2 + 100 + constant; no exceptions
° multiply mult $2,$3 Hi, Lo = $2 x $3 64-bit signed product
° multiply unsigned multu$2,$3 Hi, Lo = $2 x $3 64-bit unsigned product
° divide div $2,$3 Lo = $2 ÷ $3, Lo = quotient, Hi = remainder
° Hi = $2 mod $3
° divide unsigned divu $2,$3 Lo = $2 ÷ $3, Unsigned quotient & remainder
° Hi = $2 mod $3
° Move from Hi mfhi $1 $1 = Hi Used to get copy of Hi
° Move from Lo mflo $1 $1 = Lo Used to get copy of Lo
MULTIPLY (unsigned)
° Paper and pencil example (unsigned):
Multiplicand 1000
Multiplier 1001
1000
0000
0000
1000
Product 01001000
° m bits x n bits = m+n bit product
Binary makes it easy:
• 0 => place 0 ( 0 x multiplicand)
• 1 => place a copy ( 1 x multiplicand)
° 4 versions of multiply hardware & algorithm:
• successive refinement
° Unisigned shift-add multiplier (version 1)
° 64-bit Multiplicand reg, 64-bit ALU, 64-bit Product reg,
32-bit multiplier reg
Multiply Algorithm Version 1
° Product Multiplier Multiplicand 0000 0000 0011 0000 0010
° 0000 0010 0001 0000 0100
° 0000 0110 0000 0000 1000
° 0000 0110
° Observations on Multiply Version 1
° 1 clock per cycle => ¬ 100 clocks per multiply
• Ratio of multiply to add 5:1 to 100:1
° 1/2 bits in multiplicand always 0
=> 64-bit adder is wasted
° 0’s inserted in left of multiplicand as shifted
=> least significant bits of product never changed once formed
° Instead of shifting multiplicand to left, shift product to right?
MULTIPLY HARDWARE Version 2
° Half of the shifted multiplicand register contains 0. Why not shift the product right?
° 32-bit Multiplicand reg, 32 -bit ALU, 64-bit Product reg, 32-bit Multiplier reg
° Multiply Algorithm Version 2
Multiplier Multiplicand Product
0011 0010 0000 0000
Multiply Algorithm Version 2
° Product Multiplier Multiplicand 0000 0000 0011 0010
° 0010 0000
° 0001 0000 0001 0010
° 0011 00 0001 0010
° 0001 1000 0000 0010
° 0000 1100 0000 0010
° 0000 0110 0000 0010
° MULTIPLY HARDWARE Version 3
° Product register wastes space that exactly matches size of multiplier
=> combine Multiplier register and Product register
° 32-bit Multiplicand reg, 32 -bit ALU, 64-bit Product reg, (0-bit Multiplier reg)
Multiply Algorithm Version 3
Multiplicand Product
0010 0000 0011
Observations on Multiply Version 3
° 2 steps per bit because Multiplier & Product combined
° MIPS registers Hi and Lo are left and right half of Product
° Gives us MIPS instruction MultU
° How can you make it faster?
What about signed multiplication?
• easiest solution is to make both positive & remember whether to
complement product when done (leave out the sign bit, run for 31 steps)
• apply definition of 2’s complement
- need to sign-extend partial products and subtract at the end
• Booth’s Algorithm is elegant way to multiply signed numbers using same hardware as before and save cycles
- can handle multiple bits at a time