Computing floating-point polynomials in an integrated circuit device

• US 9,053,045 B1
• Filed: 03/08/2013
• Issued: 06/09/2015
• Est. Priority Date: 09/16/2011
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin, Pasca, Bogdan
• Primary Examiner(s): Yaary, Michael D
• Application Number:
  US13/789,882
• Time in Patent Office: 823 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 2207/5523 Calculates a power, e.g. the square, of a number or a function, e.g. polynomials
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence
• CPC Class Codes: G06F 7/548 Trigonometric functions; Co-ordinate transformations
• CPC Class Codes: G06F 7/552 Powers or roots , e.g. Pythagorean sums

Abstract

Polynomial circuitry for calculating a polynomial having terms including powers of an input variable, where the input variable is represented by a mantissa and an exponent, includes at least one respective coefficient table for each respective term, each respective coefficient table being loaded with a plurality of respective instances of a coefficient for said respective term, each respective instance being shifted by a different number of bits. The circuitry also includes decoder circuitry for selecting one of the respective instances of the coefficient for each respective term based on the exponent and on a range, from among a plurality of ranges, of values into which that input variable falls.

Claims

1. Polynomial circuitry for calculating a polynomial having terms including powers of an input variable, said input variable represented by a mantissa and an exponent, said circuitry comprising:

at least one respective coefficient table corresponding to a respective one of said terms of said polynomial;

wherein;

for each respective one of said terms of said polynomial, each respective coefficient table is loaded with a plurality of respective instances of a respective coefficient for said respective one of said terms of said polynomial, and

respective instances of said respective coefficient for said respective one of said terms of said polynomial are multiple versions of said respective coefficient, each version being shifted by a different number of bits; and

respective decoder circuitry associated with each respective one of said coefficient tables, said respective decoder circuitry selecting one of said instances of said respective coefficient for said respective one of said terms of said polynomial based on said exponent and on a range, from among a plurality of ranges, of input values into which said input variable falls.

2. The polynomial circuitry of claim 1 wherein said range of input values is determined solely by said exponent.

3. The polynomial circuitry of claim 1 wherein:

each said at least one respective coefficient table for said respective one of said terms of said polynomial comprises a plurality of sets of coefficient values for each said respective term; and

each of said sets of coefficient values applies to a respective one of said ranges.

4. The polynomial circuitry of claim 3 wherein:

each said at least one respective coefficient table for said respective one of said terms of said polynomial comprises a separate table for each of said sets of coefficient values; and

each of said separate tables is stored in a separate memory.

5. The polynomial circuitry of claim 3 wherein:

each said at least one respective coefficient table for said respective one of said terms of said polynomial comprises a separate table for each of said sets of coefficient values; and

all of said separate tables are stored in a single memory.

6. The polynomial circuitry of claim 3 wherein, for one of said respective terms, at least one coefficient value for said one of said respective terms of said polynomial in one of said sets of coefficient values is identical to a coefficient value for said one of said respective terms of said polynomial in another of said sets of coefficient values.

7. The polynomial circuitry of claim 6 wherein each of said sets of coefficient values is stored separately in a single memory.

8. The polynomial circuitry of claim 6 wherein:

said sets of coefficient values are interleaved in said single memory, said single memory containing a respective interleaved table for each respective one of said terms of said polynomial; and

said decoder circuitry selects an appropriate coefficient for each respective term from each respective interleaved table.

9. The polynomial circuitry of claim 3 comprising:

a respective coefficient memory for a respective one of said terms of said polynomial;

wherein;

all respective coefficient values from all of said sets of coefficient values for said one of said respective terms of said polynomial are stored in said respective coefficient memory.

10. The polynomial circuitry of claim 9 wherein each respective set of coefficient values for said one of said respective terms is stored in a separate respective coefficient table that is stored in said respective coefficient memory for said one of said respective terms.

11. The polynomial circuitry of claim 9 wherein:

said respective sets of coefficient values are interleaved in a single interleaved table in said respective coefficient memory; and

