Computing device performance of low precision arithmetic functions with arrays of pre-calculated values

• US 10,564,930 B2
• Filed: 04/09/2018
• Issued: 02/18/2020
• Est. Priority Date: 04/09/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Kulkarni, Saurabh Mohan, Tremblay, Marc
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US15/949,048
• Publication Number:
  US 20190310826A1
• Time in Patent Office: 680 Days
• Field of Search: None
• CPC Class Codes: G06F 7/38 Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation
• CPC Class Codes: G06F 7/544 for evaluating functions by calculation G06F7/4824 takes precedence

Abstract

Reduced precision computer number formats inherently limit the quantity of discrete numeric values that can be represented. Therefore, the solution values of an arithmetic function, for each numeric value that is individually and uniquely expressible utilizing such a reduced precision computer number format, can be precomputed since the quantity of unique solution values can be limited to a quantity that can be conveniently stored, such as in an array. Subsequently, rather than computing the solution value of such an arithmetic function, for a given input value, the precomputed array can be referenced and a solution value corresponding to the given input value can be read from the array. Reading numeric values from an array can be substantially faster than computing solution values of a computationally-expensive arithmetic function.

Claims

1. A method of improving computing device performance of arithmetic functions comprising:

generating, for a first set of numeric input values, a first set of numeric solution values, wherein each numeric solution value, in the first set of numeric solution values, is a solution to a first arithmetic function given a specific, unique numeric input value of the first set of numeric input values;

storing the first set of numeric solution values into an array such that each cell of the array corresponds to one of the input numeric values, from the first set of numeric input values, and has stored therein a numeric solution value, from the first set of numeric solution values, which is the solution to the first arithmetic function given the corresponding one of the input numeric values;

receiving, subsequent to the generating and the storing, a request to perform the first arithmetic function for a first provided numeric input value;

contingent upon the first provided numeric input value being one of the first set of numeric input values, identifying a cell of the array corresponding to the first provided numeric input value and providing, in response to the request, the numeric solution value, from the first set of numeric solution values, that is stored in the identified cell;

contingent upon the first provided numeric input value being one of a second set of numeric input values, providing a first numeric solution value that is the solution to the first arithmetic function for each of the second set of numeric input values, wherein the first and second sets of numeric input values are wholly exclusive of one another;

wherein each numeric input value, of the first and second sets of numeric input values, is represented by a predefined quantity of bits in accordance with a predefined computer number format; and

wherein the first set of numeric input values, and, separately, the second set of numeric input values are contiguous such that, given the predefined quantity of bits, the predefined computer number format cannot represent another numeric value between two adjacent input numeric values of the first set of numeric input values or between two adjacent input numeric values of the second set of numeric input values.

2. The method of claim 1, wherein the provided first numeric solution value is one of:

a maximum value representable with the predefined quantity of bits by the computer number format, a minimum value representable with the predefined quantity of bits by the computer number format, or zero.

3. The method of claim 1, further comprising:

contingent upon the first provided numeric input value being one of a third set of numeric input values, providing a second numeric solution value that is the solution to the first arithmetic function for each of the third set of numeric input values;

wherein each of the first set of numeric input values is numerically larger than any of the second set of numeric input values; and

wherein each of the first set of numeric input values is numerically smaller than any of the third set of numeric input values.

4. The method of claim 1, wherein each numeric solution value, of the first set of numeric solution values, is represented by a second predefined quantity of bits differing from the predefined quantity of bits utilized to represent each numeric input value of the first set of numeric input values.

5. The method of claim 1, further comprising:

generating, for the first set of numeric input values, a second set of numeric solution values, wherein each numeric solution value, in the second set of numeric solution values, is a solution to a second arithmetic function given a specific, unique numeric input value of the first set of numeric input values;

storing the second set of numeric solution values into the array such that each cell of a portion of the array comprising the second set of numeric solution values corresponds to one of the input numeric values, from the first set of numeric input values, and has stored therein a numeric solution value, from the second set of numeric solution values, which is the solution to the second arithmetic function given the corresponding one of the input numeric values;

receiving, subsequent to the generating and the storing, a request to perform the second arithmetic function for a second provided numeric input value;

identifying a second cell of the array corresponding to the second provided numeric input value; and

providing, in response to the request, the numeric solution value, from the second set of numeric solution values, that is stored in the identified second cell.

6. The method of claim 5, wherein either:

(1) each column or (2) each row of the array comprises;

a first cell having stored therein a first numeric solution value, from the first set of numeric solution values, which is the solution to the first arithmetic function given a first input numeric value, from the first set of numeric input values; and

a second cell having stored therein a second numeric solution value, from the second set of numeric solution values, which is the solution to the second arithmetic function given the first input numeric value, from the first set of numeric input values.

7. The method of claim 1, wherein the first arithmetic function is one of:

a logarithm of a numeric input value, an exponentiation of the numeric input value, a hyperbolic of the numeric input value or a sigmoid of the numeric input value.

8. A microprocessor comprising:

a first logic circuitry for detecting when a first provided numeric input value is one of a first set of numeric input values and, in response, identifying a cell of an array corresponding to the first provided numeric input value;

a second logic circuitry for detecting when the first provided numeric input value is one of a second set of numeric input values and, in response, returning a first numeric solution value that is the solution to a first arithmetic function given any one of the second set of numeric input values, wherein the first and second sets of numeric input values are wholly exclusive of one another; and

storage circuitry having the array encoded thereon, the array comprising a first set of numeric solution values, wherein each numeric solution value, in the first set of numeric solution values, is a solution to the first arithmetic function given a specific, unique numeric input value of the first set of numeric input values, the first set of numeric solution values being stored in the array;

