METHOD OF OPERATING A COMPUTING DEVICE TO PERFORM MEMOIZATION

• US 20110302371A1
• Filed: 12/10/2009
• Published: 12/08/2011
• Est. Priority Date: 12/10/2008
• Status: Active Grant

• Current Assignee: CSIR
• Original Assignee: CSIR
• Inventors: Lysko, Albert Anatolievich
• Granted Patent: US 9,037,798 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 1/0353 by using symmetrical properties of the function, e.g. using most significant bits for quadrant control
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• 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

Abstract

This invention relates to a method (100) of operating a computing device to perform memoization. The method (100) includes determining whether or not a result of a function is stored in a cache and, if so, retrieving the result from the cache and, if not, calculating the result and storing it in the cache. The method (100) is characterised in that it includes transforming (104) by the computing device at least one selected from the group composed of the input parameters and the output parameters of the function, the transforming being based on an analysis of the function and its input arguments to establish whether or not there is a possible relationship among and between the input parameters and output parameters of the function, the relationship reflecting redundancy.

Claims

1. A method of operating a computing device to perform memoization, the method including determining whether or not a result of a function is stored in a cache and, if so, retrieving the result from the cache and, if not, calculating the result and storing it in the cache, characterised in that the method includes:

transforming by the computing device at least one selected from the group composed of the input parameters and the output parameters of the function, the transforming being based on an analysis of the function and its input arguments to establish whether or not there is a possible relationship among and between the input parameters and output parameters of the function, the relationship reflecting redundancy.

2. A method as claimed in claim 1, which includes transforming the output parameters only.

3. A method as claimed in claim 1, which includes transforming the input parameters only.

4. A method as claimed in claim 1, which includes transforming both the input parameters and the output parameters.

5. A method as claimed in claim 4, in which transforming the output parameters compensates for the transformation of the input parameters.

6. A method as claimed in any of claims 3 to 5 inclusive, in which transforming the input parameters includes pre-processing of the input parameters.

7. A method as claimed in any of claims 3 to 6 inclusive, in which transforming the input parameters includes at least one selected from the group composed of utilisation/application of symmetry, scaling, linear shift, interchanging of variables, inversion, polynomial and/or trigonometric transformations, and spectral transformations, logical transformations, fuzzy transformations, data compression and decompression.

8. A method as claimed in any of claims 3 to 7 inclusive, in which transforming the parameters includes bringing the parameters to a desired systematic arrangement.

9. A method as claimed in any of claims 3 to 8 inclusive, which includes storing in the cache an indication of how the input parameters were transformed.

10. A method as claimed in claim 2 or claim 4, in which transforming the output parameters includes at least one selected from the group composed of utilisation/application of symmetry, scaling, linear shift, interchanging of variables, inversion, polynomial and/or trigonometric transformations, and spectral transformations, logical transformations, fuzzy transformations, data compression and decompression.

11. A method as claimed in claim 2, claim 4, or claim 10, which includes storing in the cache an indication of how the output parameters can be transformed.

12. A method as claimed in any of the preceding claims, which includes storing in the cache an indication of the relationship between the input parameters and the output parameters.

13. A method as claimed in any of the preceding claims, which includes storing in the cache additional information, including a time stamp.

14. A method as claimed in any of the preceding claims, in which:

the function is used to calculate a system of equations, matrix, tensor or vector elements; and

transforming the input parameters and/or the output parameters includes defining a specific order in which the equations or elements of the matrix, vector or tensor are calculated, thereby to optimise memoization.

15. A method as claimed in any of the preceding claims, which includes the prior step of:

analysing input parameters of the function to establish whether or not there is a possible relationship reflecting redundancy among the input parameters and/or output parameters.

17. A computer-readable medium having stored thereon a set of instructions which, when executed by a computer, causes the computer to perform a method as claimed in any of claims 1 to 15 inclusive.

16. A system for memoization, the system including:

a computing device; and

a computer-readable medium defining a cache and having stored thereon a set of instructions configured to direct the operation of the computing device such that the computing device is operable to determine whether or not a result of a function is stored in the cache and, if so, to retrieve the result from the cache and, if not, to calculate the result and store it in the cache, characterised in that the computing device is further operable to;

transform at least one selected from the group composed of the input parameters and the output parameters of the function, the transforming being based on an analysis of the function and its input arguments to establish whether or not there is a possible relationship among and between the input parameters and output parameters of the function, the relationship reflecting redundancy.