程序代写代做代考 mips Integer Multiplication and Division

Integer Multiplication and Division

Integer Multiplication
and Division
COE 301
Computer Organization
Prof. Muhamed Mudawar
College of Computer Sciences and Engineering
King Fahd University of Petroleum and Minerals

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Presentation Outline
Unsigned Integer Multiplication
Signed Integer Multiplication
Faster Integer Multiplication
Integer Division
Integer Multiplication and Division in MIPS

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›

Paper and Pencil Example:
Multiplicand 11002 = 12
Multiplier × 11012 = 13
1100
0000
1100
1100
Product 100111002 = 156
n-bit multiplicand × n-bit multiplier = (2n)-bit product
Accomplished via shifting and addition
Consumes more time and more chip area than addition
Unsigned Integer Multiplication
Binary multiplication is easy
0 × multiplicand = 0
1 × multiplicand = multiplicand

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
3

Unsigned Sequential Multiplication
Initialize Product = 0
Check each bit of the Multiplier
If Multiplier bit = 1 then Product = Product + Multiplicand
Rather than shifting the multiplicand to the left,
Shift the Product to the Right
Has the same net effect and produces the same result
Minimizes the hardware resources
One cycle per iteration (for each bit of the Multiplier)
Addition and shifting can be done simultaneously

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Initialize: HI = 0
Initialize: LO = Multiplier
Final Product in HI and LO registers
Repeat for each bit of Multiplier
Unsigned Sequential Multiplier
= 0

Start
LO[0]?
Carry, Sum = HI + Multiplicand
32nd Repetition?
Done
= 1
No
Yes
HI = 0, LO=Multiplier
HI, LO = Shift Right (Carry, Sum, LO)

32-bit ALU

Control
64 bits
32 bits
write
add
LO[0]
Multiplicand

shift right
32 bits
HI
LO
Sum

Carry
32 bits

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Sequential Multiplier Example
Consider: 11002 × 11012 , Product = 100111002
4-bit multiplicand and multiplier are used in this example
4-bit adder produces a 4-bit Sum + Carry bit
1 1 0 0
Shift Right (Carry, Sum, LO) by 1 bit
0 1 1 1 1 0 0 1
LO[0] = 0 => NO addition

1 1 0 0
Shift Right (HI, LO) by 1 bit
0 0 1 1 0 0 1 1
1 1 0 0
Shift Right (Carry, Sum, LO) by 1 bit
0 1 1 0 0 1 1 0
1 1 0 0
Shift Right (Carry, Sum, LO) by 1 bit
1 0 0 1 1 1 0 0

2
1 1 0 0
0 0 0 0 1 1 0 1
Initialize (HI = 0, LO = Multiplier)
0
1

4
Multiplicand
Product = HI, LO
Carry
Iteration

0
1 1 0 0 1 1 0 1
LO[0] = 1 => ADD

0
1 1 1 1 0 0 1 1
LO[0] = 1 => ADD

1
0 0 1 1 1 0 0 1
LO[0] = 1 => ADD

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Next . . .
Unsigned Integer Multiplication
Signed Integer Multiplication
Faster Integer Multiplication
Integer Division
Integer Multiplication and Division in MIPS

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Signed Integer Multiplication
First attempt:
Convert multiplier and multiplicand into positive numbers
If negative then obtain the 2’s complement and remember the sign
Perform unsigned multiplication
Compute the sign of the product
If product sign < 0 then obtain the 2's complement of the product Drawback: additional steps to compute the 2's complement Better version: Use the unsigned multiplication hardware When shifting right, extend the sign of the product If multiplier is negative, the last step should be a subtract Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#› Signed Multiplication (Paper & Pencil) Case 1: Positive Multiplier Multiplicand 11002 = -4 Multiplier × 01012 = +5 11111100 111100 Product 111011002 = -20 Case 2: Negative Multiplier Multiplicand 11002 = -4 Multiplier × 11012 = -3 11111100 111100 00100 (2's complement of 1100) Product 000011002 = +12 Sign-extension Sign-extension Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#› ALU produces: 32-bit sum + sign bit Sign bit can be computed: No overflow: sign = sum[31] If Overflow: sign = ~sum[31] Signed Sequential Multiplier = 0 Start LO[0]? 31 iterations: Sign, Sum = HI + Multiplicand Last iteration: Sign, Sum = HI – Multiplicand 32nd Repetition? Done = 1 No Yes HI = 0, LO = Multiplier HI, LO = Shift Right (Sign, Sum, LO) 32-bit ALU Control 64 bits 32 bits write add, sub LO[0] Multiplicand shift right 32 bits HI LO sum sign 32 bits Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#› Signed Multiplication Example Consider: 11002 (-4) × 11012 (-3), Product = 000011002 Check for overflow: No overflow  Extend sign bit Last iteration: add 2's complement of Multiplicand 1 1 0 0 Shift Right (Sign, Sum, LO) by 1 bit 1 1 0 1 1 0 0 1 LO[0] = 0 => NO addition

