Detection of bit errors in maskable content addressable memories

• US 20040015752A1
• Filed: 07/16/2002
• Published: 01/22/2004
• Est. Priority Date: 07/16/2002
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.), Intel Corporation
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Safford, Kevin David, Arnold, Ronny Lee, Patella, Benjamin J., McNairy, Cameron B.
• Granted Patent: US 7,100,097 B2
• Time in Patent Office: Days
• US Class Current: 714/718
• CPC Class Codes: G06F 11/1064 in cache or content addressable memories
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• 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

Abstract

Parity and mask bit(s) are stored in a random access memory (RAM) that is coupled to a CAM. This CAM may be part of a TLB. The parity and mask bits(s) are stored in conjunction with the CAM entry write. Upon a CAM query match, the reference parity bit(s) and mask bit(s) stored at the address output by the CAM are output from the RAM. These reference parity bit(s) are compared to parity bit(s) generated from a query data value that is masked by the retrieved mask bit(s). In the absence of a CAM or RAM bit error, the reference parity bit(s) from the RAM and the parity bit(s) generated from the masked query data will match. If a CAM or RAM bit error occurred, these two sets of parity bit(s) will not match and thus an error will be detected. This error may be used as an indication that a false CAM match has occurred.

Claims

1. A method of detecting CAM bit errors, comprising:

retrieving stored parity from a RAM;

retrieving stored mask bits from said RAM

generating masked query parity by masking query data being used to query a CAM with said stored mask bits from said RAM; and

,

comparing said stored parity and said masked query parity.

2. The method of claim 1 wherein said step of retrieving stored parity from

said RAM and said step of retrieving stored mask bits from said RAM comprise retrieving said stored parity and stored mask bits from a RAM address that corresponds to a CAM output address being output by said CAM in response to said query data being used to query said CAM.

3. The method of claim 2 further comprising:

generating input parity on input data being stored in said CAM; and

,

storing said input parity and said mask bits in said RAM.

4. The method of claim 3 wherein said CAM is part of a TLB.

5. A method of detecting CAM bit errors, comprising:

querying a CAM with a first set of data;

retrieving a second and third set of data from a location corresponding to an address provided by said CAM in response to being queried with said first set of data;

comparing parity generated from said first set of data after being masked by said second set of data to said third set of data.

6. The method of claim 5, comprising:

storing a CAM entry comprising a fourth set of data at a CAM entry address in said CAM; and

,

storing a parity entry at a location corresponding to said CAM entry address.

7. The method of claim 6 wherein said parity entry is stored in a RAM.

8. The method of claim 7 wherein additional data is stored in said RAM.

9. The method of claim 8 wherein said additional data is part of a TLB entry.

10. A method of detecting CAM bit errors, comprising:

generating and storing a parity on a CAM entry wherein said CAM entry is masked by a set of mask bits;

storing said set of mask bits;

querying a CAM for said CAM entry;

retrieving said parity and stored mask bits from an address supplied by said CAM; and

,

comparing said parity and a generated parity generated from data used to query said CAM that has been masked by said stored mask bits.

11. The method of claim 10 wherein said CAM is part of a TLB.

12. An apparatus for detecting CAM bit errors, comprising:

means for generating and storing a first parity on a masked CAM entry;

means for retrieving a second parity and a set of mask bits from an address supplied by said CAM when said CAM is queried;

means for generating a third parity from data used to query said CAM that has been masked by said set of mask bits; and

,

means for comparing said second parity and said third parity.

13. An apparatus for detecting CAM bit errors, comprising:

means for generating and storing a first parity on a masked CAM entry;

means for retrieving said first parity and a set of mask bits from an address supplied by said CAM when said CAM is queried;

means for generating a second parity from data used to query said CAM that has been masked by said set of mask bits; and

,

means for comparing said second parity and said first parity.

14. An apparatus, comprising:

a CAM supplying an address to a RAM in response to a first set of data bits, wherein said RAM outputs a second set of data bits that include a first set parity bits and a set of mask bits;

a parity generator that generates a second set of parity bits on a third set of data bits that is generated by masking said first set of data bits with said set of mask bits wherein said first set of data bits is querying said CAM; and

,

a parity comparator that compares said first set of parity bits and said second set of parity bits.

15. A TLB, comprising:

a CAM;

a RAM;

a first parity generator;

a second parity generator;

a first bit masker;

a second bit masker;

a parity comparator wherein said first parity generator is coupled to a first input of said CAM and generates a first parity on data masked by said first bit masker according to a first bit mask and said first parity and said first bit mask are stored in said RAM at a second location that corresponds to said first location and said RAM outputs a third parity and a second bit mask when said CAM supplies said RAM an address in response to said data querying said CAM and said second parity generator generates a second parity on data masked by said second bit masker according to said second bit mask said parity comparator compares said second parity and said third parity to detect at least one bit error in either of said CAM and RAM.

16. A TLB, comprising:

a CAM;

a RAM;

a first parity generator;

a second parity generator;

a first bit masker;

a second bit masker;

a parity comparator wherein said first parity generator is coupled to a first input of said CAM and generates a first parity on data masked by said first bit masker according to a first bit mask and said first parity and said first bit mask are stored in said RAM at a second location that corresponds to said first location and said RAM outputs said first parity and said first bit mask when said CAM supplies said RAM an address in response to said data querying said CAM and said second parity generator generates a second parity on data masked by said second bit masker according to said second bit mask said parity comparator compares said second parity and said first parity to detect at least one bit error in either of said CAM and RAM.

17. A method of detecting false CAM matches, comprising:

retrieving stored parity from a RAM;

retrieving stored mask bits from said RAM

generating masked query parity by masking query data being used to query a CAM with said stored mask bits from said RAM; and

,

comparing said stored parity and said masked query parity to detect a false CAM match.

18. The method of claim 17 wherein said step of retrieving stored parity from said RAM and said step of retrieving stored mask bits from said RAM comprise retrieving said stored parity and stored mask bits from a RAM address that corresponds to a CAM output address being output by said CAM in response to said query data being used to query said CAM.

19. The method of claim 18 further comprising:

generating input parity on input data being stored in said CAM; and

,

storing said input parity and said mask bits in said RAM.

20. The method of claim 19 wherein said CAM is part of a TLB.