System and method for piecewise linear approximation

Patent metadata

Field	Value
Publication number	US-10466967-B2
Application number	US-201615224237-A
Country	US
Kind code	B2
Filing date	Jul 29, 2016
Priority date	Jul 29, 2016
Publication date	Nov 5, 2019
Grant date	Nov 5, 2019

Abstract

An apparatus includes one or more registers configured to store a vector of input values. The apparatus also includes a coefficient determination unit configured to, responsive to execution by a processor of a single instruction, select a plurality of piecewise analysis coefficients. The plurality of piecewise analysis coefficients includes one or more sets of piecewise analysis coefficients, and each set of piecewise analysis coefficients corresponds to an input value of the vector of input values. The apparatus further includes arithmetic logic circuitry configured to, responsive to the execution of at least the single instruction, determine estimated output values of a function based on the plurality of piecewise analysis coefficients and the vector of input values.

First claim

What is claimed is:

1. An apparatus comprising:
one or more registers configured to store a vector that includes a plurality of input values;
a coefficient determiner communicatively coupled to the one or more registers and configured to, responsive to execution by a processor of a single instruction, select a plurality of piecewise analysis coefficients based on a table storing a plurality of sets of piecewise analysis coefficients, the plurality of piecewise analysis coefficients corresponding to one or more of the plurality of sets of piecewise analysis coefficients, and each set of piecewise analysis coefficients corresponding to a respective one of the plurality of input values; and
arithmetic logic circuitry coupled to the coefficient determiner and configured to, responsive to execution of at least the single instruction, determine estimated output values of a function based on the plurality of piecewise analysis coefficients, a shift operation of at least one of the plurality of input values, and the vector.

2. The apparatus of claim 1 , further comprising a permutation network configured to, responsive to execution of the single instruction, generate a vector of piecewise analysis coefficients that includes the plurality of piecewise analysis coefficients.

3. The apparatus of claim 1 , wherein the coefficient determiner is further configured to retrieve the table from a memory, wherein the function includes a nonlinear function, and wherein the input values correspond to input values of the nonlinear function.

4. The apparatus of claim 1 , wherein the table includes a first portion that includes multiple sets of piecewise analysis coefficients and a second portion that includes one or more shift values.

5. The apparatus of claim 1 , wherein each set of the multiple sets of piecewise analysis coefficients includes at least one coefficient of a first type and at least one coefficient of a second type.

6. The apparatus of claim 1 , wherein the table includes a first section that includes multiple piecewise analysis coefficients of a first type and a second section that includes multiple piecewise analysis coefficients of a second type.

7. The apparatus of claim 1 , further comprising a permutation network configured to select the plurality of piecewise analysis coefficients.

8. The apparatus of claim 1 , wherein the arithmetic logic circuitry is further configured to multiply a particular input value of the vector with a first piecewise analysis coefficient of a particular set of piecewise analysis coefficients of the one or more sets of piecewise analysis coefficients to generate a product.

9. The apparatus of claim 8 , wherein the arithmetic logic circuitry is further configured to generate a sum based on the product and a second piecewise analysis coefficient of the particular set of piecewise analysis coefficients, and wherein the sum corresponds to a first estimated output value of the estimated output values.

10. The apparatus of claim 1 , wherein the one or more registers include:
a first register configured to store the vector;
a second register configured to store multiple sets of piecewise analysis coefficients; and
a third register configured to store an index value vector, the index value vector generated based on the vector and one or more shift values.

11. The apparatus of claim 1 , wherein the one or more registers include a register configured to store a vector of piecewise analysis coefficients that includes the plurality of piecewise analysis coefficients and another register configured to store the estimated output values, and further comprising a permutation network configured to route, based on an index value vector, one or more sets of piecewise analysis coefficients to the register to generate the vector of piecewise analysis coefficients.

12. A method of estimating values, the method comprising:
receiving a vector of input values;
executing, at a processor of an electronic device, a single instruction to select a plurality of piecewise analysis coefficients, the plurality of piecewise analysis coefficients corresponding to one or more sets of piecewise analysis coefficients, each set of piecewise analysis coefficients corresponding to an input value of the vector of input values; and
determining, at the electronic device, estimated output values of a function based on the plurality of piecewise analysis coefficients, a shift operation of at least one of the input values, and the vector of input values.

13. The method of claim 12 , further comprising determining a shift value and generating a vector of piecewise analysis coefficients that includes the plurality of piecewise analysis coefficients based on the shift value, wherein generating the vector of piecewise analysis coefficients comprises, for each input value of the vector of input values, selecting a set of piecewise analysis coefficients from a table based on the input value, and wherein the table includes multiple sets of piecewise analysis coefficients.

14. The method of claim 12 , wherein executing the single instruction comprises:
performing a lookup to a table of piecewise analysis coefficients based on a plurality of bits corresponding to an input value of the vector of input values; and
determining, based on the lookup, a first set of piecewise analysis coefficients corresponding to the input value.

15. The method of claim 12 , wherein executing the single instruction further comprises generating a plurality of bits based on one of the input values and based on a shift value.

16. The method of claim 12 , further comprising selecting a table from a plurality of tables based on the function.

17. The method of claim 12 , further comprising performing a lookup to a table of piecewise analysis coefficients, wherein the table includes multiple groups of piecewise analysis coefficients, and wherein piecewise analysis coefficients of at least two groups of the multiple groups of piecewise analysis coefficients are the same.

18. The method of claim 12 , wherein:
one or more of the input values is associated with a shift value, and
the plurality of piecewise analysis coefficients corresponds to linear analysis coefficients.

19. The method of claim 12 , wherein the plurality of piecewise analysis coefficients includes multiple sets of piecewise analysis coefficients, and wherein each set of piecewise analysis coefficients in the multiple sets of piecewise analysis coefficients includes two piecewise analysis coefficients.

20. The method of claim 12 , wherein the function includes a nonlinear function, and wherein the vector of input values corresponds to input values of the nonlinear function.

21. The method of claim 12 , wherein the estimated output values are determined by executing a second single instruction, and wherein executing the second single instruction comprises:
generating a product of a first piecewise analysis coefficient of the plurality of piecewise analysis coefficients and an input value of the vector of input values; and
generating a first estimated output value based on a sum of the product and a second piecewise analysis coefficient of the plurality of piecewise analysis coefficients.

22. The method of claim 12 , wherein executing the single instruction further includes determining the estimated output values.

23. The method of claim 12 , further comprising:
calculating a shift value based on the vector of input values and a target range; an

Assignees

• Qualcomm Inc

Inventors

• Mathew Deepak
• Ingle Ajay Anant
• Sun Yurong
• Zhu Jianming
• Hoffman Marc

Classifications

• G06F9/3001

  Arithmetic instructions · CPC title

• G06F9/3004

  to perform operations on memory · CPC title

• G06F17/17 Primary

  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 title

• G06F1/03

  working, at least partly, by table look-up (G06F1/025 takes precedence) · CPC title

• G06F7/548

  Trigonometric functions; Co-ordinate transformations · CPC title