Cache with multiway steering and modified cyclic reuse

• US 20030204664A1
• Filed: 04/30/2002
• Published: 10/30/2003
• Est. Priority Date: 04/30/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bennett, John G.
• Granted Patent: US 6,915,373 B2
• Time in Patent Office: Days
• US Class Current: 711/3
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list

Abstract

In a cache system a steering array indirect maps queries to the cache cells, and a cyclic replacement mechanism allocates the cache cells for replacement in the cache. The cache system has a hash mechanism, a steering array and a cyclic replacement counter. The hash mechanism computes a hash value from arguments in the query. The cache has a plurality of cache cells, and each cell has an answer and a usage bit indicating whether the cell is in use. The steering array stores a cache index based on the hash value, and the cache index points to a cache cell that may contain the answer to the query. The cyclic replacement counter addresses each cell in the cache to determine if the cell is still in use or may store a new answer. A single steering array may be used with a single cache array. To handle collisions between queries producing the same hash value, a link index may be provided in a first cache cell addressed by the cache index. The link index provides access to a second cache cell having a previous answer for another query producing the same hash value. Also parallel cache arrays and parallel steering arrays may be used to provide more than one cache element for answers to queries producing the same hash value.

Claims

1. In a computing system a cache system for retrieving an answer in response to a query, the cache system comprising:

at least one cache array of cache elements,

a hash mechanism generating a hash value based on arguments in the query;

an indirect mapping module mapping the hash value to a cache index and accessing a cache element in a cache array;

a first retrieve module retrieving an answer from a first cache element if the arguments in the first cache element match the arguments in the query;

a second retrieve module retrieving an answer from a second cache element if the arguments in the second cache element match the arguments in the query;

an underlying search module searching for the answer in the storage system outside the cache array if neither first retrieve module or the second retrieve module retrieves an answer; and

a cyclic replacement module cycling through cache elements in one or more cache arrays to select a cache element in which the answer from the underlying search module is stored.

2. The cache system of claim 1 wherein the indirect mapping module comprises:

a steering array accessed with the hash value and providing a cache index for accessing the cache element.

3. The cache system of claim 2 wherein:

the first cache element in the cache array stores a link index to the second cache element;

the cyclic replacement module stores the link index in the first cache element when the answer from the underlying search module is stored in the first cache element.

4. The cache system of claim 1 wherein there are parallel cache arrays and the indirect mapping module comprises:

parallel steering arrays both accessed by the hash value and a first steering array providing a first cache index to a cache element in one of the parallel arrays and a second steering array providing a second cache index to a cache element in the other of the parallel arrays.

5. A cache system for retrieving an answer in response to a query, the cache system comprising:

a hash mechanism computing a hash value from arguments in the query;

a cache with a plurality of cache cells, each cell having an answer and a usage bit indicating whether the cell is in use;

a steering array storing a cache index based on the hash value, the cache index pointing to a cache cell that may contain the answer;

a cyclic replacement counter addressing each cell in the cache to determine in the cell is still in use.

6. The cache system of claim 5 and in addition:

each cell having arguments for comparison against arguments in the query.

7. The cache system of claim 6 and in addition:

each cell having a link index pointing to another cache cell that may contain the answer.

8. The cache system of claim 5 further comprising:

an additional cache; and

an additional steering array also storing a cache index based on the hash value, the cache indexes from both steering arrays pointing to a cache cell in each cache that may contain the answer.

9. In a computing system having a cache system, a method for optimizing the use of the cache, the method comprising;

indirectly mapping a query to a cache cell in a cache array;

retrieving an answer from a first cache cell mapped to by the act of mapping;

retrieving an old answer from a second cache cell mapped to by the act of mapping;

searching for a new answer outside of the cache if neither act of retrieving is successful; and

cyclic accessing through cells in the cache to replace an answer in a cell with a new answer from the act of searching.

10. The method of claim 9 wherein the act of indirect mapping comprises:

computing a hash value from arguments in the query; and

looking up a cache index in a steering array based on the hash value.

11. The method of claim 9 wherein the act of mapping further comprises:

retrieving a link index to the second cache cell from the first cache cell.

12. The method of claim 11 wherein the act of cyclic accessing comprises:

advancing an address to select in turn each cache cell in the cache;

testing each cache cell when addressed to detect whether or not the cache cell has been used since the last time the cache cell was selected by the act of advancing; and

replacing the answer in the cache cell selected by the act of advancing with the new answer from the act of searching.

13. The method of claim 9 wherein the cache has two parallel cache arrays and two steering arrays and the act of indirect mapping comprises:

computing a hash value from arguments in the query; and

looking up a cache index in each steering array based on the hash value, the cache index in each steering array pointing to a cache cell in separate ones of the parallel cache arrays.

14. The method of claim 13 wherein both acts of retrieving are performed in parallel.

15. The method of claim 14 wherein the act of cyclic accessing comprises:

advancing an address to select in turn each cache cell in each cache array;

testing each cache cell when addressed to detect whether or not the cache cell has been used since the last time the cache cell was selected by the act of advancing and marking the cache cell as an available cache if it has not been used;

evaluating ages of the available cache cells in each cache array to determine the remaining cyclic life of each of the available cache cells;

selecting the cache array having the greater remaining cyclic life as a selected array; and

replacing the answer in the available cache cell of the selected array with the new answer from the act of searching.

16. A computer program product readable by a computing system and encoding a computer program of instructions for executing a computer process for a cache system for retrieving an answer in response to a query, said computer process comprising:

generating a hash value based on arguments in the query;

mapping the hash value to a cache index and accessing a cache element in a cache array;

retrieving an answer from a first cache element if the arguments in the first cache element match the arguments in the query;

retrieving an answer from a second cache element if the arguments in the second cache element match the arguments in the query;

searching for the answer in a storage system outside the cache array if neither act of retrieving retrieves an answer for the query; and

cycling through cache elements in one or more cache arrays to select a cache element in which the answer from the act of searching may be stored.

17. The program product of claim 16 wherein the first cache element in the cache array stores a link index to the second cache element and the act of mapping comprises:

accessing a steering array with the hash value and providing a cache index for accessing the first cache element; and

accessing the second cache element based on the link index in the first cache element.

18. The program product of claim 17 wherein the act of cycling through cache elements comprises:

advancing an address to select in turn each cache element in the cache;

testing each cache element when addressed to detect whether or not the cache element has been used since the last time the cache element was selected by the act of advancing;

replacing the answer in the cache element selected by the act of advancing with the new answer from the act of searching; and

storing the link index in the cache element selected by the act of advancing.

19. The program product of claim 16 wherein there are parallel cache arrays and parallel steering arrays and the act of mapping comprises:

accessing both steering arrays with the hash value;

providing from a first steering array a first cache index based on the hash value to a cache element in one of the parallel arrays; and

providing from a second steering array a second cache index based on the hash value to a cache element in the other of the parallel arrays.

20. The program product of claim 19 wherein the act of cycling through cache elements comprises:

advancing an address to select in turn each cache element in each cache array;

testing each cache element when addressed to detect whether or not the cache element has been used since the last time the cache element was selected by the act of advancing and marking the cache element as an available cache element if it has not been used;

evaluating ages of the available cache elements in each cache array to determine the remaining cyclic life of each of the available cache elements;

selecting the cache array having the greater remaining cyclic life as a selected array; and

replacing the answer in the available cache element of the selected array with the new answer from the act of searching.