Maximal concurrent lookup cache for computing systems having a multi-threaded environment

Claim 2

In a multi-threaded processing system having a cache that is commonly accessible to each thread, wherein the cache has a plurality of entries for storing items, each entry being identified by an entry number and having a reference counter which indicates whether the entry is currently busy and a time stamp which records the last time the entry is accessed, a method of selecting an entry for storage of a new item, the method comprising the steps of: a) logically dividing the plurality of entries into sets of entries of equal size; b) selecting in a round robin fashion one of the sets of entries, wherein one of the entries in the set will be used to store the new item; c) arranging the entries in the selected set from step b into an ordered list according to the time each entry in the set was last accessed, wherein entries that are busy are ignored; d) if the list from step c is empty, repeating steps b-d; e) if the list from step c is not empty, then for each entry in the list, starting with the first entry in the list, verifying that the entry is available for storage of the new item; and f) repeating steps b-f if no entry is found available for storage in step e.

Claim 3

The method of claim 1, wherein each set of entries is uniquely assigned a number, starting with 1, the numbers of the sets being consecutive, the last set being assigned a set number that is the same as the number of sets in the cache, and wherein the selecting step comprises: selecting, in a round robin fashion, one of the sets of entries wherein of the entries in the set will be used to store the new item, the set being selected having a set number that is 1 greater than the set number of the set that was previously selected, or set number 1 if the previously selected set is the set that has the greatest set number, and if no such set exists, then selecting the set with a set number 1.

Claim 4

The method of claim 1, wherein an entry is busy if the reference counter has a value that is greater than zero.

Claim 5

The method of claim 1, wherein the verification to determine whether an entry is available for storage of a new item comprises the steps of: a) acquiring a mutual exclusion lock which grants exclusive access only to the entry that is being verified; b) indicating that the entry is not available if another thread is currently holding a mutual exclusion lock on the entry; and c) indicating that the entry is available if the reference counter has a value equal to zero, or if the entry has not been used to store any item.

Claim 6

The method of claim 4, further comprising the step of invoking a call back function to flush present contents of the new cache entry to a main storage location.

Claim 7

The method of claim 4, wherein a time stamp of zero indicates that the entry has not been used to store any item.

Claim 8

In a multi-threaded processing system having a cache that is commonly accessible to each thread, wherein the cache has a plurality of entries for storing items, each entry being identified by an entry number and having a reference counter which indicates whether the entry is currently busy and a time stamp which records the last time the entry is accessed, an apparatus for selecting an entry for storage of a new item, the apparatus comprising: a) means for logically dividing the plurality of entries into sets of entries of equal size; b) means for selecting in a round robin fashion one of the sets of entries, wherein one of the entries in the set will be used to store the new item; c) means for arranging the entries in the selected set into an ordered list according to the time each entry in the set was last accessed, wherein entries that are busy are ignored; d) means for determining if the selected set is empty, the means for determining causing said means for arranging to proceed to a next set if the selected set is empty; and e) means for verifying, for each entry in the list starting with the first entry, that the entry is available for storage of the new item if the means for determining determines that the selected set is not empty, the means for verifying causing said means for arranging to proceed to a next set if the verification fails.

Claim 9

In a multi-threaded processing system having a cache that is commonly accessible to each thread, wherein the cache has a plurality of entries for storing items, each entry being identified by an entry number and having a reference counter which indicates whether the entry is currently busy and a time stamp which records the last time the entry is accessed, an apparatus for selecting an entry for storage of a new item, the apparatus comprising: a) means for logically dividing the plurality of entries into sets of entries of equal size; b) means for selecting in a round robin fashion one of the sets of entries, wherein one of the entries in the set will be used to store the new item; c) means for arranging the entries in the selected set into an ordered list according to the time each entry in the set was last accessed, wherein entries that are busy are ignored; d) means for determining if the selected set is empty, the means for determining causing said means for arranging to proceed to a next set if the selected set is empty; and e) means for verifying, for each entry in the list starting with the first entry, that the entry is available for storage of the new item if the means for determining determines that the selected set is not empty, the means for verifying causing said means for arranging to proceed to a next set if the verification fails.

Claim 10

The apparatus of claim 7, wherein each set of entries is uniquely assigned a number, starting with 1, the numbers of the sets being consecutive, the last set being assigned a set number that is the same as the number of sets in the cache, and wherein the means for selecting selects, in a round robin fashion, one of the sets of entries wherein of the entries in the set will be used to store the new item, the set being selected having a set number that is 1 greater than the set number of the set that was previously selected, or set number 1 if the previously selected set is the set that has the greatest set number, and if no such set exists, then selecting the set with a set number 1.

