Systems and methods for approximation based optimization of data processors

Patent metadata

Field	Value
Publication number	US-10209971-B2
Application number	US-201514699854-A
Country	US
Kind code	B2
Filing date	Apr 29, 2015
Priority date	Apr 29, 2014
Publication date	Feb 19, 2019
Grant date	Feb 19, 2019

Abstract

A compilation system can apply a smoothness constraint to the arguments of a compute-bound function invoked in a software program, to ensure that the value(s) of one or more function arguments are within specified respective threshold(s) from selected nominal value(s). If the constraint is satisfied, the function invocation is replaced with an approximation thereof. The smoothness constraint may be determined for a range of value(s) of function argument(s) so as to determine a neighborhood within which the function can be replaced with an approximation thereof. The replacement of the function with an approximation thereof can facilitate simultaneous optimization of computation accuracy, performance, and energy/power consumption.

First claim

Accordingly, we claim:

1. A method for optimizing performance of a processing system, the method comprising:
tiling by a compilation processor a loop nest comprising at least one loop, each tile comprising a specified computation based on an argument, the argument specifying an input used by the computation, a value of the argument varying according to a tile index, a tile size being selected such that a difference between a value of the argument corresponding to a final tile index and a value of the argument corresponding to an initial tile index is at most equal to a threshold;
employing by the compilation processor an exact procedure, to be executed by a target processor, implementing the specified computation for the initial tile index;
employing by the compilation processor an approximate procedure, to be executed by the target processor, implementing the specified computation for each subsequent tile index, wherein a computation cost according to a cost metric of the approximate procedure is less than a computation cost according to that cost metric of the exact procedure, thereby improving execution of the loop nest by minimizing cost of executing the loop nest by the target processor.

2. The method of claim 1 , wherein:
the specified computation is based on a first plurality of arguments comprising a second plurality of arguments, respective values of the second plurality of arguments varying according to the tile index; and
the tile size is selected such that respective differences between respective values of the second plurality of arguments corresponding to the final tile index and respective values of the second plurality of argument corresponding to the initial tile index are at most equal to respective thresholds.

3. The method of claim 1 , wherein the threshold is based on, at least in part, an error associated with the approximate procedure.

4. The method of claim 1 , wherein the cost metric comprises at least one of a number of computations and a type of a computation.

5. The method of claim 1 , wherein:
an approximate result is computed for a first subsequent index is based on, in part, an exact result obtained from the exact procedure; and
respective approximate results computed for other subsequent indices are based on, in part, respective approximate results obtained from the approximate procedure for respective previous indices.

6. The method of claim 1 , wherein each approximate result computed for each one of the subsequent indices is based on, in part, an exact result obtained from the exact procedure.

7. The method of claim 6 , further comprising parallelizing the tiled loop nest.

8. The method of claim 1 , wherein:
for each one of a first plurality of subsequent indices a corresponding approximate result is computed based on, in part, an exact result obtained from the exact procedure; and
for each one of a second plurality of subsequent indices a corresponding approximate result is computed based on, in part, an approximate result corresponding to a respective tile index from the first plurality of subsequent indices.

9. The method of claim 8 , further comprising parallelizing computation of approximate results corresponding to the first plurality of indices.

10. A method for optimizing performance of a processing system, the method comprising:
in a tiled a loop nest comprising at least one loop, each tile comprising a specified computation based on a first argument, the first argument specifying a first input used by the computation, a value of the first argument varying according to a tile index:
employing by a compilation processor an exact procedure, to be executed by a target processor, implementing the specified computation for a reference tile index;
determining if a first difference between values of the first argument corresponding to a first non-reference tile index and corresponding to the reference index is greater than a first threshold;
if the first difference is not greater than the first threshold, employing by the compilation processor an approximate procedure, to be executed by the target processor, implementing the specified computation for the first non-reference tile index, wherein a computation cost according to a cost metric of the approximate procedure is less than a computation cost according to that cost metric of the exact procedure; and
otherwise, employing the exact procedure for the first non-reference tile index,
wherein employing of the approximate procedure improves execution of the loop nest by minimizing cost of executing the loop nest by the target processor.

11. The method of claim 10 , wherein the approximate procedure depends, in part, on the determined first difference between values of the first argument corresponding to the first non-reference tile index and corresponding to the reference index.

12. The method of claim 10 , wherein the specified computation is further based on a second argument, the second argument specifying a second input used by the computation, a value of the second argument also varying according to the tile index, the method further comprising:
determining if a second difference between values of the second argument corresponding to the first non-reference tile index and corresponding to the reference index is greater than a second threshold;
if both the first and second differences are not greater than the first and second thresholds, respectively, employing the approximate procedure for the first non-reference tile index; and
otherwise, employing the exact procedure for the first non-reference tile index.

13. The method of claim 12 , wherein the second threshold is equal to the first threshold.

14. The method of claim 10 , wherein the first threshold is based on, at least in part, an error associated with the approximate procedure.

15. The method of claim 10 , wherein the cost metric comprises at least one of a number of computations and a type of a computation.

16. The method of claim 10 , further comprising modifying the reference index by setting the first non-reference tile index as the reference index, if the exact procedure is employed for the first non-reference tile index.

17. The method of claim 10 , further comprising employing the approximate procedure implementing the specified computation for a second non-reference tile index, wherein the approximate procedure depends on, in part, one of: (i) an exact result obtained from the exact procedure, and (ii) an approximate result obtained from the approximate procedure employed for the first non-reference tile index.

18. The method of claim 17 , further comprising employing the approximate procedure implementing the specified computation for a third non-reference tile index, wherein the approximate procedure depends on, in part, one of: (i) an exact result obtained from the exact procedure, and (ii) an approximate result obtained from the approximate procedure employed for the second non-reference tile index.

19. The method of claim 10 , further comprising tiling a loop nest to generate the tiled loop nest, a tile size being selected such that a difference between a value of the argument corresponding to a final tile index and a value of the argument corresponding to an initial tile index is at most equal to a threshold.

20. The method of claim 10 , further comprising parallelizing the tiled loop nest.

21. A compilation system for optimizing performance of a processing system, the compilation system comprising:
a first processor; and

Assignees

• Reservoir Labs Inc

Inventors

• Baskaran Muthu M
• Henretty Thomas
• Johnson Ann
• Konstantinidis Athanasios
• Langston M H
• Lethin Richard A
• Mcmahon Janice O
• Meister Benoit J
• Mountcastle Paul

Classifications

• G06F8/4441 Primary

  Reducing the execution time required by the program code · CPC title