Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
A METHOD OF OPERATING A COMPUTING DEVICE TO PERFORM MEMOIZATION
Document Type and Number:
WIPO Patent Application WO/2010/067324
Kind Code:
A1
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.

More Like This:
Inventors:
LYSKO ALBERT ANATOLIEVICH (ZA)
Application Number:
PCT/IB2009/055650
Publication Date:
June 17, 2010
Filing Date:
December 10, 2009
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
CSIR (ZA)
LYSKO ALBERT ANATOLIEVICH (ZA)
International Classes:
G06F12/08; G06F1/035; G06F17/10
Foreign References:
US5260898A1993-11-09
GB2320995A1998-07-08
US6513106B12003-01-28
US6553394B12003-04-22
Other References:
None
Attorney, Agent or Firm:
DAVIES, James, Hasely et al. (Adams & Adams Place1140 Prospect Street, Hatfield,PO Box 1014, Pretoria 000, ZA)
Download PDF:
Claims:
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.

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.

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.

Description:
TITLE: A method of operating a computing device to perform memoization

FIELD OF INVENTION

This invention relates to memoization, and specifically to a method and system for memoization.

BACKGROUND OF INVENTION

A cache is a temporary memory storage area functioning as a lookup table where data which is assumed to be accessed frequently can be stored, for highspeed access. Conceptually, such a cache maps between a set of output parameters (e.g. the data itself) and a set of input parameters (e.g. an address or identifier of the data). Once the data is stored in the cache, it can be accessed and retrieved more quickly than by fetching or calculating the original data from the original source. Caching therefore saves time by storing a limited amount of frequently accessed data in a nearby or high-speed memory.

Memoization applies the theory of a cache to programming, logical or numerical functions. Thus, instead of recalculating the result of a function, a previously calculated result can be used when the input parameters are the same.

Memoization finds particular application in computer programs and applications which calculate memory- or processor-intensive functions.

The Inventor desires an improved method for memoization.

SUMMARY OF INVENTION According to one aspect of the invention, there is provided 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.

The method may include transforming the output parameters only. The method may include transforming the input parameters only.

Instead, the method may include transforming both the input parameters and the output parameters of the function. In such case, transforming the output parameters may be used to compensate for the transformation of the input parameters.

Transforming the input parameters may include pre-processing of the input parameters. The purpose of transforming the input parameters may be to decrease a number of records stored in the cache, by considering redundancy- related properties inherent in some functions. Differently stated, many mathematical or scientific functions include properties that may generate repetitive or redundant elements and the purpose of transforming the function or its arguments may be to make use of these repetitive or redundant elements to optimise computations and storage. Transforming the input parameters may include at least one selected from the group composed of symmetry consideration(s), scaling (including simple change of sign), linear shift, interchanging of variables, inversion, polynomial and/or trigonometric transformations, spectral transformations (including various forms of Fourier, Laplace and wavelet transformations), logical transformations, fuzzy transformations, data compression and decompression.

For example, if f(x) = f{-x) , it is not necessary to store results for both f{x) and f{-x) . Instead, the results of only one function, e.g. f{x) , may be stored and transforming the input parameters may then include converting the sign of the argument of f(-x) so that the results of f(x) can be used from the cache.

The transforming may include bringing the parameters to a desired systematic arrangement (thereby helping to identify or use/reuse the cache elements more efficiently).

A complex function may be split into a plurality of sub functions. The input and output parameters may then relate to the individual sub functions or a combination of thereof, thus conceptually being intermediate parameters with respect to the original complex function.

x y

For example, a function f(x, y) = \ e cosz dz + \ e smz dz may be

-1 0 memorized more effectively by memorizing the two terms separately.

A decrease in the number of records stored in the cache by appropriate manipulating the input and output parameters and/or taking advantage of redundancies may decrease a size of the cache and/or decrease steps or iterations to find a matching record, thereby improving efficiency of the cache.

The input parameters and/or the output parameters may be transformed in accordance with predefined transformation criteria, specific to the application, task and/or computed function. The input and output parameters may be represented as scalars, vectors, matrixes, tensors, individually or as a combination thereof, or the like. - A -

