Method and apparatus for achieving higher frequencies of exactly rounded results

• US 6,134,574 A
• Filed: 05/08/1998
• Issued: 10/17/2000
• Est. Priority Date: 05/08/1998
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Juffa, Norbert, Oberman, Stuart F., Weber, Fred
• Primary Examiner(s): Malzahn, David H.
• Application Number:
  US09/075,073
• Time in Patent Office: 893 Days
• Field of Search: 708/551, 708/497, 708/605, 708/606, 708/654
• US Class Current: 708/551
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 2207/3828 Multigauge devices, i.e. capable of handling packed numbers without unpacking them
• CPC Class Codes: G06F 7/4991 Overflow or underflow
• CPC Class Codes: G06F 7/49936 Normalisation mentioned as feature only
• CPC Class Codes: G06F 7/49963 Rounding to nearest G06F7/49957 takes precedence
• CPC Class Codes: G06F 7/49994 Sign extension
• CPC Class Codes: G06F 7/53 in parallel-parallel fashion, i.e. both operands being entered in parallel G06F7/533 takes precedence
• CPC Class Codes: G06F 7/5338 each bitgroup having two new bits, e.g. 2nd order MBA
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00
• CPC Class Codes: G06F 9/30036 Instructions to perform operations on packed data, e.g. vector, tile or matrix operations
• CPC Class Codes: G06F 9/3017 Runtime instruction translation, e.g. macros
• CPC Class Codes: G06F 9/3804 for branches, e.g. hedging, branch folding
• CPC Class Codes: G06F 9/3885 using a plurality of independent parallel functional units

Abstract

A multiplier configured to obtain higher frequencies of exactly rounded results by adding an adjustment constant to intermediate products generated during iterative multiplication operations is disclosed. One such iterative multiplication operation is the Newton-Raphson iteration, which may be utilized by the multiplier to perform reciprocal calculations and reciprocal square root calculations. For each iteration, the results converge toward an infinitely precise result. To improve the frequency of the exactly rounded result, the results of the iterative calculations may be studied for a large number of differing input operands to determine the best suited value for the adjustment constant. The multiplier may also be configured to perform scalar and packed vector multiplication using the same hardware.

Claims

1. A method for increasing the frequency of exactly rounded results when performing an iterative calculation in a microprocessor comprising:

receiving an operand;

determining an initial estimate of the result of said iterative calculation using said operand;

multiplying said initial estimate and said operand to generate an intermediate result;

repeating said multiplying a predetermined number of times, wherein said intermediate result is used in place of said initial estimate, wherein the final repetition generates a final result; and

adding an adjustment constant to said final result, wherein said adjustment constant increases the probability that said final result will equal the exactly rounded result of said iterative calculation.

2. The method as recited in claim 1, wherein said multiplying further comprising adding the adjustment constant to said intermediate result.

3. The method as recited in claim 1, wherein said multiplying further comprises rounding and normalizing said intermediate result.

4. The method as recited in claim 3, wherein said determining comprises reading a plurality of values from a read-only memory using said operand as an index and arithmetically manipulating said values to form said initial estimate.

5. The method as recited in claim 4, wherein said adjustment constant is determined by performing said iterative calculation for a plurality of operand values to generate a plurality of final results, and selecting a constant that, when added to each of said plurality of final results, forces a higher percentage of said plurality of final results to equal their corresponding exactly rounded results.

6. A method for increasing the probability of exactly rounded results when using a multiplier to evaluate a constant power of an operand comprising:

determining an initial estimate of the operand raised to a first constant power;

performing an iteration comprising;

multiplying the operand and the initial estimate in the multiplier to form a product;

adding an adjustment constant to said product;

calculating an intermediate approximation by inverting one or more bits from said product;

rounding said intermediate approximation;

normalizing said intermediate approximation; and

repeating said iteration, wherein said intermediate approximation is used in place of said initial estimate.

