Methods for implementing arithmetic functions with user-defined input and output formats

• US 9,811,503 B1
• Filed: 01/28/2015
• Issued: 11/07/2017
• Est. Priority Date: 01/28/2015
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Pasca, Bogdan
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US14/608,113
• Time in Patent Office: 1,014 Days
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G06F 7/00 Methods or arrangements for processing data by operating upon the order or content of the data handled logic circuits H03K19/00

Abstract

Methods for implementing fixed-point functions with user-defined input/output ranges and formats on a programmable integrated circuit are provided. A particular function may include one or more input intrusion intervals where generic fixed-point approximation methods are not sufficiently precise. Output values for these intrusion intervals may be pre-computed during function generation time using a mathematical library running on a computer-aided design tool and stored in a lookup table. During normal operation of the integrated circuit, a multiplexing network may be used to select among values generated by generic approximation methods and values obtained from one or more lookup tables depending on the current input to the function.

Claims

1. Circuitry configured to implement a function, comprising:

a generic approximation circuit that generates output values for the function;

memory for storing a table of pre-computed output values for the function, wherein the function comprises a fixed-point arithmetic function having an input range, and wherein the pre-computed output values in the table correspond to input values within the input range for which the generic approximation circuit is incapable of generating sufficiently accurate output values; and

a multiplexing circuit that receives the output values from the generic approximation circuit, that receives the pre-computed output values in the table, and that is configured to route output values from a selected one of the generic approximation circuit and the table to a multiplexer output.

2. The circuitry defined in claim 1, wherein the generic approximation circuit comprises an approximation circuit selected from the group consisting of:

a Newton-Raphson approximation circuit and a Taylor polynomial approximation circuit.

3. The circuitry defined in claim 2, further comprising:

an additional generic approximation circuit that generates output values for the function, wherein the multiplexing circuit also receives the output values from the additional generic approximation circuit.

4. The circuitry defined in claim 1, wherein the pre-computed output values in the table correspond to input values within an intrusion interval in the input range.

5. The circuitry defined in claim 1, further comprising:

additional memory that stores another table of pre-computed output values for the function, wherein the multiplexing circuit also receives the pre-computed output values from the another table.

6. The circuitry defined in claim 1, further comprising:

an index offsetting circuit that receives an input to the function and that outputs a corresponding signal for addressing the table.

7. The circuitry defined in claim 1, further comprising:

an address encoding circuit that receives an input to the function and that generates a corresponding control signal that configures the multiplexing circuit.

8. A method for operating computing circuitry to implement a function, the method comprising:

using a generic approximation circuit to generate output values for the function;

using memory to store a table of pre-computed output values for the function;

with a multiplexing circuit, receiving the output values from the generic approximation circuit and the pre-computed output values in the table and providing output values selected from one of the generic approximation circuit and the table; and

with an address encoder, receiving an input to the function and outputting a control signal to the multiplexing circuit.

9. The method defined in claim 8, wherein the computing circuitry is configured to implement a fixed-point function having a user-defined input range.

10. The method defined in claim 9, wherein using the memory to store the table of pre-computed output values comprises storing output values corresponding to input values within an intrusion interval in the input range.

11. The method defined in claim 10, further comprising:

with an index offsetting circuit, receiving an input to the function and outputting a corresponding signal for addressing the table in the memory.

12. The method defined in claim 11, wherein outputting the corresponding signal for addressing the table comprises computing a difference between the input and a lower bound of the intrusion interval.

13. The method defined in claim 8, wherein using the generic approximation circuit to generate output values for the function comprises using the generic approximation circuit to implement a selected one of:

a Newton-Raphson approximation method, a Taylor polynomial approximation method, a least-square polynomial approximation method, and a Chebychev polynomial approximation method.

14. A method for using design tools running on computing equipment to implement a function on an integrated circuit, the method comprising:

with the design tools running on the computing equipment, receiving an input range for the function;

with the design tools running on the computing equipment, identifying a generic approximation method that is used to generate output values for the function in a portion of the input range; and

with the design tools running on the computing equipment, determining whether the input range includes an intrusion interval for which the generic approximation method exhibits insufficient accuracy.

15. The method defined in claim 14, further comprising:

generating a table of pre-computed output values for the intrusion interval.

16. The method defined in claim 15, further comprising:

identifying an additional generic approximation method that is different than the generic approximation method and that is used to generate output values for the function in another portion of the input range.

17. The method defined in claim 15, further comprising:

identifying an additional intrusion interval that is different than the intrusion interval; and

generating another table of pre-computed output values for the additional intrusion interval.

18. The method defined in claim 15, further comprising:

configuring a multiplexing network to route output signals obtained from a selected one of the generic approximation method and the table to a multiplexer output.

19. The method defined in claim 14, further comprising:

receiving an output range for the function; and

receiving input and output number formats for the function.