Content-addressable memory that supports a priority ordering between banks of differing sizes

• US 7,721,042 B2
• Filed: 07/27/2006
• Issued: 05/18/2010
• Est. Priority Date: 07/27/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Oracle America, Inc. (Oracle Corporation)
• Inventors: Cypher, Robert E.
• Primary Examiner(s): Peugh; Brian R
• Assistant Examiner(s): Thammavong; Prasith
• Application Number:
  US11/495,451
• Publication Number:
  US 20080028138A1
• Time in Patent Office: 1,391 Days
• Field of Search: 711/108
• US Class Current: 711/108
• CPC Class Codes: G06F 12/0607 Interleaved addressing
• CPC Class Codes: G06F 12/0846 Cache with multiple tag or data arrays being simultaneously accessible
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]

Abstract

One embodiment of the present invention provides a system that implements a content-addressable memory (CAM) which has multiple banks. During operation, the system receives a request to insert an item into the CAM, wherein the request includes a key which is used to index the item and a body containing data. Next, for each bank in the CAM, the system calculates a different hash function based on the key to produce an index and a tag. The system then uses the calculated index and the tag for each bank to lookup an entry in each bank. If the lookups do not generate a hit in any bank, the system stores an entry for the request into a highest priority bank which does not contain a valid entry in the location accessed by the lookup. In one embodiment of the present invention, the multiple banks in the CAM have varying sizes.

Claims

1. An apparatus, comprising:

a content-addressable memory (CAM) which has multiple banks;

wherein the multiple banks have varying sizes and a priority ordering, and wherein the multiple banks have varying sizes that fall off in a predetermined pattern from highest to lowest priority, wherein in the predetermined pattern, the sizes of the banks fall off exponentially from highest to lowest priority or the sizes of the banks are constant in size and then fall off exponentially from highest to lowest priority;

an insertion mechanism, wherein upon receiving an insertion request which includes a key and a body, the insertion mechanism is configured to,

calculate a different hash function for each bank based on the key to produce a calculated index and tag for each bank,

use the calculated index and the tag for each bank to lookup an entry in each bank, and

if the lookups do not generate a hit in any bank, to store an entry for the request into a highest priority bank which does not contain a valid entry in the location accessed by the lookup.

2. The apparatus of claim 1, wherein if the lookups generate a hit in a given entry in a given bank, the insertion mechanism is configured to store the body of the request into the given entry.

3. The apparatus of claim 1, wherein the sizes of the banks fall off exponentially from highest to lowest priority, so that if the CAM is of size Y and has W banks, the multiple banks can have the following sizes:

Y/2, Y/4, Y/8 . . . , Y/2^(W-2), Y/2^(W-1), and Y/2^(W-1).

4. The apparatus of claim 1, wherein the sizes of the banks are constant in size and then fall off exponentially from highest to lowest priority, so that if the CAM is of size Y and has W banks, the multiple banks can have the following sizes:

Y/4, Y/4, Y/4, Y/8 . . . , Y/2^(W-3), Y/2^(W-2), and Y/2^(W-2).

5. The apparatus of claim 1, wherein if the lookups do not generate a hit in any bank, and if the CAM contains valid entries in all locations accessed by the lookups, the insertion mechanism is configured to:

return a fail signal;

or to

replace a valid entry in the CAM with an entry for the request.

6. The apparatus of claim 1, wherein the apparatus further comprises a lookup mechanism, wherein upon receiving a lookup request which includes a key, the lookup mechanism is configured to:

calculate a different hash function for each bank based on the key to produce a calculated index and tag for each bank;

use the calculated index and the tag for each bank to lookup an entry in each bank;

if the lookups generate a hit in a given entry in a given bank, to return the body of the given entry; and

otherwise, if the lookups do not generate a hit in any bank, to return a fail signal.

7. The apparatus of claim 1, wherein the apparatus further comprises a deletion mechanism, wherein upon receiving a deletion request which includes a key, the deletion mechanism is configured to:

calculate a different hash function for each bank based on the key to produce a calculated index and tag for each bank;

use the calculated index and the tag for each bank to lookup an entry in each bank;

if the lookups generate a hit in a given entry in a given bank, to invalidate the given entry; and

otherwise, if the lookups do not generate a hit in any bank, to return a fail signal.

8. The apparatus of claim 1, wherein each entry in each bank contains:

a tag which is used to index the entry;

a body containing data; and

a valid flag which indicates whether or not the entry is valid.

9. The apparatus of claim 1, wherein while using the calculated index and tag for a bank to look up an entry in the bank, if a valid flag in the entry indicates the entry is valid, the apparatus is configured to:

compare a tag contained in the entry against the calculated tag; and

if the tag contained in the entry matches the calculated tag, to generate a hit signal.

10. The apparatus of claim 1,

wherein the banks of the CAM are numbered consecutively;

and