Claim 11

The apparatus of claim 7, wherein an entry is busy if the reference counter has a value that is greater than zero.

Claim 12

The apparatus of claim 7, wherein the means for verifying comprises: a) means for acquiring a mutual exclusion lock which grants exclusive access only to the entry that is being verified; b) means for indicating that the entry is not available if another thread is currently holding a mutual exclusion lock on the entry; and for indicating that the entry is available if the reference counter has a value equal to zero, or if the entry has not been used to store any item.

Claim 13

The apparatus of claim 10, further comprising a means for invoking a call back function to flush present contents of the new cache entry to a main storage location.

Claim 14

The apparatus of claim 10, wherein a time stamp of zero indicates that the entry has not been used to store any item.

Claim 15

An article of manufacture for use in a multi-threaded processing system having a cache that is commonly accessible to each thread, wherein the cache has a plurality of entries for storing items, each entry being identified by an entry number and having a reference counter which indicates whether the entry is currently busy and a time stamp which records the last time the entry is accessed, the article of manufacture comprising: a computer usable medium having computer readable program code configured to select an entry for storage of a new item, the computer readable program code in the article of manufacture comprising: a) computer readable program code configured to effect logical division of the plurality of entries into sets of entries of equal size; b) computer readable program code configured to effect selection, in a round robin fashion, of one of the sets of entries, wherein one of the entries in the set will be used to store the new item; c) computer readable program code configured to effect the arrangement of the entries in the selected set into an ordered list according to the time each entry in the set was last accessed, wherein entries that are busy are ignored; d) computer readable program code configured to determine if the selected set is empty, and to cause said program code configured to effect the arrangement of the entries to proceed to a next set if the selected set is empty; and e) computer readable program code configured to verify, for each entry in the list starting with the first entry, that the entry is available for storage of the new item if the code configured to determine if the selected set is empty determines that the selected set is not empty, and causing the code configured to effect the arrangement of the entries to proceed to a next set if the verification fails.

Claim 16

An article of manufacture for use in a multi-threaded processing system having a cache that is commonly accessible to each thread, wherein the cache has a plurality of entries for storing items, each entry being identified by an entry number and having a reference counter which indicates whether the entry is currently busy and a time stamp which records the last time the entry is accessed, the article of manufacture comprising: a computer usable medium having computer readable program code configured to select an entry for storage of a new item, the computer readable program code in the article of manufacture comprising: a) computer readable program code configured to effect logical division of the plurality of entries into sets of entries of equal size; b) computer readable program code configured to effect selection, in a round robin fashion, of one of the sets of entries, wherein one of the entries in the set will be used to store the new item; c) computer readable program code configured to effect the arrangement of the entries in the selected set into an ordered list according to the time each entry in the set was last accessed, wherein entries that are busy are ignored; d) computer readable program code configured to determine if the selected set is empty, and to cause said program code configured to effect the arrangement of the entries to proceed to a next set if the selected set is empty; and e) computer readable program code configured to verify, for each entry in the list starting with the first entry, that the entry is available for storage of the new item if the code configured to determine if the selected set is empty determines that the selected set is not empty, and causing the code configured to effect the arrangement of the entries to proceed to a next set if the verification fails.

Claim 17

The article of manufacture of claim 13, wherein each set of entries is uniquely assigned a number, starting with 1, the numbers of the sets being consecutive, the last set being assigned a set number that is the same as the number of sets in the cache, and wherein the computer readable program code configured for selecting selects, in a round robin fashion, one of the sets of entries wherein of the entries in the set will be used to store the new item, the set being selected having a set number that is 1 greater than the set number of the set that was previously selected, or set number 1 if the previously selected set is the set that has the greatest set number, and if no such set exists, then selecting the set with a set number 1.

Claim 18

The article of manufacture of claim 13, wherein an entry is busy if the reference counter has a value that is greater than zero.

Claim 19

The article of manufacture of claim 13, wherein the code configured to verify comprises: a) computer readable program code configured to acquire a mutual exclusion lock which grants exclusive access only to the entry that is being verified; b) computer readable program code configured to indicate that the entry is not available if another thread is currently holding a mutual exclusion lock on the entry; and to indicate that the entry is available if the reference counter has a value equal to zero, or if the entry has not been used to store any item.

Claim 20

The article of manufacture of claim 16, further comprising a means for invoking a call back function to flush present contents of the new cache entry to a main storage location.

Claim 21

The article of manufacture of claim 16, wherein a time stamp of zero indicates that the entry has not been used to store any item.