Back to results
US 11,886,505 B2Granted
Function approximation
AssigneeGraphcore Limited
InventorsJonathan Mangnall, Stephen Felix
Life of this patent
Estimating the term…
Abstract
A function approximation system is disclosed for determining output floating point values of functions calculated using floating point numbers. Complex functions have different shapes in different subsets of their input domain, making them difficult to predict for different values of the input variable. The function approximation system comprises an execution unit configured to determine corresponding values of a given function given a floating point input to the function; a plurality of look up tables for each function type; a correction table of values which determines if corrections to the output value are required; and a table selector for finding an appropriate table for a given function.
Claims19
An execution unit configured to evaluate a function, the execution unit comprising:
- a plurality of look up tables, each of the lookup tables associated with a corresponding range of input values of a first plurality of ranges of input values, each look up table comprising a plurality of entries, each of the entries comprising a function value at a corresponding input value within a respective range of input values, wherein the input values include floating point numbers;
- a correction table comprising a plurality of correction values fewer than a quantity of the entries of the look up tables;
- a table selector configured to determine a first range of input values, within the first plurality of ranges, in which a first input value falls and further configured to select a first look up table associated with the first range of input values from the plurality of look up tables;
- and
- an input buffer to receive the first input value, wherein the first input value includes an input exponent and an input mantissa;
- wherein the execution unit is configured to search the first look up table, selected by the table selector, using the first input value to select at least one entry from the first look up table and determine therefrom an output floating point number for the first input value, and to search the correction table using at least part of the first input value to determine a correction value for first input value,
- wherein the execution unit is configured to determine the correction value by selecting either a first value stored in the correction table or a default value, and to apply the correction value to the output floating point number from the first look up table to determine a value of the function;
- wherein the execution unit is further configured to use an approximation function on a second input value that is outside of the first plurality of ranges of input values;
- and
- wherein using the first look up table to determine the output floating point number comprises using at least part of the input mantissa as an index to search the first look up table, the execution unit further comprising interpolation circuitry and configured to:
- search the first look up table using the first input value to select the at least one entry from the first look up table;
- and
- perform interpolation in dependence upon the at least one entry to determine the output floating point number.
10 more elements
A method for operating an execution unit of a processor to evaluate a function, the method comprising:
- determining, by a table selector, a particular range of a first set of one or more input ranges in which a first input value falls;
- selecting, by the table selector, a first look up table for the particular range from a plurality of look up tables associated with the first set of one or more input ranges, each look up table of the plurality of look up tables storing a plurality of entries, each of the entries comprising a respective function value, wherein a spacing between entries of the plurality of entries in each look up table is fixed, wherein the spacing varies in different look up tables in a manner which is inversely correlated with curvature of the function in a given input range for a respective look up table;
- receiving into an input buffer of the execution unit the first input value, the first input value including a floating point number comprising an input exponent and an input mantissa;
- using the first look up table to determine an output floating point number for the first input value;
- providing the output floating number for correction;
- determining, by the execution unit, a correction value for the first input value by searching a correction table using at least part of the first input value and selecting as the correction value either a first value from the correction table or a default value;
- and
- applying, by the execution unit, the correction value to the output floating point number to evaluate the function;
- wherein using the first look up table to determine the output floating point number comprises using at least part of the input mantissa as an index to search the first look up table, the execution unit further comprising interpolation circuitry and configured to:
- search the first look up table using the first input value to select the at least one entry from the first look up table;
- and
- perform interpolation in dependence upon the at least one entry to determine the output floating point number.
9 more elements
A non-transitory computer readable medium storing a computer program instruction which when executed causes a method for evaluating a function to be carried out by an execution unit which executes the instruction, the method comprising:
- receiving, at an input buffer, an input floating point number comprising an input exponent and an input mantissa;
- determining, by the execution unit, that the input floating point number falls within a first set of one or more input ranges;
- determining, by a table selector, a first input range in which the input floating point number falls in the first set of input ranges and selecting, by the table selector, a first look up table for the first input range from a plurality of look up tables, each associated with a respective range within the first set of one or more input ranges, each look up table comprising a plurality of entries, each of the entries comprising a corresponding function value at a corresponding input value,
- using the first look up table to determine an output floating point number for the input floating point number,
- searching, by the execution unit, a correction table using at least part of the input floating point number to determine a correction value for that input floating unit number, the correction table comprising a plurality of correction values fewer than a quantity of the entries of the lookup tables, wherein the execution unit is configured to determine the correction value by selecting either a first value stored in the correction table or a default value;
- applying, by the execution unit, the correction value to the output floating point number to evaluate the function;
- determining, by the execution unit, that a second input floating point number falls in a second set of input ranges;
- and
- supplying the second input floating point number to the execution unit, which is further configured to evaluate the function using approximation;
- wherein using the first look up table to determine the output floating point number comprises using at least part of the input mantissa as an index to search the first look up table, the execution unit further comprising interpolation circuitry and configured to:
- search the first look up table using the first input value to select the at least one entry from the first look up table;
- and
- perform interpolation in dependence upon the at least one entry to determine the output floating point number.
10 more elements
Dependencies are inferred from the claim text.