1 1 0 0
Shift Right (Sign, HI, LO) by 1 bit
1 1 1 1 0 0 1 1
1 1 0 0
Shift Right (Sign, Sum, LO) by 1 bit
1 1 1 0 0 1 1 0

Shift Right (Sign, Sum, LO) by 1 bit
0 0 0 0 1 1 0 0

2
1 1 0 0
0 0 0 0 1 1 0 1
Initialize (HI = 0, LO = Multiplier)
0
1

3
4
Multiplicand
Product = HI, LO
Sign
Iteration

1
1 1 0 0 1 1 0 1
LO[0] = 1 => ADD

1
1 0 1 1 0 0 1 1
LO[0] = 1 => ADD

0 1 0 0
0
0 0 0 1 1 0 0 1
LO[0] = 1 => SUB (ADD 2’s compl)
+

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Faster Multiplier
Suppose we want to multiply two numbers A and B
Example on 4-bit numbers: A = a3 a2 a1 a0 and B = b3 b2 b1 b0
Step 1: AND (multiply) each bit of A with each bit of B
Requires n2 AND gates and produces n2 product bits
Position of aibj = (i+j). For example, Position of a2b3 = 2+3 = 5
a0b0

a1b0

a2b0

a3b0

a0b1

a1b1

a2b1

a3b1

a0b2

a1b2

a2b2

a3b2

a0b3

a1b3

a2b3

a3b3

A × B

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Adding the Partial Products
Step 2: Add the partial products
The partial products are shifted and added to compute the product P
The partial products can be added in parallel
Different implementations are possible
4-bit Multiplicand A3 A2 A1 A0
4-bit Multiplier × B3 B2 B1 B0
A3B0 A2B0 A1B0 A0B0
A3B1 A2B1 A1B1 A0B1
A3B2 A2B2 A1B2 A0B2
A3B3 A2B3 A1B3 A0B3
P7 P6 P5 P4 P3 P2 P1 P0
8-bit Product
Partial Products are shifted
and added

Can be added
in parallel

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
4-bit × 4-bit Binary Multiplier

4-bit Adder

A3
0
A2
A1
A0
B0

A3
carry
A2
A1
A0
B1

4-bit Adder

A3
0
A2
A1
A0
B2

A3
A2
A1
A0
B3
4-bit Adder
carry
Half
Adder
carry
P0
P1
P4
P5
P2
P3
P6
P7

16 AND gates, Three 4-bit adders, a half-adder, and an OR gate

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Carry Save Adders
A n-bit carry-save adder produces two n-bit outputs
n-bit partial sum bits and n-bit carry bits
All the n bits of a carry-save adder work in parallel
The carry does not propagate as in a carry-propagate adder
This is why a carry-save is faster than a carry-propagate adder
Useful when adding multiple numbers (as in multipliers)
Carry-Propagate Adder
+

a0
b0

s0
+

a1
b1

s1
+

a31
b31

s31

. . .
cout
cin
Carry-Save Adder
. . .
+

a31
b31

s’31
c’31

c31

a1
b1

s’1
c’1

a0
b0

s’0
c’0

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Carry-Save Adders in a Multiplier
ADD the product bits vertically using Carry-Save adders
Full Adder adds three vertical bits
Half Adder adds two vertical bits
Each adder produces a partial sum and a carry
Use Carry-propagate adder for final addition

a0b0

a1b0

a2b0

a3b0

a0b1

a1b1

a2b1

a3b1

a0b2

a1b2

a2b2

a3b2

a0b3

a1b3

a2b3

a3b3

A × B

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Carry-Save Adders in a Multiplier
Step 1: Use carry save adders to add the partial products
Reduce the partial products to just two numbers
Step 2: Use carry-propagate adder to add last two numbers
P0
FA

a2b0 a1b1

HA
FA
FA

a3b0 a2b1

a0b0

a1b0 a0b1

HA
HA

FA
FA

a3b1 a2b2

a3b2

a2b3

a3b3

a1b3

a0b3

a1b2

a0b2

P1
P2
P3
P4
P5
P6
P7

Carry Save Adder

Carry Propagate Adder

