Methods and apparatus for fast argument reduction in a computing system

• US 7,366,748 B1
• Filed: 06/30/2000
• Issued: 04/29/2008
• Est. Priority Date: 06/30/2000
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Intel Corporation
• Inventors: Tang, Ping Tak Peter, Kubaska, Theodore, Harrison, John
• Primary Examiner(s): Do; Chat C.
• Application Number:
  US09/609,496
• Time in Patent Office: 2,860 Days
• Field of Search: 708/501, 708/270, 708/495, 708/277, 708/502, 708/650, 708/200, 708/446, 345/420
• US Class Current: 708/446
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence

Abstract

There is disclosed method, software and apparatus for evaluating a function f in a computing device using a reduction, core approximation and final reconstruction stage. According to one embodiment of the invention, an argument reduction stage uses an approximate reciprocal table in the computing device. According to another embodiment, an approximate reciprocal instruction I is operative on the computing device to use the approximate reciprocal table such that the argument reduction stage provides that—C:=I(X) and R:=X×C−1, the core approximation stage provides that p(R) is computed so that it approximates f(1+R), and the final reconstruction stage provides that T=f(1/C) is fetched and calculated if necessary, and f(X) is reconstructed based on f(X)=f([1/C]×[X×C])=g(f(1/C), f(1+R)).

Claims

1. An apparatus to evaluate an algebraic or transcendental function and make available a result of such evaluation for a scientific computational purpose, the apparatus comprising:

a processor interfacing with at least one peripheral device;

an argument reduction unit having a hardware approximate reciprocal table located within the processor, the argument reduction unit to read an approximate reciprocal instruction to use the hardware approximate reciprocal table, and the argument reduction unit to perform an argument reduction stage within a reduction period less than 20% of an overall calculation period of the function;

a core approximation unit to perform a core approximation stage that includes approximating a polynomial; and

a final reconstruction unit to obtain a value of the function, wherein the value is based on the argument reduction stage and the core approximation stage, and wherein the value of the function is interfaced to the at least one peripheral device for the scientific computational purpose.

2. An apparatus according to claim 1 further wherein the final reconstruction unit is operative to compute in parallel with the argument reduction and core approximation units.

3. A method to evaluate an algebraic or transcendental function and make available a result of such evaluation for a scientific computational purpose comprising:

calculating a value of the function on a computer system that comprises at least one processor and at least one peripheral device, wherein the calculating is performed by the processor in an overall calculation period, and wherein the calculating includes,

performing an argument reduction stage, wherein the argument reduction stage includes using an approximate reciprocal instruction, and wherein the argument reduction stage is performed in a reduction period that is less than 20% of the overall calculation period;

performing a core approximation stage, wherein the core approximation stage includes approximating a polynomial; and

performing, based on the argument reduction stage and the core approximation stage, a final reconstruction stage to obtain the value of the function; and

interfacing the value of the function to the at least one peripheral device for the scientific computational purpose.

4. The method of claim 3, wherein the obtaining the value in the final reconstruction stage occurs in parallel with generating a reduced argument in the argument reduction stage and approximating the polynomial in the core the approximation stage.

5. A computer system to evaluate an algebraic or transcendental function and make available a result of such evaluation for a scientific computational purpose, the computer system comprising:

a motherboard interfacing with one or more peripheral devices;

a processor mounted on the motherboard, the processor including an approximate reciprocal table hardware unit; and

a computer program configured to operate on the processor to perform a multi-stage computation of a function f including an argument reduction stage that uses the reciprocal table hardware unit, wherein the argument reduction stage computes an argument reduction R such that C;

=I(X) and R;

=X×

C−

1, wherein computing each of C;

=I(X) and R;

=X×

C−

1 is done within a latency of five cycles one processor, wherein the argument reduction stage is performed within a reduction period less than 20% of an overall calculation period of the function;

wherein I is an approximate reciprocal instruction on the processor, and wherein a result of the computation is interfaced to the one or more peripheral devices for the scientific computational purpose.

6. The computer system of claim 5, wherein the multi-stage computation of the function f further includes a core approximation stage and a final reconstruction stage.

7. The computer system of claim 5, wherein the function f is in a class of functions that exhibit a i) multiplicative property such that f(U×

V)=g(f(U),f(V)), and ii) simple mapping of 2^N such that f(2^N) is calculated, where N is an integer.

8. The computer system of claim 7, wherein g is addition for a logarithm function, and g is multiplication of cube root or inverse square root.

9. The computer system of claim 7, wherein the function f is a logarithm function, and wherein f(2^N) is calculated based on N and constant log(2).

10. The computer system of claim 7, wherein function f is a cube root function, and wherein f(2^J) for J=0, 1, 2 need only be tabulated.

11. A tangible machine readable medium including instructions which, when executed by a machine coupled to at least one peripheral device, cause the machine to perform operations to evaluate an algebraic or transcendental function and make available a result of such evaluation for a scientific computational purpose, the operations comprising:

calculating a value of the function, wherein the calculating is performed in an overall calculation period, and wherein the calculating includes,

performing an argument reduction stage, wherein the argument reduction stage includes using an approximate reciprocal instruction, and wherein the argument reduction stage is performed in a reduction period that is less than 20% of the overall calculation period;

performing a core approximation stage, wherein the core approximation stage includes approximating a polynomial; and

performing, based on the argument reduction stage and the core approximation stage, a final reconstruction stage to obtain the value of the function; and

interfacing the value of the function to the least one peripheral device for the scientific computational purpose.

12. The tangible machine readable medium of claim 11, wherein the obtaining the value in the final reconstruction stage occurs in parallel with generating a reduced argument in the argument reduction stage and approximating the polynomial in the core approximation stage.