High speed CAM lookup using stored encoded key

• US 7,761,774 B2
• Filed: 10/28/2005
• Issued: 07/20/2010
• Est. Priority Date: 10/28/2005
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Fischer, Jeffrey Herbert, Chai, Chiaming, Dieffenderfer, James Norris, Phan, Michael ThaiThanh
• Primary Examiner(s): Baker; Stephen M
• Application Number:
  US11/262,063
• Publication Number:
  US 20070113158A1
• Time in Patent Office: 1,726 Days
• Field of Search: 714/763, 714/773, 714/768, 714/805
• US Class Current: 714/768
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 2212/652 Page size control
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

The search key and key fields of a CAM in a cache are encoded with a Hamming distance of at least two to increase the speed of the CAM by ensuring each mismatching match line is discharged by at least two transistors in parallel. Where the cache is physically tagged, the search key is a physical address. The page address portion of the physical address is encoded prior to being stored in a TLB. The page offset bits are encoded in parallel with the TLB access, and concatenated with the encoded TLB entry. If a page address addresses a large memory page size, a plurality of corresponding sub-page addresses may be generated, each addressing a smaller page size. These sub-page addresses may be encoded and stored in a micro TLB. The encoded key and key field are tolerant of single-bit soft errors.

Claims

1. A method of accessing a Content Addressable Memory (CAM) having a plurality of encoded key fields, comprising:

encoding a search key;

storing the encoded search key within a translation lookaside buffer (TLB); and

accessing the CAM using the stored, encoded search key.

2. The method of claim 1 wherein encoding a search key comprises encoding the search key with a Hamming distance of two.

3. The method of claim 1 wherein encoding a search key comprises encoding the search key with a Hamming distance of three.

4. The method of claim 1 wherein accessing the CAM using the stored, encoded search key generates correct results despite a single-bit error in one or more encoded key fields.

5. The method of claim 1 wherein each encoded key field is encoded with a Hamming distance of two and includes a parity bit, and further comprising, if a match is detected between the encoded search key and an encoded key field:

reading the encoded key field, including the stored parity bit, from the CAM;

regenerating a parity bit for the encoded key field;

comparing the regenerated parity bit to the stored parity bit; and

if the parity bits miscompare, generating an error.

6. The method of claim 1, wherein the encoding of the search key is performed with software during run-time irrespective of a cache-miss occurrence.

7. The method of claim 1 wherein encoding a search key comprises encoding a first part of the search key, and wherein storing the encoded search key comprises storing the encoded first part of the search key.

8. The method of claim 7 further comprising encoding a second part of the search key, and wherein accessing the CAM using the stored, encoded search key comprises accessing the CAM using the stored, encoded first part of the search key concatenated with the encoded second part of the search key.

9. The method of claim 1, wherein the CAM is included in a cache that is structurally separate from the TLB.

10. The method of claim 9, wherein the cache corresponds to an instruction cache or a data cache.

11. The method of claim 1 wherein the search key comprises a physical address.

12. The method of claim 11 wherein storing the encoded search key comprises storing an encoded page address portion of the physical address in the Translation Lookaside Buffer (TLB).

13. The method of claim 12 further comprising:

generating two or more sub-page addresses from the page address, each sub-page address addressing a smaller memory page size than the page address;

encoding at least one sub-page address; and

storing the encoded sub-page addresses in a micro TLB;

wherein accessing the CAM using the stored, encoded search key comprises accessing the CAM using one of the encoded sub-page addresses in the micro TLB.

14. A method of matching an address in a Content Addressable Memory (CAM), comprising:

storing an encoded version of the address as a key field in the CAM;

storing an encoded version of a page address portion of the address in a Translation Lookaside Buffer (TLB); and

comparing the encoded address from the TLB against a plurality of encoded key fields in the CAM to detect a match.

15. The method of claim 14 wherein the encoded version of the address is the address encoded with a Hamming distance of two.

16. The method of claim 14 wherein the encoded version of the address is the address encoded with a Hamming distance of three.

17. The method of claim 14 wherein comparing the encoded address from the TLB against a plurality of encoded key fields in the CAM correctly detects a match despite a single-bit error in one or more encoded key fields.

18. The method of claim 14 further comprising encoding a page offset portion of the address, and wherein comparing the encoded address from the TLB against a plurality of encoded key fields in the CAM comprises comparing the encoded page address from the TLB concatenated with the encoded page offset against a plurality of encoded key fields in the CAM.

19. The method of claim 14 further comprising:

generating two or more sub-page addresses from the page address, each sub-page address addressing a smaller memory page size than the page address;

encoding at least one sub-page address; and

storing the encoded sub-page addresses in a micro TLB;

wherein comparing the encoded address from the TLB against a plurality of encoded key fields in the CAM comprises comparing an encoded sub-page address from the TLB against a plurality of encoded key fields in the CAM.

20. The method of claim 14 wherein each encoded key field in the CAM is encoded with a Hamming distance of two and includes a parity bit, and further comprising, if a match is detected between the encoded address from the TLB and an encoded key field in the CAM:

reading the encoded key field, including the stored parity bit, from the CAM;

regenerating a parity bit for the encoded key field;

comparing the regenerated parity bit to the stored parity bit; and

if the parity bits miscompare, generating an error.

21. A processor, comprising:

a cache memory comprising a Content Addressable Memory (CAM) and Random Access Memory (RAM), the cache operative to store or supply data to or from a RAM entry when a search key matches a corresponding key field stored in the CAM, the key fields encoded by a Hamming distance of at least two; and

a Translation Lookaside Buffer (TLB) operative to store and output page addresses as search keys for the CAM, the page addresses encoded by the same algorithm as the CAM key fields.

22. The processor of claim 21 wherein the CAM key fields and the TLB physical addresses are encoded by a Hamming distance of three.

23. The processor of claim 21 further comprising a micro TLB operative to store two or more sub-page addresses corresponding to one page address in the TLB, the sub-page addresses addressing a smaller memory page size than the TLB page address, the micro TLB operative to supply one of the sub-page addresses as a search key for the CAM.

24. The processor of claim 21 wherein each CAM entry comprises a match line precharged to a high state, and discharged through a discharge transistor for each bit of the search key that mismatches a corresponding bit of the key field stored in that entry, and wherein the discharge transistor associated with a parity bit is operative to discharge more current than the other discharge transistors in the CAM entry.

25. The processor of claim 21 wherein, if a search key matches a key field, the cache is further operative to read out the key field and a stored key field parity bit, regenerate a parity bit for the key field, compare the regenerated parity bit and the stored parity bit, and if the parity bits mismatch, generate an error.

26. A processor, comprising:

means for encoding a search key;

means for storing the encoded search key within a translation lookaside buffer (TLB); and

means for accessing a Content Addressable Memory (CAM) having a plurality of encoded key fields using the stored, encoded search key.

27. A computer-readable medium comprising instructions, which, when executed by a processor, cause the processor to perform operations, the instructions comprising:

program code to encode a search key;

program code to store the encoded search key within a translation lookaside buffer (TLB); and

program code to access a Content Addressable Memory (CAM) having a plurality of encoded key fields using the stored, encoded search key.