Method and apparatus for saving and retrieving functional results

• US 5,347,652 A
• Filed: 06/26/1991
• Issued: 09/13/1994
• Est. Priority Date: 06/26/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: McAuliffe, Kevin P., Epstein, David A., Gilley, Glenn G.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Lintz, Paul R.
• Application Number:
  US07/721,807
• Time in Patent Office: 1,175 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 364/746, 364/736, 395/200, 395/800, 395/400, 395/600, 395/425
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

Method and apparatus for use in a digital data processing system that evaluates functional networks. A method operates to assign a unique signature to each input constant of the network, assign a unique signature to each output of a network Function, and to store each of the constants and function outputs along with their assigned signatures. The signatures operate as an access key to the associated stored constants and function outputs, thereby eliminating a requirement to reevaluate a Function if its outputs already exist. A storage element, or Dictionary (20), stores data units, such as input data, intermediate values, and/or pointers to same, each with a unique signature. The storage element, in concert with a Dictionary Controller (18), provides for the deletion of a stored data unit that is associated with a specified signature and the retrieval of a stored data unit that is associated with a specified signature. Preferably, the signatures are generated from a combination of constant and Function attributes and values and are each uniquely encoded by a CRC generator (14).

Claims

1. For use in a digital data processing system of a type that repetitively evokes a set of Functions to process data, including one or more constants, a method comprising the steps of:

examining a constant to determine identifying characteristics thereof;

combining the characteristics with the value of the constant;

encoding the combination to obtain a Constant signature;

storing the Constant signature with a representation of the value;

for each Function of the set of Functions having input for which Constant signatures have been encoded,

examining a Function to determine identifying characteristics of an output of the Function;

combining the characteristics with an identification of the Function and with signatures of the inputs to the Function;

encoding the combination to obtain a first Function signature;

storing the first Function signature; and

, prior to executing a Function, performing the steps of,

examining the Function to be executed to determine identifying characteristics of an output of the Function;

combining the characteristics with an identification of the Function to be executed and with signatures of the inputs to the Function to be executed;

encoding the combination to obtain a second Function signature;

determining if there exists a stored Function signature that equals the second Function signature; and

if so,

accessing a memory means to retrieve a value associated with the stored Function signature, otherwise

executing the Function and storing the value returned by the Function with the signature of the Function.

2. A method as set forth in claim 1 wherein the step of examining a constant includes a step of determining a type, category, rank, and dimensionality of the constant.

3. A method as set forth in claim 1 wherein the steps of encoding each include a step of computing a CRC polynomial of the combination.

4. A method as set forth in claim 1 wherein the first step of encoding includes a step of concatenating a character string representation of the characteristics and the value.

5. A method as set forth in claim 1 wherein the first step of storing includes a step of creating an entry within a data structure, the entry including the Constant signature and the value of the constant.

6. A method as set forth in claim 1 wherein the first step of storing includes a step of creating an entry within a data structure, the entry including the Constant signature and a pointer to a storage location containing the value of the constant.

7. A method as set forth in claim 1 wherein the step of examining a Function includes the steps of determining an identity of all inputs to the Function, determining an identity of the Function output, and determining a name of the Function.

8. A method as set forth in claim 1 wherein the step of encoding the combination to obtain a Function signature includes a step of concatenating a character string representation of the identifying characteristics of the Function and the identification of the Function.

9. A method as set forth in claim 1 wherein the step of storing the Function signature includes a step of creating an entry within a data structure, the entry including the Function signature and the representation of the output of the Function.

10. A method as set forth in claim 1 wherein the step of storing the Function includes a step of creating an entry within a data structure, the entry including the Function signature and a pointer to a storage location of the output of the Function.

11. A method as set forth in claim 1 wherein the step of accessing includes a step of storing a time stamp indicative of a time that the access occurs.

12. A method as set forth in claim 1 wherein the step of accessing includes a step of incrementing a count indicative of a number of times that the associated output of the Function is accessed.

13. A method as set forth in claim 1 wherein the step of storing the first Function signature further includes a step of storing a cost associated with executing the function so as to obtain the output of the Function.

14. A method as set forth in claim 11

wherein the method further includes a step of

selecting a stored Function signature for removal from a means that stores the Function signature, the selection being accomplished in accordance with a Least Recently Used criteria.

15. A method as set forth in claim 14 wherein the step of storing a time stamp includes a step of incrementing a count indicative of a number of times that the associated output of the Function is accessed, and wherein the Least Recently Used criteria also considers a value of the count.

16. A method as set forth in claim 14 wherein the step of storing a time stamp further includes a step of storing a cost associated with executing the Function to obtain the output of the Function, and wherein the Least Recently Used Criteria also considers the stored cost.

17. Apparatus for use in a digital data processing system of a type that repetitively evokes a set of Functions to process data, including one or more constants, comprising:

means for examining a functional network comprised of a plurality of functional nodes each representing a network Function, at least one of said functional nodes having an input for receiving input data, at least one of said functional nodes having an output for outputting, to an input of another functional node, an intermediate result of an execution of the associated network Function, said examining means including means for examining one or more network constants to determine identifying characteristics thereof, said constant examining means including means for combining the characteristics with a value of a network constant to obtain a first combination, said examining means further including means for examining one or more network Functions to determine identifying characteristics of an output of each network Function, said Function examining means including means for combining the characteristics with an identification of a network Function and with signatures of the inputs to the network Function to obtain a second combination;

means for encoding the first combination and the second combination to obtain a Constant signature and a Function signature, respectively;

means for storing the Constant signature and the Function signature in association with a representation of a value of the network constant and with a representation of an output of the network Function, respectively; and

means, responsive to a network Function being called for execution, for accessing the storing means with a Constant signature or with a Function signature to obtain the stored representation of the value of a corresponding network constant or the stored representation of the output of a corresponding network Function, respectively.

18. Apparatus as set forth in claim 17 wherein said storing means includes hash table means having a plurality of hash cells for storing said Constant signatures, Function signatures, and associated representations.

19. Apparatus as set forth in claim 18, wherein said accessing means includes means for addressing said hash table means with a Constant signature or a Function signature.

20. Apparatus as set forth in claim 17, wherein said accessing means further includes means for accessing the storing means with a Constant signature or a Function signature so as remove from the storing means a stored entry having a signature that equals the Constant signature or the Function signature.

21. Apparatus as set forth in claim 17 wherein said encoding means includes CRC generating means.

22. Apparatus as set forth in claim 17 wherein said accessing means includes means for time stamping an accessed Constant signature or Function signature with a time that the access is made.

23. Apparatus as set forth in claim 17 and further including memory means for storing a value of a network constant or a value of a network Function output, and wherein the stored representation includes a pointer to a location within the memory means wherein the associated value is stored.

24. Apparatus as set forth in claim 17 wherein the combining means of the network constant examining means obtains the first combination as a constant signature (S_c) in accordance with the expression:

space="preserve" listing-type="equation">S.sub.c (type, category, rank, dimensions, data),

and wherein the combining means of the network Functions examining means obtains the second combination as a Function signature (S_f) in accordance with the expression;

space="preserve" listing-type="equation">S.sub.f (name, out, i.sub.1, i.sub.2, . . . , i.sub.n);

wherein i₁, i₂, . . . , i_n are inputs to a network Function being examined.

25. A method for use in a digital data processing system of a type that repetitively evokes a set of Functions to process data, including one or more constants, comprising the steps of:

operating the digital data processing system to examine a functional network comprised of a plurality of functional nodes each representing a network Function, at least one of said functional nodes having an input for receiving input data, at least one of said functional nodes having an output for outputting, to an input of another functional node, an intermediate result of an execution of the associated network Function, the step of operating the digital data processing system being comprised of the steps of,

inputting at least one network constant;

examining the at least one network constant to determine identifying characteristics thereof and combining the determined identifying characteristics with a value of the at least one network constant to obtain a first combination;

inputting at least one network Function;

examining the at least one network Function to determine identifying characteristics of an output of the at least one network Function and combining the determined identifying characteristics with an identification of the at least one network Function and with signatures of inputs to the network Function to obtain a second combination;

inputting the first combination and the second combination to an encoder;

encoding with the encoder the first combination and the second combination to obtain at an output of the encoder a Constant signature and a Function signature, respectively; and

storing, within a memory means, a plurality of items that include the Constant signature and the Function signature that are output from the encoder, the Constant signature and the Function signature being stored in association with a representation of a value of the at least one network constant and with a representation of an output of the at least one network Function, respectively;

wherein

the first combination is obtained as a constant signature (S_c) in accordance with an expression having at least the elements of;

space="preserve" listing-type="equation">S.sub.c (type, category, rank, dimensions, data),

and wherein the second combination is obtained as a Function signature (S_f) in accordance with an expression having at least the elements of;

space="preserve" listing-type="equation">S.sub.f (name, out, i.sub.1, i.sub.2, . . . , i.sub.n);

where i₁, i₂, . . . , i_n are inputs to the at least one network Function.

26. A method as set forth in claim 25, and prior to executing an evoked network Function, performing the step of accessing the memory means with a Constant signature or a Function signature so as to obtain, if available, the stored representation of the value of a corresponding network constant or the stored representation of the output of a corresponding network Function, respectively.

27. A method as set forth in claim 25 and further including the step of periodically purging the memory means to remove an item or items that meet one or more predetermined criteria.

28. A method as set forth in claim 27 wherein the one or more predetermined criteria are selected from the group consisting essentially of a time of last access, an access count, a computational cost, and combinations thereof.