said decoder circuitry selects an appropriate coefficient for said respective one of said terms of said polynomial from said interleaved table.

12. A method of configuring a programmable device as circuitry calculating a polynomial having terms including powers of an input variable, said input variable represented by a mantissa and an exponent, said method comprising:

configuring, on said programmable device;

at least one respective coefficient table corresponding to a respective one of said terms of said polynomial;

wherein;

for each respective one of said terms of said polynomial, each respective coefficient table is loaded with a plurality of respective instances of a respective coefficient for said respective one of said terms of said polynomial, and

respective instances of said coefficient for said respective one of said terms of said polynomial are multiple versions of said respective coefficient, each version being shifted by a different number of bits; and

respective decoder circuitry associated with each respective one of said coefficient tables, said respective decoder circuitry selecting one of said respective instances of said coefficient for said respective one of said terms of said polynomial based on said exponent and on a range, from among a plurality of ranges, of input values into which said input variable falls.

13. The method of claim 12 wherein said range of input values is determined solely by said exponent.

14. The method of claim 12 wherein:

each said at least one respective coefficient table for each said respective one of said terms of said polynomial comprises a plurality of sets of coefficient values for each said respective one of said terms of said polynomial; and

each of said sets of coefficient values applies to a respective one of said ranges.

15. The method of claim 14 wherein:

each said at least one respective coefficient table for each said respective one of said terms of said polynomial comprises a separate table for each of said sets of coefficient values;

said method comprising;

configuring a separate memory on said programmable device for each of said coefficient tables.

16. The method of claim 14 wherein:

each said at least one respective coefficient table for each said respective term comprises a separate table for each of said sets of coefficient values;

said method comprising;

configuring a single memory on said programmable device for all of said coefficient tables.

17. The method of claim 16 wherein, for one of said respective terms of said polynomial, at least one coefficient value for said one of said respective terms of said polynomial in one of said sets of coefficient values is identical to a coefficient value for said one of said respective terms of said polynomial in another of said sets of coefficient values.

18. The method of claim 17 wherein:

each of said sets of coefficient values is stored separately in said single memory; and

said sets of coefficient values are interleaved in said single memory, said single memory containing a respective interleaved table for each respective one of said terms of said polynomial;

said method further comprising;

configuring said decoder circuitry to select an appropriate coefficient for each respective one of said terms of said polynomial from each respective interleaved table.

19. The method of claim 17 comprising:

configuring a respective coefficient memory for each one of said respective terms of said polynomial, for storing all respective coefficient values from all of said sets of coefficient values for said one of said respective terms of said polynomial in said respective coefficient memory.

20. The method of claim 19 comprising configuring said respective coefficient memory to store each respective set of coefficient values for said one of said respective terms of said polynomial in a separate respective coefficient table.

21. The method of claim 19 comprising:

configuring said respective coefficient memory to store said respective coefficient values for said one of said respective terms of said polynomial in a single interleaved table in said respective coefficient memory; and

configuring said decoder circuitry to select an appropriate coefficient for said respective one of said terms of said polynomial from said interleaved table.

22. A non-transitory machine-readable data storage medium encoded with non-transitory machine-executable instructions for configuring a programmable device as circuitry for calculating a polynomial having terms including powers of an input variable, said input variable represented by a mantissa and an exponent, said instructions comprising:

instructions to configure at least one respective coefficient table corresponding to a respective one of said terms of said polynomial, wherein;

for each respective one of said terms of said polynomial, each respective coefficient table is loaded with a plurality of respective instances of a respective coefficient for said respective one of said terms of said polynomial, and

respective instances of said coefficient for said respective one of said terms of said polynomial are multiple versions of said respective coefficient, each version being shifted by a different number of bits; and

instructions to configure respective decoder circuitry associated with each respective one of said coefficient tables, said respective decoder circuitry selecting one of said instances of said respective coefficient for said respective one of said terms of said polynomial based on said exponent and on a range, from among a plurality of ranges, of values into which said input variable falls.