Carry Save

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Summary of a Fast Multiplier
A fast n-bit × n-bit multiplier requires:
n2 AND gates to produce n2 product bits in parallel
Many adders to perform additions in parallel
Uses carry-save adders to reduce delays
Higher cost (more chip area) than sequential multiplier
Higher performance (faster) than sequential multiplier

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Morgan Kaufmann Publishers
15 March, 2017
Chapter 3 — Arithmetic for Computers
19

Next . . .
Unsigned Integer Multiplication
Signed Integer Multiplication
Faster Integer Multiplication
Integer Division
Integer Multiplication and Division in MIPS

= 19 Quotient
Divisor 10112 110110012 = 217 Dividend
-1011
10
101
1010
10100
-1011
1001
10011
-1011
10002 = 8 Remainder
Unsigned Division (Paper & Pencil)

Dividend =
Quotient × Divisor
+ Remainder
217 = 19 × 11 + 8
1
0
0
1
12

Check how big a number can be subtracted, creating a bit of the quotient on each attempt
Binary division is done via shifting and subtraction

Sequential Division
Uses two registers: HI and LO
Initialize: HI = Remainder = 0 and LO = Dividend
Shift (HI, LO) LEFT by 1 bit (also Shift Quotient LEFT)
Shift the remainder and dividend registers together LEFT
Has the same net effect of shifting the divisor RIGHT
Compute: Difference = Remainder – Divisor
If (Difference ≥ 0) then
Remainder = Difference
Set Least significant Bit of Quotient
Observation to Reduce Hardware:
LO register can be also used to store the computed Quotient

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Sequential Division Hardware
Initialize:
HI = 0, LO = Dividend
Results:
HI = Remainder
LO = Quotient

Start
Difference?
2. HI = Remainder = Difference
Set least significant bit of LO
32nd Repetition?
Done
< 0 ≥ 0 No Yes Shift (HI, LO) Left Difference = HI – Divisor shift left Divisor 32-bit ALU LO 32 bits write sub 32 bits Difference sign set lsb HI 32 bits Control Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#› Unsigned Integer Division Example Example: 11102 / 01002 (4-bit dividend & divisor) Result Quotient = 00112 and Remainder = 00102 4-bit registers for Remainder and Divisor (4-bit ALU) Diff < 0 => Do Nothing

2
0 0 0 0

1 1 1 0
Initialize
0
1
3
4
HI
Difference
LO
Iteration

0 1 0 0
Divisor

< 0 Shift Left, Diff = HI - Divisor 0 0 0 1 1 1 0 0 0 1 0 0 < 0 Shift Left, Diff = HI - Divisor 0 0 1 1 1 0 0 0 0 1 0 0 0 0 1 1 Shift Left, Diff = HI - Divisor 0 1 1 1 0 0 0 0 0 1 0 0 0 0 1 0 Shift Left, Diff = HI - Divisor 0 1 1 0 0 0 1 0 0 1 0 0 HI = Diff, set lsb of LO 0 0 0 1 0 0 1 1 HI = Diff, set lsb of LO 0 0 1 1 0 0 1 0 Diff < 0 => Do Nothing

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Signed Integer Division
Simplest way is to remember the signs
Convert the dividend and divisor to positive
Obtain the 2’s complement if they are negative
Do the unsigned division
Compute the signs of the quotient and remainder
Quotient sign = Dividend sign XOR Divisor sign
Remainder sign = Dividend sign
Negate the quotient and remainder if their sign is negative
Obtain the 2’s complement to convert them to negative

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Signed Integer Division Examples
Positive Dividend and Positive Divisor
Example: +17 / +3 Quotient = +5 Remainder = +2
Positive Dividend and Negative Divisor
Example: +17 / –3 Quotient = –5 Remainder = +2
Negative Dividend and Positive Divisor
Example: –17 / +3 Quotient = –5 Remainder = –2
Negative Dividend and Negative Divisor
Example: –17 / –3 Quotient = +5 Remainder = –2
The following equation must always hold:
Dividend = Quotient × Divisor + Remainder

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Integer Multiplication in MIPS
Multiply instructions
mult Rs, Rt Signed multiplication
multu Rs, Rt Unsigned multiplication
32-bit multiplication produces a 64-bit Product
Separate pair of 32-bit registers
HI = high-order 32-bit of product
LO = low-order 32-bit of product
MIPS also has a special mul instruction
mul Rd, Rs, Rt Rd = Rs × Rt
Copy LO into destination register Rd
Useful when the product is small (32 bits) and HI is not needed

Multiply
Divide
$0
HI
LO