The method may include storing in the cache an indication of the how the input parameters were transformed, if relevant. The method may include storing in the cache an indication of how the output parameters can be transformed. The method may include storing in the cache an indication of a relationship between the input parameters and the output parameters. The method may include storing additional information including a time stamp (if the transformation was applied to the data before it was cached).

Similarly, transforming the output parameters may include 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.

In the method, the function may be used to calculate a system of equations, matrix, tensor or vector elements, and in such case, transforming the input parameters and/or the output parameters may include defining a specific order, in which the equations or elements of the matrix, tensor, or vector are calculated, thereby to optimise memoization.

The method may find application in calculating functions which are relatively resource-intensive (e.g. in the fields of computational electromagnetics, fluid dynamics, etc.).

The method may include 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.

The invention extends to 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 a 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.

Examples of input parameters may include arguments, variables, constants, and the like. Examples of output parameters may include results, functions, values, and the like.

The system need not necessarily be consolidated into one device, but may be distributed and/or networked among a number of devices. Similarly, the computer-readable media need not necessarily be consolidated into one component, but may be distributed and/or networked among a number of components.

The invention extends further to a computer-readable medium having stored thereon a set of instructions which, when executed by a computing device, causes the computing device to perform a method as defined above.

BRIEF DESCRIPTION OF DRAWINGS

The invention will now be further described, by way of example, with reference to the accompanying diagrammatic drawings. In the drawings:

Figure 1 shows a flow diagram of a method of operating a computing device to perform memoization, in accordance with the invention; Figure 2 shows a schematic view of a system for memoization in accordance with the invention; and

Figures 3a - 3d show a schematic representation of a plurality of matrices calculated in accordance with the method of Figure 1.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENT

With reference to Figure 1, reference numeral 100 generally indicates a flow diagram of a method of operating a computing device to perform memoization, in accordance with the invention.

The method 100 includes receiving, at block 102, input parameters. The input parameters may come from a user via a user interface but may instead come from a computer program (or a subroutine thereof) attempting to calculate an output or result of a function or a part thereof. The method 100 finds particular application in the calculation of mathematical or scientific functions, but may also be applicable to computer or programming functions (e.g. iterative functions) or other relationships with input and output parameters. The method 100 is also preferably applied to functions whose calculation is relatively resource-consuming so that in many circumstances it will be quicker to retrieve, or possibly transform and use, the result of a previously calculated function rather than recalculate the result.

The method 100 includes analysing or interrogating the input parameters of the function to establish, at block 103, whether or not there is a possible relationship reflecting redundancy among/between the input parameters and output parameters and, if so, the input parameters are transformed, at block

104. (This step of analysis may also be done beforehand by a human.) This may be done in a number of ways and examples of this are further described below. The transformation of the input parameters takes into account redundant or repetitive characteristics of the function with respect to the input and/or output parameters, the characteristics such as symmetry consideration(s), possibility of scaling (including change of sign), linear shift, interchangability of variables, inversion, polynomial and/or trigonometric transformations, spectral transformations (including various forms of Fourier, Laplace and wavelet transformations), logical and/or fuzzy relationship(s), and any combination thereof. Through the transformation, the input parameters (or arguments) may then be brought to an intermediate form identifiable with respect to the output result(s) (i.e. the output parameters).

Next, the cache is interrogated, at block 106 to determine, at block 108, whether or not the intermediate parameters can be matched to parameters stored in the cache, possibly including comparison(s) of additional flags or criteria. If matched, the record possibly including the result, possibly including additional information is retrieved, at block 114, from the cache. If not, the result is calculated, at block 110, and saved, possibly with additional information, at block 112, in the cache. It is then determined, at block 116, whether or not it is required to transform output parameters and, if so, the output parameters are transformed, at block 118, accordingly.

Example 1

If, for example, f(a,b) = f(b, a), it can be said that the input parameters of the function / are interchangeable. To minimise the number of functions stored within the cache thereby to optimise the use of the cache, the variables of the functions are transformed in accordance with the transformation criteria, which in this case indicate that they must be transformed and ordered in, for instance, increasing numerical order (increasing with the position of the argument).