wherein each numeric input value, of the first and second set of numeric input values, is represented by a predefined quantity of bits in accordance with a predefined computer number format, the first and second subsets being wholly exclusive of one another;

wherein the first set of numeric input values, and, separately, the second set of numeric input values are contiguous such that, given the predefined quantity of bits, the predefined computer number format cannot represent another numeric value between two adjacent input numeric values of the first set of numeric input values or between two adjacent input numeric values of the second set of numeric input values; and

wherein the microprocessor performs the first arithmetic function by receiving the first provided numeric input value, returning the first numeric solution value if the first provided numeric input value is one of the second set of numeric input values, and returning the numeric solution value that is stored in the identified cell if the first provided numeric input value is one of the first set of numeric input values.

9. The microprocessor of claim 8, wherein the array is encoded onto the storage circuitry during an initialization of the microprocessor by the microprocessor pre-calculating each numeric solution value, in the first set of numeric solution values.

10. The microprocessor of claim 8, wherein the provided first numeric solution value is one of:

a maximum value representable with the predefined quantity of bits by the computer number format, a minimum value representable with the predefined quantity of bits by the computer number format, or zero.

11. The microprocessor of claim 8, wherein each numeric solution value, of the first set of numeric solution values, is represented by a second predefined quantity of bits differing from the predefined quantity of bits utilized to represent each numeric input value of the first set of numeric input values.

12. The microprocessor of claim 8, further comprising:

a third logic circuitry for detecting when the first provided numeric input value is one of a third set of numeric input values and, in response, returning a second numeric solution value that is the solution to the first arithmetic function given any one of the third set of numeric input values;

wherein each of the first set of numeric input values is numerically larger than any of the second set of numeric input values; and

wherein each of the first set of numeric input values is numerically smaller than any of the third set of numeric input values.

13. The microprocessor of claim 8, wherein either:

(1) each column or (2) each row of the array comprises;

a first cell having stored therein a first numeric solution value, from the first set of numeric solution values, which is the solution to the first arithmetic function given a first input numeric value, from the first set of numeric input values; and

a second cell having stored therein a second numeric solution value, from a second set of numeric solution values, which is a solution to a second arithmetic function given the first input numeric value, from the first set of numeric input values.

14. A computing device comprising:

one or more processing units;

a first computer-readable storage medium having an array encoded thereon, the array comprising a first set of numeric solution values, wherein each numeric solution value, in the first set of numeric solution values, is a solution to a first arithmetic function given a specific, unique numeric input value of a first set of numeric input values, the first set of numeric solution values being stored in the array such that each cell of the array corresponds to one of the input numeric values, from the first set of numeric input values, and has stored therein a numeric solution value, from the first set of numeric solution values, which is the solution to the first arithmetic function given the corresponding one of the input numeric values; and

a second computer-readable storage medium comprising computer-executable instructions which, when executed by the one or more processing units, cause the computing device to;

receive a request to perform the first arithmetic function for a first provided numeric input value;

contingent upon the first provided numeric input value being one of the first set of numeric input values, identify a cell of the array corresponding to the first provided numeric input value and provide, in response to the request, the numeric solution value, from the first set of numeric solution values, that is stored in the identified cell;

contingent upon the first provided numeric input value being one of a second set of numeric input values, provide a first numeric solution value that is the solution to the first arithmetic function for each of the second set of numeric input values, wherein the first and second sets of numeric input values are wholly exclusive of one another;

wherein each numeric input value, of the first and second sets of numeric input values, is represented by a predefined quantity of bits in accordance with a predefined computer number format;

wherein the first set of numeric input values, and, separately, the second set of numeric input values are contiguous such that, given the predefined quantity of bits, the predefined computer number format cannot represent another numeric value between two adjacent input numeric values of the first set of numeric input values or between two adjacent input numeric values of the second set of numeric input values.

15. The computing device of claim 14, wherein the first computer-readable storage medium is a ROM.

16. The computing device of claim 14, wherein the first computer-readable storage medium is a RAM;

and wherein further the second computer-readable storage medium comprises further computer-executable instructions which, when executed by the one or more processing units, cause the computing device to read the array from the second computer-readable storage medium and load it into the RAM.

17. The computing device of claim 14, wherein the second computer-readable storage medium comprises further computer-executable instructions which, when executed by the one or more processing units, cause the computing device to:

generate, for the first set of numeric input values, the first set of numeric solution values; and

store the first set of numeric solution values into the array.

18. The computing device of claim 14, wherein either:

(1) each column or (2) each row of the array comprises;

a first cell having stored therein a first numeric solution value, from the first set of numeric solution values, which is the solution to the first arithmetic function given a first input numeric value, from the first set of numeric input values; and

a second cell having stored therein a second numeric solution value, from a second set of numeric solution values, which is a solution to a second arithmetic function given the first input numeric value, from the first set of numeric input values.

19. The computing device of claim 14, wherein the provided first numeric solution value is one of:

a maximum value representable with the predefined quantity of bits by the computer number format, a minimum value representable with the predefined quantity of bits by the computer number format, or zero.

20. The computing device of claim 14, wherein the second computer-readable storage medium comprises further computer-executable instructions which, when executed by the one or more processing units, cause the computing device to:

contingent upon the first provided numeric input value being one of a third set of numeric input values, providing a second numeric solution value that is the solution to the first arithmetic function for each of the third set of numeric input values;

wherein each of the first set of numeric input values is numerically larger than any of the second set of numeric input values; and

wherein each of the first set of numeric input values is numerically smaller than any of the third set of numeric input values.