$1
.
.
$31

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Integer Division in MIPS
Divide instructions
div Rs, Rt Signed division
divu Rs, Rt Unsigned division
Division produces quotient and remainder
Separate pair of 32-bit registers
HI = 32-bit remainder
LO = 32-bit quotient
If divisor is 0 then result is unpredictable
Moving data from HI, LO to MIPS registers
mfhi Rd (Rd = HI)
mflo Rd (Rd = LO)

Multiply
Divide
$0
HI
LO

$1
.
.
$31

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Integer Multiply and Divide Instructions
Instruction Meaning Format
mult Rs, Rt HI, LO = Rs ×s Rt Op = 0 Rs Rt 0 0 0x18
multu Rs, Rt HI, LO = Rs ×u Rt Op = 0 Rs Rt 0 0 0x19
mul Rd, Rs, Rt Rd = Rs ×s Rt 0x1c Rs Rt Rd 0 2
div Rs, Rt HI, LO = Rs /s Rt Op = 0 Rs Rt 0 0 0x1a
divu Rs, Rt HI, LO = Rs /u Rt Op = 0 Rs Rt 0 0 0x1b
mfhi Rd Rd = HI Op = 0 0 0 Rd 0 0x10
mflo Rd Rd = LO Op = 0 0 0 Rd 0 0x12
mthi Rs HI = Rs Op = 0 Rs 0 0 0 0x11
mtlo Rs LO = Rs Op = 0 Rs 0 0 0 0x13

×s = Signed multiplication, ×u = Unsigned multiplication
/s = Signed division, /u = Unsigned division
NO arithmetic exception can occur

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
String to Integer Conversion
Consider the conversion of string “91052” into an integer

How to convert the string into an integer?
Initialize: sum = 0
Load each character of the string into a register
Check if the character is in the range: ‘0’ to ‘9’
Convert the character into a digit in the range: 0 to 9
Compute: sum = sum * 10 + digit
Repeat until end of string or a non-digit character is encountered
To convert “91052”, initialize sum to 0 then …
sum = 9, then 91, then 910, then 9105, then 91052
‘9’
‘1’
‘0’
‘5’
‘2’

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
String to Integer Conversion Function
#———————————————————–
# str2int: Convert a string of digits into unsigned integer
# Input: $a0 = address of null terminated string
# Output: $v0 = unsigned integer value
#———————————————————–
str2int:
li $v0, 0 # Initialize: $v0 = sum = 0
li $t0, 10 # Initialize: $t0 = 10
L1: lb $t1, 0($a0) # load $t1 = str[i]
blt $t1, ‘0’, done # exit loop if ($t1 < '0') bgt $t1, '9', done # exit loop if ($t1 > ‘9’)
addiu $t1, $t1, -48 # Convert character to digit
mul $v0, $v0, $t0 # $v0 = sum * 10
addu $v0, $v0, $t1 # $v0 = sum * 10 + digit
addiu $a0, $a0, 1 # $a0 = address of next char
j L1 # loop back
done: jr $ra # return to caller

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Integer to String Conversion
Convert an unsigned 32-bit integer into a string
How to obtain the decimal digits of the number?
Divide the number by 10, Remainder = decimal digit (0 to 9)
Convert decimal digit into its ASCII representation (‘0’ to ‘9’)
Repeat the division until the quotient becomes zero
Digits are computed backwards from least to most significant
Example: convert 2037 to a string
Divide 2037/10 quotient = 203 remainder = 7 char = ‘7’
Divide 203/10 quotient = 20 remainder = 3 char = ‘3’
Divide 20/10 quotient = 2 remainder = 0 char = ‘0’
Divide 2/10 quotient = 0 remainder = 2 char = ‘2’

Integer Multiplication and Division COE 301 / ICS 233 Computer Organization – KFUPM © Muhamed Mudawar – slide ‹#›
Integer to String Conversion Function
#———————————————————-
# int2str: Converts an unsigned integer into a string
# Input: $a0 = value, $a1 = buffer address (12 bytes)
# Output: $v0 = address of converted string in buffer
#———————————————————-
int2str:
li $t0, 10 # $t0 = divisor = 10
addiu $v0, $a1, 11 # start at end of buffer
sb $zero, 0($v0) # store a NULL character
L2: divu $a0, $t0 # LO = value/10, HI = value%10
mflo $a0 # $a0 = value/10
mfhi $t1 # $t1 = value%10
addiu $t1, $t1, 48 # convert digit into ASCII
addiu $v0, $v0, -1 # point to previous byte
sb $t1, 0($v0) # store character in memory
bnez $a0, L2 # loop if value is not 0
jr $ra # return to caller

/docProps/thumbnail.jpeg

Related Posts