wherein the lower-numbered banks have higher priority than the higher-numbered banks.

11. The apparatus of claim 1, wherein the CAM is used to implement one of the following:

a store buffer;

a cache memory;

a translation-lookaside buffer;

a structure that keeps track of outstanding requests to access cache lines for coherence purposes;

or

a structure that keeps track of cache lines that were read speculatively.

12. A method for accessing a content-addressable memory (CAM), comprising:

receiving a request to insert an item into the CAM, wherein the request includes a key which is used to index the item and a body containing data;

wherein the CAM has multiple banks with varying sizes and a priority ordering, and wherein a set of the multiple banks have varying sizes that fall off in a predetermined pattern from highest to lowest priority, wherein in the predetermined pattern, the sizes of the banks fall off exponentially from highest to lowest priority or the sizes of the banks are constant in size and then fall off exponentially from highest to lowest priority;

for each bank in the CAM, calculating a different hash function based on the key to produce an index and a tag;

using the calculated index and the tag for each bank to lookup an entry in each bank; and

if the lookups do not generate a hit in any bank, storing an entry for the request into a highest priority bank which does not contain a valid entry in the location accessed by the lookup.

13. The method of claim 12, wherein if the lookups generate a hit in a given entry in a given bank, the method further comprises storing the body of the request into the given entry.

14. The apparatus of claim 12, wherein the sizes of the banks fall off exponentially from highest to lowest priority, so that if the CAM is of size Y and has W banks, the multiple banks can have the following sizes:

Y/2, Y/4, Y/8 . . . , Y/2^(W-2), Y/2^(W-1), and Y/2^(W-1).

15. The apparatus of claim 12, wherein the sizes of the banks are constant and then fall off exponentially from highest to lowest priority, so that if the CAM is of size Y and has W banks, the multiple banks can have the following sizes:

Y/4, Y/4, Y/4, Y/8 . . . , Y/2^(W-3), Y/2^(W-2), and Y/2^(W-2).

16. The method of claim 12, wherein if the lookups do not generate a hit in any bank, and if the CAM contains valid entries in all locations accessed by the lookups, the method further comprises:

returning a fail signal;

or

replacing a valid entry in the CAM with an entry for the request.

17. The method of claim 12, wherein the method further comprises:

receiving a request to lookup an item in the CAM, wherein the request includes a key which is used to index the item;

for each bank in the CAM, calculating a different hash function based on the key to produce an index and a tag;

using the calculated index and tag for each bank to lookup an entry in each bank;

if the lookups generate a hit in a given entry in a given bank, returning the body of the given entry; and

otherwise, if the lookups do not generate a hit in any bank, returning a fail signal.

18. The method of claim 12, wherein the method further comprises:

receiving a request to delete an item from the CAM, wherein the request includes a key which is used to index the item;

for each bank in the CAM, calculating a different hash function based on the key to produce an index and a tag;

using the calculated index and tag for each bank to lookup an entry in each bank;

if the lookups generate a hit in a given entry in a given bank, invalidating the given entry; and

otherwise, if the lookups do not generate a hit in any bank, returning a fail signal.

19. The method of claim 12, wherein each entry in each bank contains:

a tag which is used to index the entry;

a body containing data; and

a valid flag which indicates whether or not the entry is valid.

20. The method of claim 12, wherein while using the calculated index and tag for a bank to look up an entry in the bank, if a valid flag in the entry indicates the entry is valid, the method further comprises:

comparing a tag contained in the entry against the calculated tag; and

if the tag contained in the entry matches the calculated tag, generating a hit signal.

21. The method of claim 12,

wherein the banks of the CAM are numbered consecutively;

and

wherein the lower-numbered banks have higher priority than the higher-numbered banks.

22. The method of claim 12, wherein the CAM is used to implement one of the following:

a store buffer;

a cache memory;

a translation-lookaside buffer;

a structure that keeps track of outstanding requests to access cache lines for coherence purposes;

or

a structure that keeps track of cache lines that were read speculatively.

23. A computer system, comprising:

a processor;

a memory;

a content-addressable memory (CAM) which has multiple banks;

wherein the multiple banks have varying sizes and a priority ordering, and wherein a set of the multiple banks have varying sizes that fall off in a predetermined pattern from highest to lowest priority, wherein in the predetermined pattern, the sizes of the banks fall off exponentially from highest to lowest priority or the sizes of the banks are constant in size and then fall off exponentially from highest to lowest priority;

an insertion mechanism within the CAM, wherein upon receiving an insertion request which includes a key and a body, the insertion mechanism is configured to,

calculate a different hash function for each bank based on the key to produce a calculated index and tag for each bank,

use the calculated index and the tag for each bank to lookup an entry in each bank, and

if the lookups do not generate a hit in any bank, to store an entry for the request into a highest priority bank which does not contain a valid entry in the location accessed by the lookup.