Thus, if it is desired to calculate the result of /(2,1) , the variables or inputs are transformed to /(1,2) . As this is the first iteration, /(1,2) has not previously been calculated and therefore it is calculated, at block 110 and saved, at block 112 in the cache; the result is the same as it is for /(2,1) . In future, if either /(1,2) or /(2,1) need to be calculated, the result can simply be retrieved, at block 114, based on the result of /(1,2) . In this example, no output parameter transformation is required.

Example 2

It may be that when bounds of an integral are interchanged, the result a b has the same absolute value but a different sign, i.e. [ /(x) dx = - [ /(x) dx. In this b a example, the output criteria dictate that the lower numerical number of a and b must be transformed, if not already there, to the lower bound of the integral and, correspondingly, that the higher number must be transformed, also of not already there, to the upper bound of the integral. Thus, in the first iteration of the method

4

100, [/(x), for example, is to be calculated. For the specific iteration, no

3 transformation need be done and the result is calculated and saved, at blocks 110,

3

112. In the next iteration, however, \ f{x) is to be calculated. The input

4 parameters, e.g. the bounds of the integral, are now interchanged in accordance

with the defined convention and the result of can then be retrieved from the cache 114 where it was stored in the first iteration. However, in this example, it is necessary also to transform, at block 118, the output parameters in that the sign of the result needs to be changed. Thus, also stored in the cache 114 along with the result may be associated details of required output parameter transformation and determining, at block 116, whether or not output parameter transformation is required may include reading this from the cache. Alternatively, it could be determined based on the nature of the input parameter transformation.

Example 3

If the function includes a system of equations or a matrix (e.g. A-X=B), transforming the input parameters may include defining a specific order in which the equations or elements of the matrix are calculated, thereby to optimise memoization. The matrix illustrated in Figure 3 is symmetrical with respect to the main diagonal and so is a Toeplitz matrix. Conventional computerised processing of matrix elements typically includes processing elements in a predefined, fixed order, typically row-wise (from the beginning of one row to the end and then repeating the process from the following rows) or column-wise. However, in accordance with the invention, the elements of the matrix are processed in an order which groups similar or equivalent input parameters or expected output parameters together. This matrix is processed in the order indicated by arrowed lines in Figures 3a - 3d, so that more efficient use may be made of the memoization in that elements of the matrix with the same result can be addressed and calculated (if necessary) and retrieved from the cache successively and more efficiently.

The exact order of following the arrowed lines in Figure 3 may be different from the one illustrated and may be specific to a particular programming language and its realisation on a particular computer platform (platform-dependant).

It may help to increase the efficiency even further by accessing the computer memory in a manner minimising the distance in memory between the called matrix elements in order to improve the efficiency of utilising the computing device (including processor and/or motherboard) caches. Also, it is possible to store the matrix elements in an order minimizing the distance in memory between the consequently called elements.

For example, FORTRAN and C store rectangular matrices differently (FORTRAN stores column-wise, whilst C stores row-wise). If a column-wise approach is used, it may be beneficial to try to group the calling of matrix element from the same or neighbouring columns.

More specifically, in the example of the method of moments (or related methods, e.g. the boundary element method), an integral equation with a boundary condition defined on a geometric structure is transformed into a set of linear algebraic equations. The elements of the resulting N x N matrix are integrals. Usually these are double, triple or quadruple integrals, and are computed using numerical quadratures. Accurate evaluation of these integrals is time-consuming and the higher the degree of accuracy required, the more time is required. Many practical geometric structures, and types of mesh applied to the structure, result in a plurality of the same or similar geometric mesh elements. The same combinations of these geometrical elements produce integrals with the same result. Thus, similarities in the geometric combinations may be recognised in a few simple steps. Then, the integrals need to be calculated once only (for each combination) and the already computed values may be used thereafter instead of performing the time- consuming calculation repeatedly. Under ideal circumstances, the number of integral evaluations can be reduced from N 2 to N .

Example 4 (redundancy provided by the geometrical elements)

A method of moments is often applied to wire structures for the purpose of establishing the properties of resultant electromagnetic radiation. A basis element in the matrix, forming a part of the system of linear algebraic equations, is a weighted moment. It expresses the interaction between the basis geometrical elements, i.e. wire segments. In this example, for simplicity and demonstration purposes, only wire segments that are both thin compared to the wavelength and long compared to their radius are being considered.

One of the ways to describe the geometry of this problem is to state the radius of each wire segment and the three-dimensional coordinates of the beginning and the end. Following this example, the matrix element can be expressed as a double integral with the integrand dependant only on the distance between the points on the wire segments.

The input parameters to such a function computing interaction between a pair of wire segments, can be represented by: 3 coordinates for the beginning of the first wire;

3 coordinates for the end of the first wire; 3 coordinates for the beginning of the second wire; 3 coordinates for the end of the second wire; and 2 scalars for radii of the two wires.

As no two wires can occupy the same space, this set of input parameters cannot take advantage of the redundancies. The redundancy elements come from the fact that the integrand depends on the distance between the points rather than on the absolute coordinates. Thus, another, mathematically equivalent set of parameters can be introduced:

Length of the first wire; length of the second wire; distance between the beginning of the first wire and the beginning of the second wire; distance between the beginning of the first wire and the end of the second wire; distance between the end of the first wire and the beginning of the second wire; distance between the end of the first wire and the end of the second wire; and

2 scalars for radii of the two wires.

Another aspect in utilising the redundancy properties in this example is that the two wires can be interchanged (with appropriate interchange in the distances between the respective ends of the wires); and the numbering of the ends of the wires can be interchanged.

Each of these two redundancies permits to reduce the storage space required in the cache by a factor of two. The taking advantage of such redundancies becomes possible when the original geometrical structure is divided into basic elements that are similar. Figure 2 illustrates an example computer system 200 which includes computing device, e.g. a processor 202 (e.g., a central processing unit (CPU), a graphics processing unit (GPU) or both, a main memory 204 and a static memory 206, which communicate with each other via a bus 208. The computer system 200 may further include a video display unit 210 (e.g., a liquid crystal display (LCD), a plasma display, or a cathode ray tube (CRT)). The computer system 200 may also include an alphanumeric input device 212 (e.g., a keyboard), a user interface (Ul) navigation device 214 (e.g., a mouse), a disk drive unit 216, a signal generation device 218 (e.g., a speaker) and a network interface device 220.

The disk drive unit 216 includes a computer-readable medium 222 on which is stored one or more sets of instructions and data structures (e.g., software 224) embodying or utilised by any one or more of the methodologies or functions described herein. The software 224 may also reside, completely or at least partially, within the main memory 204 and/or within the processor 202 during execution thereof by the computer system 200, the main memory 204 and the processor 202 also constituting computer-readable media.

The software 224 may further be transmitted or received over a network 226 via the network interface device 220 utilising any one of a number of well-known transfer protocols (e.g., HTTP, Ethernet, I 2 C).

While the computer-readable medium 222 is shown in an example embodiment to be a single medium, the term "computer-readable medium" should be taken to include a single medium or multiple media (e.g., a centralised or distributed database, and/or associated caches and servers) that store the one or more sets of instructions. The term "computer-readable medium" shall also be taken to include any medium that is capable of storing, encoding or carrying a set of instructions for execution by the computer and that cause the computer to perform any one or more of the methodologies of the present embodiments, or that is capable of storing, encoding or carrying data structures utilised by or associated with such a set of instructions. The term "computer-readable medium" shall accordingly be taken to include, but not be limited to, solid-state memories, optical and magnetic media, and carrier wave signals.

The computer system 200 may be programmed to implement the method 100 of Figure 1, but it is to be appreciated that the method 100 may be applied to other systems also.

The method 100 of memoization could also be realized as a standalone device, or be a part of another physical device, or could be software-based.

The Inventor believes that the invention as exemplified provides an enhanced method 100 of memoization which provides improved performance compared with conventional memoization in that inherent redundancies of functions are not only considered but exploited.