7. The method as recited in claim 6, wherein said multiplying and said adding is performed by summing a plurality of partial products and the adjustment constant in an adder tree.

8. The method as recited in claim 6, wherein said iteration comprises a Newton-Raphson iteration.

9. The method as recited in claim 6, wherein said adjustment constant varies with said product.

10. The method as recited in claim 6, wherein said adjustment constant comprises a value selected from a plurality of values, wherein said value is selected during each iteration based upon the type of iteration being performed.

11. An execution unit configured to evaluate a constant power of an operand comprising:

an initial estimate generator configured to receive an operand and output an initial estimate of said operand raised to a particular constant power; and

a multiplier coupled to receive said operand and said initial estimate, wherein said multiplier is configured to calculate a product of said initial estimate and said operand, wherein said multiplier is further configured to conditionally add an adjustment constant to said product to form an adjusted product, wherein said

multiplier is further configured to round and normalize said adjusted product, wherein said adjustment constant is selected to increase the probability that said adjusted product equals an exactly rounded product.

12. The execution unit as recited in claim 11, wherein said multiplier comprises a partial product array adder configured to sum said adjustment constant and a plurality of partial products, wherein said plurality of partial products are a function of said operand and said initial estimate.

13. The execution unit as recited by claim 11, wherein said multiplier comprises a partial product array adder configured to conditionally sum said adjustment constant and a plurality of partial products, wherein said plurality of partial products are a function of said operand and said initial estimate, wherein said multiplier further comprises a control unit coupled to said partial product array adder, wherein said partial product array adder is configured to sum said adjustment constant only in response to a control signal from said control unit.

14. The execution unit as recited in claim 13, wherein said control unit is configured to assert said control signal only on final multiplication cycles of iterative multiplication operations.

15. A multiplier comprising:

a partial product generator coupled to receive a multiplicand input and configured to generate one or more partial products based upon said multiplicand operand;

selection logic coupled to said partial product generator and configured to receive a multiplier operand, wherein said selection logic is configured to select a plurality of partial products based upon said multiplier operand; and

a partial product array adder coupled to said selection logic, wherein said adder is configured to receive and sum a number of said partial products and an adjustment constant to form a product, wherein said adjustment constant is selected to increase the frequency that said product is exactly rounded.

16. The multiplier as recited in claim 15, further comprising:

a first plurality of inverters coupled to receive, invert, and normalize selected bits from said product to form a first approximation, wherein said first approximation assumes an overflow has occurred in said multiplier;

a second plurality of inverters coupled to receive, invert, and normalize selected bits from said product to form a second approximation, wherein said second approximation assumes an overflow has not occurred in said multiplier; and

a multiplexer configured to select either said first or second approximations.

17. The multiplier as recited in claim 16, further comprising a control unit coupled to said partial product array adder, wherein said control unit is configured to prevent said adjustment constant from being summed unless a final step of an iterative calculation is being performed.

18. The multiplier as recited in claim 17, wherein said control unit is configured to select said adjustment constant from a plurality of values, wherein each value corresponds to a particular type of iterative calculation.

19. The multiplier as recited in claim 17, wherein said adjustment constant is predetermined and hard-wired into said control unit.

20. A microprocessor comprising:

an instruction cache;

a load/store unit coupled to said instruction cache; and

an execution unit coupled to receive and execute instructions from said instruction cache, wherein said execution unit is configured to evaluate a constant power of an operand, wherein said execution unit comprises;

an initial estimate generator configured to receive an operand and output an initial estimate of said operand raised to a particular constant power; and

a multiplier coupled to receive said operand and said initial estimate, wherein said multiplier is configured to calculate a product of said initial estimate and said operand, wherein said multiplier is further configured to conditionally add an adjustment constant to said product to form an adjusted product, wherein said multiplier is further configured to round and normalize said adjusted product, wherein said adjustment constant is selected to increase the probability that said adjusted product equals an exactly rounded product.