Fractional caching

• US 20070198777A1
• Filed: 02/23/2006
• Published: 08/23/2007
• Est. Priority Date: 02/23/2006
• Status: Active Grant

• Current Assignee: Phothena Optics Corporation
• Original Assignee: Phothena Optics Corporation
• Inventors: Reinertsen, Lars
• Granted Patent: US 7,464,226 B2
• Time in Patent Office: Days
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack

Abstract

A microprocessor-based system generates an electronic document based on a set of microprocessor-readable instructions organized in logical units known as instruction nodes. Each instruction node includes at least one microprocessor-readable instruction. If an instruction node is eligible for caching, it is associated with a cache key value, which is compared with a cache key value that is stored in a cache memory and that is associated with a data item. If the cache key value associated with the instruction node matches the cache key value stored in the cache memory, the microprocessor-based system retrieves the data item with the cache key value stored in the cache memory, rather than executing the instruction node. The microprocessor-based system generates at least a portion of the electronic document as a function of the retrieved data item.

Claims

1. A microprocessor-based system for generating an electronic document, the microprocessor-based system comprising:

a program memory configured to store an instruction node comprising at least one microprocessor-readable instruction;

a cache memory configured to store a cache key value and a data item associated with the stored cache key value;

a requester subsystem configured to receive the instruction node from the program memory; and

an interpreter subsystem configured to

if the instruction node is eligible for caching, compare a cache key value associated with the instruction node with a cache key value stored in a cache memory and associated with a data item, and

if the cache key value associated with the instruction node matches the cache key value stored in the cache memory, retrieve the data item with the cache key value stored in the cache memory, and generate at least a portion of the electronic document as a function of the retrieved data item,

whereby the interpreter subsystem generates portions of the electronic document that are associated with instruction nodes associated with stored cache key values by retrieving data items from the cache memory rather than executing such instruction nodes.

2. The microprocessor-based system of claim 1, wherein the interpreter subsystem is further configured to calculate the cache key value associated with the instruction node.

3. The microprocessor-based system of claim 1, wherein the cache key value associated with the instruction node is encoded in the instruction node.

4. The microprocessor-based system of claim 1, wherein the interpreter subsystem is further configured to, when the cache key value associated with the instruction node does not match the stored cache key value:

execute the at least one microprocessor-readable instruction of the instruction node to obtain a result;

generate at least a portion of the electronic document as a function of the result; and

store the result as a data item in the cache memory.

5. The microprocessor-based system of claim 1, wherein the interpreter subsystem is further configured to identify the instruction node as not eligible for caching if the instruction node contains a microprocessor-readable instruction designating the instruction node as not eligible for caching.

6. The microprocessor-based system of claim 5, wherein the interpreter subsystem is further configured to, in response to identifying the instruction node as not eligible for caching:

execute the at least one microprocessor-readable instruction of the instruction node to obtain a result; and

generate at least a portion of the electronic document as a function of the result without storing the result as a data item in the cache memory.

7. The microprocessor-based system of claim 1, wherein the instruction node comprises at least one child instruction node.

8. The microprocessor-based system of claim 1, wherein the microprocessor-based system is configured to execute a plurality of instruction nodes using a multi-threaded execution technique.

9. A method for generating an electronic document as a function of a set of microprocessor-readable instructions, the method comprising:

receiving an instruction node comprising at least one microprocessor-readable instruction from the set of microprocessor-readable instructions;

if the instruction node is eligible for caching, comparing a cache key value associated with the instruction node with a cache key value stored in a cache memory and associated with a data item;

if the cache key value associated with the instruction node matches the cache key value stored in the cache memory, retrieving the data item with the cache key value stored in the cache memory; and

generating at least a portion of the electronic document as a function of the retrieved data item.

10. The method of claim 9, further comprising calculating the cache key value associated with the instruction node.

11. The method of claim 9, wherein the cache key value associated with the instruction node is encoded in the instruction node.

12. The method of claim 9, further comprising, when the cache key value associated with the instruction node does not match the stored cache key value:

executing the at least one microprocessor-readable instruction of the instruction node to obtain a result;

generating at least a portion of the electronic document as a function of the result; and

storing the result as a data item in the cache memory.

13. The method of claim 9, further comprising identifying the instruction node as not eligible for caching if the instruction node contains a microprocessor-readable instruction designating the instruction node as not eligible for caching.

14. The method of claim 13, further comprising, in response to identifying the instruction node as not eligible for caching:

executing the at least one microprocessor-readable instruction of the instruction node to obtain a result; and

generating at least a portion of the electronic document as a function of the result without storing the result as a data item in the cache memory.

15. The method of claim 9, wherein the instruction node comprises at least one child node.

16. The method of claim 9, further comprising:

receiving a plurality of instruction nodes each comprising at least one microprocessor-readable instruction from the set of microprocessor-readable instructions; and

executing the instruction nodes using a multi-threaded execution technique.

17. A microprocessor-readable medium containing microprocessor-readable instructions that, when executed using a microprocessor-based system, cause the microprocessor-based system to perform a method for generating an electronic document, the method comprising:

receiving an executable instruction node from a program memory;

if the executable instruction node is eligible for caching, comparing a cache key value associated with the executable instruction node with a cache key value stored in a cache memory and associated with a data item;

if the cache key value associated with the executable instruction node matches the cache key value stored in the cache memory, retrieving the data item with the cache key value stored in the cache memory; and

generating at least a portion of the electronic document as a function of the retrieved data item.

18. The microprocessor-readable medium of claim 17, containing further microprocessor-readable instructions that, when executed using the microprocessor-based system, cause the microprocessor-based system to calculate the cache key value associated with the instruction node.

19. The microprocessor-readable medium of claim 17, wherein the cache key value associated with the instruction node is encoded in the instruction node.

20. The microprocessor-readable medium of claim 17, containing further microprocessor-readable instructions that, when executed using the microprocessor-based system, cause the microprocessor-based system to, when the cache key value associated with the instruction node does not match the stored cache key value:

execute the at least one microprocessor-readable instruction of the instruction node to obtain a result;

generate at least a portion of the electronic document as a function of the result; and

store the result as a data item in the cache memory.

21. The microprocessor-readable medium of claim 17, containing further microprocessor-readable instructions that, when executed using the microprocessor-based system, cause the microprocessor-based system to identify the instruction node as not eligible for caching if the instruction node contains a microprocessor-readable instruction designating the instruction node as not eligible for caching.

22. The microprocessor-readable medium of claim 21, containing further microprocessor-readable instructions that, when executed using the microprocessor-based system, cause the microprocessor-based system to, in response to identifying the instruction node as not eligible for caching:

execute the at least one microprocessor-readable instruction of the instruction node to obtain a result; and

generate at least a portion of the electronic document as a function of the result without storing the result as a data item in the cache memory.

23. The microprocessor-readable medium of claim 17, wherein the executable instruction node comprises at least one child node.

24. The microprocessor-readable medium of claim 17, containing further microprocessor-readable instructions that, when executed using the microprocessor-based system, cause the microprocessor-based system to:

receive a plurality of executable instruction nodes from the program memory; and

execute the instruction nodes using a multi-threaded execution technique.